跳转到内容

计算不可区分性

本页使用了标题或全文手工转换
维基百科,自由的百科全书

算法分析密码学中,如果没有高效的算法可以区分两个分布族之间的差异(或区分出两者的概率可以忽略),那么两个分布族被称为是计算不可区分(英語:computationally indistinguishable)的。

正式定义

是两个分布集合英语distribution ensemble,下标n(通常指输入的长度)是安全参数英语security parameter。如果对于任意的非均匀英语Uniformity (complexity)概率多项式时间算法 A,以下值是一个n上的可忽略函数,则我们说它们在计算上是不可区分的:

记为[1] 换言之,在时,每个高效的算法A的行为在DnEn上不会有明显变化。对计算不可区分性的另一种解释是,主动尝试区分这两个集合的多项式时间算法不能实现目标:任何这样的算法的表现与单纯猜测相比,优势可以忽略不计。

相关概念

定义中隐含的条件是算法必须根据其中一个分布的单个样本中决定。有人可能会设想这样一种情况,即算法为了区分两个分布,可以根据需要访问尽可能多的样本。因此,两个分布无法由多项式时间算法通过观察多个样本区分的情形,被称为无法通过多项式时间采样区分(英語:indistinguishable by polynomial-time sampling)。[2]:107 如果多项式时间算法可以在多项式时间内生成样本,或者可以访问为其生成样本的隨機預言機,那么多项式时间采样的不可区分性等同于计算不可区分性。[2]:108

参考资料

  1. ^ Lecture 4 - Computational Indistinguishability, Pseudorandom Generators (PDF). [2022-09-09]. (原始内容存档 (PDF)于2022-09-09). 
  2. ^ 2.0 2.1 Goldreich, O. (2003). Foundations of cryptography. Cambridge, UK: Cambridge University Press.

外部链接


本條目含有来自PlanetMathcomputationally indistinguishable》的內容,版权遵守知识共享协议:署名-相同方式共享协议