Cryptology ePrint Archive: Report 2014/719
Bivariate Polynomials Modulo Composites and their Applications
Dan Boneh and Henry Corrigan-Gibbs
Abstract: We investigate the hardness of finding solutions to bivariate polynomial congruences modulo RSA composites. We establish necessary conditions for a bivariate polynomial to be one-way, second preimage resistant, and collision resistant based on arithmetic properties of the polynomial. From these conditions we deduce a new computational assumption that implies an efficient algebraic collision-resistant hash function. We explore the assumption and relate it to known computational problems. The assumption leads to (i) a new statistically hiding commitment scheme that composes well with Pedersen commitments, (ii) a conceptually simple cryptographic accumulator, and (iii) an efficient chameleon hash function.
Category / Keywords: public-key cryptography / algebraic curves, bivariate polynomials, cryptographic commitments, Merkle trees
Original Publication (in the same form): IACR-ASIACRYPT-2014
Date: received 14 Sep 2014, last revised 8 Mar 2015
Contact author: henrycg at stanford edu
Available format(s): PDF | BibTeX Citation
Note: Edited text of Propositions 5 and 6 to indicate that they necessarily hold only when the curve is given in Weierstrass form.
Version: 20150308:225044 (All versions of this report)
Short URL: ia.cr/2014/719
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]