Henry
Corrigan-
Gibbs

Bivariate Polynomials Modulo Composites and their Applications

Dan Boneh and Henry Corrigan-Gibbs

ASIACRYPT
December 7-11, 2014, Kaohsiung, Taiwan

Materials

• Paper: PDF (237 KB)
• IACR ePrint: 2014/719
• Slides: PDF (312 KB)

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.