Authors: Pooya Farshim, Louiza Khati, Yannick Seurin and Damien Vergnaud
Abstract: Key-Alternating Feistel (KAF) ciphers are a popular variant
of Feistel ciphers whereby the round functions are defined as x 7→ F(k i ⊕x),
where k i are the round keys and F is a public random function. Most
Feistel ciphers, such as DES, indeed have such a structure. However,
the security of this construction has only been studied in the classical
CPA/CCA models. We provide the first security analysis of KAF ciphers
in the key-dependent message (KDM) attack model, where plaintexts can
be related to the private key. This model is motivated by cryptographic
schemes used within application scenarios such as full-disk encryption or
anonymous credential systems.
We show that the four-round KAF cipher, with a single function F
reused across the rounds, provides KDM security for a non-trivial set of
KDM functions. To do so, we develop a generic proof methodology, based
on the H-coefficient technique, that can ease the analysis of other block
ciphers in such strong models of security.
Authors: Vivek Arte, Mihir Bellare, Louiza Khati
Abstract: This paper gives the first definitions and constructions for incremental pseudo-randomfunctions (IPRFs). The syntax is nonce based. (Algorithms are deterministic but may takeas 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 whichincremental 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) asymmetric 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 withthe broader field of symmetric cryptography itself.
Email: firstname.lastname@ens.fr
Linkedin Follow @LokLkt