Paper 2017/288

Security of Symmetric Primitives under Incorrect Usage of Keys

Pooya Farshim, Claudio Orlandi, and Răzvan Roşie


We study the security of symmetric primitives under the incorrect usage of keys. Roughly speaking, a key-robust scheme does not output ciphertexts/tags that are valid with respect to distinct keys. Key-robustness is a notion that is often tacitly expected/assumed in protocol design — as is the case with anonymous auction, oblivious transfer, or public-key encryption. We formalize simple, yet strong definitions of key robustness for authenticated-encryption, message-authentication codes and PRFs. We show standard notions (such as AE or PRF security) guarantee a basic level of key-robustness under honestly generated keys, but fail to imply key-robustness under adversarially generated (or known) keys. We show robust encryption and MACs compose well through generic composition, and identify robust PRFs as the main primitive used in building robust schemes. Standard hash functions are expected to satisfy key-robustness and PRF security, and hence suffice for practical instantiations. We however provide further theoretical justifications (in the standard model) by constructing robust PRFs from (left-and-right) collision-resistant PRGs.

Available format(s)
Publication info
A minor revision of an IACR publication in FSE 2017
incorrect key usagekey-robustnessauthenticated encryptionMACgeneric compositioncollision-resistant PRFcollision-resistant PRG
Contact author(s)
razvan rosie @ ens fr
2017-04-03: received
Short URL
Creative Commons Attribution


      author = {Pooya Farshim and Claudio Orlandi and Răzvan Roşie},
      title = {Security of Symmetric Primitives under Incorrect Usage of Keys},
      howpublished = {Cryptology ePrint Archive, Paper 2017/288},
      year = {2017},
      doi = {10.13154/tosc.v2017.i1.449-473},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.