The Polynomial Composition Problem in (Z/nZ)[X]

Marc Joye; David Naccache; Stephanie Porte

Paper 2004/224

The Polynomial Composition Problem in (Z/nZ)[X]

Marc Joye, David Naccache, and Stephanie Porte

Abstract

Let n be an RSA modulus and let P,Q in (Z/nZ)[X]. This paper explores the following problem: Given polynomials Q and Q(P), find polynomial P. We shed light on the connections between the above problem and the RSA problem and derive from it new zero-knowledge protocols suited to smart-card applications.

Note: Revised version

Metadata

Available format(s): PDF PS
Publication info: Published elsewhere. To appear in CARDIS 2010
Keywords: Polynomial composition zero-knowledge protocols Fiat- Shamir protocol Guillou-Quisquater protocol smart cards
Contact author(s): marc joye @ thomson net
History: 2010-01-26: revised; 2004-09-05: received; See all versions
Short URL: https://ia.cr/2004/224
License: CC BY

BibTeX

@misc{cryptoeprint:2004/224,
      author = {Marc Joye and David Naccache and Stephanie Porte},
      title = {The Polynomial Composition Problem in (Z/{nZ})[X]},
      howpublished = {Cryptology {ePrint} Archive, Paper 2004/224},
      year = {2004},
      url = {https://eprint.iacr.org/2004/224}
}