Cryptology ePrint Archive: Report 2009/249

Pseudo-randomness and partial information in symbolic security analysis

Daniele Micciancio

Abstract: We prove computational soundness results for cryptographic expressions with pseudo-random keys, as used, for example, in the design and analysis of secure multicast key distribution protocols. In particular, we establish a symbolic notion of independence (for pseudo-random keys) that exactly matches the standard computational security definition (namely, indistinguishability from the uniform distribution) for pseudo-random generators. As a conceptual contribution, we initiate the study of partial information in the context of computationally sound symbolic security analysis. Specifically, we show that (within our admittedly simple, but hopefully evocative setting) partial information can be taken into account in the symbolic model, in a computationally sound way, by simply annotating each key with a label which specifies that the key is either known, unknown, or partially known, without further details about the amount and type of partial information.

Category / Keywords: foundations / Computational soundness, formal methods for security, pseudo-random generators, partial information, greatest fix-points

Date: received 29 May 2009

Contact author: daniele at cs ucsd edu

Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20090530:160722 (All versions of this report)

Discussion forum: Show discussion | Start new discussion