Paper 2020/1360

Incremental Cryptography Revisited: PRFs, Nonces and Modular Design

Vivek Arte, Mihir Bellare, and Louiza Khati


This paper gives the first definitions and constructions for incremental pseudo-random functions (IPRFs). The syntax is nonce based. (Algorithms are deterministic but may take as input a non-repeating quantity called a nonce.) The design approach is modular. First, given a scheme secure only in the single-document setting (there is just one document on which incremental updates are being performed) we show how to generically build a scheme that is secure in the more realistic multi-document setting (there are many documents, and they are simultaneously being incrementally updated). Then we give a general way to build an IPRF from (1) an incremental hash function with weak collision resistance properties and (2) a symmetric encryption scheme. (This adapts the classic Carter-Wegman paradigm used to build message authentication schemes in the non-incremental setting.) This leads to many particular IPRFs. Our work has both practical and theoretical motivation and value: Incremental PRFs bring the benefits of incrementality to new applications (such as incremental key derivation), and the movement from randomized or stateful schemes to nonce based ones, and from UF (unforgeability) to PRF security, bring incremental symmetric cryptography up to speed with the broader field of symmetric cryptography itself.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. MAJOR revision.Indocrypt 2020
incremental cryptographypseudorandom functionsnonces
Contact author(s)
varte @ eng ucsd edu
mihir @ eng ucsd edu
louiza khati @ ens fr
2020-11-02: revised
2020-10-29: received
See all versions
Short URL
Creative Commons Attribution


      author = {Vivek Arte and Mihir Bellare and Louiza Khati},
      title = {Incremental Cryptography Revisited: PRFs, Nonces and Modular Design},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1360},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.