Decisional Diffie-Hellman Problem on Elliptic Curves
In this study, the decisional Diffie-Hellman problem is explored in the context of class group actions on elliptic curves. The formalization and applications of the problem are discussed along with potential solutions and implications. The research delves into distinguishing distributions and the theoretical underpinnings of cryptographic security in algebraically closed fields and ideal-class groups. Various instances and historical developments related to the problem are also analyzed.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
On On the class class group group actions on the decisional decisional Diffie actions on oriented Diffie- -Hellman Hellman problem oriented elliptic problem for elliptic curves for curves Wouter Castryck 1 , Marc Houben 1 , Frederik Vercauteren 1 , Benjamin Wesolowski 2 A N T S A N T S X V X V University of Bristol, August 8 12, 2022 1 2
1/16 1. 1. Decisional Decisional Diffie Diffie- -Hellman Hellman Classical Diffie-Hellman (1976): = ? ?? chooses ? ?? 1 chooses ? ?? 1 ?? ?? Can Can eavesdropper eavesdropper learn about about ??? from learn something something from ?, ??, ?? ? ? common secret: = ??? ??? ?? ? = Ideally: no !
2/16 1. 1. Decisional Decisional Diffie Diffie- -Hellman Hellman Formalized in the decisional decisional Diffie Diffie- -Hellman Hellman problem problem: Distinguish between the distributions $?? 1 ?,??,??,??? ?,? $?? 1 ?,??,??,?? ?,?,? ( ( key key hardness hardness assumption in in provable provable security ) security ) assumption with a non-negligible advantage. In this case: not not hard hard because of distinguishing property ??? ? ?? ? ?? ? = 1 = 1 or = 1 . Easy to fix by working in prime order subgroup of ?? with ? the Legendre Legendre symbol symbol.
3/16 1. 1. Decisional Decisional Diffie Diffie- -Hellman Hellman Diffie-Hellman for class group actions on elliptic curves (CRS 1997-2004, CSIDH 2018, OSIDH 2020): Cl ? Ell?(?) ? Ell?(?) chooses ? Cl(?) chooses ? Cl(?) ? = algebraically closed field ? ? ? = imaginary quadratic order ? ? Cl(?) = its ideal-class class group group Ell?(?) = set of ?- -oriented elliptic elliptic curves oriented curves over ? common secret: ?? ? ? ? ? = = ? ? ? = isogeny isogeny-wise action
4/16 1. 1. Decisional Decisional Diffie Diffie- -Hellman Hellman The decisional decisional Diffie Diffie- -Hellman Hellman problem problem for class group actions (Stolbunov 2006): Distinguish between the distributions $ Cl(?) ?,? ?,? ?,?? ? ?,? $ Cl(?) ?,? ?,? ?,? ? ?,?,? with a non-negligible advantage. This This work work: : we give a family of distinguishers distinguishers, breaking DDH for almost all instances of Cl(?). reminiscent of Legendre Legendre symbol symbol for classical DDH Again: easy to fix.
5/16 1. 1. Decisional Decisional Diffie Diffie- -Hellman Hellman More precise statement over ??: For each assigned assigned character character ? Cl ? { 1} and each given pair Ell? ?? (? unknown!) ?,?? = ? ? possible to compute ?(?) using ? ?4log? operations in ??, with ? the modulus of ?. will become apparent classical ! field of definition of ?,? ,? ? ,? (?) This distinguishes between ?,? ?,? ?,?? ? and ?,? ?,? ?,? ? : ? ? ?? = ? ? ? ? = 1 while ? ? ? = ? ? ? ? =1 2 as soon as ? is non-trivial.
6/16 2. 2. Prerequisites Prerequisites: : assigned assigned characters characters Fundamental observation (Legendre 1798) : Fundamental observation (Legendre 1798) : for all odd primes ? ? and every non-zero ideal ? ? the Legendre symbol for all odd primes ? ?we have a well well- -defined defined character character ?(?) ? ?(?) ? ? Cl ? { 1} ? , , depends depends only to 2 ? we may attach similar characters : ?4mod 8 0 extra characters ? and ? only on on its its ideal ideal- -class class [?], assuming gcd ? ? , ? = 1 , 1, 4, 5 2 6 ? ? ?2 1 8 ? ? 1 2 ? ? 1 , ? ? 1 ? ? ? Genus Genus theory theory (Gauss 1801) : The number ? of assigned characters satisfies #Cl(?)[2] = 2? 1. at most one of them is trivial (if ? = 1 then trivial).
7/16 2. 2. Prerequisites Prerequisites: : oriented oriented elliptic elliptic curves curves A ( (primitive primitive) ) ?-orientation orientation on an elliptic curve ?/? is an injective ring morphism ? ? End ? that cannot be extended to a larger imaginary quadratic order. Examples: CM elliptic curves over ?, ordinary elliptic curves over ?? : ? is an isomorphism supersingular elliptic curves over ?? : ? embeds ? in a quaternion order e.g., ? ?2= ?3+ ? and ? 3 mod 4 ? ? End E ? Frobp ? 1 End E 1 ?,? ( ?, 1?)
8/16 2. 2. Prerequisites Prerequisites: : oriented oriented elliptic elliptic curves curves ?-oriented elliptic curve (?,?) ? -orientation ? on ? isogeny ? ? ? order in same imaginary quadratic field (conductor changes by at most deg?) if ? = ? then ? called horizontal horizontal if ? is isomorphism, then horizontal we write ?,? (? ,? ) Definition: Definition: Ell?? = ?,? ? an elliptic curve over ? and ? an ? orientation on ?} (non-empty as soon as char ? | ?(?), Onuki 2021)
9/16 2. 2. Prerequisites Prerequisites: class : class group group action action To each (?,?) Ell?(?) and invertible ideal ? ? one can attach isogeny ?? ? ? Ell?(?) whose kernel is the subgroup (scheme) (?,?) ker?(?). ? ? deg? = ?(?) ? (?,?) horizontal ! So we get ? ,? Ell?(?). Always horizontal The pair (? ,? ) only depends on the class [?]. Notation: (? ,? ) = ? (?,?). This is a free free group action.
10/16 3. Basic 3. Basic strategy strategy (C., Sot kov , V. 2020) Eavesdropper sees ?,? , (? ,? ) = ? (?,?) Ell?(?) for unknown ? Cl ? . Let ? ? an odd prime divisor. ?(?) ? Goal: Goal: compute assigned character value? ? = . Knows: an isogeny ? ? ? of degree ?(?) (coprime with ?) Strategy: Strategy: extract information about ? ? mod ? using the Weil Weil pairing pairing ??:? ? ? ? ?? ? deg? ?(?) through its compatibility compatibility property: ??? ? ,? ? = ???,?
10/16 3. Basic 3. Basic strategy strategy (C., Sot kov , V. 2020) Strategy: Strategy: extract information about ? ? mod ? using the Weil Weil pairing pairing ??:? ? ? ? ?? ? ?(?) through its compatibility compatibility property: ??? ? ,? ? = ???,? Naive Naive hope: hope: simply find matching point pairs HOW? HOW? ? = ? ? ,? = ? ? ? [?] ?,? ?[?] and with a non-trivial pairing value and recover ?(?) as a discrete logarithm in ??.
10/16 3. Basic 3. Basic strategy strategy (C., Sot kov , V. 2020) Strategy: Strategy: extract information about ? ? mod ? using the Weil Weil pairing pairing ??:? ? ? ? ?? ? ?(?) through its compatibility compatibility property: ??? ? ,? ? = ???,? same unknown scalar Less Less naive naive hope: hope: find point pairs ? = ?? ? ,? = ?? ? ? [?] ?,? ?[?] and ?(?) ? with a non-trivial pairing value and recover via a discrete logarithm in ??. = ???,??2?(?), so still good enough! ??? ,? = ???? ? ,?? ?
11/16 3. Basic 3. Basic strategy strategy (C., Sot kov , V. 2020) For ordinary ordinary elliptic curves over finite finite fields fields (CRS): idea can be made to work using Tate Tate pairing pairing (instead of Weil) reason: allows for non-trivial self-pairings, so can take ?,? proportional proportional requires cyclic ? ?? ? and ? ?? ? , can be enforced by descent of ?-isogeny volcano Bad news: Bad news: does not work in oriented case because of infinite volcanoes (for ?[ ?]-orientations (CSIDH): ad-hoc solution but does not generalize)
12/16 4. Solution 4. Solution Back to the Weil pairing Weil pairing. Instead of using proportional points, take ? = ?(?)(?) for well-chosen ? ?. Easy but key key observation observation: : write ? = ?[?] then since ? ? we must have that ?(?) acts as ? ? ? ) (? ?? 0 with respect to some basis ?1,?2 ?[?].
12/16 4. Solution 4. Solution Easy but key key observation observation: : write ? = ?[?] then since ? ? we must have that ?(?) acts as ? ? ? ) (? ?? 0 with respect to some basis ?1,?2 ?[?]. Corollary: Corollary: if ? is any non-eigenvector of ?(?), then ???,?(?) ? = ??(??1+ ??2,? ? ??1+ ??2)? ??, ? ?? = ??(??1+ ??2,???1+ ???1+ ???2) = ????1,???2 ????2,???1 ??(??2,???1) ?2= ???2,? ? ?2 ?2 = ???2,??1 does not depend on the choice of ?, modulo squares in the exponent.
13/16 4. Solution 4. Solution Leads to following method: pick generator ? ? of norm coprime to ?, pick non-eigenvector ? ?[?] of ?(?), pick non-eigenvector ? ? [?] of ? ? . then automatically ? ? ? [?] is a non-eigenvector of ? ? It follows: ?2 ?2?(?) ??? ,? ? ? = ?? ? ? ,? ? ? ? = ???,? ? ? ?(?) ? so can recover via a discrete logarithm in ??. Even moduli (? = 4,8): similar but slightly more technical
14/16 5. A few 5. A few remarks remarks 1. 1. For ordinary ordinary elliptic conceptually simpler than C., Sot kov , V. 2020 (no descent of volcanoes) worst-case: slightly less efficient (full ?-torsion needed) elliptic curves curves over finite finite fields fields: 2. 2. Often possible to evaluate several allows to distinguish with probability up to 1 2? 1 per sample, actually computes the coset of ? modulo several/all assigned characters ?1,?2, ,?? at ? cl(?): ? Cl ?2= ker??, ?=1 thereby reducing the security of Cl(?) to that of Cl ?2. generalizations: reductions to Cl ?4, Cl ?8, 3. 3. Best candidates for generalizations
15/16 6. An 6. An application application The vectorization vectorization problem: given ?,?? = ? ? Ell?? , find ? Cl(?). much harder harder and more more fundamental fundamental than decisional Diffie-Hellman! Theorem Theorem (W. 2022, informal statement) Given oracle access to an algorithm for computing endomorphism rings of supersingular elliptic curves over ??, the vectorization problem for Ell? ?? can be solved in time polynomial in log? and #Cl(?)[2] = 2? 1. Source: Source: the reduction actually computes ?2 primorial ?= 3 ? ??. Note: #Cl(?)[2] can be exponential in input size, e.g. for primorial
16/16 6. An 6. An application application Source: Source: the reduction actually computes ?2 exhaustive search through all #Cl(?)[2] options for ? can be avoided if we know ? modulo Cl ?2! not compute this in poly-time: each ? ? takes ?(?4), note: in general we do not but worst cases worst cases for exhaustive search are best cases best cases for us (e.g., primorial ?), trade-off leads to reduction in time 12,#Cl ? 2 . min ? ?
Questions Questions? ? Thanks for listening!
