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)
PDF
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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2015/644}},
      url = {https://eprint.iacr.org/2015/644}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.