Paper 2014/719 Original: eprint.iacr.org/2014/719 ↗
Bivariate Polynomials Modulo Composites and their Applications
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.
Metadata
- Available format(s)
PDF- Category
- Public-key cryptography
- Publication info
- Preprint.
- History
- 2015-03-08: last updated
- 2014-09-16: published
- Short URL
- https://ia.cr/2014/719
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2014/719}
}