Proving knowledge of isogenies, quaternions and signatures

Let E and E’ be two elliptic curves defined over a finite field with q elements. Verifying that E and E’ are isogenous can be done in time polynomial in log(q) using Schoof’s poing counting algorithm. Computing an isogeny between E and E’, though, may require exponential time in log(q), in general.

Our goal is to design (zero-knowledge) interactive proofs of isogeny knowledge (PoIK): polynomial-time two-party protocols where a prover tries to convince a verifier that he knows an isogeny φ : E → E’, without revealing (any) information on the isogeny itself. These are immensely useful tools, which can be used to construct digital signatures and much more. But designing efficient PoIKs has been an elusive goal for several years.

In this talk, I will review some variants of PoIK problem, and present recent progress and open problems.