Questions tagged [isogeny]

Elliptic curve isogenies are structure-preserving maps between elliptic curves which have been proposed as a foundation of post-quantum cryptosystems.

Filter by
Sorted by
Tagged with
0
votes
1answer
38 views

Public points in SIDH

I was going through a presentation titled "SIKE in Hardware" by professor Reza Azarderakhsh. On the page $10$ of the presentation he introduces a variable $w$. Could you please explain what the ...
2
votes
1answer
72 views

SIDH: key agreement - why does it work?

In SIDH both parties agree on the key in following way: Alice calculates a kernel $R = mPB + nQB$ Thanks to Velu formulas (and further improvements), she can now compute isogeny $\phi_a$ She uses $\...
0
votes
2answers
70 views

SIDH cryptosystem question

I'm trying to understand the SIDH cryptosystem and got confused at this point: Alice fixes base $\{P_A,Q_A\}$ so that it generates $E_0[l_A^{e_A}]$. Then she chooses secret parameters $m_A,n_A$ and ...
0
votes
0answers
37 views

Regarding the isogeny path problem

Given two elliptic curves, it is hard to calculate an isogeny of large degree between them. Does this only apply to supersingular isogenies or to ordinary ones as well? Additionally, is the mapping ...
1
vote
1answer
103 views

CSIDH: Why do we need ideals in the form of $\langle \ell, \pi \pm 1 \rangle$ in order to apply Vélu's formulas when computing the action?

I am trying to understand the action of the CSIDH protocol. Let $E_0:y^2=x^3+ax^2+bx$ be a Montgomery elliptic curve over $\mathbb{F}_p$ for some prime $p$. If we take $\mathcal{O}$ as $End_{\mathbb{...
3
votes
1answer
91 views

Why are computations (isogeny) in SIDH done in an extended prime field?

While reading the SIDH key exchange protocol, I noticed that all the isogeny computations and curves are defined over the extended prime field $\mathbb{F}_{p^2}$. Does it make the problem ...
1
vote
0answers
53 views

What does the absence of Abelian group actions on supersingular isogenies implicate?

There are no Abelian group actions on supersingular isogenies. Why does this make them secure? - motivated by De Feo's Paper on mathematics of IBS
3
votes
1answer
177 views

How are isogeny graphs made and how are they helpful to crypto?

I don't understand how the shapes of isogeny graphs are determined. While Alice and Bob do walk on it and don't backtrack, are they actually relevant to crypto? Also, I was told that supersingular ...
1
vote
1answer
145 views

Exactly what part of SIDH is proven to be NP-hard?

SIDH is quantum secure, why is it quantum secure? Exactly which part of the algorithm is proven to be NP-hard? Computing the isogeny function?
2
votes
1answer
64 views

How could you find the preimage of an isogeny function?

How do you know if an isogeny is surjective or not, and how do you tell how many points on E maps to E'? Does the answer lie in the degree of the isogeny function?
0
votes
1answer
74 views

Using Microsoft SIDH library for messages signing

SIDH library looks good but lacks documentation and samples. The only signature-related code was found at http://github.com/yhyoo93/isogenysignature/blob/master/tests/kex_tests.c appeared not able to ...
2
votes
1answer
249 views

SIKE/SIDH algorithm 6

I was recently reading this paper on SIKE and I'm trying to understand the details of the implementation. I've noticed the point tripling algorithm (algorithm 6) was already described in a different ...
5
votes
1answer
111 views

SIKE: choice of n

The "Supersingular Isogeny Key Encapsulation" proposal submited to PQC-NIST (PDF) defines the value $n$ to be from set $\{192,256,320\}$ (see point 1.4). Does anybody have an idea to what it ...
0
votes
1answer
99 views

SIKE algorithm 2

I was recently reading this paper on SIKE and there on page 20 I encountered algorithm 2. I understanding line 14 of algorithm 2 in sike but I don't understanding line 17 of algorithm 2. $h (s || (c_0,...
5
votes
2answers
229 views

How to get an optimal strategy in computing isogenies for SIDH/SIKE

How to get a strategy $(s_1,...,s_{t-1})$ as mentioned in section 1.3.7 of SIKE spec? If possible, can anyone give me an example? And why do we need to compute all leaf point? I though we just need ...
0
votes
1answer
192 views

Quantum bit level security of Supersingular Isogeny based Diffie Hellman scheme

I'm a newbie in studying and learning how SIDH works. I have a simple doubt. So my question is in the SIKE submission present in this link (https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/...
2
votes
2answers
351 views

How to compute a smooth-degree isogeny given a generator point of its kernel?

I need to compute an isogeny from $E: y^2 = x^3 + ax + b$, given a generator point for its kernel subgroup, using Python. The point has smooth order. I need both the parameters for the curve and ...
2
votes
1answer
106 views

Supersingular isogeny Diffie–Hellman key exchange (SIDH) Library Support AES-256?

In the version 3.0 of the SIDH library, it implements SIDH/SIKEp503 (AES-128) and SIDH/SIKEp751 (AES-192) only. Are there plans to incorporate AES-256? Nathan Aw
5
votes
1answer
250 views

Any Supersingular Isogeny-based Diffie-Hellman (SIDH) key exchange recommended Curve Domain Parameters?

For existing ECDH, I understand that there are recommended Elliptic Curve Domain Parameters. May I know if there are such similar considerations in SIDH? Any recommended Curve Domain Parameters?
5
votes
1answer
609 views

Can Microsoft's SIDH (Supersingular Isogeny) keypairs be reused for encryption? If not, why?

I was considering using Microsoft's SIDH implementation for post-quantum public-key encryption because of its relatively small key size. I realized however, thanks to Issue #4, that it might not be as ...
3
votes
0answers
182 views

How can I calculate the security level provided by a supersingular Elliptic Curve?

I want to know what security level is provided by an elliptic curve used in Supersingular isogeny Diffie–Hellman key exchange (SIDH). Is there any mathematical convention to follow or by looking at ...
4
votes
2answers
394 views

Elliptic Curve Isogenies, Frobenius endomorphism relation to characteristic equation

In Schoof's 1995 paper, Counting points on elliptic curves over finite fields, page 236, Proposition 6.1(i) states: Let $\mathbb{E}$ be an elliptic curve over $\mathbb{F}_p$. Suppose that its $j$-...
4
votes
2answers
196 views

How does the key size in supersingular isogeny schemes relate to their security level?

I'm looking at the De Feo, Jao, and Plût 2014 paper: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. My understanding of section 3.2 Key Exchange, is that Alice'...
5
votes
2answers
342 views

Finding the subgroup in isogeny-based cryptography

Isogeny-based cryptography is one of the newest post-quantum cryptography. Hardness of this system is based on finding isogeny between two elliptic curves. Also this is theorem: Elliptic curves are ...
6
votes
3answers
436 views

Supersingular Isogeny Key Exchange broken?

Found this report detailing a quantum algorithm for computing isogenies between supersingular elliptic curves. http://cacr.uwaterloo.ca/techreports/2014/cacr2014-24.pdf with the quote "...
3
votes
1answer
77 views

DSSP reduction to DSSI

In “Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies" by DeFeo, Jao and Plut, a reduction from the Decisional Supersingular Product (DSSP) problem to Decisional ...
5
votes
1answer
179 views

Parameter choice Supersingular Isogeny DH

In “Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies” by DeFeo, Jao and Plut (PDF), the public parameters are defined as: Supersingular curve $E$, and bases $P, Q$ ...
3
votes
1answer
1k views

Supersingular Isogeny Key Exchange Software [closed]

Are there any optimised implementations of the Supersingular Isogeny Key Exchange by Defeo, Jao, and Plut. It seems like this would be a great drop-in replacement for Diffie-Hellman in both OpenSSL ...
2
votes
2answers
380 views

PQ Key Exchange based on Elliptic Curve Isogenies

I was reading the Wikipedia article on Post Quantum Cryptography and was interested in opinions as to whether the Supersingular Elliptic Curve Isogeny Diffie-Hellman listed there would be a good Post ...