Paper 2021/1013

Iterative Oblivious Pseudo-Random Functions and Applications

Erik-Oliver Blass, Florian Kerschbaum, and Travis Mayberry

Abstract

We consider the problem of a client querying an encrypted binary tree structure, outsourced to an untrusted server. While the server must not learn the contents of the binary tree, we also want to prevent the client from maliciously crafting a query that traverses the tree out-of-order. That is, the client should not be able to retrieve nodes outside one contiguous path from the root to a leaf. Finally, the server should not learn which path the client accesses, but is guaranteed that the access corresponds to one valid path in the tree. This is an extension of protocols such as structured encryption, where it is only guaranteed that the tree's encrypted data remains hidden from the server. To this end, we initiate the study of Iterative Oblivious Pseudorandom Functions (iOPRFs), new primitives providing two-sided, fully malicious security for these types of applications. We present a first, efficient iOPRF construction secure against both malicious clients and servers in the standard model, based on the DDH assumption. We demonstrate that iOPRFs are useful to implement different interesting applications, including an RFID authentication protocol and a protocol for private evaluation of outsourced decision trees. Finally, we implement and evaluate our full iOPRF construction and show that it is efficient in practice.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. Minor revision.
Keywords
one-way functionszero knowledgeoblivious transfermalicious security
Contact author(s)
mayberry @ usna edu
History
2022-02-22: revised
2021-08-06: received
See all versions
Short URL
https://ia.cr/2021/1013
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1013,
      author = {Erik-Oliver Blass and Florian Kerschbaum and Travis Mayberry},
      title = {Iterative Oblivious Pseudo-Random Functions and Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1013},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1013}},
      url = {https://eprint.iacr.org/2021/1013}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.