A new version of the NIST Federal Information Processing Standard (FIPS) for Digital Signatures has been published. Also see here.
This version includes EdDSA. There are (at least) two notable features of EdDSA. First, it is more closely related to Schnorr signatures than ECDSA. This means it avoids (in my opinion) many of the clunky aspects of ECDSA and allows a much more elegant security analysis. Second, it uses curves in Edwards form. Specifically, the document Recommendations for Discrete Logarithm-based Cryptography: Elliptic Curve Domain Parameters states “this Recommendation includes two newly specified Edwards curves, which provide increased performance, side-channel resistance, and simpler implementation when compared to traditional curves”. The curves include the widely used Edwards25519 curve.
I also take the opportunity to advertise this page which lists applications that use Ed25519.
— Steven Galbraith
and isogenies 
of degree 
and 
of degree 
, together with some auxiliary points. Assume 
.
on points of order 
and SIDH is broken. (This is the goal of the torsion-point attacks by Petit et al, it is also the idea for the improvement to the original attack by Rémy Oudompheng and others that I mentioned above.) This is what Damien Robert’s attack does too.
. Then we can write 
as a sum of four squares. In this post I will take the simpler case when all prime factors of the square-free part of 
where 
are integers. [Note added 15/8/2022 thanks to Daniel Bernstein: To do this we need to factor 
. Then 
where 
is the 
identity matrix. Hence 
defines an isogeny 
for any elliptic curve 
. Specifically ![\alpha(X,Y) = ( [a_1]X + [a_2]Y, [-a_2]X + [a_1] Y )](https://s0.wp.com/latex.php?latex=%5Calpha%28X%2CY%29+%3D+%28+%5Ba_1%5DX+%2B+%5Ba_2%5DY%2C+%5B-a_2%5DX+%2B+%5Ba_1%5D+Y+%29&bg=ffffff&fg=333333&s=0&c=20201002)
. The dual isogeny 
corresponds to the transpose 
. We have ![\hat{\alpha}\alpha = [c]](https://s0.wp.com/latex.php?latex=%5Chat%7B%5Calpha%7D%5Calpha+%3D+%5Bc%5D&bg=ffffff&fg=333333&s=0&c=20201002)
as a map from 
to itself. We will apply this map to both 
.
as 
. Note that 
, since 
on the 4-dimensional Abelian variety 
, by 
. The dual isogeny is 
and one can check 
where 
is the identity map (or identity matrix if you want to view these as matrices).![E_0[ 2^a ]](https://s0.wp.com/latex.php?latex=E_0%5B+2%5Ea+%5D&bg=ffffff&fg=333333&s=0&c=20201002)
. Since ![\hat{\phi}_B \phi_B = [ 3^b]](https://s0.wp.com/latex.php?latex=%5Chat%7B%5Cphi%7D_B+%5Cphi_B+%3D+%5B+3%5Eb%5D&bg=ffffff&fg=333333&s=0&c=20201002)
we can also compute how 
acts on ![E_B[ 2^a ]](https://s0.wp.com/latex.php?latex=E_B%5B+2%5Ea+%5D&bg=ffffff&fg=333333&s=0&c=20201002)
. Hence we can compute how ![{\bf A}[2^a]](https://s0.wp.com/latex.php?latex=%7B%5Cbf+A%7D%5B2%5Ea%5D&bg=ffffff&fg=333333&s=0&c=20201002)
. Since ![\ker(F) \subseteq {\bf A}[2^a]](https://s0.wp.com/latex.php?latex=%5Cker%28F%29+%5Csubseteq+%7B%5Cbf+A%7D%5B2%5Ea%5D&bg=ffffff&fg=333333&s=0&c=20201002)
it means we compute 
.![{\bf A}[ 3^b]](https://s0.wp.com/latex.php?latex=%7B%5Cbf+A%7D%5B+3%5Eb%5D&bg=ffffff&fg=333333&s=0&c=20201002)
and hence compute ![E_0[ 3^b]](https://s0.wp.com/latex.php?latex=E_0%5B+3%5Eb%5D&bg=ffffff&fg=333333&s=0&c=20201002)
and break SIDH.
. I am not aware of any implementation of the attack as yet, but I look forward to seeing one. The attack can also be set up to compute the isogeny 
instead, simply by brute-forcing an extra small 3-power isogeny so that 
.
have order 
be given such that there exists an isogeny 
of degree 
, 
, and 
connected by 3-isogenies.
and hence eventually determines the private key. At step 
the attack does a brute-force search of all possible 
, and the magic ingredient is a gadget that shows which one is correct.
for various 
and it is not clear how to do this if we are not close to a curve with small discriminant complex multiplication. So one hope is that SIDH can be saved by choosing a base curve 
where 
are points. The points 
) can be used to construct a two-round oblivious transfer (OT) scheme. The paper has a fully UC-secure 3-round version. In the live Q&A session, Lai announced that the paper has a “fixable bug” that means the fully secure version requires 4 rounds. Keep an eye on eprint for an updated version.
-NAF for Koblitz Curves Revisited” by Yu and Xu is about efficient discrete-log crypto using elliptic curves. Sadly there were technical problems during the live session and so Yu was unable to answer questions. Since 
on Kohel’s 
-model of elliptic curves, and by organising the precomputation stage for the window method more effectively. Combined, these methods allow to potentially go as far as windows of length 
.
such that 
and 
are very smooth.
with known endomorphism ring (for simplicity let’s take 
). Let 
be an elliptic curve such that there is an isogeny 
of degree 
. Suppose we are also given 
where 
generate the subgroup of points of order 
on 
on 
from 
(Petit’s original paper needed the stronger condition 
). This is an important result, but it has no impact on standard implementations of SIDH (such as the SIKE submission to NIST), which have 
. However, the paper is a warning about non-standard variants of SIDH, and the paper discusses several such situations.
with 
for small 
is at least 4000 bits, so that protocol messages in key exchange are now at least 4000 bits. This is much worse than the originally suggested 512 bits. The timings are of the order of a few seconds for each operation, which again is much worse than desired. In conclusion, CSIDH may be saved, but it does lose some of its advantages over lattices (e.g., small keys and messages).
be the elliptic curve over 
be an endomorphism of 
be a certain multiplicative subgroup of ![\mathbb{Z}[\iota]](https://s0.wp.com/latex.php?latex=%5Cmathbb%7BZ%7D%5B%5Ciota%5D&bg=ffffff&fg=333333&s=0&c=20201002)
. We need 
be a subgroup of 
is defined to be 
. So 
-invariants). Computing the group action is easy when 
in the SIDH protocol (when 
is not known). To do this, the authors use torsion point information, as already discussed in item 1 above. So suppose we are given 
where 
. Since SIDH with such parameters can already be broken in classical polynomial time by Petit (or the first paper discussed above), one would not use Kuperberg’s algorithm in this case. Hence this paper does not weaken SIDH. Instead the merit of the paper is to explain how group actions can be introduced in the SIDH setting, which contradicts the conventional wisdom that “SIDH is not based on group actions”.
the prover wants to prove that they know the secret isogeny 
. To do this, as in SIDH, commit to an isogeny 
and the value 
, where 
and 
where 
and 
. The verifier sends a single bit, and the prover reveals either 
and its image on 
, or 
.
. The signer/prover, knowing the secret key, can compute the isogeny 
. However it is insecure to publish this isogeny, since it would leak the kernel of 
and hence reveal the private key. Instead, we’d like to use the KLPT algorithm to create an isogeny 
which is “independent” of 
(this is exactly what KLPT does). If there was an efficient way to do this then we’d have a cool signature scheme. See the below figure, taken from the SQISign paper.
. Then, given the challenge 
, and could win.
. The KLPT algorithm exploits the fact that isogenies from 
corresponding to an ideal 
. That’s nice in quaternion-land, but we can’t compute the public key, so we need to compute an equivalent ideal whose norm is a power of small primes, and thus compute the corresponding isogeny 
. The public key of a signer is 
.
corresponding to 
.
and then push forward (via Lemma 3 of the paper). This results in 
, which is a left-
-ideal.
. The isogeny 
corresponds to 
. Somehow we need to compute an equivalent ideal, but this is a left-
-ideal, which is no good to us. The trick is to pull back 
for some curve 
. Then we would run KLPT on this ideal to get a random ideal of suitable smooth norm, then push forward via 
, and the pushforward of one of them to 
. (This is the reason why the degree of 
in the Eichler order. It is necessary to develop a variant of KLPT to ensure this restriction is possible.
. The attacker can’t run the same algorithm as the signer, since they have no way to pull back isogenies to 
ellipticnews 