ON THE SCALED INVERSE OF (xi − xj) MODULO CYCLOTOMIC POLYNOMIAL OF THE FORM Φps (x) OR Φps qt(x)

Jung Hee Cheon, Dongwoo Kim, Duhyeong Kim, Keewoo Lee

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)621-634
Number of pages14
JournalJournal of the Korean Mathematical Society
Volume59
Issue number3
DOIs
StatePublished - May 2022

Keywords

  • Cyclotomic polynomial
  • scaled inverse
  • zero-knowledge proof

Fingerprint

Dive into the research topics of 'ON THE SCALED INVERSE OF (xi − xj) MODULO CYCLOTOMIC POLYNOMIAL OF THE FORM Φps (x) OR Φps qt(x)'. Together they form a unique fingerprint.

Cite this