Cryptology ePrint Archive: Report 2020/1360

Incremental Cryptography Revisited: PRFs, Nonces and Modular Design

Vivek Arte and Mihir Bellare and Louiza Khati

Abstract: 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.

Category / Keywords: secret-key cryptography / incremental cryptography, pseudorandom functions, nonces

Original Publication (with major differences): Indocrypt 2020

Date: received 28 Oct 2020, last revised 2 Nov 2020

Contact author: varte at eng ucsd edu,mihir@eng ucsd edu,louiza khati@ens fr

Available format(s): PDF | BibTeX Citation

Version: 20201102:170025 (All versions of this report)

Short URL: ia.cr/2020/1360


[ Cryptology ePrint archive ]