On the scaled inverse of (x^i-x^j) modulo cyclotomic polynomial of the form _p^s(x) or _p^s q^t(x)

DOI10.4134/JKMS.J210446MaRDI QIDQ5074074zbMATH OpenFDO

Authors Jung Hee Cheon, Du Hyeong Kim, Keewoo Lee, Dongwoo Kim

Publication date 6 May 2022

Full work available at URL https://arxiv.org/abs/2106.01742

zbMATH Keywords

cyclotomic polynomialscaled inversezero-knowledge proof

Mathematics Subject Classification ID

Polynomials in number theory (11C08) Cryptography (94A60)

Abstract: The scaled inverse of a nonzero element $a(x)inmathbbZ[x]/f(x)$, where $f(x)$ is an irreducible polynomial over $mathbbZ$, is the element $b(x)inmathbbZ[x]/f(x)$ such that $a(x)b(x)=cpmodf(x)$ for the smallest possible positive integer scale $c$. In this paper, we investigate the scaled inverse of $(x^i-x^j)$ modulo cyclotomic polynomial of the form $Ph{i}_{p^s}(x)$ or $Ph{i}_{p^s{q}^t}(x)$, where $p,q$ are primes with $p<q$ and $s,t$ are positive integers. Our main results are that the coefficient size of the scaled inverse of $(x^i-x^j)$ is bounded by $p-1$ with the scale $p$ modulo $Ph{i}_{p^s}(x)$, and is bounded by $q-1$ with the scale not greater than $q$ modulo $Ph{i}_{p^s{q}^t}(x)$. Previously, the analogous result on cyclotomic polynomials of the form $Ph{i}_{2^n}(x)$ gave rise to many lattice-based cryptosystems, especially, zero-knowledge proofs. Our result provides more flexible choice of cyclotomic polynomials in such cryptosystems. Along the way of proving the theorems, we also prove several properties of ${x^k}_{kinmathbbZ}$ in $mathbbZ[x]/Ph{i}_{pq}(x)$ which might be of independent interest.

Recommendations

• On modular inverses of cyclotomic polynomials and the magnitude of their coefficients
• Short, invertible elements in partially splitting cyclotomic rings and applications to lattice-based zero-knowledge proofs
• A note about the cyclotomic polynomial \(\Phi_{pq}(x)\) and some related results
• A note on inverses of cyclotomic mapping permutation polynomials over finite fields
• On the Cyclotomic Polynomial $Phi\{pq} (X)$

Cites work

• A toolkit for ring-LWE cryptography
• Better zero-knowledge proofs for lattice encryption and their application to group signatures
• Maliciously secure matrix multiplication with applications to private deep learning
• Maximum gap in (inverse) cyclotomic polynomial
• Mhz2K: MPC from HE over \(\mathbb{Z}_{2^k}\) with new packing, simpler reshare, and better ZKP
• On binary cyclotomic polynomials
• On ideal lattices and learning with errors over rings
• The Midterm Coefficient of the Cyclotomic Polynomial F pq (x)
• Using TopGear in overdrive: a more efficient ZKPoK for SPDZ

Cited in

(2)

• Short, invertible elements in partially splitting cyclotomic rings and applications to lattice-based zero-knowledge proofs
• On modular inverses of cyclotomic polynomials and the magnitude of their coefficients

Describes a project that uses

Uses Software

• ring-LWE

This page was built for publication: On the scaled inverse of \((x^i-x^j)\) modulo cyclotomic polynomial of the form \(\Phi_{p^s}(x)\) or \(\Phi_{p^s q^t}(x)\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5074074)