Paper 2019/1200

A note on short invertible ring elements and applications to cyclotomic and trinomials number fields

Thomas Attema, Ronald Cramer, and Chaoping Xing


Ring-SIS based $\Sigma$-protocols require the construction of a challenge set $\mathcal{C}$ in some ring $R$, usually an order in a number field $L$. These protocols impose various requirements on the subset $\mathcal{C}$, and constructing a good or even optimal challenge set is a non-trivial task that involves making various trade-offs. </p> In particular, the set $\mathcal{C}$ should be 'large', elements in $\mathcal{C}$ should be 'small', differences of distinct elements in $\mathcal{C}$ should be invertible modulo a rational prime $p$, this prime $p$ should be small, and finally primes $p$ that split in many factors are favorable. Clearly, these requirements on $\mathcal{C}$ require certain trade-offs. The splitting behavior and size of the prime $p$, for example, influence the invertibility condition. </p> Given an order $\mathcal{O}$ in an arbitrary number field $L$, this work aims at constructing subsets $\mathcal{C} \subset \mathcal{O}$ with precisely the above mentioned properties. Cyclotomic number fields possess some convenient properties and as a result most protocols are defined over these specific fields. However, recent attacks have shown that these convenient properties might also be of use to an attacker, thereby weakening or even breaking the cryptographic schemes. </p> In this paper, we show that a known result on constructing challenge sets in cyclotomic number fields (Lyubashevsky and Seiler 2018) follows from standard Galois theory, thereby simplifying the proof. In addition, this approach leads to a natural generalization from cyclotomic to arbitrary number fields. Along the way we prove a conjectured result on the practical applicability for cyclotomic number fields and prove the optimality of certain constructions. We apply the generalization to construct challenge sets in trinomial number fields of the form $\mathbb{Q}[X]/(f)$ with $f=X^n+aX^k+b \in \mathbb{Z}[X]$ irreducible. Finally, we find a new construction for challenge sets resulting in smaller prime sizes at the cost of slightly increasing the $\ell_2$-norm of the challenges.

Note: #

Available format(s)
Publication info
Preprint. Minor revision.
Latticezero-knowledge proofchallenge setinvertibilitytrinomialsnumber theory.
Contact author(s)
thomas attema @ tno nl
2021-03-14: revised
2019-10-15: received
See all versions
Short URL
Creative Commons Attribution


      author = {Thomas Attema and Ronald Cramer and Chaoping Xing},
      title = {A note on short invertible ring elements and applications to cyclotomic and trinomials number fields},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1200},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.