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

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: #