Paper 2021/645
Legendre PRF (Multiple) Key Attacks and the Power of Preprocessing
Alexander May and Floyd Zweydinger
Abstract
Due to its amazing speed and multiplicative properties the Legendre PRF recently finds widespread applications e.g. in Ethereum 2.0, multiparty computation and in the quantumsecure signature proposal LegRoast. However, its security is not yet extensively studied. The Legendre PRF computes for a key $k$ on input $x$ the Legendre symbol $L_k(x) = \left( \frac {x+k} {p} \right)$ in some finite field $\F_p$. As standard notion, PRF security is analysed by giving an attacker oracle access to $L_k(\cdot)$. Khovratovich's collisionbased algorithm recovers $k$ using $L_k(\cdot)$ in time $\sqrt{p}$ with constant memory. It is a major open problem whether this birthdaybound complexity can be beaten. We show a somewhat surprising wideranging analogy between the discrete logarithm problem and Legendre symbol computations. This analogy allows us to adapt various algorithmic ideas from the discrete logarithm setting. More precisely, we present a small memory multiplekey attack on $m$ Legendre keys $k_1, \ldots, k_m$ in time $\sqrt{mp}$, i.e. with amortized cost $\sqrt{p/m}$ per key. This multiplekey attack might be of interest in the Ethereum context, since recovering many keys simultaneously maximizes an attacker's profit. Moreover, we show that the Legendre PRF admits precomputation attacks, where the precomputation depends on the public $p$ only  and not on a key $k$. Namely, an attacker may compute e.g. in precomputation time $p^{\frac 2 3}$ a hint of size $p^{\frac 1 3}$. On receiving access to $L_k(\cdot)$ in an online phase, the attacker then uses the hint to recover the desired key $k$ in time only $p^{\frac 1 3}$. Thus, the attacker's online complexity again beats the birthdaybound. In addition, our precomputation attack can also be combined with our multiplekey attack. We explicitly give various tradeoffs between precomputation and online phase. E.g. for attacking $m$ keys one may spend time $mp^{\frac 2 3}$ in the precomputation phase for constructing a hint of size $m^2 p^{\frac 1 3}$. In an online phase, one then finds {\em all $m$ keys in total time} only $p^{\frac 1 3}$. Precomputation attacks might again be interesting in the Ethereum 2.0 context, where keys are frequently changed such that a heavy keyindependent precomputation pays off.
Note: final version
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Preprint. MINOR revision.
 Keywords
 PreprocessingLegendre PRFEthereum 2.0
 Contact author(s)

alex may @ rub de
floyd zweydinger @ rub de  History
 20210917: last of 2 revisions
 20210520: received
 See all versions
 Short URL
 https://ia.cr/2021/645
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/645, author = {Alexander May and Floyd Zweydinger}, title = {Legendre PRF (Multiple) Key Attacks and the Power of Preprocessing}, howpublished = {Cryptology ePrint Archive, Paper 2021/645}, year = {2021}, note = {\url{https://eprint.iacr.org/2021/645}}, url = {https://eprint.iacr.org/2021/645} }