20210612
A note on short invertible ring elements and applications to cyclotomic and trinomials number fields
Publication
Publication
Mathematical Cryptology , Volume 1  Issue 1 p. 45 70
RingSIS based $\Sigma$protocols require a challenge set $\mathcal{C}$ in some ring $R$, usually an order in a number field $L$. These $\Sigma$protocols impose various requirements on the subset $\mathcal{C}$, and finding a good, or even optimal, challenge set is a nontrivial task that involves making various tradeoffs. RingSIS based $\Sigma$protocols require a challenge set $\mathcal{C}$ in some ring $R$, usually an order in a number field $L$. These $\Sigma$protocols impose various requirements on the subset $\mathcal{C}$, and finding a good, or even optimal, challenge set is a nontrivial task that involves making various tradeoffs. In particular, (1) the set $\mathcal{C}$ should be `large', (2) elements in $\mathcal{C}$ should be `small', and (3) differences of distinct elements in $\mathcal{C}$ should be invertible modulo a rational prime $p$. Moreover, for efficiency purposes, it is desirable that (4) the prime $p$ is small, and that (5) it splits in many factors in the number field $L$. These requirements on $\mathcal{C}$ are subject to certain tradeoffs, e.g., between the splitting behavior of the prime $p$ and its size. Lyubashevsky and Seiler (Eurocrypt 2018) have studied these tradeoffs for subrings of cyclotomic number fields. Cyclotomic number fields possess convenient properties and as a result most RingSIS based protocols are defined over these specific fields. However, recent attacks have shown that, in certain protocols, these convenient properties can be exploited by adversaries, thereby weakening or even breaking the cryptographic protocols. In this work, we revisit the results of Lyubashevsky and Seiler and show that they follow from standard Galois theory, thereby simplifying their proofs. Subsequently, this approach leads to a natural generalization from cyclotomic to arbitrary number fields. We apply the generalized results 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. Along the way we prove a conjectured result on the practical applicability for cyclotomic number fields and prove the optimality of certain constructions. 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.
Additional Metadata  

, , , , ,  
Mathematical Cryptology  
Organisation  Cryptology 
Attema, T, Cramer, R.J.F, & Xing, C. (2021). A note on short invertible ring elements and applications to cyclotomic and trinomials number fields. Mathematical Cryptology, 1(1), 45–70.
