**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 format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Note: **Revised version

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

**Short URL: **ia.cr/2004/224

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]