一个高效的匹配协议

比较两个秘密整数是否相等这类协议称为匹配协议。目前这样的协议要么效率极低，要么不能抗击字典攻击。本文给出了一个新的匹配协议，该协议是语义安全的，不存在概率多项式时间算法区分对两个输入的猜测值。协议是高效的，可以比较两个大整数是否相等，计算复杂性和通信复杂性都为D(1)，可以验证参与者是否诚实。该协议可以用于口令认证、电子彩票、可证实加密等安全协议设计。

An efficient match protocol

The protocol of compare of two secret integers is known as the match protocol. Up to now most of such protocols are either inefficient or insecure under the dictionary attacks. In this paper, we present a new match protocol. It is of semantic security: there exists no probabilistic polynomial time algorithm to distinguish two guessed inputs. It js also efficient: the protocol can compare two large secret integers and require only O(1)rounds of communications and O(1) modular exponentiations, and prevent one player from cheating the other at the cost of only a bit more computations. The protocol is suited to be used in password authentication, electronic lotteries, publicly verifiable encryption, etc.