Indistinguishability of Random Systems

详细信息

下载全文

推荐本文 |

• 作者：Ueli Maurer
• 关键词：Indistinguishability ; random systems ; pseudo ; random functions ; pseudo ; random permutations ; quasi ; randomness ; CBC ; MAC
• 刊名：Lecture Notes in Computer Science
• 出版时间：2002
• 出版年：2002
• 期刊代码：99_0302-9743
• 类别：cp
• 卷：2332
• 期：1
• 页码：110-132
• 数据来源：sp

摘要

An (χY)-random system takes inputs X ₁ X ₂,... ∈ χ and generates, for each new input X _i , an output Y _i ∈ Y, depending probabilistically on X ₁,..., X _i and Y ₁,..., Y _i-1. Many cryptographic systems like block ciphers, MAC-schemes, pseudo-random functions, etc., can be modeled as random systems, where in fact Y _i often depends only on X _i, i.e., the system is stateless. The security proof of such a system (e.g. a block cipher) amounts to showing that it is indistinguishable from a certain perfect system (e.g. a random permutation). We propose a general framework for proving the indistinguishability of two random systems, based on the concept of the equivalence of two systems, conditioned on certain events. This abstraction demonstrates the common denominator among many security proofs in the literature, allows to unify, simplify, generalize, and in some cases strengthen them, and opens the door to proving new indistinguishability results.