Cryptology ePrint Archive: Report 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.
Category / Keywords: Foundations / symbolic security, computational soundness, completeness, pseudo-randomness, information leakage, greatest fixed points
Date: received 29 May 2009, last revised 23 Feb 2018
Contact author: daniele at cs ucsd edu
Available format(s): PDF | BibTeX Citation
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.
Version: 20180223:160820 (All versions of this report)
Short URL: ia.cr/2009/249
[ Cryptology ePrint archive ]