Computational Independence in the Design of Cryptographic Protocols

Statistical independence of instances of primitives and protocols is a clear-cut approach for guaranteeing protection against harmful interactions in concurrent and multi-execution environment. Therefore it is surprising that computational indistinguishability of independence from dependence between two or several random variables received no attention since the introduction of classic binary pseudorandom sequences. In this work we propose the use of the notion of computational independence (CI) in the analysis and design of provably secure cryptographic protocols. We generalize the classic result on equivalence of unpredictability and CI to general non-binary random variables. An application of this result is the use of unpredictability-based standard secure primitives in supporting the achievement of CI. This work is inherently related to Canetti’s universal composition framework [4], [5].