Shrinking the Keys of Discrete-Log-Type Lossy Trapdoor Functions

By Xavier Boyen and Brent Waters.

In Applied Cryptography ans Network Security (ACNS 2010), volume 6123 of Lecture Notes in Computer Science, pages 35-52. Springer, 2010.

Abstract

To this day, realizations in the standard-model of (lossy) trapdoor functions from discrete-log-type assumptions require large public key sizes, e.g., about $\Theta(\lambda^2)$ group elements for a reduction from the decisional Diffie-Hellman assumption (where $\lambda$ is a security parameter). We propose two realizations of lossy trapdoor functions that achieve public key size of only $\Theta(\lambda)$ group elements in bilinear groups, with a reduction from the decisional Bilinear Diffie-Hellman assumption.
Our first construction achieves this result at the expense of a long common reference string of $\Theta(\lambda^2)$ elements, albeit reusable in multiple LTDF instantiations. Our second scheme also achieves public keys of size $\Theta(\lambda)$, entirely in the standard model and in particular without any reference string, at the cost of a slightly more involved construction.
The main technical novelty, developed for the second scheme, is a compact encoding technique for generating compressed representations of certain sequences of group elements for the public parameters.

Material

- published paper (PS) (PDF) (also accessible from the publisher) ©
- presentation slides (HTML)

Reference

@InProceedings{Boyen+Waters:ACNS-2007:shrinking,
  author = {Xavier Boyen and Brent Waters},
  title = {Shrinking the Keys of Discrete-Log-Type Lossy Trapdoor Functions},
  booktitle = {Applied Cryptography ans Network Security---ACNS 2010},
  series = {Lecture Notes in Computer Science},
  volume = {6123},
  pages = {35--52},
  publisher = {Berlin: Springer-Verlag},
  year = {2010},
  note = {Available at \url{http://www.cs.stanford.edu/~xb/acns10/}}
}