MAK Crypto Seminar: Javier Silva
- MAK Crypto Seminar: Javier Silva
- By: Javier Silva (Univ. Pompeu Fabra). Title: A signature scheme from supersingular isogeny problems. Wednesday 9 November 2016, at 12'00\. Campus Nord UPC, Building C3, Room 204a (2nd floor).
By: Javier Silva (Univ. Pompeu Fabra). Title: A signature scheme from supersingular isogeny problems. Wednesday 9 November 2016, at 12'00\. Campus Nord UPC, Building C3, Room 204a (2nd floor).
- 09/11/2016 des de/d' 12:00"
- Campus Nord UPC, Building C3, Room 204a (2nd floor)
- Afegeix un esdeveniment al calendari
In this talk, we present an identification protocol and a signature scheme due to Galbraith, Petit and Silva. We rely on the hardness of an isogeny problem on supersingular elliptic curves, which is believed to be a hard problem, and even the best known quantum algorithms to solve it run in exponential time.
Our identification protocol relies on two key ingredients. First, the good mixing properties of supersingular isogeny graphs, which allow us to move through the graph efficiently and at the same time achieve random-looking outputs.
Second, we make use of Deuring’s correspondence, which identifies endomorphism rings of supersingular elliptic curves with maximal orders in a certain quaternion algebra. We use the algorithm of Kohel-Lauter-Petit-Tignol (ANTS 2014) to compute ideals of a certain norm between maximal orders in the quaternion algebra. This will allow to simulate the protocol with indistinguishable distribution.
Finally, we use the standard technique of Fiat-Shamir to derive a signature scheme from the identification protocol, and we discuss its security.
Background on elliptic curves, quaternion algebras and expander graphs will be provided at the beginning of the talk, only cryptography definitions are required.