You are looking at a specific version 20201102:170025 of this paper. See the latest version.

Paper 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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Major revision. Indocrypt 2020
Keywords
incremental cryptographypseudorandom functionsnonces
Contact author(s)
varte @ eng ucsd edu,mihir @ eng ucsd edu,louiza khati @ ens fr
History
2020-11-02: revised
2020-10-29: received
See all versions
Short URL
https://ia.cr/2020/1360
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.