J. Korean Math. Soc. 2022; 59(3): 621-634
Online first article May 1, 2022 Printed May 1, 2022
https://doi.org/10.4134/JKMS.j210446
Copyright © The Korean Mathematical Society.
Jung Hee Cheon, Dongwoo Kim, Duhyeong Kim, Keewoo Lee
Seoul National University; Western Digital Research; Intel Labs; Seoul National University
The scaled inverse of a nonzero element $a(x)\in \mathbb{Z}[x]/f(x)$, where $f(x)$ is an irreducible polynomial over $\mathbb{Z}$, is the element $b(x)\in \mathbb{Z}[x]/f(x)$ such that $a(x)b(x)=c \pmod{f(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 $\Phi_{p^s}(x)$ or $\Phi_{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 $\Phi_{p^s}(x)$, and is bounded by $q-1$ with the scale not greater than $q$ modulo $\Phi_{p^s q^t}(x)$. Previously, the analogous result on cyclotomic polynomials of the form $\Phi_{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\}_{k\in\mathbb{Z}}$ in $\mathbb{Z}[x]/\Phi_{pq}(x)$ which might be of independent interest.
Keywords: Cyclotomic polynomial, scaled inverse, zero-knowledge proof
MSC numbers: Primary 11C08, 94A60
Supported by: This work was supported by Samsung Electronics Co., Ltd(IO201209-07883-01). This work was done while Duhyeong Kim and Dongwoo Kim were at Seoul National University.
© 2022. The Korean Mathematical Society. Powered by INFOrang Co., Ltd