Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Cryptographic Agility and its Relation to Circular Encryption

Tolga Acar, Mira Belenkiy, Mihir Bellare, and David Cash


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 first, 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 first as well. We go on to provide a comprehensive treatment of agility, with definitions for various different 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.


Publication typeInproceedings
Published inEUROCRYPT 2010
PublisherSpringer Verlag

Newer versions

Tolga Acar, Cedric Fournet, and Dan Shumow. Cryptographically Verified Design and Implementation of a Distributed Key Manager, Microsoft Technical Report, 15 April 2014.

Tolga Acar and Lan Nguyen. High Assurance Policy-Based Key Management at Low Cost, Microsoft Research Technical Report, April 2014.

Tolga Acar, Mira Belenkiy, Lan Nguyen, and Carl Ellison. Key Management In Distributed Systems, Microsoft Research, 17 June 2010.

> Publications > Cryptographic Agility and its Relation to Circular Encryption