Robust encryption is a property of an algorithm which ensures that an attempt to decrypt a message with the wrong (private) key fails with high probability. This property applies to both asymmetric and symmetric algorithms. It is of most importance in settings where multiple keys are present and an attacker has access or control over them.
The term “robust encryption” was coined in a 2010 paper, mostly with the goal of defining a new security notion in public-key encryption and identity-based encryption schemes. Schemes that have anonymity as a goal were of particular importance. In the words of the paper authors: “Where you need anonymity, there is a good chance you need robustness too.” Weak robustness represents a game where an adversary can find a message M which, when encrypted with some public key pk0, can be validly decrypted using the secret key sk1 of another public key pk1. Strong robustness represents a game where the adversary has access to a decryption oracle and can identify a ciphertext C which decrypts validly under two distinct public keys.
Encryption-with-redundancy, though seemingly a natural solution, is shown to be insufficient to qualify. A scheme proposed to fulfill the weak robustness guarantee is for a (separate) key to be appended to the encrypted message and checked by the receiving entity as a verification. For strong robustness, a transform is introduced to construct robust encryption from an existing encryption scheme. It uses commitments generated from the encryption key - somewhat like a MAC, but for the key.
The schemes proposed by that initial paper in support of robust PKE were shown to be still insufficient, under some assumptions, in a 2013 paper.
TODO: Continue digging into this
For symmetric primitives
A first look at robustness in the context of symmetric crypto can be seen here, where an analysis of the notion is done, along with proofs that “the AE schemes obtained through either Encrypt-then-Mac (EtM), Encrypt-and-MAC (EaM), or AC-then-Encrypt (MtE) (with independent keys) are CROB (Complete ROBustness) secure as long as their encryption and MAC components are CROB secure”. A new scheme, similar to that mentioned above for key commitment, is proposed, whereby encryption and tag generation are performed using keys derived from the same base key.
A similar concept/requirement can be seen in message franking - a mechanism designed to allow users to report abusive content in the context of E2EE messaging - where committing authenticated encryption is required. This topic was introduced and first discussed in this paper. An attack to Facebook’s scheme is given here, along with the definition of another compactly committing AEAD (ccAEAD) called encryptment. Encryptment aims to handle both the encryption and commitment with a smaller performance overhead on top of simple AEAD. One such scheme is proposed, using Merkle-Damgard hashes.
Another paper looks at other places where lack of commitments could lead to vulnerabilities (e.g. key rotation in AWS KMS, as you can end up with multiple versions of the same key with no clear way of determining which one was used) and offers alternative solutions for implementing it that cut down even more on performance overhead.
A generic, abstract notation for key-committing in AEADs can be seen here. It essentially describes an extra dimension to the encryption process where the encryption key (K_e) is derived from a “root” key K using a PRF. Another value called Key Committing String (K_c) is also derived from the same root key K. The derivation uses different labels for the two keys, and can be randomized by including a nonce. K_c is a public value, sent along with the ciphertext, authentication tag, and nonce, and its purpose is to confirm that the correct root key K was used. The non-randomized version of key committing can be used when there is no privacy risk from advertising that the same root key K was used for multiple encryptions/payloads. Otherwise, randomizing K_c helps prevent this issue.