We prove the equivalence between the Ring learning With errors (RLWE) and the polynomial learning with errors (PLWE) problems for the maximal totally real subfield of the 2r3s\documentclass[12pt]{minimal} \usepackage{...
详细信息
We prove the equivalence between the Ring learning With errors (RLWE) and the polynomial learning with errors (PLWE) problems for the maximal totally real subfield of the 2r3s\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2<^>r 3<^>s$$\end{document}th cyclotomic field for r >= 3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r \ge 3$$\end{document} and s >= 1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$s \ge 1$$\end{document}. Moreover, we describe a fast algorithm for computing the product of two elements in the ring of integers of these subfields. This multiplication algorithm has quasilinear complexity in the dimension of the field, as it makes use of the fast Discrete Cosine Transform (DCT). Our approach assumes that the two input polynomials are given in a basis of Chebyshev-like polynomials, in contrast to the customary power basis. To validate this assumption, we prove that the change of basis from the power basis to the Chebyshev-like basis can be computed with O(nlogn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {O}}(n \log n)$$\end{document} arithmetic operations, where n is the problem dimension. Finally, we provide a heuristic and theoretical comparison of the vulnerability to some attacks for the pth cyclotomic field versu
We discuss the advantages and limitations of cyclotomic fields to have fast polynomial arithmetic within homomorphic encryption, and show how these limitations can be overcome by replacing cyclotomic fields by a famil...
详细信息
We discuss the advantages and limitations of cyclotomic fields to have fast polynomial arithmetic within homomorphic encryption, and show how these limitations can be overcome by replacing cyclotomic fields by a family that we refer to as cyclo-multiquadratic. This family is of particular interest due to its arithmetic efficiency properties and to the fact that the polynomial learning with errors (PLWE) and Ring learning with errors (RLWE) problems are equivalent for it. Likewise, we provide exact expressions for the condition number for any cyclotomic field, but under what we call the twisted power basis. As a tool for our result, we obtain refined polynomial upper bounds for the condition number of cyclotomic fields with up to 6 different primes dividing the conductor. From a more practical side, we also show that for this family, swapping between NTT (Number Theoretic Transform) and coefficient representations can be achieved at least twice faster than for the usual cyclotomic family.
In this work we present HERatio, a homomorphic encryption scheme that builds on the scheme of Brakerski, and Fan and Vercauteren. Our scheme naturally accepts Laurent polynomials as inputs, allowing it to work with ra...
详细信息
ISBN:
(纸本)9789819750245;9789819750252
In this work we present HERatio, a homomorphic encryption scheme that builds on the scheme of Brakerski, and Fan and Vercauteren. Our scheme naturally accepts Laurent polynomials as inputs, allowing it to work with rationals via their bounded base-b expansions. This eliminates the need for a specialized encoder and streamlines encryption, while maintaining comparable efficiency to BFV. To achieve this, we introduce a new variant of the polynomial learning with errors (PLWE) problem which employs Laurent polynomials instead of the usual "classic" polynomials, and provide a reduction to the PLWE problem.
We study the equivalence between the ring learning with errors and polynomial learning with errors problems for cyclotomic number fields, namely: we prove that both problems are equivalent via a polynomial noise incre...
详细信息
We study the equivalence between the ring learning with errors and polynomial learning with errors problems for cyclotomic number fields, namely: we prove that both problems are equivalent via a polynomial noise increase as long as the number of distinct primes dividing the conductor is kept constant. We refine our bound in the case where the conductor is divisible by at most three primes and we give an asymptotic subexponential formula for the condition number of the attached Vandermonde matrix valid for arbitrary degree.
We propose and justify a generalized approach to prove the polynomial reduction of the RLWE to the PLWE problem attached to the ring of integers of a monogenic number field. We prove such equivalence in the case of th...
详细信息
We propose and justify a generalized approach to prove the polynomial reduction of the RLWE to the PLWE problem attached to the ring of integers of a monogenic number field. We prove such equivalence in the case of the maximal totally real subextension of the 4pth cyclotomic field, with p arbitrary prime.
In 2011, Chris Peikert and Brent Waters proposed the concept of lossy trapdoor functions, which is an inherent and powerful cryptographic concept. Lossy trapdoor functions can be used for simple black-box constructing...
详细信息
In 2011, Chris Peikert and Brent Waters proposed the concept of lossy trapdoor functions, which is an inherent and powerful cryptographic concept. Lossy trapdoor functions can be used for simple black-box constructing CCA encryption schemes, collision-resistent hash functions and oblivious transfer schemes. Chris Peikert and Brent Waters constructed lossy trapdoor functions based on decisional Diffie-Hellman assumption and learning with errors problem separately, which can be generalized to all-but-one trapdoor functions. In this paper, we generalize the lossy trapdoor functions and all-but-one trapdoor functions based on the polynomial ring separately, and we construct two types of trapdoor functions based on polynomial learning with errors assumption, which have more throughput and efficiency.
暂无评论