Date Added: Mar 2010
The authors 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. They 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. They resolve the second question in the negative and thereby the first as well. They go on to provide a comprehensive treatment of agility, with definitions for various different primitives.