Paper 2009/249

Symbolic Encryption with Pseudorandom Keys

Daniele Micciancio


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.

Available format(s)
Publication info
Published elsewhere. Unknown status
symbolic securitycomputational soundnesscompletenesspseudo-randomnessinformation leakagegreatest fixed points
Contact author(s)
daniele @ cs ucsd edu
2018-02-23: revised
2009-05-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Daniele Micciancio},
      title = {Symbolic Encryption with Pseudorandom Keys},
      howpublished = {Cryptology ePrint Archive, Paper 2009/249},
      year = {2009},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.