Paper 2021/1013

Iterative Oblivious Pseudo-Random Functions and Applications

Erik-Oliver Blass, Florian Kerschbaum, and Travis Mayberry


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.

Available format(s)
Cryptographic protocols
Publication info
Preprint. Minor revision.
one-way functionszero knowledgeoblivious transfermalicious security
Contact author(s)
mayberry @ usna edu
2022-02-22: revised
2021-08-06: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.