International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

The Polynomial Composition Problem in $(\mathbb{Z}/n\mathbb{Z})[X]$

Authors:
Marc Joye
David Naccache
St\'ephanie Porte
Download:
URL: http://eprint.iacr.org/2004/224
Search ePrint
Search Google
Abstract: Let $n$ be an RSA modulus and let $P,Q \in (\mathbb{Z}/n\mathbb{Z})[X]$. This paper explores the following problem: Given $Q$ and $Q(P)$, find~$P$. We shed light on the connections between the above problem to the RSA problem and derive from it new zero-knowledge protocols.
BibTeX
@misc{eprint-2004-12194,
  title={The Polynomial Composition Problem in $(\mathbb{Z}/n\mathbb{Z})[X]$},
  booktitle={IACR Eprint archive},
  keywords={foundations /},
  url={http://eprint.iacr.org/2004/224},
  note={ david.naccache@gemplus.com 12665 received 4 Sep 2004},
  author={Marc Joye and David Naccache and St\'ephanie Porte},
  year=2004
}