1 Introduction
The main building block of the protocol in [17] is a MKFHE scheme with circuit privacy against malicious adversaries. This scheme is in turn constructed based on the MKFHE scheme by Lopez-Alt et al. [31], which leads to the dependency on the DSPR assumption, as the scheme from [31] requires this.Can a client-server MPC protocol with (malicious) circuit privacy be obtained from standard assumptions?
Can a maliciously circuit-private MKFHE scheme be obtained from standard assumptions?
1.1 Our results
MPC for circuits | Main tools | Communication complexity | Can client computation be |
---|---|---|---|
independent of circuit size? | independent of circuit size? | ||
GMW/BGW paradigm | secret sharing | \(\times \) | \(\times \) |
Yao/BMR paradigm | garbled circuit | \(\times \) | \(\times \) |
FHE based paradigm | multi-key FHE | \(\checkmark \) | \(\checkmark \) |
Construction | Circuit | Rounds | Assumptions | Circuit | Client |
---|---|---|---|---|---|
class | Privacy | Privacy | |||
[31] | Any | 5 | DSPR, RLWE | No | Semi-honest |
[17] | Any | 3 | DSPR, RLWE | Yes | Malicious |
Ours 1 | \(\textsf{NC}^1\) | 4 | LWE | Yes | Malicious |
Ours 2 | Any | 4 | LWE | Yes | Malicious |
1.2 Overview of our constructions
1.3 Organization
2 Preliminaries
2.1 Gaussian, learning with errors, and gadget matrix
2.2 Branching programs
-
G is a connected directed acyclic graph. We denote by \(\Gamma (v)\) the set of the child nodes of \(v\in V\).
-
\(v_{0}\) is the initial node with indegree 0.
-
\(T\subseteq V\) is the set of terminal nodes of outdegree 0. Any node in \(V\backslash T\) has outdegree 2.
-
\(\phi _{V}: V\rightarrow [n]\cup \{0,1\}\) is the node-labeling function with \(\phi _{V}(v)\in \{0,1\}\) for \(v\in T\), and \(\phi _{V}(v)\in [n]\) for \(v\in V\backslash T\).
-
\(\phi _{E}:E\rightarrow \{0,1\}\) is the edge-labeling function, such that the outgoing edges from each vertex are labeled by different values.
2.3 Single-key homomorphic encryption and its circuit privacy
-
(Syntax)
-
\((\textsf{pk}, \textsf{sk})\xleftarrow {\$}{\textsf{KG}(1^{\lambda })}\): This is the key generation algorithm that takes a security parameter \(1^\lambda \) as input, and outputs a public/secret key pair \((\textsf{pk}, \textsf{sk})\).
-
\(\textsf{ct}\xleftarrow {\$}{\textsf{Enc}(\textsf{pk}, x)}\): This is the encryption algorithm that takes a public key \(\textsf{pk}\) and a plaintext \(x \in \{0,1\}\) as input, and outputs a ciphertext \(\textsf{ct}\).
-
\(\widehat{\textsf{ct}}\xleftarrow {\$}{\textsf{Eval}(C, \textsf{pk}, (\textsf{ct}_k)_{k \in [n]})}:\) This is the homomorphic evaluation algorithm that takes a circuit \(C \in \mathcal {C}\) (with domain \(\{0,1\}^n\)), a public key \(\textsf{pk}\), and n ciphertexts \((\textsf{ct}_k)_{k \in [n]}\) as input, and outputs an evaluated ciphertext \(\widehat{\textsf{ct}}\).
-
\(\widehat{x}:= \textsf{Dec}(\textsf{sk}, \widehat{\textsf{ct}})\): This is the (deterministic) decryption algorithm that takes a secret key \(\textsf{sk}\) and an evaluated ciphertext \(\widehat{\textsf{ct}}\) as input, and outputs a decryption result \(\widehat{x}\).
-
-
(Correctness) For any circuit \(C \in \mathcal {C}\) (with n-bit input), and any \((x_{1},\ldots , x_{n})\in \{0,1\}^{n}\), if \((\textsf{pk}, \textsf{sk})\xleftarrow {\$}{\textsf{KG}(1^\lambda )}\), \(\textsf{ct}_{k} \xleftarrow {\$}{\textsf{Enc}(\textsf{pk}, x_{k})}\) for every \(k \in [n]\), and \(\widehat{\textsf{ct}}\xleftarrow {\$}\textsf{Eval}(C, \textsf{pk}, (\textsf{ct}_k)_{k \in [n]})\), then we have \(\Pr [\textsf{Dec}(\textsf{sk}, \widehat{\textsf{ct}})\ne C(x_1, \ldots , x_n)]=\textsf{negl}(\lambda )\).
-
(Semantic Security) Defined in the same way as that for ordinary public-key encryption.
2.4 Oblivious transfer
-
(Syntax)
-
\((q, \textsf{st}) \xleftarrow {\$}\textsf{Q}(1^\lambda , b)\): This is the receiver’s first algorithm that takes a security parameter \(1^\lambda \) and a selection bit \(b\in \{0,1\}\) as input, and outputs a receiver message q and a secret state \(\textsf{st}\).
-
\(a \xleftarrow {\$}\textsf{A}(q, s_{0}, s_{1}):\) This is the sender’s algorithm that takes a receiver message q and two strings \(s_{0}, s_{1}\) as input, and outputs a sender message a.
-
\(s' := \textsf{D}(a, \textsf{st}):\) This is the (deterministic) receiver’s second algorithm that takes a sender message a and a secret state \(\textsf{st}\) as input, and outputs a string \(s'\).
-
-
(Correctness) For all \(\lambda \in \mathbb {N}\), \(b \in \{0,1\}\), and \(s_0, s_1 \in \{0,1\}^*\) such that \(\Vert s_0\Vert = \Vert s_1\Vert \), if \((q, \textsf{st}) \xleftarrow {\$}\textsf{Q}(1^\lambda , b)\) and \(a\xleftarrow {\$}\textsf{A}(q, s_0, s_1)\), then it holds that \(s_b = \textsf{D}(a, \textsf{st})\).
-
(Receiver Privacy) It holds that \(\textsf{Q}(1^\lambda , 0) \approx _{c} \textsf{Q}(1^\lambda , 1)\).
-
(Statistical Sender Privacy against Malicious Receivers) There exist possibly computationally unbounded algorithms \(\textsf{Ext}\) (called the extractor) and \(\textsf{Sim}\) (called the simulator) such that for any receiver message q (which could be outside the image of \(\textsf{Q}\)) and inputs \((s_0, s_1)\) with \(\Vert s_0\Vert = \Vert s_1\Vert \), we have \(\textsf{A}(q, s_0, s_1)\approx _{s} \textsf{Sim}(q, s_{b^*})\), where \(b^*:=\textsf{Ext}(q)\).
2.5 Circuit garbling
-
(Syntax)
-
\((G, e) \xleftarrow {\$}\textsf{GCircuit}\): This is the garbling algorithm that takes a security parameter \(1^{\lambda }\) and a circuit C with n-bit input (for some polynomial \(n = n(\lambda )\)) as input, and outputs a garbled circuit G and a set of tokens \(e = (X_i^0, X_i^1)_{i \in [n]}\).
-
\(y \,= \textsf{GEval}(G, (X_i)_{i \in [n]}\): This is the (deterministic) evaluation algorithm that takes a garbled circuit G and n tokens \((X_i)_{i \in [n]}\) as input, and outputs some value y.
-
-
(Correctness) For any \(\lambda , n \in \mathbb {N}\), any n-bit input circuit C, and any \(x = (x_1, \ldots , x_n) \in \{0,1\}^n\), if \((G, e = (X_i^0, X_i^1)_{i \in [n]}) \xleftarrow {\$}\textsf{GCircuit}(1^\lambda , C)\), then we have \(\textsf{GEval}(G, (X_i^{x_i})_{i \in [n]}) = C(x)\).
-
(Security) For any two circuits \(C_0, C_1\) (with n-bit input) of the same size and any two inputs \(x_0 = (x_{1,0}, \ldots , x_{n,0}), x_1 = (x_{1,1}, \ldots , x_{n,1}) \in \{0,1\}^n\) such that \(C_0(x_0)=C_1(x_1)\), if \((G_b, e_b = (X_{i,b}^0, X_{i,b}^1)_{i \in [n]}) \xleftarrow {\$}\textsf{GCircuit}(1^\lambda , C_i)\) for both \(b \in \{0,1\}\), then we have \((G_0, (X_{i,0}^{x_{i,0}})_{i \in [n]}) \approx _{c} (G_1, (X_{i,1}^{x_{i,1}})_{i \in [n]})\).
2.6 Multi-key homomorphic encryption with distributed setup
-
(Syntax)
-
\(\textsf{pp}_i \xleftarrow {\$}{\textsf{dSetup}(1^\lambda , 1^N, i)}\): This is the distributed setup algorithm that takes a security parameter \(1^\lambda \), the maximal number of inputs N (in unary), and an index \(i \in [N]\) as input, and outputs the i-th user’s public parameter \(\textsf{pp}_{i}\). We require that given \(i \in [N]\) and \(\textsf{pp}\), whether \(\textsf{pp}\in [\textsf{dSetup}(1^\lambda ,1^N,i)]\) or not is efficiently checkable.5
-
\((\textsf{pk}_{i}, \textsf{sk}_{i})\xleftarrow {\$}{\textsf{KG}((\textsf{pp}_j)_{j \in [N]}, i)}\): This is the key generation algorithm that takes N public parameters \((\textsf{pp}_i)_{i \in [N]}\) and an index \(i \in [N]\) as input, and outputs the i-th user’s public/secret key pair \((\textsf{pk}_{i}, \textsf{sk}_{i})\).
-
\(\textsf{ct}\xleftarrow {\$}{\textsf{Enc}(\textsf{pk}_i, x)}\): This is the encryption algorithm that takes a public key \(\textsf{pk}_i\) and a plaintext \(x \in \{0,1\}\) as input, and outputs a ciphertext \(\textsf{ct}\).
-
\(\widehat{\textsf{ct}}\xleftarrow {\$}{\textsf{Eval}(C, (\textsf{pp}_{j})_{j\in [N]}, (\textsf{pk}_{j})_{j\in [N]}, \{(I_{k}, \textsf{ct}_{k})\}_{k\in [n]})}\): This is the homomorphic evaluation algorithm that takes as input a circuit \(C \in \mathcal {C}\) (with domain \(\{0,1\}^n\)), N public parameters \((\textsf{pp}_j)_{j \in [N]}\), N public keys \((\textsf{pk}_i)_{i \in [N]}\), and n pairs \((I_k, c_k)_{k \in [n]}\), where \(I_k \in [N]\) and \(\textsf{ct}_k\) is presumed to be a ciphertext under \(\textsf{pk}_{I_k}\). Then, this algorithm outputs an evaluated ciphertext \(\widehat{\textsf{ct}}\).
-
\(\widehat{x}:=\textsf{Dec}((\textsf{sk}_i)_{i \in [N]}, \widehat{\textsf{ct}})\): This is the (deterministic) decryption algorithm that takes N secret keys \((\textsf{sk}_i)_{i \in [N]}\) and an evaluated ciphertext6\(\widehat{\textsf{ct}}\) as input, and outputs a decryption result \(\widehat{x}\).
-
-
(Correctness) For any \(N \in \mathbb {N}\), any circuit \(C \in \mathcal {C}\) (with n-bit input), any indices \(I_1, \ldots , I_n \in [N]\), and any bits \(x_1, \ldots , x_n \in \{0,1\}\), the following holds: If \(\textsf{pp}_{j}\xleftarrow {\$}{\textsf{dSetup}(1^\lambda , 1^N, j)}\) for all \(j \in [N]\), \((\textsf{pk}_j, \textsf{sk}_j)\xleftarrow {\$}{\textsf{KG}((\textsf{pp}_{j})_{j\in [N]}, j)}\) for all \(j \in [N]\), \(\textsf{ct}_k \xleftarrow {\$}{\textsf{Enc}(\textsf{pk}_{I_k}, x_k)}\) for all \(k \in [n]\), and \(\widehat{\textsf{ct}}\xleftarrow {\$}\textsf{Eval}(C, (\textsf{pp}_j)_{j \in [N]}, (\textsf{pk}_j)_{j \in [N]}, (I_k, \textsf{ct}_k)_{k \in [n]})\), then we have$$\begin{aligned} \Pr [\textsf{Dec}((\textsf{sk}_j)_{j \in [N]}, \widehat{\textsf{ct}})\ne C(x_1,\ldots ,x_n)]=\textsf{negl}(\lambda ). \end{aligned}$$
-
(Semantic Security) For any PPT adversary \(\mathcal {A}\), we havewhere \(\textsf{Exp}_{\textsf{MKHE}, \mathcal {A}}(\lambda , b)\) for \(b \in \{0,1\}\) is the following experiment run between the challenger and the (rushing) adversary \(\mathcal {A}\) (namely, \(\mathcal {A}\) generates corrupted public parameters after seeing an honest public parameter):$$\begin{aligned} |\Pr [\textsf{Exp}_{\textsf{MKHE}, \mathcal {A}}(\lambda , 0)\rightarrow 1]-\Pr [\textsf{Exp}_{\textsf{MKHE}, \mathcal {A}}(\lambda , 1)\rightarrow 1]|=\textsf{negl}(\lambda ), \end{aligned}$$1.\(\mathcal {A}\) chooses the maximal number of inputs N and the challenge index \(i\in [N]\), and sends them to the challenger.2.The challenger returns public parameters \(\textsf{pp}_{i}\xleftarrow {\$}{\textsf{dSetup}(1^\lambda , 1^N, i)}\).3.\(\mathcal {A}\) chooses public parameters \(\textsf{pp}_{j}\) for all \(j\in [N]\backslash \{i\}\), and sends \(\{\textsf{pp}_j\}_{j \in [N] \setminus \{i\}}\) to the challenger.4.The challenger generates \((\textsf{pk}_{i}, \textsf{sk}_{i})\xleftarrow {\$}{\textsf{KG}((\textsf{pp}_{j})_{j\in [N]}, i)}\) and sends \(\textsf{pk}_i\) to \(\mathcal {A}\).5.\(\mathcal {A}\) sends the challenge plaintexts \(x_{0}, x_{1}\) to the challenger.6.The challenger returns the challenge ciphertext \(\textsf{ct}^* \xleftarrow {\$}\textsf{Enc}(\textsf{pk}_{i}, x_{b})\) to \(\mathcal {A}\).7.\(\mathcal {A}\) outputs its guess \(b'\in \{0,1\}\), which is treated as output of the experiment \(\textsf{Exp}_{\textsf{MKHE}, \mathcal {A}}(\lambda , b)\).
3 Privately expandable MKHE with distributed setup
3.1 Private expandability of MKHE with distributed setup
-
(Syntax)
-
\(\widetilde{\textsf{ct}}\xleftarrow {\$}\textsf{Expand}(\textbf{pp}, \textbf{pk}, i, \textsf{ct})\): This is the expansion algorithm that takes N public parameters \(\textbf{pp}\), N public keys \(\textbf{pk}\), an index \(i \in [N]\), and a ciphertext \(\textsf{ct}\) as input, and outputs an expanded ciphertext \(\widetilde{\textsf{ct}}\).
-
\(\widehat{\textsf{ct}}\xleftarrow {\$}\widetilde{\textsf{Eval}}(C, \textbf{pp}, \textbf{pk}, (\widetilde{\textsf{ct}}_k)_{k \in [n]})\): This is the homomorphic evaluation algorithm for expanded ciphertexts. It takes a circuit \(C \in \mathcal {C}\) (with n-bit input), N public parameters \(\textbf{pp}\), N public keys \(\textbf{pk}\), and n expanded ciphertexts \((\widetilde{\textsf{ct}}_k)_{k \in [n]}\) as input7, and outputs an evaluated ciphertext \(\widehat{\textsf{ct}}\).
-
-
(Correctness) For any circuit \(C \in \mathcal {C}\) (with n-bit input), any plaintexts \(x_1,\ldots , x_n \in \{0,1\}\), and indices \(I_1,\ldots , I_n \in [N]\), if \(\textsf{pp}_{j}\xleftarrow {\$}\textsf{dSetup}(1^{\lambda }, 1^{N}, j)\) for all \(j \in [N]\), \((\textsf{pk}_{j}, \textsf{sk}_{j})\xleftarrow {\$}\textsf{KG}(\textbf{pp}, j)\) for all \(j \in [N]\), \(\textsf{ct}_k \xleftarrow {\$}\textsf{Enc}(\textsf{pk}_{I_k}, x_k)\) for all \(k \in [n]\), \(\widetilde{\textsf{ct}}_k \xleftarrow {\$}\textsf{Expand}(\textbf{pp}, \textbf{pk}, I_k, \textsf{ct}_k)\) for all \(k \in [n]\), and \(\widehat{\textsf{ct}}\xleftarrow {\$}\textsf{Eval}(\textbf{pp}, \textbf{pk}, (\widetilde{\textsf{ct}}_k)_{k \in [n]})\), then$$\begin{aligned} \Pr \left[ \begin{array}{l} ~~~\exists k \in [n]: \textsf{Dec}(\textbf{sk}, \widetilde{\textsf{ct}}_k) \ne x_k\\ \vee ~\textsf{Dec}(\textbf{sk}, \widehat{\textsf{ct}}) \ne C(x_1, \ldots , x_n) \end{array} \right] = \textsf{negl}(\lambda ). \end{aligned}$$
3.2 LWE-based expandable MKFHE by brakerski et al.
-
\(\textsf{dSetup}_{\textsf{BHP}}(1^{\lambda }, 1^{N}, i\in [N])\): Let \(n = n(\lambda )\) be a polynomial in security parameter \(\lambda \), \(q = q(\lambda )\) be a superpolynomial in \(\lambda \), \(\ell := \lceil \log q\rceil \), \(m=O(n\ell )\), \(w:=m\ell \), and \(D\) be a Gaussian distribution whose samples have norm bounded by some polynomial \(B = B(\lambda ) \in \mathbb {N}\) except with negligible probability. Sample a matrix \(\textbf{A}_{i} \xleftarrow {\$}\mathbb {Z}_{q}^{m\times n}\), and output \(\textsf{pp}_{i}:=\textbf{A}_{i}\). (Note that any member in \(\mathbb {Z}_q^{m \times n}\) is a possible public parameter.)
-
\(\textsf{KG}_{\textsf{BHP}}(\textbf{pp}, i \in [N])\): Sample \(\textbf{s}_{i}\xleftarrow {\$}\{0, 1\}^{m-1}\), and set \(\textbf{t}_{i}^{T}:=[\textbf{s}_{i}^{T}\Vert 1]\in \mathbb {Z}_{q}^{1\times m}\). For every \(j \in [N]\), compute \(\textbf{b}_{i,j}^{T}:=\textbf{t}_{i}^{T}\textbf{A}_{j}\in \mathbb {Z}_{q}^{1\times n}\) andwhich satisfies \(\textbf{t}_{i}^{T} \textbf{B}_{i, j} = \textbf{b}_{i, i}^{T} - \textbf{b}_{i, j}^{T} \in \mathbb {Z}_{q}^{1\times n}\). Let \(\textbf{B}_{i} := \textbf{B}_{i,i}\).$$\begin{aligned} \textbf{B}_{i,j}:=\textbf{A}_{i}- \begin{bmatrix} \textbf{0}_{(m-1)\times n}\\ \textbf{b}_{i, j}^{T} \end{bmatrix} \in \mathbb {Z}_{q}^{m\times n}, \end{aligned}$$For every \(k \in [m]\), sample \(\textbf{R}_{k} \xleftarrow {\$}D^{n\times w}\) and \(\textbf{E}_{k} \xleftarrow {\$}D^{m\times w}\), and compute an encryption of the k-th bit \(\textbf{t}_i[k]\) of the secret key \(\textbf{t}_i\) byOutput \(\textsf{pk}_{i}:=((\textbf{b}_{i, j})_{j\in [N]}, (\textbf{T}_{i, k})_{k\in [m]})\) and \(\textsf{sk}_{i}:=\textbf{t}_{i}\).$$\begin{aligned} \textbf{T}_{i, k} := \textbf{B}_{i} \textbf{R}_{k} + \textbf{E}_{k} + \textbf{t}_{i}[k] \textbf{G}\in \mathbb {Z}_{q}^{m\times w}. \end{aligned}$$
-
\(\textsf{Enc}_{\textsf{BHP}}(\textsf{pk}_{i}, x \in \{0,1\})\): Sample \(\textbf{R}\xleftarrow {\$}D^{n\times w}\) and \(\textbf{E}\xleftarrow {\$}D^{m\times w}\), and computeFor every \(\tau \in [n]\) and \(k \in [w]\), sample \(\textbf{R}_{\tau , k} \xleftarrow {\$}D^{n\times w}\) and \(\textbf{E}_{\tau , k}\xleftarrow {\$}D^{m\times w}\), and compute an encryption of the \((\tau , k)\)-entry \(\textbf{R}[\tau , k]\) of \(\textbf{R}\) by$$\begin{aligned} \textbf{C}:= \textbf{B}_{i} \textbf{R}+ \textbf{E}+ x \textbf{G}\in \mathbb {Z}_{q}^{m\times w}. \end{aligned}$$Output \(\textsf{ct}_{i}:=(\textbf{C}, (\textbf{U}_{\tau , k})_{\tau \in [n], k \in [w]})\).$$\begin{aligned} \textbf{U}_{\tau , k} := \textbf{B}_{i} \textbf{R}_{\tau , k} + \textbf{E}_{\tau , k} + \textbf{R}[\tau , k] \textbf{G}\in \mathbb {Z}_{q}^{m\times w}. \end{aligned}$$
-
\(\textsf{Expand}_{\textsf{BHP}}(\textbf{pp}, \textbf{pk}, i, \textsf{ct}_{i})\): This algorithm uses the “linear combination” algorithm \(\textsf{LComb}\) described below as a sub-algorithm. Roughly, \(\textsf{LComb}\) takes encryptions of the randomness matrix, i.e. \((\textbf{U}_{\tau , k})_{\tau \in [n], k \in [w]}\), used to encrypt a message, and some input vector in \(\mathbb {Z}_{q}^{n}\) as input, and generates an encryption of the multiplication between the randomness matrix and the input vector. This is used to erase junk terms in decryption.Using \(\textsf{LComb}\), \(\textsf{Expand}_{\textsf{BHP}}\) proceeds as follows: For every \(j\in [N] \setminus \{ i \}\), compute
-
\(\textsf{LComb}((\textbf{U}_{\tau , k} \in \mathbb {Z}_{q}^{m\times w})_{\tau \in [n], k \in [w]}, \textbf{v}\in \mathbb {Z}_{q}^{n})\): First define a matrix \(\textbf{Z}^{(\textbf{v})}_{\tau , k} \in \mathbb {Z}^{n\times w}\) for \(\tau \in [n]\) and \(k \in [w]\) asthen output \(\textbf{X}:= \sum _{\tau \in [n],k \in [w]} \textbf{U}_{\tau , k} \textbf{G}^{-1} (\textbf{Z}^{(\textbf{v})}_{\tau , k}) \in \mathbb {Z}_q^{m \times w}\).$$\begin{aligned} \textbf{Z}^{(\textbf{v})}_{\tau , k}[a, b]:= \left\{ \begin{aligned} v_\tau&\text { if }a=n \text { and }b=k \\ 0&\text { otherwise, } \end{aligned} \right. \end{aligned}$$
Then, output the expanded ciphertext \(\widetilde{\textbf{C}}\in \mathbb {Z}_{q}^{N\cdot m\times N\cdot w}\) that consists of \(N^2\) submatrices of size \(m\times w\), has the input ciphertext \(\textbf{C}\) in diagonal, and \(\textbf{X}_{j}\) in the (i, j)-th submatrix for \(j \in [N] \setminus \{i\}\). More visually, the expanded ciphertext \(\widetilde{\textbf{C}}\) is of the following form$$\begin{aligned} \textbf{X}_{j}:=\textsf{LComb}((\textbf{U}_{\tau , k})_{\tau \in [n], k\in [w]}, \textbf{b}_{i,i} - \textbf{b}_{j,i}). \end{aligned}$$where all the empty submatrices are zero matrices.$$\begin{aligned} \widetilde{\textbf{C}}:= \begin{bmatrix} \textbf{C}&{} &{} &{} &{} &{} &{} \\ &{} \ddots &{} &{} &{} &{} &{} \\ &{} &{} \textbf{C}&{} &{} &{} &{} \\ \textbf{X}_{1}&{} \cdots &{} \textbf{X}_{i-1} &{}\, \textbf{C}\, &{} \textbf{X}_{i+1} &{} \cdots &{} \textbf{X}_{N}\\ &{} &{} &{} &{} \textbf{C}&{} &{} \\ &{} &{} &{} &{} &{} \ddots &{} \\ &{} &{} &{} &{} &{} &{} \textbf{C}\\ \end{bmatrix} \in \mathbb {Z}_{q}^{N\cdot m\times N\cdot w}, \end{aligned}$$ -
-
\(\textsf{Eval}_{\textsf{BHP}}(C, \textbf{pp}, \textbf{pk}, (\widetilde{\textbf{C}}_{k})_{k \in [n]})\): This algorithm homomorphically evaluates the given circuit C over input ciphertexts \((\widetilde{\textbf{C}}_k)_{k \in [n]}\) gate-by-gate (assuming C is described via NAND gates only), and outputs the final result as an evaluated ciphertext \(\widehat{\textsf{ct}}\). To implement the NAND evaluation algorithm \(\textsf{NAND}\), the algorithm makes use of homomorphic addition \(\textsf{Add}\) and multiplication \(\textsf{Mult}\) algorithms described below.
-
\(\textsf{Add}(\widetilde{\textbf{C}}_{1}, \widetilde{\textbf{C}}_{2})\): Homomorphic addition can be just computed by adding the expanded ciphertext matrices: \(\widetilde{\textbf{C}}_{\textsf{Add}}:=\widetilde{\textbf{C}}_{1} + \widetilde{\textbf{C}}_{2} \in \mathbb {Z}_{q}^{N\cdot m\times N\cdot w}\). We can see correctness of this homomorphic addition from the condition satisfied for the expanded ciphertexts.
-
\(\textsf{Mult}(\widetilde{\textbf{C}}_{1}, \widetilde{\textbf{C}}_{2})\): Homomorphic multiplication is computed by first decomposing the expanded ciphertexts by the gadget inverse function and multiplying it to the normal expanded ciphertext: \(\widetilde{\textbf{C}}_{\textsf{Mult}} := \widetilde{\textbf{C}}_{1} \textbf{G}^{-1} (\widetilde{\textbf{C}}_{2}) \in \mathbb {Z}_{q}^{N\cdot m\times N\cdot w}\). Also, correctness of the homomorphic multiplication can be easily checked from the relation between expanded ciphertexts and the concatenation of the involved secret keys.
-
\(\textsf{NAND}(\textbf{pp}, \textbf{pk}, \widetilde{\textbf{C}}_1, \widetilde{\textbf{C}}_2)\): For all \(j\in [N], k\in [m]\), compute the expanded bootstrapping keys \(\widetilde{\textbf{T}}_{j, k} := \textsf{Expand}_{\textsf{BHP}}(\textbf{pp}, \textbf{pk}, j, \textbf{T}_{j, k})\).8 Compute a ciphertext \(\widetilde{\textbf{C}}_{\textsf{NAND}}\) by evaluating the multi-key augmented decryption function \(h_{\widetilde{\textbf{C}}_1,\widetilde{\textbf{C}}_2}\) (in Definition 2.7) on \(\widetilde{\textbf{T}}_{j, k}\)’s gate-by-gate via \(\textsf{Add}\) and \(\textsf{Mult}\).
-
-
\(\textsf{Dec}_{\textsf{BHP}}(\textbf{sk}, \widehat{\textsf{ct}})\): Parse \(\widehat{\textsf{ct}}\) as \(\widetilde{\textbf{C}}\in \mathbb {Z}_{q}^{N\cdot m\times N\cdot w}\).Set \(\widetilde{\textbf{t}}^{T}:=[\textbf{t}_1^T\Vert \cdots \Vert \textbf{t}_N^T]\), and output \(x':=\lfloor (2/q)\cdot \widetilde{\textbf{t}}^T \widetilde{\textbf{C}}\textbf{u}_{N\cdot w}\rceil \), where \(\textbf{u}_{N\cdot w}:=(0,\ldots ,0,1)\in \{0,1\}^{N\cdot w}\).
3.3 Making \(\textsf{MKHE}_{\textsf{BHP}}\) privately expandable
-
\(\textsf{Enc}^*(\textsf{pk}_i, x)\): Generate a ciphertext \(\textsf{ct}= (\textbf{C}, (\textbf{U}_{\tau ,k})_{\tau \in [n], k \in [w]})\) in the same way as \(\textsf{Enc}_{\textsf{BHP}}(\textsf{pk}_i, x)\), except that each entry in \(\textbf{R}\), \(\textbf{E}\), \(\textbf{R}_{\tau ,k}\), and \(\textbf{E}_{\tau ,k}\) for every \(\tau \in [n]\) and \(k \in [w]\), is sampled from \(D_t\) where t is superpolynomial in \(\lambda \).
-
\(\textsf{Add}^*(\textsf{ct}, \textsf{ct}')\): Parse \(\textsf{ct}\) as \((\textbf{C}, (\textbf{U}_{\tau , k})_{\tau \in [n], k \in [w]})\) and \(\textsf{ct}'\) as \((\textbf{C}', (\textbf{U}'_{\tau , k})_{\tau \in [n],k \in [w]})\). Compute \(\textbf{C}'' := \textbf{C}+ \textbf{C}' \in \mathbb {Z}_{q}^{m\times w}\) and \(\textbf{U}_{\tau ,k}'' := \textbf{U}_{\tau ,k} + \textbf{U}_{\tau ,k}' \in \mathbb {Z}_{q}^{m\times w}\) for all \(\tau \in [n]\) and \(k \in [w]\). Output \(\textsf{ct}'' := (\textbf{C}'', (\textbf{U}_{\tau ,k}'')_{\tau \in [n], k \in [w]})\).
-
\(\textsf{pExpand}_{\textsf{BHP}}(\textbf{pp}, \textbf{pk}, i, \textsf{ct}_{i})\): For every \(j\in [N]\), computeand \(\widetilde{\textsf{ct}}_j^* := \textsf{Expand}_{\textsf{BHP}}(\textbf{pp}, \textbf{pk}, j, \textsf{ct}_j^*)\). Output \(\widetilde{\textsf{ct}}_i := \sum _{j\in [N]} \widetilde{\textsf{ct}}_{j}^*\), where the summation of \(\widetilde{\textsf{ct}}_{j}^*\)’s is realized by \(\textsf{Add}\).$$\begin{aligned} \textsf{ct}_{j}^*:= {\left\{ \begin{array}{ll} \textsf{Add}^*(\textsf{ct}_{i}, \textsf{Enc}^*(\textsf{pk}_i, 0)) &{} \text { if }j=i \\ \textsf{Enc}^*(\textsf{pk}_j, 0) &{} \text {otherwise} \\ \end{array}\right. }. \end{aligned}$$
4 Maliciously circuit-private MKHE based on LWE
4.1 Definition
4.2 Scheme for branching programs
-
Let \(\textsf{MKHE}_{\textsf{PE}}=(\textsf{dSetup}_{\textsf{PE}}, \textsf{KG}_{\textsf{PE}}, \textsf{Enc}_{\textsf{PE}}, \textsf{Expand}_{\textsf{PE}}, \textsf{Eval}_{\textsf{PE}}, \textsf{Dec}_{\textsf{PE}})\) be a privately-expandable MKFHE scheme with distributed setup, for which we also assume weak circular security. We also require that this scheme is additive homomorphic over fresh (pre-expanded) ciphertexts such that for any \(i \in [N]\), public parameters \(\textbf{pp}= (\textsf{pp}_j)_{j \in [N]}\) generated by \(\textsf{dSetup}_{\textsf{PE}}(1^\lambda ,1^N,i)\), an honestly generated key pair \((\textsf{pk}_{\textsf{PE},i}, \textsf{sk}_{\textsf{PE},i}) \in [\textsf{KG}_{\textsf{PE}}(\textbf{pp}, i)]\), plaintexts \(x_1, x_2 \in \{0,1\}\), and randomness \(r_1, r_2\) for \(\textsf{Enc}_{\textsf{PE}}\), we have \(\textsf{Enc}_{\textsf{PE}}(\textsf{pk}_{\textsf{PE},i}, x_1; r_1) + \textsf{Enc}_{\textsf{PE}}(\textsf{pk}_{\textsf{PE},i}, x_2;r_2) = \textsf{Enc}_{\textsf{PE}}(\textsf{pk}_{\textsf{PE},i}, x_1 + x_2; r_1 + r_2)\). (In the following, we will just use “−” to denote the homomorphic subtraction between ciphertexts.)
-
Let \(\textsf{SKHE}_{\textsf{mCP}}=(\textsf{KG}_{\textsf{mCP}}, \textsf{Enc}_{\textsf{mCP}}, \textsf{Eval}_{\textsf{mCP}}, \textsf{Dec}_{\textsf{mCP}})\) be a maliciously circuit-private single-key FHE scheme. (see Sect. 2.3 for the formal definitions of single-key HE and malicious circuit privacy for single-key HE.)
-
\(\textsf{dSetup}_{\textsf{BP}}(1^\lambda , 1^N, i\in [N])\): Output \(\textsf{pp}_{i} \xleftarrow {\$}\textsf{dSetup}_{\textsf{PE}}(1^\lambda , 1^N, i)\).
-
\(\textsf{KG}_{\textsf{BP}}(\textbf{pp}, i)\): Pick randomness \(r_{\textsf{KG},i}\) for \(\textsf{KG}_{\textsf{PE}}\), and computeOutput \(\textsf{pk}_{i} :=(\textsf{pk}_{\textsf{PE}, i}, \textsf{pk}_{\textsf{mCP}, i}, [\![{\textsf{sk}_{\textsf{PE}, i}}]\!]_{i}, [{\textsf{sk}_{\textsf{PE}, i} \Vert r_{\textsf{KG}, i}}]_{i})\) and \(\textsf{sk}_{i} := (\textsf{sk}_{\textsf{PE}, i}, \textsf{sk}_{\textsf{mCP}, i})\).$$\begin{aligned}&(\textsf{pk}_{\textsf{PE}, i}, \textsf{sk}_{\textsf{PE}, i}) := \textsf{KG}_{\textsf{PE}}(\textbf{pp}, i; r_{\textsf{KG}, i}),(\textsf{pk}_{\textsf{mCP}, i}, \textsf{sk}_{\textsf{mCP}, i}) \xleftarrow {\$}\textsf{KG}_{\textsf{mCP}}(1^\lambda ),\\&[\![{\textsf{sk}_{\textsf{PE},i}}]\!]_{i} \xleftarrow {\$}\textsf{Enc}_{\textsf{PE}}(\textsf{pk}_{\textsf{PE}, i}, \textsf{sk}_{\textsf{PE}, i}), [{\textsf{sk}_{\textsf{PE},i} \Vert r_{\textsf{KG}, i}}]_{i} \xleftarrow {\$}\textsf{Enc}_{\textsf{mCP}}(\textsf{pk}_{\textsf{mCP}, i}, \textsf{sk}_{\textsf{PE},i} \Vert r_{\textsf{KG}, i}). \end{aligned}$$
-
\(\textsf{Enc}_{\textsf{BP}}(\textsf{pk}_i, x \in \{0,1\})\): Parse \(\textsf{pk}_i\) as \((\textsf{pk}_{\textsf{PE},i}, \textsf{pk}_{\textsf{mCP},i}, [\![{\textsf{sk}_{\textsf{PE}, i}}]\!]_{i}, [{\textsf{sk}_{\textsf{PE}, i} \Vert r_{\textsf{KG}, i}}])\). Pick randomness \(r_{\textsf{Enc}, i}\) for \(\textsf{Enc}_{\textsf{PE}}\), and computeOutput \(\textsf{ct}_{i}:=([\![{x}]\!]_i, [{r_{\textsf{Enc}, i}}]_i)\).$$\begin{aligned}&[\![{x}]\!]_i := \textsf{Enc}_{\textsf{PE}}(\textsf{pk}_{\textsf{PE}, i}, x; r_{\textsf{Enc}, i}),&[{r_{\textsf{Enc}, i}}]_i \xleftarrow {\$}\textsf{Enc}_{\textsf{mCP}}(\textsf{pk}_{\textsf{mCP}, i}, r_{\textsf{Enc}, i}). \end{aligned}$$
-
\(\textsf{Eval}_{\textsf{BP}}(P, \textbf{pp}, \textbf{pk}, (I_k, \textsf{ct}_k)_{k\in [n]})\): If there exists \(j \in [N]\) such that \(\textsf{pp}_j \notin [\textsf{dSetup}_{\textsf{PE}}(1^\lambda ,1^N, j)]\), then output \(\bot \) and terminate. Otherwise, parse P as a length-\(\ell \) branching program \((G = (V, E), v_{0}, T, \phi _{V}, \phi _{E})\), and suppose its input length is n-bit. Parse each \(\textsf{pk}_j\) as \((\textsf{pk}_{\textsf{PE},j}, \textsf{pk}_{\textsf{mCP},j}, [\![{\textsf{sk}_{\textsf{PE}, j}}]\!]_{j}, [{\textsf{sk}_{\textsf{PE}, j} \Vert r_{\textsf{KG}, j}}]_{j})\) and each \(\textsf{ct}_k\) as \(([\![{x_k}]\!]_{I_k}, [{r_{\textsf{Enc},k}}]_{I_k})\). Let \(s_0\) be the length of \(\textsf{Label}(v_0)\) determined below. (\(s_0\) itself is known a priori.) For every \(j \in [N]\), choose \(S_{j}\xleftarrow {\$}\{0,1\}^{s_0}\), set \(q_j := |\{k \in [n]: I_k = j\}|\), and computeFor each \(v \in T\), set \(\textsf{Label}(v) := \phi _V(v)\). For each10\(v\in V \setminus T\) for which \(\textsf{Label}(u_0)\) and \(\textsf{Label}(u_1)\) with \(\Gamma (v) = \{u_0,u_1\}\) are already defined, do the following:$$\begin{aligned} \widehat{V}_{\textsf{mCP},j}&\xleftarrow {\$}\textsf{Eval}_{\textsf{mCP}} \left( \begin{array}{l} \textsf{Validate}^{N, q_j}_{\textbf{pp}, j, \textsf{pk}_{\textsf{PE}, j}, \{[\![{x_k}]\!]_{I_k}\}_{I_{k}=j}, S_{j}}, \textsf{pk}_{\textsf{mCP},j},\\ ([{\textsf{sk}_{\textsf{PE}, j} \Vert r_{\textsf{KG}, j}}]_j, \{[{r_{\textsf{Enc}, k}}]_j\}_{I_k=j}) \end{array} \right) ,\\ \widetilde{[\![{\textsf{sk}_{\textsf{PE}, j}}]\!]}&\xleftarrow {\$}\textsf{Expand}_{\textsf{PE}}(\textbf{pp}, \textbf{pk}_{\textsf{PE}}, j, [\![{\textsf{sk}_{\textsf{PE}, j}}]\!]_j). \end{aligned}$$Finally, output \(\widehat{\textsf{ct}}:=(\textsf{Label}(v_{0}) \oplus \bigoplus _{j \in [N]} S_j, (\widehat{V}_{\textsf{mCP},j})_{j \in [N]})\).
-
Let \(h:=\textsf{height}(v)\), \(k^{\star }:=\phi _{V}(v)\), and \(\{u_{0}, u_{1} \} = \Gamma (v)\) such that \(\phi _{E}(v, u_0)=0\) and \(\phi _{E}(v, u_1)=1\).
-
Let \([\![{0}]\!]_{I_{k^{\star }}} := \textsf{Enc}_{\textsf{PE}}(\textsf{pk}_{\textsf{PE},I_{k^\star }}, 0; 0)\) and \([\![{1}]\!]_{I_{k^{\star }}} := \textsf{Enc}_{\textsf{PE}}(\textsf{pk}_{\textsf{PE},I_{k^\star }}, 1; 0)\).
-
For \(t=1,\ldots ,s=|\textsf{Label}(u_0)|\), do the following:and compute \(\widetilde{a}_{\textsf{PE},t} \xleftarrow {\$}\textsf{Expand}_{\textsf{PE}}(\textbf{pp}, \textbf{pk}_{\textsf{PE}}, I_{k^\star }, a_{\textsf{PE},t})\).11
-
\(*\) For \(\sigma \in \{0,1\}\), let \(\textsf{Label}(u_\sigma )[t]\) be the t-th bit of \(\textsf{Label}(u_\sigma )\).
-
\(*\) Set$$\begin{aligned} a_{\textsf{PE},t} := {\left\{ \begin{array}{ll} {[\![{0}]\!]_{I_{k^{\star }}}} &{} \text {if }\textsf{Label}(u_{0})[t] = 0 \wedge \textsf{Label}(u_{1})[t] = 0 \\ {[\![{x_{k^{\star }}}]\!]_{I_{k^{\star }}}} &{} \text {if }\textsf{Label}(u_{0})[t] = 0 \wedge \textsf{Label}(u_{1})[t] = 1 \\ {[\![{1}]\!]_{I_{k^{\star }}}} - {[\![{x_{k^{\star }}}]\!]_{I_{k^{\star }}}} &{} \text {if }\textsf{Label}(u_{0})[t] = 1 \wedge \textsf{Label}(u_{1})[t] = 0 \\ {[\![{1}]\!]_{I_{k^{\star }}}} &{} \text {if } \textsf{Label}(u_{0})[t] = 1 \wedge \textsf{Label}(u_{1})[t] = 1 \\ \end{array}\right. }, \end{aligned}$$
-
-
Set \(\widetilde{a}_{\textsf{PE},v}: = (\widetilde{a}_{\textsf{PE},1}, \ldots , \widetilde{a}_{\textsf{PE},s})\).12
-
Computewhere the inputs to \(\textsf{Dec}_{\textsf{PE}}\) in \(\textsf{Eval}_{\textsf{PE}}\) are naturally arranged: the secret keys encrypted in \((\widetilde{[\![{\textsf{sk}_{\textsf{PE},j}}]\!]})_{j \in [N]}\) are used as \(\textbf{sk}_{\textsf{PE}}\), and what is encrypted in \(\widetilde{a}_{\textsf{PE},v}\) (which, for honestly generated ciphertexts, is \(\textsf{Label}(u_{x_{k^\star }})\)) is used as an expanded ciphertext to be decrypted.$$\begin{aligned} \textsf{Label}(v):= {\left\{ \begin{array}{ll} {\widetilde{a}_{\textsf{PE},v}} &{} \text {if }h=1,\\ {\textsf{Eval}_{\textsf{PE}}} \Bigl (\textsf{Dec}_{\textsf{PE}}, \textbf{pp}, \textbf{pk}_{\textsf{PE}}, ((\widetilde{[\![{\textsf{sk}_{\textsf{PE}, j}}]\!]})_{j\in [N]}, \widetilde{a}_{\textsf{PE},v}) \Bigr ) &{} \text {otherwise} \end{array}\right. }. \end{aligned}$$
-
-
\(\textsf{Dec}_{\textsf{BP}}(\textbf{sk}, \widehat{\textsf{ct}})\): Parse each \(\textsf{sk}_j\) as \((\textsf{sk}_{\textsf{PE},j}, \textsf{sk}_{\textsf{mCP},j})\) and \(\widehat{\textsf{ct}}\) as \((\widehat{c}, (\widehat{V}_{\textsf{mCP},j})_{j \in [N]})\). For every \(j \in [N]\), compute \(S_{j}:=\textsf{Dec}_{\textsf{mCP}}(\textsf{sk}_{\textsf{mCP}, j}, \widehat{V}_{\textsf{mCP},j})\). Let \(\widehat{\textsf{ct}}_{\textsf{PE}}:=\widehat{c}\oplus \bigoplus _{j \in [N]} S_j\). Output \(\widehat{x}:= \textsf{Dec}_{\textsf{PE}}(\textbf{sk}_{\textsf{PE}}, \widehat{\textsf{ct}}_{\textsf{PE}})\).
-
\(\textsf{Ext}_{\textsf{BP}}(\textbf{pp}^*, i, \textsf{pk}^*_i, \textsf{ct}^*)\): Parse \(\textsf{pk}^*_i\) as \((\textsf{pk}_{\textsf{PE},i}^*, \textsf{pk}_{\textsf{mCP},i}^*, [\![{\textsf{sk}_{\textsf{PE},i}}]\!]^*_i, [{\textsf{sk}_{\textsf{PE},i} \Vert r_{\textsf{KG},i}}]_i^*)\) and \(\textsf{ct}^*\) as \(([\![{x}]\!]^*_i, [{r_{\textsf{Enc}}}]^*_i)\). Extract14Check whether \((\textsf{pk}_{\textsf{PE}, i}^{*}, \textsf{sk}_{\textsf{PE}, i}^{*})=\textsf{KG}_{\textsf{PE}}(\textbf{pp}^*, i; r_{\textsf{KG}}^*)\) and there exists \(x' \in \{0,1\}\) such that \([\![{x}]\!]^*_i = \textsf{Enc}_{\textsf{PE}}(\textbf{pp}^*, \textsf{pk}_{\textsf{PE}, i}^{*}, x'; r_{\textsf{Enc}}^{*})\). If the check passes, then output \(x'\). Otherwise, output 0.$$\begin{aligned} \textsf{sk}_{\textsf{PE}, i}^{*} \Vert r_{\textsf{KG},i}^*&:= \textsf{Ext}_{\textsf{mCP}}(\textsf{pk}_{\textsf{mCP}, i}^{*}, [{\textsf{sk}_{\textsf{PE}, i} \Vert r_{\textsf{KG},i}}]^{*}_{i}),\\ r_{\textsf{Enc}}^{*}&:=\textsf{Ext}_{\textsf{mCP}}(\textsf{pk}_{\textsf{mCP}, i}^{*}, [{r_{\textsf{Enc}}}]^{*}_i). \end{aligned}$$
-
\(\textsf{Sim}_{\textsf{BP}}(\textbf{pp}^*, \textbf{pk}^*, (I_k, \textsf{ct}_k^*)_{k\in [n]}, b^* \in \{0,1\})\): If there exists \(j \in [N]\) such that \(\textsf{pp}^*_j \notin [\textsf{dSetup}_{\textsf{PE}}(1^\lambda ,1^N, j)]\), then output \(\bot \) and terminate. Otherwise, parse each \(\textsf{pk}^*_j\) as \((\textsf{pk}_{\textsf{PE},j}^*, \textsf{pk}_{\textsf{mCP},j}^*, [\![{\textsf{sk}_{\textsf{PE},j}}]\!]^*_{j}, [{\textsf{sk}_{\textsf{PE},j} \Vert r_{\textsf{KG},j}}]^*_j)\) and each \(\textsf{ct}_k^*\) as \(([\![{x_k}]\!]^*_{I_k}, [{r_{\textsf{Enc},k}}]^*_{I_k})\). For every \(j \in [N]\), do the following:If one of the checks during the computation of \(\widehat{V}_{\textsf{mCP},j}\) was not satisfied, then pick \(\widehat{c}^* \xleftarrow {\$}\{0,1\}^{s_0}\), and terminate with output \(\widehat{\textsf{ct}}^* := (\widehat{c}^*, (\widehat{V}^*_{\textsf{mCP},j})_{j \in [N]})\). Otherwise (i.e. the checks did not fail), set \(\textsf{out}_0:=b^*\), and for \(h=1, \ldots , \ell \), do the following:
-
Sample \(S_{j}\xleftarrow {\$}\{0,1\}^{s_0}\).
-
Do the same check on \(\textsf{pk}_{\textsf{PE},j}^*\) and \([\![{x_k}]\!]^*_{j}\) as done in \(\textsf{Ext}_{\textsf{BP}}(\textbf{pp}^*, j, \textsf{pk}_{\textsf{PE},j}^*, \textsf{ct}^*_k)\) for all k such that \(I_k = j\).
-
Compute$$\begin{aligned} \widehat{V}^*_{\textsf{mCP},j} := {\left\{ \begin{array}{ll} \begin{array}{r} \textsf{Sim}_{\textsf{mCP}} \Bigl (\textsf{pk}_{\textsf{mCP}, j}^{*}, ([{\textsf{sk}_{\textsf{mCP}, j} \Vert r_{\textsf{KG}, j}}]^{*}_j, \{[{r_{\textsf{Enc}, k}}]^{*}_{j}\}_{I_k=j}), S_j \Bigr )\\ \text {if the above check passes}\end{array}\\ \begin{array}{r} \textsf{Sim}_{\textsf{mCP}} \Bigl (\textsf{pk}_{\textsf{mCP}, j}^{*}, ([{\textsf{sk}_{\textsf{mCP}, j} \Vert r_{\textsf{KG}, j}}]^{*}_j, \{[{r_{\textsf{Enc}, k}}]^{*}_{j}\}_{I_k=j}), 0^{s_0} \Bigr )\\ \text {otherwise}\end{array} \end{array}\right. }. \end{aligned}$$
-
Compute \(\widetilde{[\![{\textsf{sk}_{\textsf{PE}, j}}]\!]}^* \xleftarrow {\$}\textsf{Expand}_{\textsf{PE}}(\textbf{pp}^*, \textbf{pk}^*, [\![{\textsf{sk}_{\textsf{PE}, j}}]\!]^{*}_j)\).
Set \(\widehat{c}^* := \textsf{out}_{\ell } \oplus \bigoplus _{j \in [N]} S_j\) and output \(\widehat{\textsf{ct}}^*:=(\widehat{c}^*, (\widehat{V}^*_{\textsf{mCP}, j})_{j \in [N]})\).-
Let \([\![{0}]\!]_1:= \textsf{Enc}_{\textsf{PE}}(\textsf{pk}^*_{\textsf{PE},1}, 0;0)\) and \([\![{1}]\!]_1 := \textsf{Enc}_{\textsf{PE}}(\textsf{pk}^*_{\textsf{PE},1}, 1;0)\).
-
For \(t=1,\dots , s:=|\textsf{out}_{h-1}|\) (where \(|\textsf{out}_0|:=1\)), setand compute \(\widetilde{a}^*_{\textsf{PE},t} \xleftarrow {\$}\textsf{Expand}_{\textsf{PE}}(\textbf{pp}^*, \textbf{pk}_{\textsf{PE}}^*, 1, a^*_{\textsf{PE},t})\).$$\begin{aligned} a^*_{\textsf{PE},t}:= {\left\{ \begin{array}{ll} {[\![{0}]\!]_{1}} &{} \text {if the }t\text {-th bit of }\textsf{out}_{h-1}\text { is }0\\ {[\![{1}]\!]_{1}} &{} \text {if the }t\text {-th bit of }\textsf{out}_{h-1}\text { is }1\\ \end{array}\right. }, \end{aligned}$$
-
Set \(\widetilde{a}^*_{\textsf{PE},h} := (\widetilde{a}^*_{\textsf{PE},1}, \ldots , \widetilde{a}^*_{\textsf{PE},s})\).
-
Compute$$\begin{aligned} \textsf{out}_h:= {\left\{ \begin{array}{ll} \widetilde{a}^*_{\textsf{PE},1} &{} \text {if }h=1,\\ \textsf{Eval}_{\textsf{PE}} \Bigl (\textsf{Dec}_{\textsf{PE}}, \textbf{pp}^*, \textbf{pk}^*_{\textsf{PE}}, ((\widetilde{[\![{\textsf{sk}_{\textsf{PE}, j}}]\!]}^{*})_{j\in [N]}, \widetilde{a}^*_{\textsf{PE},h}) \Bigr ) &{} \text {otherwise} \end{array}\right. }. \end{aligned}$$
-
4.3 Achieving full homomorphism
-
Let \(\textsf{MKHE}_{\textsf{F}} = (\textsf{dSetup}_{\textsf{F}}, \textsf{KG}_{\textsf{F}}, \textsf{Enc}_{\textsf{F}}, \textsf{Eval}_{\textsf{F}}, \textsf{Dec}_{\textsf{F}})\) be a (non-circuit-private) MKFHE scheme with distributed setup whose decryption circuit can be computed by \(\textsf{NC}^1\) circuits.
-
Let \(\textsf{MKHE}_{\textsf{BP}} = (\textsf{dSetup}_{\textsf{BP}}, \textsf{KG}_{\textsf{BP}}, \textsf{Enc}_{\textsf{BP}}, \textsf{Eval}_{\textsf{BP}}, \textsf{Dec}_{\textsf{BP}})\) be a maliciously circuit-private MKHE scheme with distributed setup for length-\(\ell \) branching programs, where \(\ell \) is a polynomial of \(\lambda \) large enough so that it can compute the validation circuits \(\textsf{KValidate}\) and \(\textsf{CValidate}\) introduced below, and the decryption circuit of \(\textsf{Dec}_{\textsf{F}}\). For notational convenience, we treat this scheme as an MKHE scheme for circuits that can be computed by length \(\ell \)-branching programs. (Thus, \(\textsf{Eval}_{\textsf{BP}}\) takes a circuit as input, rather than a branching program).
-
\(\textsf{KValidate}\) checks whether a hardwired public key of \(\textsf{MKHE}_{\textsf{F}}\) is well-formed. It has the following values hardwired: \(N \in \mathbb {N}\), public parameters \(\textbf{pp}_{\textsf{F}}\), an index \(i \in [N]\), a public key \(\textsf{pk}_{\textsf{F}}\), and some value \(\textsf{out}\in \{0,1\}^*\). Then, it takes a pair of (candidate) secret key \(\textsf{sk}_{\textsf{F}}\) and randomness \(r_{\textsf{KG}}\) as input, and its output is defined as follows:$$\begin{aligned} \textsf{KValidate}^N_{\textbf{pp}_{\textsf{F}}, i, \textsf{pk}_{\textsf{F}}, \textsf{out}}(\textsf{sk}_{\textsf{F}}, r_{\textsf{KG}}) := {\left\{ \begin{array}{ll} \textsf{out}&{} \text { if } (\textsf{pk}_{\textsf{F}}, \textsf{sk}_{\textsf{F}}) = \textsf{KG}_{\textsf{F}}(\textbf{pp}_{\textsf{F}}, i; r_{\textsf{KG}})\\ 0 &{} \text {otherwise} \end{array}\right. }. \end{aligned}$$
-
\(\textsf{CValidate}\) checks whether the hardwired ciphertext of \(\textsf{MKHE}_{\textsf{F}}\) is well-formed. It has the following values hardwired: a public key \(\textsf{pk}_{\textsf{F}}\), a ciphertext \(\textsf{ct}_{\textsf{F}}\), and some value \(\textsf{out}\in \{0,1\}^*\). Then, it takes randomness \(r_{\textsf{Enc}}\) as input, and its output is defined as follows:$$\begin{aligned} \textsf{CValidate}_{\textsf{pk}_{\textsf{F}}, \textsf{ct}_{\textsf{F}}, \textsf{out}}(r_{\textsf{Enc}}) := {\left\{ \begin{array}{ll} \textsf{out}&{} \text { if } \exists x \in \{0,1\} : \textsf{ct}_{\textsf{F}} = \textsf{Enc}_{\textsf{F}}(\textsf{pk}_{\textsf{F}}, x; r_{\textsf{Enc}})\\ 0 &{} \text {otherwise} \end{array}\right. }. \end{aligned}$$
-
\(\textsf{CombineDec}\) checks whether the given ciphertexts of \(\textsf{MKHE}_{\textsf{BP}}\) are correctly decrypted to a hardwired element. It has \(N,q \in \mathbb {N}\) and some value \(\textsf{out}\in \{0,1\}^*\) hardwired, takes N secret keys \(\textbf{sk}_{\textsf{BP}} = (\textsf{sk}_{\textsf{BP}, j})_{j \in [N]}\) and q evaluated ciphertexts \(\{\widehat{\textsf{ct}}_{\textsf{BP},j}\}_{j \in [q]}\) as input, and its output is defined as follows:$$\begin{aligned} \textsf{CombineDec}^{N,q}_{\textsf{out}} \Bigl (\textbf{sk}_{\textsf{BP}}, \{\widehat{\textsf{ct}}_{\textsf{BP},j}\}_{j \in [q]} \Bigr ) := {\left\{ \begin{array}{ll} \textsf{out}&{} \begin{array}{l} \text {if }\textsf{Dec}_{\textsf{BP}}(\textbf{sk}_{\textsf{BP}}, \widehat{\textsf{ct}}_{\textsf{BP},j}) = \textsf{out}\\ ~~~~~~~~~~~~~~~~~~\text { for all } j \in [q] \end{array}\\ 0 &{} \text {otherwise} \end{array}\right. }. \end{aligned}$$
-
\(\textsf{dSetup}_{\textsf{mCP}}(1^\lambda , 1^N, i\in [N])\): Compute \(\textsf{pp}_{\textsf{BP}, i} \xleftarrow {\$}\textsf{dSetup}_{\textsf{BP}}(1^\lambda , 1^N, i)\) and \(\textsf{pp}_{\textsf{F}, i} \xleftarrow {\$}\textsf{dSetup}_{\textsf{F}}(1^{\lambda }, 1^N, i)\). Output \(\textsf{pp}_i:=(\textsf{pp}_{\textsf{BP}, i}, \textsf{pp}_{\textsf{F}, i})\).
-
\(\textsf{KG}_{\textsf{mCP}}(\textbf{pp}, i \in [N])\): Parse each \(\textsf{pp}_j\) as \((\textsf{pp}_{\textsf{BP}, j}, \textsf{pp}_{\textsf{F}, j})\). Pick randomness \(r_{\textsf{KG},i}\) for \(\textsf{KG}_{\textsf{F}}\), and computeOutput \(\textsf{pk}_i:=(\textsf{pk}_{\textsf{F}, i}, \textsf{pk}_{\textsf{BP}, i}, [\![{\textsf{sk}_{\textsf{BP}, i}}]\!]_i, [{\textsf{sk}_{\textsf{F}, i}}], [{r_{\textsf{KG}, i}}]_i)\) and \(\textsf{sk}_i:=\textsf{sk}_{\textsf{F}, i}\).$$\begin{aligned}&(\textsf{pk}_{\textsf{F}, i}, \textsf{sk}_{\textsf{F}, i}) := \textsf{KG}_{\textsf{F}}(\textbf{pp}_{\textsf{F}}, i; r_{\textsf{KG}, i}),{} & {} (\textsf{pk}_{\textsf{BP}, i}, \textsf{sk}_{\textsf{BP}, i}) \xleftarrow {\$}\textsf{KG}_{\textsf{BP}}(\textbf{pp}_{\textsf{BP}}, i),\\&[\![{\textsf{sk}_{\textsf{BP}, i}}]\!]_i \xleftarrow {\$}\textsf{Enc}_{\textsf{F}}(\textsf{pk}_{\textsf{F}, i}, \textsf{sk}_{\textsf{BP}, i}),{} & {} [{\textsf{sk}_{\textsf{F}, i}}]_i \xleftarrow {\$}\textsf{Enc}_{\textsf{BP}}(\textsf{pk}_{\textsf{BP}, i}, \textsf{sk}_{\textsf{F}, i}),\\&[{r_{\textsf{KG}, i}}]_i \xleftarrow {\$}\textsf{Enc}_{\textsf{BP}}(\textsf{pk}_{\textsf{BP}, i}, r_{\textsf{KG}, i}). \end{aligned}$$
-
\(\textsf{Enc}_{\textsf{mCP}}(\textsf{pk}_i, x \in \{0,1\})\): Parse \(\textsf{pk}_i\) as \((\textsf{pk}_{\textsf{F}, i}, \textsf{pk}_{\textsf{BP}, i}, [\![{\textsf{sk}_{\textsf{BP}, i}}]\!]_i, [{\textsf{sk}_{\textsf{F}, i}}]_i, [{r_{\textsf{KG}, i}}]_i)\). Pick randomness \(r_{\textsf{Enc}, i}\) for \(\textsf{Enc}_{\textsf{F}}\), and computeOutput \(\textsf{ct}_i:=([\![{x}]\!]_i, [{r_{\textsf{Enc}, i}}]_i)\).$$\begin{aligned}&[\![{x}]\!]_i := \textsf{Enc}_{\textsf{F}}(\textsf{pk}_{\textsf{F}, i}, x; r_{\textsf{Enc}, i}),{} & {} [{r_{\textsf{Enc}, i}}]_i \xleftarrow {\$}\textsf{Enc}_{\textsf{BP}}(\textsf{pk}_{\textsf{BP}, i}, r_{\textsf{Enc}, i}). \end{aligned}$$
-
\(\textsf{Eval}_{\textsf{mCP}}(C, \textbf{pp}, \textbf{pk}, (I_k, \textsf{ct}_k)_{k\in [n]})\): If there exists \(j \in [N]\) such that \(\textsf{pp}_j \notin [\textsf{dSetup}_{\textsf{mCP}}(1^\lambda ,1^N, j)]\), then output \(\bot \) and terminate. Otherwise, parse each \(\textsf{pp}_j\) as \((\textsf{pp}_{\textsf{BP},j}, \textsf{pp}_{\textsf{F},j})\), each \(\textsf{pk}_j\) as \((\textsf{pk}_{\textsf{F}, j}, \textsf{pk}_{\textsf{BP}, j}, [\![{\textsf{sk}_{\textsf{BP}, j}}]\!]_j, [{\textsf{sk}_{\textsf{F}, j}}]_j, [{r_{\textsf{KG}, j}}]_j)\), and each \(\textsf{ct}_k\) as \(([\![{x_k}]\!]_{I_k}, [{r_{\textsf{Enc}, k}}]_{I_k})\). ComputeFor every \(j \in [N]\), compute$$\begin{aligned} \widehat{\textsf{ct}}_{\textsf{F}}&\xleftarrow {\$}\textsf{Eval}_{\textsf{F}} \Bigl ( C, \textbf{pp}_{\textsf{F}}, \textbf{pk}_{\textsf{F}}, (I_k, [\![{x_k}]\!]_{I_k})_{k\in [n]} \Bigr ),\\ \widehat{\textsf{ct}}_{\textsf{BP}}&\xleftarrow {\$}\textsf{Eval}_{\textsf{BP}} \Bigl ( \textsf{Dec}_{\textsf{F}}(\cdot , \widehat{\textsf{ct}}_{\textsf{F}}), \textbf{pp}_{\textsf{BP}}, \textbf{pk}_{\textsf{BP}}, (j, [{\textsf{sk}_{\textsf{F}, j}}]_j)_{j\in [N]} \Bigr ). \end{aligned}$$For every \(k \in [n]\), compute$$\begin{aligned} \widehat{\textsf{ct}}^K_{\textsf{BP}, j} \xleftarrow {\$}\textsf{Eval}_{\textsf{BP}} \left( \begin{array}{l} \textsf{KValidate}^N_{\textbf{pp}_{\textsf{F}}, j, \textsf{pk}_{\textsf{F}, j}, \widehat{\textsf{ct}}_{\textsf{BP}}},\\ \textbf{pp}_\textsf{BP}, \textbf{pk}_{\textsf{BP}}, (j, ([{\textsf{sk}_{\textsf{F}, j}}]_j, [{r_{\textsf{KG}, j}}]_j)) \end{array} \right) . \end{aligned}$$Output$$\begin{aligned} \widehat{\textsf{ct}}^C_{\textsf{BP}, k} \xleftarrow {\$}\textsf{Eval}_{\textsf{BP}} \left( \begin{array}{l} \textsf{CValidate}_{\textsf{pk}_{\textsf{F}, I_k}, [\![{x_k}]\!]_{I_k}, \widehat{\textsf{ct}}_{\textsf{BP}}},\\ \textbf{pp}_{\textsf{BP}}, \textbf{pk}_{\textsf{BP}}, (I_k, [{r_{\textsf{Enc}, k}}]_{I_k}) \end{array} \right) . \end{aligned}$$$$\begin{aligned} \widehat{\textsf{ct}}\xleftarrow {\$}\textsf{Eval}_{\textsf{F}} \left( \begin{array}{l} \textsf{Dec}_{\textsf{BP}}(\cdot , \textsf{CombineDec}^{N,N+n}_{\widehat{\textsf{ct}}_{\textsf{BP}}}(\cdot , \{\widehat{\textsf{ct}}^K_{\textsf{BP}, j}\}_{j\in [N]} \cup \{\widehat{\textsf{ct}}^C_{\textsf{BP}, k}\}_{k\in [n]})),\\ \textbf{pp}_{\textsf{F}}, \textbf{pk}_\textsf{F}, (j, [\![{\textsf{sk}_{\textsf{BP}, j}}]\!]_j)_{j\in [N]} \end{array} \right) . \end{aligned}$$
-
\(\textsf{Dec}_{\textsf{mCP}}(\textbf{sk}, \widehat{\textsf{ct}})\): Parse each \(\textsf{sk}_j\) as \(\textsf{sk}_{\textsf{F}, j}\). Output \(\widehat{x}:=\textsf{Dec}_{\textsf{F}}(\textbf{sk}_{\textsf{F}}, \widehat{\textsf{ct}})\).
-
\(\textsf{Ext}_{\textsf{mCP}}(\textbf{pp}^*,i, \textsf{pk}^*_i, \textsf{ct}^*_i)\): Parse each \(\textsf{pp}^*_j\) as \((\textsf{pp}_{\textsf{F},j}^*, \textsf{pp}_{\textsf{BP},j}^*)\), \(\textsf{pk}^*_i\) as \((\textsf{pk}_{\textsf{F}, i}^*, \textsf{pk}_{\textsf{BP}, i}^*, [{\textsf{sk}_{\textsf{F}, i}}]^*_i, [{r_{\textsf{KG}, i}}]^*_i, [\![{\textsf{sk}_{\textsf{BP}, i}}]\!]^*_i)\), and \(\textsf{ct}^*_i\) as \(([\![{x}]\!]^*_i, [{r_{\textsf{Enc},i}}]^*_i)\). ExtractCheck whether \((\textsf{pk}_{\textsf{F}, i}^*, \textsf{sk}_{\textsf{F}, i}^*) = \textsf{KG}_{\textsf{F}}(\textbf{pp}_{\textsf{F}}^*, i; r_{\textsf{KG}, i}^*)\) and there exists \(x' \in \{0,1\}\) such that \([\![{x}]\!]^*_i = \textsf{Enc}_{\textsf{F}}(\textsf{pk}_{\textsf{F},i}^*, x'; r^*_{\textsf{Enc},i})\). If the check passes, then output \(x'\). Otherwise, output 0.$$\begin{aligned} \textsf{sk}_{\textsf{F}, i}^*&:= \textsf{Ext}_{\textsf{BP}}(\textbf{pp}_{\textsf{BP}}^*, i, \textsf{pk}_{\textsf{BP}, i}^*, [{\textsf{sk}_{\textsf{F}, i}}]^*_i),\\ r_{\textsf{KG}, i}^*&:= \textsf{Ext}_{\textsf{BP}}(\textbf{pp}_{\textsf{BP}}^*, i, \textsf{pk}_{\textsf{BP}, i}^*, [{r_{\textsf{KG}, i}}]^*_i),\\ r_{\textsf{Enc}, i}^*&:= \textsf{Ext}_{\textsf{BP}}(\textbf{pp}_{\textsf{BP}}^*, i, \textsf{pk}_{\textsf{BP}, i}^*, [{r_{\textsf{Enc}, i}}]^*_i). \end{aligned}$$
-
\(\textsf{Sim}_{\textsf{mCP}}(\textbf{pp}^*, \textbf{pk}^*, (I_k, \textsf{ct}_k^*)_{k\in [n]}, b^{*})\): If there exists \(j \in [N]\) such that \(\textsf{pp}^*_j \notin [\textsf{dSetup}_{\textsf{mCP}}(1^\lambda ,1^N, j)]\) holds, then output \(\bot \) and terminate. Otherwise, parse each \(\textsf{pp}_j^*\) as \((\textsf{pp}_{\textsf{F}, j}^*, \textsf{pp}_{\textsf{BP}, j}^*)\), each \(\textsf{pk}_j^*\) as \((\textsf{pk}_{\textsf{F}, j}^*, \textsf{pk}_{\textsf{BP}, j}^*, [\![{\textsf{sk}_{\textsf{BP}, j}^*}]\!]_j, [{\textsf{sk}_{\textsf{F}, j}}]^*_j, [{r_{\textsf{KG}, j}}]^*_j)\), and each \(\textsf{ct}_k^*\) as \(([\![{x_k}]\!]^*_{I_k}, [{r_{\textsf{Enc},k}}]^*_{I_k})\). Compute \(\widehat{\textsf{ct}}_{\textsf{BP}}^* \xleftarrow {\$}\textsf{Sim}_{\textsf{BP}}(\textbf{pp}_{\textsf{BP}}^*, \textbf{pk}_{\textsf{BP}}^*, (j, [{\textsf{sk}_{\textsf{F}, j}}]^*_j))_{j\in [N]}, b^{*})\). For every \(j \in [N]\), computeFor every \(k \in [n]\), compute$$\begin{aligned} \textsf{sk}_{\textsf{F}, j}^*&:=\textsf{Ext}_{\textsf{BP}}(\textbf{pp}_{\textsf{BP}}^*, j, \textsf{pk}_{\textsf{BP}, j}^*, [{\textsf{sk}_{\textsf{F}, j}}]^*_j),\\ r_{\textsf{KG}, j}^*&:=\textsf{Ext}_{\textsf{BP}}(\textbf{pp}_{\textsf{BP}}^*, j, \textsf{pk}_{\textsf{BP}, j}^*, [{r_{\textsf{KG}, j}}]^*_j),\\ \textsf{out}^{*K}_j&:= {\left\{ \begin{array}{ll} \widehat{\textsf{ct}}_{\textsf{BP}}^* &{} \text {if } (\textsf{pk}_{\textsf{F}, j}^*, \textsf{sk}_{\textsf{F}, j}^*) = \textsf{KG}_{\textsf{F}}(\textbf{pp}_{\textsf{F}}, j; r_{\textsf{KG}, j}^*)\\ 0 &{} \text {otherwise} \end{array}\right. },\\ \widehat{\textsf{ct}}_{\textsf{BP}, j}^{*K}&\xleftarrow {\$}\textsf{Sim}_{\textsf{BP}} \Bigl (\textbf{pp}_{\textsf{BP}}^*, \textbf{pk}_{\textsf{BP}}^*, (j, ([{\textsf{sk}_{\textsf{BHP}, j}}]^*_j, [{r_{\textsf{KG}, j}}]^*_j)), \textsf{out}^{*K}_j \Bigr ). \end{aligned}$$Output$$\begin{aligned} r_{\textsf{Enc}, k}^*&:= \textsf{Ext}_{\textsf{BP}}(\textbf{pp}_{\textsf{BP}}^*, I_k, \textsf{pk}_{\textsf{BP}, I_k}^*, [{r_{\textsf{Enc}, k}}]^*_{I_k}),\\ \textsf{out}^{*C}_k&:= {\left\{ \begin{array}{ll} \widehat{\textsf{ct}}_{\textsf{BP}}^* &{} \text {if }\exists x' \in \{0,1\} : [\![{x_k}]\!]^*_{I_k} = \textsf{Enc}_{\textsf{F}}(\textsf{pk}_{\textsf{F}, I_k}^*, x'; r_{\textsf{Enc}, k}^*)\\ 0 &{} \text {otherwise} \end{array}\right. },\\ \widehat{\textsf{ct}}_{\textsf{BP}, k}^{*C}&\xleftarrow {\$}\textsf{Sim}_{\textsf{BP}} \Bigl ( \textbf{pp}^*_{\textsf{BP}}, \textbf{pk}_{\textsf{BP}}^*, (I_k, [{r_{\textsf{Enc}, k}}]^*_k), \textsf{out}^{*C}_k \Bigr ). \end{aligned}$$$$\begin{aligned} \widehat{\textsf{ct}}^* \xleftarrow {\$}\textsf{Eval}_{\textsf{F}} \left( \begin{array}{l} \textsf{Dec}_{\textsf{BP}}(\cdot , \textsf{CombineDec}^{N,N+n}_{\widehat{\textsf{ct}}^*_{\textsf{BP}}}(\cdot , \{\widehat{\textsf{ct}}_{\textsf{BP}, j}^{*K}\}_{j\in [N]} \cup \{\widehat{\textsf{ct}}_{\textsf{BP}, k}^{*C}\}_{k\in [n]})),\\ \textbf{pp}_{\textsf{F}}^*, \textbf{pk}_{\textsf{F}}^*, (j, [\![{\textsf{sk}_{\textsf{BP}, j}}]\!]^*_j)_{j\in [N]} \end{array} \right) . \end{aligned}$$
5 Maliciously circuit-private MPC based on LWE
5.1 Definitions for MPC
-
Privacy against clients For every adversary \(\mathcal {A}\) corrupting parties \(\{P_i\}_{i\in T}\) with \(|T|=t<N\), for all N-input functions \(F\in \mathcal {C}\) and for all input sets \(\textbf{x}=(x_1,\ldots ,x_N)\) and \(\textbf{x}'=(x_1',\ldots ,x_N')\) such that \(x_i=x_i'\) for any \(i\in T\), for all y the range of F,$$\begin{aligned}{}[\textsf{View}_{\Pi , \mathcal {A}}(F, \textbf{x}): y=F(\textbf{x})] \approx _c [\textsf{View}_{\Pi , \mathcal {A}}(F, \textbf{x}'): y=F(\textbf{x}')]. \end{aligned}$$
-
Privacy against a server For every server S, for all N-input functions \(F\in \mathcal {C}\) and for all input sets \(\textbf{x}=(x_1,\ldots ,x_N)\) and \(\textbf{x}'=(x_1',\ldots ,x_N')\) such that \(x_{i}=x_{i}'\) for any \(i\in T\), for all y the range of F,$$\begin{aligned}{}[\textsf{View}_{\Pi , S}(F, \textbf{x}): y=F(\textbf{x})] \approx _c [\textsf{View}_{\Pi , S}(F, \textbf{x}'): y=F((\textbf{x}')]. \end{aligned}$$
5.2 Construction
-
Let \(\textsf{MKHE}_{\textsf{mCP}} = (\textsf{dSetup}_{\textsf{mCP}}, \textsf{KG}_{\textsf{mCP}}, \textsf{Enc}_{\textsf{mCP}}, \textsf{Eval}_{\textsf{mCP}}, \textsf{Dec}_{\textsf{mCP}})\) be a maliciously circuit-private MKFHE scheme with distributed setup.
-
Let \(\textsf{OT}= (\textsf{Q}, \textsf{A}, \textsf{D})\) be a maliciously sender-private OT protocol.
-
Let \(\textsf{GC}= (\textsf{GCircuit}, \textsf{GEval})\) be a projective circuit garbling scheme.
-
Inputs and outputs: The clients \(P_{i}\) (\(i=1,.,N\)) is given \(x_{i}\) as input, and the server S is given a function F on N inputs. Each \(P_{i}\) outputs \(F(x_{1},., x_{N})\) while S outputs \(\bot \).
-
Round 1: For \(i\in [N]\), the client \(P_i\) computes \(\textsf{pp}_{i}\xleftarrow {\$}\textsf{dSetup}_{\textsf{mCP}}(1^\lambda , 1^N, i\in [N])\), and broadcasts \(\textsf{pp}_{i}\) to other parties and the server S. Each of the parties \(P_i\) and the server S checks if \(\textsf{pp}_j \in [\textsf{dSetup}_{\textsf{mCP}}(1^\lambda ,1^N, j)\) for all \(j \in [N]\). If the check fails, the parties abort the protocol. Let \(\textbf{pp}:=(\textsf{pp}_j)_{j\in [N]}\).
-
Round 2: For \(i\in [N]\), the client \(P_i\) runs \((\textsf{pk}_{i}, \textsf{sk}_{i})\xleftarrow {\$}\textsf{KG}_{\textsf{mCP}}(\textbf{pp}, i; r_{\textsf{KG}, i})\). Let s and r be the bit-size of \(\textsf{sk}_{i}\) and \(r_{\textsf{KG}, i}\), respectively. The client \(P_i\) computes \((q_{i}^{k}, \textsf{st}_{i}^{k})\xleftarrow {\$}\textsf{Q}(1^{\lambda }, \textsf{sk}_{i, k})\) for \(k\in [s]\) (where \(\textsf{sk}_{i, k}\) is the k-th bit of \(\textsf{sk}_{i}\)), and \((q_{i}^{s+k}, \textsf{st}_{i}^{s+k})\xleftarrow {\$}\textsf{Q}(1^{\lambda }, r_{\textsf{KG}, i, k})\) for \(k\in [r]\) (where \(r_{\textsf{KG}, i, k}\) is the k-th bit of \(r_{\textsf{KG}, i}\)). Also \(P_{i}\) computes a ciphertext \(\textsf{ct}_{i}\xleftarrow {\$}\textsf{Enc}_{\textsf{mCP}}(\textsf{pk}_{i}, x_{i})\), and sends \((\textsf{pk}_{i}, \textsf{ct}_{i}, (q_{i}^{k})_{k\in [s+r]})\) to the server S.
-
Round 3: The input of the server S is a function F that takes on inputs \(\textbf{x}=(x_1,\ldots ,x_N)\). The server S selects a circuit C representing the function F. It then computes \(\widehat{\textsf{ct}}\xleftarrow {\$}\textsf{Eval}_{\textsf{mCP}}(C, \textbf{pp}, \textbf{pk}, (\textsf{ct}_j)_{j \in [N]})\), where we denote \(\textbf{pk}:=(\textsf{pk}_{j})_{j\in [N]}\). Let \(g_{\widehat{\textsf{ct}}, \textbf{pp}, \textbf{pk}}\) be the following circuit:where we denote \(\textbf{sk}:= (\textsf{sk}_j)_{j \in [N]}\). The server S then generates a garbled circuit \((G, e)\xleftarrow {\$}\textsf{GCircuit}(1^{\lambda }, g_{\widehat{\textsf{ct}}, \textbf{pp}, \textbf{pk}})\), where \(e=(X_{j}^{0}, X_{j}^{1})_{j \in [N(r+s)]}\). For each \(i\in [N]\) and \(k\in [r+s]\), the server S computes \(a_{i}^{k} \xleftarrow {\$}\textsf{A}(q_{i}^{k}, X_{(i-1)(r+s)+k}^{0}, X_{(i-1)(r+s)+k}^{1})\). It finally sends \((G, (a_{i}^{k})_{k \in [r + s]})\) to the client \(P_{i}\) for each \(i\in [N]\).$$\begin{aligned}&g_{\widehat{\textsf{ct}}, \textbf{pp}, \textbf{pk}}((\textsf{sk}_{j}, r_{j})_{j\in [N]})\\&:= {\left\{ \begin{array}{ll} \textsf{Dec}(\textbf{sk}, \widehat{\textsf{ct}}) &{} \text {if }(\textsf{pk}_{j}, \textsf{sk}_{j})=\textsf{KG}_{\textsf{mCP}}(\textbf{pp}, j; r_{j}) \text { for all }j\in [N]; \\ \bot &{} \text {otherwise}\\ \end{array}\right. }, \end{aligned}$$
-
Round 4: For \(i\in [N]\), \(P_{i}\) computes the garbled input \(X_{(i-1)(r+s)+k}=\textsf{D}(a_{i}^{k}, \textsf{st}_{i}^{k})\) for \(k\in [s+r]\). The client \(P_{i}\) broadcasts these to all the other clients, \(P_{j}\) for \(j\in [N]\backslash \{i\}\). Each client computes \(y:=\textsf{GEval}(G, (X_{j})_{j \in [N(r+s)]})\).
-
Step 1: The simulator \(\mathcal {S}\) receives \(\textsf{pp}_{j}^{*}\) for \(j\in T=[N]\) from \(\mathcal {A}\). Denote \(\textbf{pp}^* := (\textsf{pp}_j^*)_{j \in [N]}\).
-
Step 2: Given \((\textsf{pk}_{i}^*, \textsf{ct}_{i}^*, (q_{i, k}^*)_{k\in [r+s]})_{i\in T}\) from \(\mathcal {A}\), \(\mathcal {S}\) runs \(\textsf{Ext}_{\textsf{mCP}}\) to compute the corrupted input \(\tilde{x_{i}}:=\textsf{Ext}_{\textsf{mCP}}(\textbf{pp}^*, i, \textsf{pk}_i^*, \textsf{ct}_i^*)\). It then submits them to the ideal functionality \(\mathcal {F}\) and obtains \(b^*:=F(\tilde{x}_1,\ldots , \tilde{x}_N)\).
-
Step 3: Denote \(\textbf{pk}^*=(\textsf{pk}_{j}^*)_{j\in [N]}\). The simulator \(\mathcal {S}\) runs \(\textsf{Sim}_{\textsf{mCP}}\) to computethen defines a circuit$$\begin{aligned} \widehat{\textsf{ct}}^* \xleftarrow {\$}\textsf{Sim}_{\textsf{mCP}}(\textbf{pp}^*, \textbf{pk}^*, (j, \textsf{ct}_{j}^*)_{j\in [N]}, b^{*}), \end{aligned}$$The simulator generates a garbled circuit \((G^*, e^*)\xleftarrow {\$}\textsf{GCircuit}(1^\lambda , g_{\widehat{\textsf{ct}}^*, \textbf{pp}^*, \textbf{pk}^*})\) where \(e^* = (X^{*0}_{j}, X^{*1}_j)_{j \in [N (r+s)]}\). For all \(i\in [N]\) and \(k\in [r+s]\), the simulator \(\mathcal {S}\) computes \(a_{i,k}^{*} \xleftarrow {\$}\textsf{A}(q^{*k}_i, X^{*0}_{(i-1)(r+s)+k}, X^{*1}_{(i-1)(r+s)+k})\), and sends \((G^*, (a_{i,k}^{*})_{k \in [r+s]})\) for \(i\in T\) to \(\mathcal {A}\).$$\begin{aligned}&{g_{\widehat{\textsf{ct}}^*, \textbf{pp}^*, \textbf{pk}^*}((\textsf{sk}_{j}, r_{j})_{j\in [N]}) }\\&\quad := {\left\{ \begin{array}{ll} \textsf{Dec}_{\textsf{mCP}}(\textsf{sk}_1, \ldots , \textsf{sk}_N, \widehat{\textsf{ct}}^*) &{} \begin{aligned} \text {if } (\textsf{pk}_{j}^*, \textsf{sk}_{j})=\textsf{KG}_{\textsf{mCP}}(\textbf{pp}^*, j; r_{j})\\ \text { for all }j\in [N] \end{aligned}\\ 0 &{} \text {otherwise} \end{array}\right. }. \end{aligned}$$
-
Output: In Round 4 of the protocol, no interaction between the server S and the clients \(P_i\) occurs. Since we are assuming that all clients are corrupted and controlled by \(\mathcal {A}\), the simulator \(\mathcal {S}\) need not do any action until \(\mathcal {A}\) returns the outputs of the corrupted parties. Finally, when \(\mathcal {A}\) terminates with the outputs of the corrupted parties in the real-world execution of \(\Pi \), \(\mathcal {S}\) just forwards the received outputs and terminates.