Shrinking the Keys of Discrete-Log-Type Lossy Trapdoor FunctionsBy 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.

AbstractTo 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/}} }

Unless indicated otherwise, these documents are Copyright © Xavier Boyen; all rights reserved in all countries.

Back to Xavier's homepage