Design and analysis of isogeny-based static-key protocols

Basso, Andrea (2024). Design and analysis of isogeny-based static-key protocols. University of Birmingham. Ph.D.

Preview

Basso2024PhD.pdf
Text - Accepted Version
Available under License All rights reserved.
Download (2MB) | Preview

Abstract

The advent of quantum computers renders most cryptographic protocols obsolete and urges for a quick transition to post-quantum solutions. Many valid techniques for quantum-secure encryption and digital signatures have been proposed, but more advanced primitives do not yet have efficient post-quantum replacements. Among these are primitives where multiple parties have long-term secrets; we refer to these protocols as static-key cryptography. Few post-quantum static-key protocols have been reported in the literature, and nearly all are based on isogenies. In this work, we focus on two fundamental static-key primitives: non-interactive key exchanges (NIKE) and oblivious pseudorandom functions (OPRF). We first study the security of existing constructions with long-term static keys, and then we develop new protocols that outperform the existing ones.

In particular, we first assess the security of the isogeny-based NIKE based on k-SIDH proposed by Jao and Urbanik. Compared to the original k-SIDH, the protocol relies on non-trivial automorphisms to improve its efficiency. However, we show the protocol is vulnerable to an attack that exploits the additional automorphism structure. While the attack does not fully break the proposed parameters, it shows that the k-SIDH variant by Jao and Urbanik reduces the security level more so than it increases efficiency, making it less preferable over the standard k-SIDH.

We also analyze a validation method proposed by Fouotsa and Petit that checks the correctness of SIDH public keys. If the method were secure, it could be translated into an efficient NIKE. However, we demonstrate an efficient attack that allows a malicious party to provide dishonest public keys and satisfy the validation check. As part of this work, we also discuss possible improvements to the countermeasures but show that they are similarly vulnerable to an extension of our attack. We then conclude with a discussion on the possibilities and the requirements of future validation techniques.

Beyond NIKEs, we analyze the security of the isogeny-based OPRF proposed by Boneh, Kogan, and Woo at Asiacrypt 2021. We introduce a polynomial-time attack on the one more unpredictability property of the OPRF, which allows a malicious user to evaluate the PRF independently after some interactions. We show that a simple countermeasure can prevent the attack; we also propose a second attack that achieves the same goals but cannot be easily defended against. The second attack, however, has subexponential complexity. To demonstrate its feasibility, we develop a proof-of-concept implementation that can efficiently carry out the attack.

In follow-up work, we develop an efficient countermeasure against the previously introduced attack. We also integrate the countermeasures against the SIDH attacks into the OPRF protocol, and we propose a new proof of isogeny knowledge that can work with the countermeasures. Moreover, we introduce a novel zero-knowledge proof of parallel isogeny that provides non-interactive verifiability. By combining everything together, we obtain an OPRF protocol that is post-quantum secure, verifiable, round-optimal, and moderately compact.

Lastly, we study the problem of generating supersingular elliptic curves with unknown endomorphism ring. Such curves are often needed as starting parameters in many isogeny-based protocols, including the OPRF protocol we have developed. To generate curves of unknown endomorphism ring, we propose a distributed trusted-setup protocol that relies on a new statistical zero-knowledge proof; we prove its security in the general universally composable framework.

These works, both constructive and cryptanalytic, provide a better understanding of the limitations and the possibilities of isogeny-based cryptography in developing static-key protocols, and they are an important stepping stone towards fully practical post-quantum NIKEs and OPRFs.

Type of Work:

Thesis (Doctorates > Ph.D.)

Award Type:

Doctorates > Ph.D.

Supervisor(s):