6. Mappature deterministiche

Le mappature in questa sezione sono adatte per l'implementazione di codifiche non uniformi o uniformi utilizzando le costruzioni della Sezione 3. Alcune mappature limitano la forma della curva o i suoi parametri. Per ogni mappatura presentata, questo documento elenca le restrizioni pertinenti.

Si noti che le mappature in questa sezione non sono intercambiabili: mappature diverse produrranno quasi certamente punti diversi se valutate sullo stesso input.

6.1. Scelta di una funzione di mappatura

Questa sezione fornisce brevi linee guida sulla scelta di una funzione di mappatura per una data curva ellittica. Si noti che le suite fornite nella Sezione 8 sono mappature raccomandate per le rispettive curve.

Se la curva ellittica di destinazione è una curva di Montgomery (Sezione 6.7), si raccomanda il metodo Elligator 2 (Sezione 6.7.1). Allo stesso modo, se la curva ellittica di destinazione è una curva di Edwards ritorta (Sezione 6.8), si raccomanda il metodo Elligator 2 per Edwards ritorta (Sezione 6.8.2).

I casi rimanenti sono curve di Weierstrass. Per le curve supportate dal metodo Shallue-van de Woestijne-Ulas (SWU) semplificato (Sezione 6.6.2), questa mappatura è quella raccomandata. Altrimenti, il metodo SWU semplificato per AB == 0 (Sezione 6.6.3) è raccomandato se l'obiettivo è una migliore performance, mentre il metodo Shallue-van de Woestijne (Sezione 6.6.1) è raccomandato se l'obiettivo è la semplicità dell'implementazione. (La ragione di questa distinzione è che il metodo SWU semplificato per AB == 0 richiede l'implementazione di una mappa di isogenia in aggiunta alla funzione di mappatura, mentre il metodo Shallue-van de Woestijne no).

Il metodo Shallue-van de Woestijne (Sezione 6.6.1) funziona con qualsiasi curva e può essere utilizzato nei casi in cui è richiesta una mappatura generica. Si noti tuttavia che questa mappatura è quasi sempre più costosa in termini di calcolo rispetto alle raccomandazioni specifiche della curva sopra indicate.

6.2. Interfaccia

L'interfaccia generica condivisa da tutte le mappature in questa sezione è la seguente:

(x, y) = map_to_curve(u)

L'input u e gli output x e y sono elementi del campo F. Le coordinate affini (x, y) specificano un punto su una curva ellittica definita su F. Si noti tuttavia che il punto (x, y) non è un punto casuale uniforme.

6.3. Notazione

Come guida approssimativa, nel pseudo-codice vengono utilizzate le seguenti convenzioni:

• Tutte le operazioni aritmetiche sono eseguite su un campo F, se non diversamente specificato esplicitamente.

• u: l'input della funzione di mappatura. Si tratta di un elemento di F prodotto dalla funzione hash_to_field.

• (x, y), (s, t), (v, w): le coordinate affini del punto prodotto dalla mappatura. Vengono utilizzate variabili indicizzate (ad esempio, x1, y2, ...) per i valori candidati.

• tv1, tv2, ...: variabili temporanee riutilizzabili.

• c1, c2, ...: valori costanti, che possono essere calcolati in anticipo.

6.4. Segno del punto risultante

In generale, le curve ellittiche hanno equazioni della forma y^2 = g(x). Le mappature in questa sezione identificano prima una x tale che g(x) sia un quadrato, quindi estraggono la radice quadrata per trovare y. Poiché esistono due radici quadrate quando g(x) != 0, ciò può portare ad ambiguità riguardo al segno di y.

Ove applicabile, le mappature in questa sezione risolvono tale ambiguità specificando il segno della coordinata y in funzione dell'input della funzione di mappatura. Due ragioni principali supportano questo approccio: in primo luogo, copre le curve ellittiche su qualsiasi campo in modo uniforme e, in secondo luogo, lascia agli implementatori spazio per ottimizzare le implementazioni delle radici quadrate.

6.5. Casi eccezionali

Le mappature possono presentare casi eccezionali, ovvero input u sui quali la mappatura non è definita. Tali casi devono essere gestiti con cura, specialmente per le implementazioni a tempo costante.

Per ogni mappatura in questa sezione, discutiamo i casi eccezionali e mostriamo come gestirli a tempo costante. Si noti che tutte le implementazioni DOVREBBERO utilizzare inv0 (Sezione 4) per calcolare gli inversi moltiplicativi, al fine di evitare casi eccezionali derivanti dal tentativo di calcolare l'inverso di 0.

6.6. Mappature per le curve di Weierstrass

Le mappature in questa sezione si applicano a una curva di destinazione E definita dall'equazione

y^2 = g(x) = x^3 + A * x + B

dove 4 * A^3 + 27 * B^2 != 0.

6.6.1. Metodo Shallue-van de Woestijne

Shallue e van de Woestijne [SW06] descrivono una mappatura che si applica essenzialmente a qualsiasi curva ellittica. (Si noti tuttavia che questa mappatura è più costosa da valutare rispetto alle altre mappature in questo documento).

La parametrizzazione fornita di seguito è per le curve di Weierstrass; la sua derivazione è dettagliata in [W19]. Questa parametrizzazione funziona anche per le curve di Montgomery (Sezione 6.7) e le curve di Edwards ritorte (Sezione 6.8) tramite le mappe razionali fornite nell'Appendice D: prima si valuta la mappatura Shallue-van de Woestijne verso una curva di Weierstrass equivalente, quindi si mappa questo punto verso la curva di destinazione di Montgomery o Edwards ritorta utilizzando la corrispondente mappa razionale.

Precondizioni: Una curva di Weierstrass y^2 = x^3 + A * x + B.

Costanti:

• A e B, i parametri della curva di Weierstrass.

• Z, un elemento diverso da zero di F che soddisfi i criteri seguenti. L'Appendice H.1 fornisce uno script Sage [SAGE] che produce lo Z RACCOMANDATO.

  1. g(Z) != 0 in F.
  2. -(3 * Z^2 + 4 * A) / (4 * g(Z)) != 0 in F.
  3. -(3 * Z^2 + 4 * A) / (4 * g(Z)) è un quadrato in F.
  4. Almeno uno tra g(Z) e g(-Z / 2) è un quadrato in F.

Segno di y: Gli input u e -u danno la stessa coordinata x per molti valori di u. Pertanto, fissiamo sgn0(y) == sgn0(u).

Eccezioni: I casi eccezionali per u si verificano quando (1 + u^2 * g(Z)) * (1 - u^2 * g(Z)) == 0. Le restrizioni su Z fornite sopra garantiscono che le implementazioni che utilizzano inv0 per invertire questo prodotto siano prive di eccezioni.

Operazioni:

1. tv1 = u^2 * g(Z)
2. tv2 = 1 + tv1
3. tv1 = 1 - tv1
4. tv3 = inv0(tv1 * tv2)
5. tv4 = sqrt(-g(Z) * (3 * Z^2 + 4 * A)) # può essere precalcolato
6. Se sgn0(tv4) == 1, fissare tv4 = -tv4 # sgn0(tv4) DEVE essere 0
7. tv5 = u * tv1 * tv3 * tv4
8. tv6 = -4 * g(Z) / (3 * Z^2 + 4 * A) # può essere precalcolato
9. x1 = -Z / 2 - tv5
10. x2 = -Z / 2 + tv5
11. x3 = Z + tv6 * (tv2^2 * tv3)^2
12. Se is_square(g(x1)), fissare x = x1 e y = sqrt(g(x1))
13. Altrimenti Se is_square(g(x2)), fissare x = x2 e y = sqrt(g(x2))
14. Altrimenti fissare x = x3 e y = sqrt(g(x3))
15. Se sgn0(u) != sgn0(y), fissare y = -y
16. ritorna (x, y)

L'Appendice F.1 fornisce un esempio di implementazione "straight-line" di questa mappatura.

6.6.2. Metodo Shallue-van de Woestijne-Ulas semplificato

La funzione map_to_curve_simple_swu(u) implementa una semplificazione della mappatura Shallue-van de Woestijne-Ulas [U07] descritta da Brier et al. [BCIMRT10], da loro chiamata mappatura "SWU semplificata". Wahby e Boneh [WB19] generalizzano e ottimizzano questa mappatura.

Precondizioni: Una curva di Weierstrass y^2 = x^3 + A * x + B dove A != 0 e B != 0.

Costanti:

• A e B, i parametri della curva di Weierstrass.

• Z, un elemento di F che soddisfi i criteri seguenti. L'Appendice H.2 fornisce uno script Sage [SAGE] che produce lo Z RACCOMANDATO. I criteri sono i seguenti:

  1. Z è un non-quadrato in F,
  2. Z != -1 in F,
  3. il polinomio g(x) - Z è irriducibile su F, e
  4. g(B / (Z * A)) è un quadrato in F.

Segno di y: Gli input u e -u danno la stessa coordinata x. Pertanto, fissiamo sgn0(y) == sgn0(u).

Eccezioni: I casi eccezionali sono i valori di u tali che Z^2 * u^4 + Z * u^2 == 0. Ciò include u == 0 e può includere altri valori che dipendono da Z. Le implementazioni devono rilevare questo caso e fissare x1 = B / (Z * A), il che garantisce che g(x1) sia un quadrato per la condizione su Z fornita sopra.

Operazioni:

1. tv1 = inv0(Z^2 * u^4 + Z * u^2)
2. x1 = (-B / A) * (1 + tv1)
3. Se tv1 == 0, fissare x1 = B / (Z * A)
4. gx1 = x1^3 + A * x1 + B
5. x2 = Z * u^2 * x1
6. gx2 = x2^3 + A * x2 + B
7. Se is_square(gx1), fissare x = x1 e y = sqrt(gx1)
8. Altrimenti fissare x = x2 e y = sqrt(gx2)
9. Se sgn0(u) != sgn0(y), fissare y = -y
10. ritorna (x, y)

L'Appendice F.2 fornisce un'implementazione "straight-line" generale e ottimizzata di questa mappatura. Per ulteriori informazioni sull'ottimizzazione di questa mappatura, vedere la Sezione 4 di [WB19] o il codice di esempio trovato su [hash2curve-repo].

6.6.3. SWU semplificato per AB == 0

Wahby e Boneh [WB19] mostrano come adattare la mappatura SWU semplificata alle curve di Weierstrass con A == 0 o B == 0, che non è supportato dalla mappatura della Sezione 6.6.2. (Il caso A == B == 0 è escluso poiché y^2 = x^3 non è una curva ellittica).

Questo metodo si applica a curve come secp256k1 [SEC2] e curve pairing-friendly nella famiglia Barreto-Lynn-Scott [BLS03], nella famiglia Barreto-Naehrig [BN05] e in altre famiglie.

Questo metodo richiede di trovare un'altra curva ellittica E' data dall'equazione

y'^2 = g'(x') = x'^3 + A' * x' + B'

che sia isogena ad E e abbia A' != 0 e B' != 0. (Vedere [WB19], Appendice A, per un modo per trovare E' utilizzando [SAGE]). Questa isogenia definisce una mappa iso_map(x', y') data da una coppia di funzioni razionali. iso_map prende in input un punto su E' e produce in output un punto su E.

Una volta identificate E' e iso_map, questa mappatura funziona come segue: sull'input u, applicare prima la mappatura SWU semplificata per ottenere un punto su E', quindi applicare la mappa di isogenia a tale punto per ottenere un punto su E.

Si noti che iso_map è un omomorfismo di gruppo, il che significa che l'addizione di punti commuta con iso_map. Pertanto, quando si utilizza questa mappatura nella costruzione hash_to_curve trattata nella Sezione 3, si può eseguire una piccola ottimizzazione mappando prima u0 e u1 su E', sommando i punti risultanti su E' e infine applicando iso_map alla somma. Ciò produce lo stesso risultato richiedendo una sola valutazione di iso_map.

Precondizioni: Una curva ellittica E' con A' != 0 e B' != 0 che sia isogena alla curva di destinazione E con una mappa di isogenia iso_map da E' ad E.

Funzioni ausiliarie:

• map_to_curve_simple_swu è la mappatura della Sezione 6.6.2 verso E'

• iso_map è la mappa di isogenia da E' ad E

Segno di y: Per questa mappa, il segno è determinato da map_to_curve_simple_swu. Non sono necessari ulteriori aggiustamenti del segno.

Eccezioni: map_to_curve_simple_swu gestisce i propri casi eccezionali. I casi eccezionali di iso_map sono gli input che causano l'annullamento del denominatore di una funzione razionale; tali casi DEVONO restituire il punto identità su E.

Operazioni:

1. (x', y') = map_to_curve_simple_swu(u) # (x', y') è su E'
2. (x, y) = iso_map(x', y') # (x, y) è su E
3. ritorna (x, y)

Vedere [hash2curve-repo] o la Sezione 4.3 di [WB19] per ulteriori dettagli sull'implementazione della mappa di isogenia.

6.7. Mappature per le curve di Montgomery

La mappatura definita in questa sezione si applica a una curva di destinazione M definita dall'equazione

K * t^2 = s^3 + J * s^2 + s

6.7.1. Metodo Elligator 2

Bernstein, Hamburg, Krasnova e Lange forniscono una mappatura che si applica a qualsiasi curva con un punto di ordine 2 [BHKL13], da loro chiamata Elligator 2.

Precondizioni: Una curva di Montgomery K * t^2 = s^3 + J * s^2 + s dove J != 0, K != 0, e (J^2 - 4) / K^2 è diverso da zero e non è un quadrato in F.

Costanti:

• J e K, i parametri della curva ellittica.

• Z, un elemento non quadrato di F. L'Appendice H.3 fornisce uno script Sage [SAGE] che produce lo Z RACCOMANDATO.

Segno di t: Questa mappatura fissa il segno di t come specificato in [BHKL13]. Non sono richiesti ulteriori aggiustamenti.

Eccezioni: Il caso eccezionale è Z * u^2 == -1, ovvero 1 + Z * u^2 == 0. Le implementazioni devono rilevare questo caso e fissare x1 = -(J / K). Si noti che ciò può accadere solo quando q = 3 (mod 4).

Operazioni:

1. x1 = -(J / K) * inv0(1 + Z * u^2)
2. Se x1 == 0, fissare x1 = -(J / K)
3. gx1 = x1^3 + (J / K) * x1^2 + x1 / K^2
4. x2 = -x1 - (J / K)
5. gx2 = x2^3 + (J / K) * x2^2 + x2 / K^2
6. Se is_square(gx1), fissare x = x1, y = sqrt(gx1) con sgn0(y) == 1.
7. Altrimenti fissare x = x2, y = sqrt(gx2) con sgn0(y) == 0.
8. s = x * K
9. t = y * K
10. ritorna (s, t)

L'Appendice F.3 fornisce un esempio di implementazione "straight-line" di questa mappatura. L'Appendice G.2 fornisce procedure "straight-line" ottimizzate che si applicano a specifiche classi di curve e campi di base.

6.8. Mappature per le curve di Edwards ritorte

Le curve di Edwards ritorte (una classe di curve che include le curve di Edwards) sono date dall'equazione

a * v^2 + w^2 = 1 + d * v^2 * w^2

con a != 0, d != 0 e a != d [BBJLP08].

Queste curve sono strettamente correlate alle curve di Montgomery (Sezione 6.7): ogni curva di Edwards ritorta è birazionalmente equivalente a una curva di Montgomery ([BBJLP08], teorema 3.2). Questa equivalenza fornisce un modo efficiente per eseguire l'hashing verso una curva di Edwards ritorta: prima si esegue l'hashing verso una curva di Montgomery equivalente, quindi si trasforma il risultato in un punto sulla curva di Edwards ritorta tramite una mappa razionale. Questo metodo di hashing verso una curva di Edwards ritorta richiede quindi l'identificazione di una curva di Montgomery corrispondente e di una mappa razionale. Descriviamo come identificare tale curva e tale mappa immediatamente di seguito.

6.8.1. Mappe razionali da Montgomery alle curve di Edwards ritorte

Esistono due modi per selezionare una curva di Montgomery e una mappa razionale da utilizzare durante l'hashing verso una data curva di Edwards ritorta. La curva di Montgomery e la mappa razionale selezionate DEVONO essere specificate come parte della suite di hashing su curva per una data curva di Edwards ritorta; vedere la Sezione 8.

1. Quando si esegue l'hashing verso una curva di Edwards ritorta normalizzata per la quale sono normalizzate anche una forma di Montgomery corrispondente e una mappa razionale, DOVREBBERO essere utilizzate la forma di Montgomery e la mappa razionale standard per garantire la compatibilità con il software esistente.

   In alcuni casi, ad esempio edwards25519 [RFC7748], il segno della mappa razionale della curva di Edwards ritorta verso la sua corrispondente forma di Montgomery non è indicato esplicitamente. In questo caso, il segno DEVE essere fissato in modo tale che l'applicazione della mappa razionale al punto base della curva di Edwards ritorta produca il punto base della curva di Montgomery con il segno corretto. (Per edwards25519, vedere [RFC7748] e [Err4730]).

   Quando si definiscono nuove curve di Edwards ritorte, DOVREBBERO essere specificati anche un equivalente di Montgomery e una mappa razionale, e il segno della mappa razionale DOVREBBE essere indicato esplicitamente.

2. Quando si esegue l'hashing verso una curva di Edwards ritorta che non ha una forma di Montgomery o una mappa razionale normalizzata, DOVREBBE essere utilizzata la mappa fornita nell'Appendice D.

6.8.2. Metodo Elligator 2

Precondizioni: Una curva di Edwards ritorta E e una curva di Montgomery equivalente M che soddisfino i requisiti della Sezione 6.8.1.

Funzioni ausiliarie:

• map_to_curve_elligator2 è la mappatura della Sezione 6.7.1 verso la curva M.

• rational_map è una funzione che prende un punto (s, t) su M e restituisce un punto (v, w) su E. Questa mappa razionale deve essere scelta come definito nella Sezione 6.8.1.

Segno di t (e v): Per questa mappa, il segno è determinato da map_to_curve_elligator2. Non sono necessari ulteriori aggiustamenti del segno.

Eccezioni: Le eccezioni per la mappatura Elligator 2 sono quelle fornite nella Sezione 6.7.1. Le eccezioni per la mappa razionale sono quelle fornite nella Sezione 6.8.1. Non sono possibili altre eccezioni.

La seguente procedura implementa la mappatura Elligator 2 per una curva di Edwards ritorta. (Si noti che il punto di output è indicato con (v, w) in quanto è un punto sulla curva di Edwards ritorta di destinazione).

map_to_curve_elligator2_edwards(u)

Input: u, un elemento di F. Output: (v, w), un punto su E.

1. (s, t) = map_to_curve_elligator2(u) # (s, t) è su M
2. (v, w) = rational_map(s, t) # (v, w) è su E
3. ritorna (v, w)