Paper 2019/204

The Security of All Private-key Bits in Isogeny-based Schemes

Barak Shani

Abstract

We study the computational hardness of recovering single bits of the private key in the supersingular isogeny Diffie--Hellman (SIDH) key exchange and similar schemes. Our objective is to give a polynomial-time reduction between the problem of computing the private key in SIDH to the problem of computing any of its bits. The parties in the SIDH protocol work over elliptic curve torsion groups of different order $N$. Our results depend on the parity of $N$. Our main result shows that if $N$ is odd, then each of the top and lower $O(\log\log N)$ bits of the private key is as hard to compute, with any noticeable advantage, as the entire key. A similar, but conditional, result holds for each of the middle bits. This condition can be checked, and heuristically holds almost always. The case of even $N$ is a bit more challenging. We give several results, one of which is similar to the result for an odd $N$, under the assumption that one always succeeds to recover the designated bit. To achieve these results we extend the solution to the chosen-multiplier hidden number problem, for domains of a prime-power order, by studying the Fourier coefficients of single-bit functions over these domains.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Discrete Applied Mathematics
Keywords
supersingular isogeny Diffie--Hellmanbit securityhardcore bits
Contact author(s)
baraksh @ seas upenn edu
History
2019-10-25: revised
2019-02-27: received
See all versions
Short URL
https://ia.cr/2019/204
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/204,
      author = {Barak Shani},
      title = {The Security of All Private-key Bits in Isogeny-based Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2019/204},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/204}},
      url = {https://eprint.iacr.org/2019/204}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.