PDF《Cryptographic Agility》

Cryptographic Agility and its Relation to Circular Encryption Tolga Acar1 Mira Belenkiy2 Mihir Bellare3 David Cash4 Abstract We initiate a provable-security treatment of cryptographic agility.

A primitive (for example PRFs, authenticated encryption schemes or digital signatures) is agile when multiple, individually secure schemes can securely share the same key. We provide a surprising connection between two seemingly unrelated but challenging questions. The ?rst, new to this paper, is whether wPRFs (weak-PRFs) are agile. The second, already posed several times in the literature, is whether every secure (IND-R) encryption scheme is secure when encrypting cycles. We resolve the second question in the negative and thereby the ?rst as well. We go on to provide a comprehensive treatment of agility, with de?nitions for various di?erent primitives. We explain the practical motivations for agility. We provide foundational results that show to what extent it is achievable and practical constructions to achieve it to the best extent possible. On the theoretical side our work uncovers new notions and relations and settles stated open questions, and on the practical side it serves to guide developers. Keywords: Circular encryption.

1 eXtreme Computing Group, Microsoft Research, Microsoft, One Microsoft Way, Redmond, WA 98052, USA. Email: [email protected]. URL: http://research.microsoft.com/en-us/people/tolga.

2 eXtreme Computing Group, Microsoft Research, Microsoft, One Microsoft Way, Redmond, WA 98052, USA. Email: [email protected].

3 Department of Computer Science &

Engineering, University of California San Diego,

9500 Gilman Drive, La Jolla, California 92093, USA. Email: [email protected]. URL: http://cseweb.ucsd.edu/~mihir/.

4 Department of Computer Science &

Engineering, University of California San Diego,

9500 Gilman Drive, La Jolla, California 92093, USA. Email: [email protected]. URL: http://cseweb.ucsd.edu/~cdc/. Contents

1 Introduction

1 2 Preliminaries

5 3 Agility de?nitions

6 4 Negative results

8 4.1 Some simple non-agility results

8 4.2 Auxiliary de?nitions for encryption

9 4.3 Relating wPRF agility and encryption security

10 4.4 IND-R-but-not-IND-CYC encryption schemes

13 4.5 Non-agility of wPRFs

18 5 Positive results

18 5.1 Agile primitives

18 5.2 PRF-based agility for AE

18 5.3 wPRF-based agility for AE

21 A Proof of Lemma 4.5

23 i

1 Introduction This paper initiates a provable-security treatment of cryptographic agility. Agility considers a set of schemes, all meeting some base notion of security, and requires that security is maintained when mul- tiple schemes use the same key. Agility may be considered for any cryptographic primitive: PRFs, au- thenticated symmetric encryption, collision-resistant hashing, IND-CCA public-key encryption, what- ever. To illustrate let us jump right to the example where we have the most interesting results. Then we will back up and discuss motivation and other results. Are wPRFs agile? Let F be a family of functions and consider a game that picks a random key K and challenge bit b and gives the adversary an oracle Fn that takes no inputs. Each time it is called, Fn picks random x, y, returning (x, FK(x)) if b =

1 and (x, y) otherwise. Naor and Reingold [25] call F a weak-PRF (wPRF) if the adversary can'

t guess b. Why this notion? Being a wPRF is, in practice, a much weaker assumption on a blockcipher than the usual PRF or PRP one. Yet powerful results by Naor and Reingold [25], Maurer and Sj¨ odin [21] and Maurer and Tessaro [22] show that symmetric cryptography can be e?ciently and securely based on wPRFs. Letting F1, F2 be wPRFs having keys of the same length, consider a game that picks a single random key K and challenge bit b and gives the adversary an oracle Fn that, on input i ∈ {1, 2}, picks random x, y, returning (x, Fi K(x)) if b =