Paper 2017/012

Universal Samplers with Fast Verification

Venkata Koppula, Andrew Poelstra, and Brent Waters

Abstract

Recently, Hofheinz, Jager, Khurana, Sahai, Waters and Zhandry proposed a new primitive called universal samplers that allows oblivious sampling from arbitrary distributions, and showed how to construct universal samplers using indistinguishability obfuscation (iO) in the ROM. One important limitation for applying universal samplers in practice is that the constructions are built upon indistinguishability obfuscation. The costs of using current iO constructions is prohibitively large. We ask is whether the cost of a (universal) sampling could be paid by one party and then shared (soundly) with all other users? We address this question by introducing the notion of universal samplers with verification. Our notion follows the general path of Hofheinz et al, but has additional semantics that allows for validation of a sample. In this work we define and give a construction for universal samplers with verification. Our verification procedure is simple and built upon one-time signatures, making verification of a sample much faster than computing it. Security is proved under the sub exponential hardness of indistinguishability obfuscation, puncturable pseudorandom functions, and one-time signatures.

Note: Full version

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in PKC 2017
Contact author(s)
kvenkata @ cs utexas edu
History
2017-01-11: revised
2017-01-11: received
See all versions
Short URL
https://ia.cr/2017/012
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/012,
      author = {Venkata Koppula and Andrew Poelstra and Brent Waters},
      title = {Universal Samplers with Fast Verification},
      howpublished = {Cryptology ePrint Archive, Paper 2017/012},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/012}},
      url = {https://eprint.iacr.org/2017/012}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.