Bivariate Polynomials Modulo Composites and Their Applications
Authors: D. Boneh and H. 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.
Reference:
In proceedings of Asiacrypt 2014, LNCS 8873, pp. 42-62
Full paper: pdf