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

Marc Joye; David Naccache; Stephanie Porte

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

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},
      note = {\url{https://eprint.iacr.org/2004/224}},
      url = {https://eprint.iacr.org/2004/224}
}