How to generate and exchange secrets
How to generate and exchange secrets
复制标题
DOI：
10.1145/266420.266424
复制
发表时间：
1986
期刊：
影响因子：
--
通讯作者：
A. Yao
中科院分区：
文献类型：
--
作者：
A. Yao
在本文中，我们介绍了一种新的工具，用于控制知识转移过程中的密码协议设计。它适用于解决一般类的问题，其中包括大多数的两方密码问题的文献。具体来说，我们展示了双方A和B如何交互式地生成一个随机整数N = p <$q，使得其秘密，即，素因子（p，q）对任何一方单独隐藏，但如果需要，可以共同恢复。这可以用于给出具有私有值i和j的双方的协议，以计算具有最小知识转移和强公平性的任何多项式可计算函数f（i，j）和g（i，j）。作为特殊情况，A和B可以交换一对秘密sA、sB，例如图中整数的因式分解和哈密尔顿回路，以这样的方式，当且仅当sB变得可由A计算时，sA变得可由B计算。所有这些结果证明假设只有大整数的因式分解问题是计算上难以解决的。
In this paper we introduce a new tool for controlling the knowledge transfer process in cryptographic protocol design. It is applied to solve a general class of problems which include most of the two-party cryptographic problems in the literature. Specifically, we show how two parties A and B can interactively generate a random integer N = p¿q such that its secret, i.e., the prime factors (p, q), is hidden from either party individually but is recoverable jointly if desired. This can be utilized to give a protocol for two parties with private values i and j to compute any polynomially computable functions f(i,j) and g(i,j) with minimal knowledge transfer and a strong fairness property. As a special case, A and B can exchange a pair of secrets sA, sB, e.g. the factorization of an integer and a Hamiltonian circuit in a graph, in such a way that sA becomes computable by B when and only when sB becomes computable by A. All these results are proved assuming only that the problem of factoring large intergers is computationally intractable.