Paper 2021/1533

The Legendre Symbol and the Modulo-2 Operator in Symmetric Schemes over (F_p)^n

Lorenzo Grassi, Dmitry Khovratovich, Sondre Rønjom, and Markus Schofnegger

Abstract

Motivated by modern cryptographic use cases such as multi-party computation (MPC), homomorphic encryption (HE), and zero-knowledge (ZK) protocols, several symmetric schemes that are efficient in these scenarios have recently been proposed in the literature. Some of these schemes are instantiated with low-degree nonlinear functions, for example low-degree power maps (e.g., MiMC, HadesMiMC, Poseidon) or the Toffoli gate (e.g., Ciminion). Others (e.g., Rescue, Vision, Grendel) are instead instantiated via high-degree functions which are easy to evaluate in the target application. A recent example for the latter case is the hash function Grendel, whose nonlinear layer is constructed using the Legendre symbol. In this paper, we analyze high-degree functions such as the Legendre symbol or the modulo-2 operation as building blocks for the nonlinear layer of a cryptographic scheme over (F_p)^n. Our focus regards the security analysis rather than the efficiency in the mentioned use cases. For this purpose, we present several new invertible functions that make use of the Legendre symbol or of the modulo-2 operation. Even though these functions often provide strong statistical properties and ensure a high degree after a few rounds, the main problem regards their small number of possible outputs, that is, only three for the Legendre symbol and only two for the modulo-2 operation. By fixing them, it is possible to reduce the overall degree of the function significantly. We exploit this behavior by describing the first preimage attack on full Grendel, and we verify it in practice.

Note: Updated proofs and attack details

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published by the IACR in Fse 2022
Keywords
Legendre SymbolModulo-2 OperatorGrendelPreimage Attack
Contact author(s)
L Grassi @ cs ru nl
khovratovich @ gmail com
Sondre Ronjom @ uib no
markus schofnegger @ tugraz at
History
2022-02-17: revised
2021-11-22: received
See all versions
Short URL
https://ia.cr/2021/1533
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1533,
      author = {Lorenzo Grassi and Dmitry Khovratovich and Sondre Rønjom and Markus Schofnegger},
      title = {The Legendre Symbol and the Modulo-2 Operator in Symmetric Schemes over (F_p)^n},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1533},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1533}},
      url = {https://eprint.iacr.org/2021/1533}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.