Clever Arbiters Versus Malicious Adversaries

When moving from known-input security to chosen-input security, some generic attacks sometimes become possible and must be discarded by a specific set of rules in the threat model. Similarly, common practices consist of fixing security systems, once an exploit is discovered, by adding a specific rule to thwart it. To study feasibility, we investigate a new security notion: security against undetectable attacks. I.e., attacks which cannot be ruled out by any specific rule based on the observable behavior of the adversary. In this model, chosen-input attacks must specify inputs which are indistinguishable from the ones in known-input attacks. Otherwise, they could be ruled out, in theory. Although non-falsifiable, this notion provides interesting results: for any primitives based on symmetric encryption, message authentication code (MAC), or pseudorandom function (PRF), known-input security is equivalent to this restricted chosen-input security in Minicrypt. Otherwise, any separation implies the construction of a public-key cryptosystem (PKC): for a known-input-secure primitive, any undetectable chosen-input attack transforms the primitive into a PKC. In this paper, we develop the notion of security based on open rules. We show the above results. We revisit the notion of related-key security of block ciphers to illustrate these results. Interestingly, when the relation among the keys is specified as a black box, no chosen-relation security is feasible. By translating this result to non-black box relations, either no known-input security is feasible, or we can recognize any obfuscated relation by a fixed set of rules, or we can build a PKC. Any of these three results is quite interesting in itself.