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
Abstract
RingSIS 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 nontrivial task that involves making various tradeoffs. </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 tradeoffs. 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: #
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint. Minor revision.
 Keywords
 Latticezeroknowledge proofchallenge setinvertibilitytrinomialsnumber theory.
 Contact author(s)
 thomas attema @ tno nl
 History
 20210314: revised
 20191015: received
 See all versions
 Short URL
 https://ia.cr/2019/1200
 License

CC BY
BibTeX
@misc{cryptoeprint:2019/1200, 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{https://eprint.iacr.org/2019/1200}}, url = {https://eprint.iacr.org/2019/1200} }