International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Symbolic Encryption with Pseudorandom Keys

Daniele Micciancio
DOI: 10.1007/978-3-030-17659-4_3 (login may be required)
Search ePrint
Search Google
Abstract: We give an efficient decision procedure that, on input two (acyclic) expressions making arbitrary use of common cryptographic primitives (namely, encryption and pseudorandom generators), determines (in polynomial time) if the two expressions produce computationally indistinguishable distributions for any cryptographic instantiation 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. Our main result shows that if two expressions are mapped to different symbolic patterns, then there are secure pseudorandom generators and encryption schemes for which the two distributions can be distinguished with overwhelming advantage. At the same time if any two (acyclic) expressions are mapped to the same pattern, then the associated distributions are indistinguishable.
Video from EUROCRYPT 2019
  title={Symbolic Encryption with Pseudorandom Keys},
  booktitle={Advances in Cryptology – EUROCRYPT 2019},
  series={Advances in Cryptology – EUROCRYPT 2019},
  author={Daniele Micciancio},