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.


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.


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


  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{}}

Unless indicated otherwise, these documents are Copyright © Xavier Boyen; all rights reserved in all countries.
Back to Xavier's homepage