Paper 2009/249

Symbolic Encryption with Pseudorandom Keys

Daniele Micciancio

Abstract

We give an efficient decision procedure that, on input two (acyclic) cryptographic expressions making arbitrary use of an encryption scheme and a (length doubling) pseudorandom generator, determines (in polynomial time) if the two expressions produce computationally indistinguishable distributions for any pseudorandom generator and encryption scheme satisfying the standard security notions of pseudorandomness and indistinguishability under chosen plaintext attack. The procedure works by mapping each expression to a symbolic pattern that captures, in a fully abstract way, the information revealed by the expression to a computationally bounded observer. We then prove that if any two (possibly cyclic) expressions are mapped to the same pattern, then the associated distributions are indistinguishable. At the same time, if the expressions are mapped to different symbolic patterns and do not contain encryption cycles, there are secure pseudorandom generators and encryption schemes for which the two distributions can be distinguished with overwhelming advantage.

Note: This is a major extension and revision of the previous version of this report. All the completeness results in Section 5 are new. The soundness results in Section 4 are similar to the previous version, but we have substantially improved the presentation by providing a new, direct definition of the key recovery function.