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:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]