×

The polynomial composition problem in \((\mathbb Z/n\mathbb Z)[X]\). (English) Zbl 1300.94066

Gollmann, Dieter (ed.) et al., Smart card research and advanced application. 9th IFIP WG 8.8/11.2 international conference, CARDIS 2010, Passau, Germany, April 14–16, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-12509-6/pbk). Lecture Notes in Computer Science 6035, 1-12 (2010).
Summary: Let \(n\) be an RSA modulus and let \(\mathcal{P},\,\mathcal{Q} \in (\mathbb{Z}/n\mathbb{Z})[X]\). This paper explores the following problem: Given polynomials \(\mathcal{Q}\) and \(\mathcal{Q}(\mathcal{P})\), find polynomial \(\mathcal{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.
For the entire collection see [Zbl 05692199].

MSC:

94A60 Cryptography
68P25 Data encryption (aspects in computer science)
Full Text: DOI