论文标题
基于二次残留的私人同时消息
Private Simultaneous Messages Based on Quadratic Residues
论文作者
论文摘要
私有同时消息（PSM）模型是安全多阶级计算的最小模型。 Feige，Kilian和Naor（Stoc 1994）和Ishai（Cryptology and Information Security Series 2013）基于二次残基构建了PSM协议。在本文中，我们将QR-PSM协议定义为这些协议的概括。 QR-PSM协议是PSM协议，其解码函数输出了从消息计算出的二次残留量。我们为任何对称函数$ f设计QR-PSM协议$ f：\ {0,1 \}^n \ rightArrow \ {0,1 \} $的通信复杂性$ o（n^2）$。据我们所知，这是最有效的PSM协议，因为先前已知的最佳PSM协议是$ O（N^2 \ log n）$（Beimel等人，Crypto 2014）。我们还研究了协议中基础有限字段$ \ mathbb {f} _p $的大小，因为QR-PSM协议的通信复杂性与Prime $ P $的位长度成正比。 In particular, we show that the $N$-th Peralta prime $P_N$, which is used for general QR-PSM protocols, can be taken as at most $(1+o(1))N^2 2^{2N-2}$, which improves the Peralta's known result (Mathematics of Computation 1992) by a constant factor $(1+\sqrt{2})^2$.
Private Simultaneous Messages (PSM) model is a minimal model for secure multiparty computation. Feige, Kilian, and Naor (STOC 1994) and Ishai (Cryptology and Information Security Series 2013) constructed PSM protocols based on quadratic residues. In this paper, we define QR-PSM protocols as a generalization of these protocols. A QR-PSM protocol is a PSM protocol whose decoding function outputs the quadratic residuosity of what is computed from messages. We design a QR-PSM protocol for any symmetric function $f: \{0,1\}^n \rightarrow \{0,1\}$ of communication complexity $O(n^2)$. As far as we know, it is the most efficient PSM protocol since the previously known best PSM protocol was of $O(n^2\log n)$ (Beimel et al., CRYPTO 2014). We also study the sizes of the underlying finite fields $\mathbb{F}_p$ in the protocols since the communication complexity of a QR-PSM protocol is proportional to the bit length of the prime $p$. In particular, we show that the $N$-th Peralta prime $P_N$, which is used for general QR-PSM protocols, can be taken as at most $(1+o(1))N^2 2^{2N-2}$, which improves the Peralta's known result (Mathematics of Computation 1992) by a constant factor $(1+\sqrt{2})^2$.
