TY - JOUR
T1 - ON THE SCALED INVERSE OF (xi − xj) MODULO CYCLOTOMIC POLYNOMIAL OF THE FORM Φps (x) OR Φps qt(x)
AU - Cheon, Jung Hee
AU - Kim, Dongwoo
AU - Kim, Duhyeong
AU - Lee, Keewoo
N1 - Publisher Copyright:
© 2022 Korean Mathematical Society.
PY - 2022/5
Y1 - 2022/5
N2 - The scaled inverse of a nonzero element a(x) ∈ Z[x]/f(x), where f(x) is an irreducible polynomial over Z, is the element b(x) ∈ Z[x]/f(x) such that a(x)b(x) = c (mod f(x)) for the smallest possible positive integer scale c. In this paper, we investigate the scaled inverse of (xi − xj) modulo cyclotomic polynomial of the form Φps (x) or Φps qt(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 (xi − xj) is bounded by p − 1 with the scale p modulo Φps (x), and is bounded by q − 1 with the scale not greater than q modulo Φps qt (x). Previously, the analogous result on cyclotomic polynomials of the form Φ2n (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 {xk }k∈Z in Z[x]/Φpq(x) which might be of independent interest.
AB - The scaled inverse of a nonzero element a(x) ∈ Z[x]/f(x), where f(x) is an irreducible polynomial over Z, is the element b(x) ∈ Z[x]/f(x) such that a(x)b(x) = c (mod f(x)) for the smallest possible positive integer scale c. In this paper, we investigate the scaled inverse of (xi − xj) modulo cyclotomic polynomial of the form Φps (x) or Φps qt(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 (xi − xj) is bounded by p − 1 with the scale p modulo Φps (x), and is bounded by q − 1 with the scale not greater than q modulo Φps qt (x). Previously, the analogous result on cyclotomic polynomials of the form Φ2n (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 {xk }k∈Z in Z[x]/Φpq(x) which might be of independent interest.
KW - Cyclotomic polynomial
KW - scaled inverse
KW - zero-knowledge proof
UR - http://www.scopus.com/inward/record.url?scp=85129724669&partnerID=8YFLogxK
U2 - 10.4134/JKMS.j210446
DO - 10.4134/JKMS.j210446
M3 - Article
AN - SCOPUS:85129724669
SN - 0304-9914
VL - 59
SP - 621
EP - 634
JO - Journal of the Korean Mathematical Society
JF - Journal of the Korean Mathematical Society
IS - 3
ER -