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.Category / Keywords: cryptographic protocols / partially oblivious pseudorandom function, verifiable pseudorandom function Original Publication (with major differences): USENIX Security Symposium 2015 Date: received 29 Jun 2015, last revised 17 Sep 2015 Contact author: ace at cs wisc edu Available format(s): PDF | BibTeX Citation Note: Minor typos corrected in proof. Version: 20150917:183644 (All versions of this report) Short URL: ia.cr/2015/644 Discussion forum: Show discussion | Start new discussion