Cryptology ePrint Archive: Report 2004/224

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

Marc Joye and 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.

Category / Keywords: Polynomial composition, zero-knowledge protocols, Fiat- Shamir protocol, Guillou-Quisquater protocol, smart cards

Publication Info: To appear in CARDIS 2010

Date: received 4 Sep 2004, last revised 26 Jan 2010

Contact author: marc joye at thomson net

Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Note: Revised version

Version: 20100126:094943 (All versions of this report)

Discussion forum: Show discussion | Start new discussion