Paper 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.
Note: Edited text of Propositions 5 and 6 to indicate that they necessarily hold only when the curve is given in Weierstrass form.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published by the IACR in ASIACRYPT 2014
- Keywords
- algebraic curvesbivariate polynomialscryptographic commitmentsMerkle trees
- Contact author(s)
- henrycg @ stanford edu
- History
- 2015-03-08: last of 2 revisions
- 2014-09-16: received
- See all versions
- Short URL
- https://ia.cr/2014/719
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2014/719,
author = {Dan Boneh and Henry Corrigan-Gibbs},
title = {Bivariate Polynomials Modulo Composites and their Applications},
howpublished = {Cryptology ePrint Archive, Paper 2014/719},
year = {2014},
note = {\url{https://eprint.iacr.org/2014/719}},
url = {https://eprint.iacr.org/2014/719}
}
