2022 Developer Survey is open! Take survey.

Hot answers tagged

10 votes
Accepted

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

On page 67 of the same spec, Algorithm 42 does exactly what you are asking for. Here it is again in Python: ...
user avatar
8 votes
Accepted

SIKE: choice of n

I am the principal submitter for the SIKE proposal. The reference implementation uses 24, 32, and 40 bytes respectively for SIKEp503, SIKEp751, and SIKEp964 respectively. The motivation for these ...
user avatar
  • 746
7 votes

Supersingular Isogeny Key Exchange broken?

Sorry I will have to answer my own question. I received a mail from Luca De Feo a moment ago. "Nope, I discussed this at length with Jean-François Biasse, and we couldn't find a way to apply this ...
user avatar
7 votes
Accepted

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

Is SIDH actually insecure when keys are reused? If so, why? How can SIDH actually be broken? Can you demonstrate an attack? Yes it is. There is a well known adaptative attack, described here ...
user avatar
7 votes

PQ Key Exchange based on Elliptic Curve Isogenies

The Supersingular Elliptic Curve Isogeny Key Exchange that you refer to was first published in 2011 by DeFeo, Jao, and Plut. It builds on but is quite distinct from earlier work by Rostovetsev and ...
user avatar
7 votes
Accepted

Has Burdges and De Feo's concept of Delayed Encryption ever been implemented?

There is PoC code for the De Feo-Masson-Petit-Sanso VDF here: https://github.com/isogenies-vdf/isogenies-vdf-sage. It's easily adapted to Delay Encryption.
user avatar
6 votes

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

Those numbers for the key sizes come from the bit length of the prime chosen for the finite field $F_p$. To clarify, there are no complex numbers used at all. The elliptic curve is over a quadratic ...
user avatar
6 votes
Accepted

SIKE/SIDH algorithm 6

Not a complete answer, just trying to shed some of your doubts. I've noticed the point tripling algorithm (algorithm 6) was already described in a different paper. Nevertheless, the SIKE paper uses ...
user avatar
5 votes

Supersingular Isogeny Key Exchange broken?

Also, the algorithm given in the mentioned paper has a complexity os $\tilde{O}(p^{\frac{1}{4}})$. The best known attack (As mentioned by de Feo, Jao and Plut) on the SSIKE is based on the claw ...
user avatar
  • 482
5 votes
Accepted

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

SIDH is believed to be quantum secure because the fastest known quantum attacks against it (which is based on claw finding algorithm) require exponential time with complexity $\mathcal{O}(p^{1/6})$.
user avatar
  • 990
5 votes

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?

You are right that Vélu's formulas also work for any extension field, but then they require arithmetic in that field. Doing computations in $\mathbb F_p$ is simply much more efficient than in ...
user avatar
  • 10.9k
5 votes
Accepted

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

I am an inventor of SIDH. The computations take place in $\operatorname{GF}(p^2)$ just because all supersingular elliptic curves are defined over $\operatorname{GF}(p^2)$, up to isomorphism. It's just ...
user avatar
  • 746
5 votes

Quantum bit level security of Supersingular Isogeny based Diffie Hellman scheme

Block cipher is a concept from symmetric cryptography. Here we're talking about public key cryptography. SIKE is a public key encryption (PKE), and a key encapsulation mechanism (KEM). Of course ...
user avatar
4 votes
Accepted

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

The complexity of Vélu's formulas scales linearly with the size of the kernel subgroup, so directly applying them to a point of huge order is not feasible for isogenies of "cryptographic" degree. ...
user avatar
  • 10.9k
4 votes

Supersingular Isogeny Key Exchange Software

The inventors of the Supersingular Isogeny Key Exchange, Defeo, Jao and Plut have posted some code on GITHUB at: https://github.com/defeo/ss-isogeny-software/ There is also a paper on implementation ...
user avatar
4 votes

SIDH: key agreement - why does it work?

I invented SIDH and can surely answer any technical questions about it. Proofs of $E_{ab} \cong E_{ba}$ are given in several places, though rarely in official Theorem / Proof form, because this result ...
user avatar
  • 746
4 votes
Accepted

SIKE as Diffie-Hellman exchange

I am one of the inventors of SIKE. There is no actual Diffie-Hellman group in SIKE. If there were, then SIKE would be vulnerable to Shor's algorithm, as you said, largely defeating the purpose of a ...
user avatar
  • 746
4 votes
Accepted

What basic knowledge is required to understand SIKE?

Craig Costello has tried writing precisely what you're interested in, see SIKE for Beginners. It refers to numerous other surveys for isogeny-based crypto which may be useful (lecture notes by De Feo, ...
user avatar
  • 8,424
4 votes
Accepted

CSIDH - l ideal generators

To answer your first question: it's as simple as that. Restating what you wrote, it's enough to check that $l$ divides all the four generators: $l^2$, $l(π-1)$, $l(π+1)$ and $π^2-1$. It's obvious for ...
user avatar
3 votes
Accepted

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

Let an elliptic curve $E(F_p)$ have the Frobenius discriminant $D_\pi$, and $\left(\frac{D_\pi}{l}\right)$ be a Kronecker symbol for some $l$-degree isogeny. If $\left(\frac{D_\pi}{l}\right)=-1$, then ...
user avatar
3 votes

How could you find the preimage of an isogeny function?

Isogenies are always surjective, but there's a nuance. They are surjective over the algebraic closure. The correct statement would be "for every $\mathbb{F}_{17}$-point on the green curve there are ...
user avatar
3 votes
Accepted

Using Microsoft SIDH library for messages signing

SIDH is a key exchange algorithm, not a digital signature algorithm. The way SIDH works is each side generates a private, random value along with a corresponding public value. The public values are ...
user avatar
  • 12.9k
3 votes

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

All 'good' implementations so far have used the same curve, but there is now variation in the underlying finite field, which affects the other base parameters of the public points for each party and ...
user avatar
3 votes
Accepted

SIDH cryptosystem question

I invented SIDH. $E_0[\ell_A^{e_A}]$ has cardinality $(\ell_A^{e_A})^2$. Each of $P_A$, $Q_A$, and $R$ has order $\ell_A^{e_A}$ and they all generate different subgroups. This is possible because $E_0[...
user avatar
  • 746
3 votes

Parameter choice Supersingular Isogeny DH

Found the answer: The $l$-torsion subgroup is isomorphic to a direct sum of two quotient groups: $E[l] \simeq \mathbb{Z}_n \oplus \mathbb{Z}_n$, hence the basis requires two points and the elements ...
user avatar
  • 482
3 votes

PQ Key Exchange based on Elliptic Curve Isogenies

Two approaches to Post Quantum Key Exchange that have acceptable bandwidth requirements are the NTRU/Ring-LWE lattice designs and the ECC Isogeny Key exchange you mention. Since the UK spy agency ...
user avatar
3 votes

Finding the subgroup in isogeny-based cryptography

While there is a sub-exponential attack to compute isogenies on ORDINARY elliptic curves (the basis for the Rostovev and Stulbunov paper that you reference) there is not (yet at least) a sub-...
user avatar
2 votes

Finding the subgroup in isogeny-based cryptography

There is a quantum sub-exponential time algorithm to extract the private keys from the system you cite. Another paper by Luca De Feo, David Jao, and Jerome Plut improves upon that system, addresses ...
user avatar
  • 1,104

Only top scored, non community-wiki answers of a minimum length are eligible