布尔电路的零知识模拟  

作　　者：Gilles BRASSARD claude CREPEAU 王晓鸣 

出　　处：《信息安全与通信保密》1989年第2期53-62,共10页Information Security and Communications Privacy

摘　　要：零知识交互式证明是一个协议,用这一协议爱莉斯(Alice)不用给予鲍勃(Bob)关于如何进行证明的任何暗示就能使一多项式有界的Bob相信某一定理的真实性,在密码假设下,为达此目的,对于NP中的每个问题,我们给出一般技术,这扩展到可能的一大类,它们兼有非决定性及随机性的能力。我们的协议是强有力的,它足以供Alice使Bob相信一些她还未曾证明过的定理之用。也许由于Alice懂得一些陷门信息,该协议也足以使Alice自己从概率上去相信一定理,这样Alice也能使Bob相信而不以任何方式泄露陷门。

关 键 词：零知识 陷门信息 交互式证明 二次剩余 错误概率 ALICE 布尔函数 二次非剩余 因子分解 多项式时间 

分 类 号：TN918[电子电信—通信与信息系统]