This work explores the application and efficient deployment of (standardized) post-quantum (PQ) digital signature algorithms in the blockchain environment. Specifically, we implement and evaluate four PQ signatures in the Ethereum Virtual Machine: W-OTS+ , XMSS, SPHINCS+, and MAYO. We focus on optimizing the gas costs of the verification algorithms as that is the signature schemes’ only algorithm executed on-chain, thus incurring financial costs (transaction fees) for the users. Hence, the verification algorithm is the signature schemes’ main bottleneck for decentralized applications. We examine two methods to verify post-quantum digital signatures on-chain. Our practical performance evaluation shows that full on-chain verification is often prohibitively costly. Naysayer proofs (FC’24) allow a novel optimistic verification mode. We observe that the Naysayer verification mode is generally the cheapest, at the cost of additional trust assumptions. We release our implementation called poqeth as an open-source library.

Abstract An oriented supersingular elliptic curve is a curve which is enhanced with the information of an endomorphism. Computing the full endomorphism ring of a supersingular elliptic curve is a known hard problem, so one might consider how hard it is to find one such orientation. We prove that access to an oracle which tells if an elliptic curve is $$\mathfrak {O}$$ O -orientable for a fixed imaginary quadratic order $$\mathfrak {O}$$ O provides non-trivial information towards computing an endomorphism corresponding to the $$\mathfrak {O}$$ O -orientation. We provide explicit algorithms and in-depth complexity analysis. We also consider the question in terms of quaternion algebras. We provide algorithms which compute an embedding of a fixed imaginary quadratic order into a maximal order of the quaternion algebra ramified at p and $$\infty $$ ∞ . We provide code implementations in Sagemath (in Stein et al. Sage Mathematics Software (Version 10.0), The Sage Development Team, http://www.sagemath.org , 2023) which is efficient for finding embeddings of imaginary quadratic orders of discriminants up to O(p), even for cryptographically sized p.

Abstract Isogeny‐based cryptography is a promising approach for post‐quantum cryptography. The best‐known protocol following that approach is the supersingular isogeny Diffie–Hellman protocol (SIDH); this protocol was turned into the CCA‐secure key encapsulation mechanism SIKE, which was submitted to and remains in the third round of NIST's post‐quantum standardisation process as an ‘alternate’ candidate. Isogeny‐based cryptography generally relies on the conjectured hardness of computing an isogeny between two isogenous elliptic curves, and most cryptanalytic work referenced on SIKE's webpage exclusively focusses on that problem. Interestingly, the hardness of this problem is sufficient for neither SIDH nor SIKE. In particular, these protocols reveal additional information on the secret isogeny, in the form of images of specific torsion points through the isogeny. This paper surveys existing cryptanalysis approaches exploiting this often called ‘torsion point information’, summarises their current impact on SIKE and related algorithms, and suggests some research directions that might lead to further impact.

We propose polynomial-time algorithms for finding nontrivial zeros of quadratic forms with four variables over rational function fields of characteristic 2. We apply these results to find prescribed quadratic subfields of quaternion division algebras and zero divisors in $M_2(D)$, the full matrix algebra over a division algebra, given by structure constants. We also provide an implementation of our results in MAGMA which shows that the algorithms are truly practical.