Oblivious Polynomial Evaluation
Oblivious Polynomial Evaluation
复制标题
DOI：
10.1137/s0097539704383633
复制
发表时间：
2006-05
期刊：
影响因子：
--
通讯作者：
M. Naor;Benny Pinkas
中科院分区：
文献类型：
--
作者：
M. Naor;Benny Pinkas
不经意多项式评估是一种涉及两方的协议，发送方的输入是多项式P，接收方的输入是值$\α$。在协议结束时，接收方获知$P(\Alpha)$，而发送方未获知任何信息。我们描述了该协议的有效构造，这些构造基于与噪声多项式重构密切相关的新的难解性假设。不经意多项式求值在许多应用中都可以用作原语。我们描述了几个这样的应用，包括用于数据私密比较的协议、用于基于(可能弱的)密码的相互认证密钥交换的协议，以及用于匿名券的协议。
Oblivious polynomial evaluation is a protocol involving two parties, a sender whose input is a polynomial P, and a receiver whose input is a value $\alpha$. At the end of the protocol the receiver learns $P(\alpha)$ and the sender learns nothing. We describe efficient constructions for this protocol, which are based on new intractability assumptions that are closely related to noisy polynomial reconstruction. Oblivious polynomial evaluation can be used as a primitive in many applications. We describe several such applications, including protocols for private comparison of data, for mutually authenticated key exchange based on (possibly weak) passwords, and for anonymous coupons.