Paper 2015/644
The Pythia PRF Service
Adam Everspaugh, Rahul Chatterjee, Samuel Scott, Ari Juels, and Thomas Ristenpart
Abstract
Conventional cryptographic services such as hardware-security modules and software-based key-management systems offer the ability to apply a pseudorandom function (PRF) such as HMAC to inputs of a client’s choosing. These services are used, for example, to harden stored password hashes against offline brute-force attacks. We propose a modern PRF service called PYTHIA designed to offer a level of flexibility, security, and ease- of-deployability lacking in prior approaches. The keystone of PYTHIA is a new cryptographic primitive called a verifiable partially-oblivious PRF that reveals a portion of an input message to the service but hides the rest. We give a construction that additionally supports efficient bulk rotation of previously obtained PRF values to new keys. Performance measurements show that our construction, which relies on bilinear pairings and zero-knowledge proofs, is highly practical. We also give accompanying formal definitions and proofs of security. We implement PYTHIA as a multi-tenant, scalable PRF service that can scale up to hundreds of millions of distinct client applications on commodity systems. In our prototype implementation, query latencies are 15 ms in local-area settings and throughput is within a factor of two of a standard HTTPS server. We further report on implementations of two applications using PYTHIA, showing how to bring its security benefits to a new enterprise password storage system and a new brainwallet system for Bitcoin.
Note: Minor typos corrected in proof.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Major revision. USENIX Security Symposium 2015
- Keywords
- partially oblivious pseudorandom functionverifiable pseudorandom function
- Contact author(s)
- ace @ cs wisc edu
- History
- 2015-09-17: last of 2 revisions
- 2015-07-01: received
- See all versions
- Short URL
- https://ia.cr/2015/644
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2015/644, author = {Adam Everspaugh and Rahul Chatterjee and Samuel Scott and Ari Juels and Thomas Ristenpart}, title = {The Pythia {PRF} Service}, howpublished = {Cryptology {ePrint} Archive, Paper 2015/644}, year = {2015}, url = {https://eprint.iacr.org/2015/644} }