Paper 2021/984

On the Use of the Legendre Symbol in Symmetric Cipher Design

Alan Szepieniec


This paper proposes the use of Legendre symbols as component gates in the design of ciphers tailored for use in cryptographic proof systems. Legendre symbols correspond to high-degree maps, but can be evaluated much faster. As a result, a cipher that uses Legendre symbols can offer the same security as one that uses high-degree maps but without incurring the penalty of a comparatively slow evaluation time. After discussing the design considerations induced by the use of Legendre symbol gates, we present a concrete design that follows this strategy, along with an elaborate security analysis thereof. This cipher is called Grendel.

Note: add root finding attack to security analysis

Available format(s)
Secret-key cryptography
Publication info
Preprint. MINOR revision.
arithmetization-orientedhash functionszero knowledge
Contact author(s)
alan szepieniec @ gmail com
2021-11-29: revised
2021-07-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Alan Szepieniec},
      title = {On the Use of the Legendre Symbol in Symmetric Cipher Design},
      howpublished = {Cryptology ePrint Archive, Paper 2021/984},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.