6. Mapping deterministici

I mapping in questa sezione sono adatti per implementare sia codifiche non uniformi sia codifiche uniformi utilizzando le costruzioni della Sezione 3. Alcuni mapping limitano la forma della curva o i suoi parametri. Per ciascun mapping presentato, questo documento elenca le restrizioni pertinenti.

Si noti che i mapping in questa sezione non sono interscambiabili: mapping diversi produrranno quasi certamente punti diversi quando valutati sullo stesso input.

6.1. Scelta di una funzione di mapping

Questa sezione fornisce brevi linee guida per la scelta di una funzione di mapping per una data curva ellittica. Si noti che le suite date nella Sezione 8 costituiscono i mapping raccomandati per le rispettive curve.

Se la curva ellittica target è una curva Montgomery (Sezione 6.7), è raccomandato il metodo Elligator 2 (Sezione 6.7.1). Allo stesso modo, se la curva ellittica target è una curva twisted Edwards (Sezione 6.8), è raccomandato il metodo twisted Edwards Elligator 2 (Sezione 6.8.2).

I casi rimanenti sono curve Weierstraß. Per le curve supportate dal metodo Simplified Shallue-van de Woestijne-Ulas (SWU) (Sezione 6.6.2), tale mapping è quello raccomandato. Altrimenti, il metodo Simplified SWU per AB == 0 (Sezione 6.6.3) è raccomandato se l'obiettivo è le migliori prestazioni, mentre il metodo Shallue-van de Woestijne (Sezione 6.6.1) è raccomandato se l'obiettivo è la semplicità di implementazione. (Il motivo di questa distinzione è che il metodo Simplified SWU per AB == 0 richiede l'implementazione di una mappa di isogenia oltre alla funzione di mapping, mentre il metodo Shallue-van de Woestijne non lo richiede.)

Il metodo Shallue-van de Woestijne (Sezione 6.6.1) funziona con qualsiasi curva e può essere utilizzato nei casi in cui è richiesto un mapping generico. Si noti, tuttavia, che questo mapping è quasi sempre più costoso dal punto di vista computazionale rispetto alle raccomandazioni specifiche per curva sopra riportate.

6.2. Interfaccia

L'interfaccia generica condivisa da tutti i mapping 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 uniformemente casuale.

6.3. Notazione

Come guida approssimativa, le seguenti convenzioni sono utilizzate nel pseudocodice:

• Tutte le operazioni aritmetiche sono eseguite su un campo F, salvo diversa indicazione esplicita.

• u: l'input alla funzione di mapping. È un elemento di F prodotto dalla funzione hash_to_field.

• (x, y), (s, t), (v, w): le coordinate affini del punto emesso dal mapping. Le variabili indicizzate (es. x1, y2, ...) sono usate per 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). I mapping in questa sezione identificano prima un x tale che g(x) sia un quadrato, quindi estraggono una radice quadrata per trovare y. Poiché ci sono due radici quadrate quando g(x) != 0, ciò può comportare un'ambiguità riguardo al segno di y.

Quando necessario, i mapping in questa sezione risolvono questa ambiguità specificando il segno della coordinata y in funzione dell'input alla funzione di mapping. Due ragioni principali supportano questo approccio: in primo luogo, esso copre le curve ellittiche su qualsiasi campo in modo uniforme, e in secondo luogo, esso lascia agli implementatori libertà nell'ottimizzazione delle implementazioni delle radici quadrate.

6.5. Casi eccezionali

I mapping possono avere casi eccezionali, cioè input u su cui il mapping non è definito. Questi casi devono essere gestiti con cura, specialmente per le implementazioni in tempo costante.

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

6.6. Mapping per curve Weierstraß

I mapping in questa sezione si applicano a una curva target 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 un mapping che si applica a praticamente qualsiasi curva ellittica. (Si noti, tuttavia, che questo mapping è più costoso da valutare rispetto agli altri mapping in questo documento.)

I parametri riportati di seguito sono per curve Weierstraß; la loro derivazione è dettagliata in [W19]. Questa parametrizzazione funziona anche per le curve Montgomery (Sezione 6.7) e le curve twisted Edwards (Sezione 6.8) tramite le mappe razionali date nell'Appendice D: prima si valuta il mapping Shallue-van de Woestijne su una curva Weierstraß equivalente, quindi si mappa quel punto sulla curva Montgomery o twisted Edwards target utilizzando la mappa razionale corrispondente.

Precondizioni: Una curva Weierstraß y^2 = x^3 + A * x + B.

Costanti:

• A e B, i parametri della curva Weierstraß.

• Z, un elemento non nullo di F che soddisfa i criteri seguenti. L'Appendice H.1 fornisce uno script Sage [SAGE] che emette il 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, poniamo 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 date 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, poniamo 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)), poniamo x = x1 e y = sqrt(g(x1))
13. Altrimenti se is_square(g(x2)), poniamo x = x2 e y = sqrt(g(x2))
14. Altrimenti poniamo x = x3 e y = sqrt(g(x3))
15. Se sgn0(u) != sgn0(y), poniamo y = -y
16. return (x, y)

L'Appendice F.1 fornisce un esempio di implementazione straight-line di questo mapping.

6.6.2. Metodo Simplified Shallue-van de Woestijne-Ulas

La funzione map_to_curve_simple_swu(u) implementa una semplificazione del mapping Shallue-van de Woestijne-Ulas [U07] descritta da Brier et al. [BCIMRT10], che essi chiamano mapping "simplified SWU". Wahby e Boneh [WB19] generalizzano e ottimizzano questo mapping.

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

Costanti:

• A e B, i parametri della curva Weierstraß.

• Z, un elemento di F che soddisfa i criteri seguenti. L'Appendice H.2 fornisce uno script Sage [SAGE] che emette il 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, poniamo 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 porre x1 = B / (Z * A), il che garantisce che g(x1) sia un quadrato per la condizione su Z data sopra.

Operazioni:

1. tv1 = inv0(Z^2 * u^4 + Z * u^2)
2.  x1 = (-B / A) * (1 + tv1)
3.  Se tv1 == 0, poniamo 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), poniamo x = x1 e y = sqrt(gx1)
8.  Altrimenti poniamo x = x2 e y = sqrt(gx2)
9.  Se sgn0(u) != sgn0(y), poniamo y = -y
10. return (x, y)

L'Appendice F.2 fornisce un'implementazione straight-line generale e ottimizzata di questo mapping. Per maggiori informazioni sull'ottimizzazione di questo mapping, si veda la Sezione 4 di [WB19] o il codice di esempio disponibile in [hash2curve-repo].

6.6.3. Simplified SWU per AB == 0

Wahby e Boneh [WB19] mostrano come adattare il mapping Simplified SWU a curve Weierstraß aventi A == 0 o B == 0, che il mapping della Sezione 6.6.2 non supporta. (Il caso A == B == 0 è escluso perché y^2 = x^3 non è una curva ellittica.)

Questo metodo si applica a curve come secp256k1 [SEC2] e a curve pairing-friendly nelle famiglie Barreto-Lynn-Scott [BLS03], Barreto-Naehrig [BN05] e 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 è isogena a E e ha A' != 0 e B' != 0. (Si veda [WB19], Appendice A, per un modo di 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, questo mapping funziona così: sull'input u, si applica prima il mapping Simplified SWU per ottenere un punto su E', quindi si applica la mappa di isogenia a quel 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 questo mapping nella costruzione hash_to_curve discussa nella Sezione 3, si può ottenere una piccola ottimizzazione mappando prima u0 e u1 su E', addizionando i punti risultanti su E', e quindi applicando iso_map alla somma. Ciò dà lo stesso risultato richiedendo una sola valutazione di iso_map.

Precondizioni: Una curva ellittica E' con A' != 0 e B' != 0 che è isogena alla curva target E con mappa di isogenia iso_map da E' a E.

Funzioni ausiliarie:

• map_to_curve_simple_swu è il mapping della Sezione 6.6.2 verso E'

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

Segno di y: Per questa mappa, il segno è determinato da map_to_curve_simple_swu. Non sono necessarie ulteriori rettifiche di segno.

Eccezioni: map_to_curve_simple_swu gestisce i suoi casi eccezionali. I casi eccezionali di iso_map sono input che causano la valutazione a zero del denominatore di una delle due funzioni razionali; 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. return (x, y)

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

6.7. Mapping per curve Montgomery

Il mapping definito in questa sezione si applica a una curva target M definita dall'equazione

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

6.7.1. Metodo Elligator 2

Bernstein, Hamburg, Krasnova e Lange danno un mapping che si applica a qualsiasi curva con un punto di ordine 2 [BHKL13], che essi chiamano Elligator 2.

Precondizioni: Una curva Montgomery K * t^2 = s^3 + J * s^2 + s dove J != 0, K != 0, e (J^2 - 4) / K^2 è non nullo 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 emette il Z RACCOMANDATO.

Segno di t: Questo mapping fissa il segno di t come specificato in [BHKL13]. Non è richiesta alcuna rettifica aggiuntiva.

Eccezioni: Il caso eccezionale è Z * u^2 == -1, cioè 1 + Z * u^2 == 0. Le implementazioni devono rilevare questo caso e porre 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, poniamo 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), poniamo x = x1, y = sqrt(gx1) con sgn0(y) == 1.
7.  Altrimenti poniamo x = x2, y = sqrt(gx2) con sgn0(y) == 0.
8.   s = x * K
9.   t = y * K
10. return (s, t)

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

6.8. Mapping per curve twisted Edwards

Le curve twisted Edwards (una classe di curve che include le curve 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 Montgomery (Sezione 6.7): ogni curva twisted Edwards è birezionalmente equivalente a una curva Montgomery ([BBJLP08], Teorema 3.2). Questa equivalenza produce un modo efficiente di eseguire l'hash verso una curva twisted Edwards: prima, si esegue l'hash verso una curva Montgomery equivalente, quindi si trasforma il risultato in un punto sulla curva twisted Edwards tramite una mappa razionale. Questo metodo di hash verso una curva twisted Edwards richiede pertanto di identificare una curva Montgomery e una mappa razionale corrispondenti. Descriviamo qui sotto come identificare tale curva e tale mappa.

6.8.1. Mappe razionali da Montgomery a curve twisted Edwards

Ci sono due modi per selezionare una curva Montgomery e una mappa razionale da utilizzare quando si esegue l'hash verso una data curva twisted Edwards. La curva Montgomery e la mappa razionale selezionate DEVONO essere specificate come parte della suite di hash-to-curve per una data curva twisted Edwards; si veda la Sezione 8.

1. Quando si esegue l'hash verso una curva twisted Edwards standardizzata per la quale sono anch'esse standardizzate una forma Montgomery e una mappa razionale corrispondenti, la forma Montgomery e la mappa razionale standard DOVREBBERO essere utilizzate per garantire la compatibilità con il software esistente.

   In certi casi, ad esempio edwards25519 [RFC7748], il segno della mappa razionale dalla curva twisted Edwards alla sua curva Montgomery corrispondente non è dato esplicitamente. In questo caso, il segno DEVE essere fissato in modo tale che l'applicazione della mappa razionale al punto base della curva twisted Edwards produca il punto base della curva Montgomery con il segno corretto. (Per edwards25519, si veda [RFC7748] e [Err4730].)

   Quando si definiscono nuove curve twisted Edwards, DOVREBBE essere specificata anche una equivalente Montgomery e una mappa razionale, e il segno della mappa razionale DOVREBBE essere dichiarato esplicitamente.

2. Quando si esegue l'hash verso una curva twisted Edwards che non ha una forma Montgomery o una mappa razionale standardizzata, DOVREBBE essere utilizzata la mappa data nell'Appendice D.

6.8.2. Metodo Elligator 2

Precondizioni: Una curva twisted Edwards E e una curva Montgomery equivalente M che soddisfano i requisiti della Sezione 6.8.1.

Funzioni ausiliarie:

• map_to_curve_elligator2 è il mapping 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 dovrebbe 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 richieste ulteriori rettifiche di segno.

Eccezioni: Le eccezioni per il mapping Elligator 2 sono come date nella Sezione 6.7.1. Le eccezioni per la mappa razionale sono come date nella Sezione 6.8.1. Non sono possibili altre eccezioni.

La seguente procedura implementa il mapping Elligator 2 per una curva twisted Edwards. (Si noti che il punto di output è denotato (v, w) perché è un punto sulla curva twisted Edwards target.)

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. return (v, w)