1 Introduction
1.1 PSM protocols based on quadratic residues
1.1.1 Feige–Kilian–Naor’s protocol
1.1.2 Ishai’s protocol
1.2 Our contributions
function | comm. complexity | |
---|---|---|
Ishai [23] | any function | \(O(n \cdot 2^n)\) |
Corollary 7 | symmetric function | \(O(n^2)\) |
Corollary 8 | weighted threshold function with weight \(\varvec{w}\) | \(O(n \cdot \sum _{i=1}^n \vert w_i\vert )\) |
Proposition 20 | AND function | \(o(n^2)\) |
Proposition 21 | equality (EQ) function | \(o(n^2)\) |
1.3 Related work
1.4 Organization
2 Preliminaries
2.1 Notations
2.2 PSM protocols
2.3 Decomposable randomized encodings
2.4 Quadratic residues
p | \(\textsf{S}_p\) |
---|---|
2 | 1 |
3 | 10 |
5 | 1001 |
7 | 110100 |
11 | 1011100010 |
13 | 101100001101 |
17 | 1101000110001011 |
19 | 100111101010000110 |
n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|
\(P_n\) | 3 | 7 | 11 | 37 | 67 | 181 | 367 | 1091 |
3 QR-PSM protocols
3.1 Definition of QR-PSM protocols
3.2 LQR-PSM protocols
-
The randomness space R is
-
The encoding function \(\textsf{Enc}_i: \{0,1\}\times R \rightarrow \mathbb {Z}_p\) iswhere \(r = (r_0, r_1, r_2, \ldots , r_n) \in R\) and \(x_i \in \{0,1\}\).$$\begin{aligned} \textsf{Enc}_i(x_i, r) = {\left\{ \begin{array}{ll} r_0(a_0 + a_i x_i) + r_i \;(\bmod \;p) &{} \hbox { if}\ i = 1,~\\ r_0a_i x_i + r_i \;(\bmod \;p) &{} \text {otherwise}, \end{array}\right. } \end{aligned}$$
-
The decoding function \(\textsf{Dec}: (\mathbb {Z}_p)^n \rightarrow \{-1, 0, 1\}\) is$$\begin{aligned} \textsf{Dec}(m_1, m_2, \ldots , m_n) = \left( \dfrac{\sum _{i=1}^n m_i}{p}\right) . \end{aligned}$$
n | AND | XOR | EQ | MAJ |
---|---|---|---|---|
2 | \([2,1,1]_5\) | \([2,2,4]_5\) | \([1,1,2]_5\) | \([2,2,2]_5\) |
3 | \([6,1,1,1]_{11}\) | \([6,3,3,3]_7\) | \([1,1,1,1]_5\) | \([3,3,3,2]_7\) |
4 | \([5,1,1,1,1]_{13}\) | \([12,1,1,1,7]_{17}\) | \([5,1,1,1,1]_{11}\) | \([6,2,2,2,2]_{11}\) |
5 | \([11,1,1,1,1,1]_{41}\) | \([14,2,2,2,2,2]_{19}\) | \([4,1,1,1,1,1]_{13}\) | \([6,2,2,2,2,2]_{11}\) |
6 | \([18,1,1,1,1,1,1]_{53}\) | \([15,1,1,1,1,1,6]_{41}\) | \([10,1,1,1,1,1,1]_{41}\) | \([21,3,3,3,3,3,3]_{31}\) |
7 | \([52,1,1,1,1,1,1,1]_{83}\) | \([35,1,1,1,1,1,1,1]_{79}\) | \([17,1,1,1,1,1,1,1]_{53}\) | \([21,3,3,3,3,3,3,2]_{31}\) |
3.3 QR-PSM protocols from DREs
-
\(M_1 = \mathbb {Z}_{p}^{s_0 + s_1 + s_{n+1} + s_{n+2}}\) and \(M_i = \mathbb {Z}_{p}^{s_i}\) for all \(2 \le i \le n\).
-
\(R = \mathbb {Z}_{p}^m \times \mathcal {R}_{p}\). (Recall that \(\mathcal {R}_{p}\) is the set of nonzero quadratic residues modulo p).
-
\(\textsf{Enc}_1(x_1, (r, r')) = (\hat{h}_0(r), \hat{h}_1(r' \cdot x_1, r), \hat{h}_{n+1}(a_0, r), \hat{h}_{n+2}(r', r))\) and \(\textsf{Enc}_i(x_i, (r, r')) = \hat{h}_i(x_i, r)\) for \(2 \le i \le n\), where \(r \in \mathbb {Z}_{p}^m\) and \(r' \in \mathcal {R}_{p}\).
-
\(\textsf{Dec}(m_1, m_2, \ldots , m_n) = \left( \dfrac{\textsf{dec}(m_1, m_2, \ldots , m_n)}{p}\right) \).