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 compositionzero-knowledge protocolsFiat- Shamir protocolGuillou-Quisquater protocolsmart 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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.