Zero-Knowledge Proofs of Isogeny Diamonds

Commutative diagrams of isogenies between supersingular elliptic curves, which are called isogeny diamonds, have become fundamental to isogeny-based cryptography for both constructive and cryptanalytic purposes. In parallel, proofs of knowledge of isogenies have been widely studied and have found many applications. In this work, we combine these two directions and introduce zero-knowledge proofs of isogeny diamonds, namely, we prove knowledge of isogenies that form a commutative diagram between four curves. We present four constructions that work in various settings. The first, Windmill-ZKP assumes that the prover knows only two parallel isogenies in the diamond. The second, Cube-ZKP assumes the prover has knowledge of four of specified degree isogenies. Finally, Kube-ZKP and Kani-ZKP prove knowledge of isogeny diamonds whose degree sum is smooth. We also provide proof-of-concept implementations of the proposed constructions and compare their performance. Our results demonstrate the trade-offs between security, efficiency and compactness in these constructions.