Welcome to the resource topic for 2019/1200
Title:
A note on short invertible ring elements and applications to cyclotomic and trinomials number fields
Authors: Thomas Attema, Ronald Cramer, 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.
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. 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. 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.ePrint: https://eprint.iacr.org/2019/1200
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .