Verifiable Multi-party Computation with Perfectly Private Audit Trail

Abstract

We propose an efficient protocol for the evaluation of functions getting their inputs from multiple parties in a way that guarantees the result correctness. In our setting, a worker is trusted with the confidentiality of the inputs and, given this assumption, our protocol guarantees perfect privacy to the clients.

Our protocol offers an interesting middle ground between traditional verifiable computation protocols, that usually do not come with privacy guarantees and focus on one or a small number of clients, and secure multi-party computation protocol that distribute the privacy trust between a number of parties, at the cost of much more expensive protocols (especially for $\mathsf {NP}$ functions and functions that do not admit an efficient static circuit representation) and a demanding infrastructure of independently managed servers interacting in multiple rounds. By contrast, our protocol is single-pass: the clients submit their inputs asynchronously, and everyone can collect the result at any later time.

We present three unrelated applications of our technique: solving a system of linear equations, an auction scheme and the search of the shortest path in a shared graph. These examples illustrate the ease of use and the advantage in terms of complexity of our approach. We made a prototype implementation that illustrates the practicality of our solution.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

We investigate the well-known problem of a set of clients holding private inputs and looking for an efficient solution for the evaluation of a function of these inputs.

In most practical cases, e.g., auctions, health information management systems, benchmarking services, or cloud services in general, this problem is handled by delegating all the confidential inputs to a trusted third party, or worker, who is in charge of computing and distributing the output of the computation to the clients. The trust encompasses two different aspects: the correctness of the computation, and the confidentiality of the inputs.

Several important lines of work addressed these two forms of trust in different settings. Secure Multi-Party Computation ($\mathsf {SMC}$) addresses the confidentiality issue by distributing the computation between several workers (who can also be the clients) and often also addresses the correctness aspect through zero-knowledge proofs. Despite tremendous improvements in terms of efficiency that happened during the last few years, e.g., through the “SPDZ” protocol of Damgård et al. [1] and its publicly verifiable improvement proposed by Baum et al. [2], there remain important practical obstacles to the broad deployment of these techniques. First, a large computational and communication overhead seems inevitable due to the need to perform the whole computation process step by step in a distributed fashion. This concern becomes even stronger when the function that needs to be evaluated does not admit a simple static circuit representation, as it is the case when efficient solutions require non-uniform data-dependent branching (see examples from Aly et al. for instance [3]). Besides, from an organizational point of view, it is often difficult to obtain that the various workers independently deploy and manage servers on a common high-speed network. For example, the sugar beet auction in Denmark [4] was performed between three parties representing farmers, buyers and the $\mathsf {SMC}$ project promoters, who were trusted by all the clients. This is also the case in some cryptographic voting systems such as Helios [5] where, despite the simplicity of the function that is evaluated (a sum), the tallying is performed by a small set of trustees sharing the private key of a distributed encryption scheme.

As a second line of work, Verifiable Computation ($\mathsf {VC}$) addresses this infrastructure problem by investigating solutions based on a single worker, who could be a cloud service provider. For instance, the “Pinocchio” protocol proposed by Parno et al. [6], and its refinement “Gepetto” [7] are highly efficient solutions that offer public verifiability in a single client-worker setting. However the protocol does not aim at providing privacy of the inputs. Even more efficient than “Pinocchio”, Backes et al. [8] developed a three-party protocol where a worker is requested to prove computations to a client over authenticated data received from a single trusted source. The construction of Parno has also been used by Zhang et al. [9] in “Alitheia”, a single-client verifiable computation system for graph problems such as the shortest path studied in this paper.

The addition of confidentiality constraints in VC, that is, considering a single worker that is not trusted for confidentiality, has been formalized by Gennaro et al. [10] in the single client setting, then extended by Choi et al. [11] who achieve non-interactive multi-client verifiable computation by relying on garbled circuits, oblivious transfer and fully homomorphic encryption. In the follow-up works of Goldwaser et al. [12] and Gordon et al. [13], the solution uses functional encryption and indistinguishability obfuscation. These works have a largely theoretical flavor, and do not provide any concrete efficiency analysis.

Our Contributions. Our setting aims at practical solutions and focuses on an interesting middle-ground between the two forms of $\mathsf {VC}$ described above. Our unique worker performs verifiable computation, and the proof of correctness of its outputs preserves the privacy of the inputs (in an information theoretic way). Still, our worker is trusted to preserve the privacy of the inputs.

Trusting the worker for confidentiality has serious practical benefits: the worker is able to compute efficiently on cleartext data, and the function evaluation therefore does not come with any overhead. The proof of correctness is based on cryptographic primitives but, in many practical applications, is considerably cheaper than the computation itself: these applications include most problems in NP, and even simple standard problems like sorting. Besides, it makes it possible to perform the computation using highly sophisticated algorithms, circumventing issues related to functions that do not have a static circuit representation, and allowing the worker to use its own proprietary and confidential solution.

The level of interaction in our protocol is minimal: the clients submit their inputs to the worker as a single message, and the result and a single publicly verifiable proof is made available at the end of the computation. This makes our solution practical even for applications based on a web interface, which clients could use to submit their input, and later retrieve the outcome of the computation.

We define the security properties of our scheme through ideal functionalities for secure function evaluation. Our protocol guarantees the correctness of the output, even if the worker is corrupted. Furthermore, our protocol guarantees information theoretic privacy if the worker is honest.

We illustrate our technique via three test applications: solving a system of linear equations, electronic auctions and finding the shortest path in a graph. Finally, we give some insight on the performances obtained for these applications by a prototype implementation realized in Python.

Related Works. Besides the works described above, and very close to our technique, Rabin et al. [14, 15] present a secrecy-preserving proof of correctness scheme for the evaluation of any function with straight line computation through an agreed public circuit. Indeed, similar to what is done in this paper, they propose to perform the proof of correctness on the commitments on the inputs of the function. A parallel circuit is evaluated by a worker on the commitments and every operation is validated by a zero-knowledge proof of knowledge. While the schemes proposed there rely on symmetric cryptography and a split-value representation to perform cut-and-choose proofs, we show in this work better timing results as well as more compact proofs using homomorphic cryptography based on elliptic curves.

2 Verifiable Multi-party Function Evaluation

The Ideal Protocol. In this section, we specify our protocol in terms of an ideal functionality, following the notations and definitions of Canetti [16]. We will then require our protocol to offer the same security features as that functionality.

In this regard, let us consider a set of clients $\mathcal {C}=\lbrace C_1,\ldots ,C_n\rbrace$. Each $C_i$ has a private input $x_i\in I$, the input space. We define our ideal functionality $\mathcal {F}_{}^f$ as a process that privately receives inputs from the clients and then evaluates the function $f:I^n\rightarrow O$ on these inputs (O is the output space), and outputs that result to all parties. So, correctness is always guaranteed by this functionality.

We consider two corruption models for our protocol, which lead to two flavors of our functionality. In the case of a honest-but-curious (also often called “passive”) adversary $\mathcal {A}_p$, that is, an adversary who learns the internal state of the corrupted parties but lets them follow the protocol, the functionality $\mathcal {F}_{\mathcal {A}_p}^f$ also guarantees that the clients do not learn anything about each other’s inputs (apart from what might be derived from the output of the function). In the case of an active adversary $\mathcal {A}_a$, correctness remains guaranteed, but the client’s inputs are leaked to the adversary, and confidentiality is therefore not guaranteed anymore.

The Real Protocol. We now turn to the design of our real-world protocol, that realizes the ideal functionalities.

We require our protocol to produce a perfectly private audit trail ($\mathsf {PPAT}$) of its computation, that is, the privacy guarantees offered by our protocol will be perfect in the sense of information theory. For simplicity, we focus on the case of static corruption: corruption of parties happen before the beginning of the protocol, and not dynamically as the protocol executes.

We build the protocol $\varPi _{\mathsf {PPAT}}^f$ which realizes these functionalities in the real world in the presence of honest-but-curious and active adversaries. In this protocol, most of the work of the functionality is performed by an entity called the Worker $\mathcal {W}$. However, contrary to the ideal functionality, the worker can be corrupted by the adversary and, in the case of an active adversary, might be willing to evaluate a function different of f.

Designing a protocol that implements our functionality in the presence of an honest-but-curious adversary is fairly immediate: clients hand their inputs to the worker through a secure channel (which can be realized by means of a $\mathsf {CPA}$-secure encryption scheme), then the worker simply outputs the result.

The case of an active adversary is more demanding: in order to make sure that an invalid output of the worker will not be accepted by the clients, our protocol requires the worker to provide a proof of the correctness of the output. And, in order to ensure that every client receives the same result at the end of the protocol, this proof will be posted on a Public Bulletin Board $\mathbf{PB }$, which maintains publicly available every input sent to him by any parties.

The most immediate way of building the proof would be to use zero-knowledge proofs computed from the encrypted inputs of the clients. This has two downsides, however. In terms of efficiency, secure encryption is length increasing, which will typically lead to more expensive proofs, since they need to apply to larger statements. In terms of security, the ciphertexts that will be needed to verify the proofs are only computationally hiding, meaning that the inputs of the client will eventually become available through data that are published as part of the protocol.

An alternative approach, which we adopt, is to work on perfectly hiding commitments: they do not need to be length increasing, potentially leading to more efficient proofs, and they do not cause any weakening of privacy. Perfectly hiding commitments can only be computationally binding, but this is a much lower concern, since the workers only have a relatively short period of time for producing their proofs, making any future computational breakthrough innocuous.

So, our protocol will rely on a commitment scheme, that is, a triple of algorithms $\varPi _\mathsf {C}:=(\mathsf {Gen}_\mathsf {C},\mathsf {Com},\mathsf {Verify})$. Algorithm $\mathsf {Com}$, on input x and public key $\mathsf {cpk}$ generated by $\mathsf {Gen}_\mathsf {C}$, produces d, o where d is the commitment and o is the opening value used afterwards to open the commitment through the $\mathsf {Verify}$ algorithm. The perfectly hiding property of the commitment scheme means that for any commitment d, we can find, for any value x in the input space, an opening o such that $\mathsf {Verify}(d,o,x)$ accepts. In other words, it implies that no single piece of information from x could be extracted from d. We also require the commitments to be computationally binding: it must be hard to produce a commitment d, two messages $x \ne x'$ and two opening values o, $o'$ on which d can be opened.

As a first step in our protocol, the clients send a commitment $d_i\leftarrow \mathsf {Com}(x_i)$ on their private inputs $x_i$ to $\mathbf{PB }$. Along with the commitment $d_i$, each client must produce a proof denoted $\mathsf {\pi }_{\mathsf {ver}} (d_i)$ that ensures non-malleability [17], under the form of a $\varSigma$-proof of knowledge (see [18]). Non-malleability will be used to enforce the independence of the inputs posted by the clients [18], preventing one client from choosing his input as a function of someone else’s input, which could have devastating effects in some contexts (e.g., auctions). In some cases, the proof $\mathsf {\pi }_{\mathsf {ver}} (d_i)$ can also be designed to be more than just a proof of knowledge: for instance, a $\varSigma$-proof of membership can be used to ensure the validity of $x_i$.

In parallel with the posting of these commitments and proofs, all clients submit an opening of their commitment to the worker $\mathcal {W}$, using a private channel. From these inputs, $\mathcal {W}$ posts the evaluation of f on $\mathbf{PB }$. And, in order to capture an actively corrupted $\mathcal {W}$, we require that $\mathcal {W}$ also publishes a proof denoted $\mathsf {\pi }_{\mathsf {cor}}$ of the correctness of the evaluation y of f on the inputs. The key point is that the verification of $\mathsf {\pi }_{\mathsf {cor}}$ relies on the commitments $d_1, \dots , d_n$ posted by the clients on $\mathbf{PB }$. In the general case, this verification involves the computation of a commitment $d_y$ that must be a commitment on y computed from $d_1, \dots ,d_n$. With this requirement, an active adversary who would be willing to cheat during the function evaluation process would need to be able to break the binding property of the commitment scheme or the soundness of the proof $\mathsf {\pi }_{\mathsf {cor}}$.

Protocol $\varvec{\varPi }_\mathbf{PPAT}^{{\varvec{f}}}$ and Formal Security. The proofs we are referring to here are built from the notion of sigma (or $\varSigma$)-protocols [19]. In the following, we define relations R in a formal $\mathsf {NP}$-language such as $R \subset \mathcal {L}_\mathsf {NP}\times W(s)$ where s is called the statement and $w\in W(s)$ a witness of s.

We rely on the Fiat-Shamir/Blum transformation [20, 21] to turn $\varSigma$-protocols into non-interactive zero-knowledge proofs of knowledges ($\mathsf {NIZKPK}$). This heuristic relies on the existence of an efficient hash function which is used to create the challenge of the $\varSigma$-protocol. Careful attention must be paid on the choice of the values thrown into the hash function [18].

Definition 1

(Non-interactive Zero-Knowledge Proof of Knowledge). A Non-Interactive Zero-Knowledge Proof of Knowledge $\pi$ for a relation R on an $\mathsf {NP}$-language $\mathcal {L}_\mathsf {NP}$ is a couple of efficient algorithms $(\mathsf {Prove},\mathsf {Check})$ such that:

• $\mathsf {Prove}(s,w)$: on inputs $(s,w)\in R$, outputs a transcript $\mathfrak {t}$.

• $\mathsf {Check}(s,\mathfrak {t})$: on inputs a statement s and a transcript $\mathfrak {t}$, outputs 0 or 1.

where $\mathsf {Prove}$ is probabilistic and $\mathsf {Check}$ is deterministic. The next properties hold:

• Completeness: $\forall (s,w)\in R, \forall \mathfrak {t}\leftarrow \mathsf {Prove}(s,w)$, we have that $\mathsf {Check}(s,\mathfrak {t})=1$ with overwhelming probability.

• Soundness: there exists a polynomial time extractor E such that, when E receives on inputs two valid transcripts $\mathfrak {t},\mathfrak {t}'$ with respect to the same s, E returns a correct witness w.

• Perfect Zero-Knowledge: there exists a probabilistic polynomial time simulator $\mathcal {M}$ that produces simulated transcripts that are perfectly indistinguishable from real transcripts produced through the $\mathsf {Prove}$ algorithm.

The parties involved in the protocol $\varPi _{\mathsf {PPAT}}^f$ will publish on $\mathbf{PB }$ transcripts of $\mathsf {NIZKPK}$ to prove some relations. We describe in Sect. 3 the relations we aim to prove and how to build specific proofs for our applications.

The relations for the $\mathsf {NIZKPK}$ $\mathsf {\pi }_{\mathsf {cor}}$ and $\mathsf {\pi }_{\mathsf {ver}} (d_i)$ mentioned in $\varPi _{\mathsf {PPAT}}^f$ are defined as follows: $R^{\mathsf {cor}} := \lbrace ((y,d_1,\ldots ,d_n),(x_1,o_1,\ldots ,x_n,o_n)) \vert y = f(x_1,\ldots ,x_n) \bigwedge _i \mathsf {Verify}(d_i,o_i,x_i)=1 \rbrace$ and $R^{\mathsf {ver}} := \lbrace (d,(x,o)) \vert \mathsf {Verify}(d,o,x)=1 \wedge x \in I \rbrace$

where the algorithm $\mathsf {Verify}(d,o,x)$ of the commitment scheme returns 1 only if d is a commitment on x with opening o.

These proofs are published on $\mathbf{PB }$ and $\mathsf {\pi }_{\mathsf {cor}}$ will be checked by each $C_i$ at the end of the protocol to convince itself of the correctness of the function’s computation. We are now ready to define protocol $\varPi _{\mathsf {PPAT}}^f$ which realizes functionalities $\mathcal {F}_{\mathcal {A}_p}^{f}$ and $\mathcal {F}_{\mathcal {A}_a}^{f}$ in the presence of $\mathcal {A}_p$ and $\mathcal {A}_a$ respectively.

We show in Sect. 3.3 how to build protocol $\varPi _{\mathsf {PPAT}}^f$ for any function f and how $\mathcal {W}$ can prepare the proof $\mathsf {\pi }_{\mathsf {cor}}$. Note that, in step 2, it is crucial for $\mathcal {W}$ to verify that the commitments on $\mathbf{PB }$ are consistent with the private inputs. Indeed, if a cheating client published a commitment that is not consistent with his private input, then $\mathcal {W}$ will not be able to provide a correct proof $\mathsf {\pi }_{\mathsf {cor}}$ on the result since this proof is bound to the commitments. In the full version of this paper, we point out two modifications of the protocol that achieve slightly different functionalities. The first one keeps the outcome y secret so that the function evaluation can be used as a subroutine of a larger function without revealing intermediary results. The second one aims at encountering active adversaries that dynamically chooses the inputs of the corrupted clients as a function of the inputs of honest clients.

One can see that the security of the protocol in the presence of a passive adversary $\mathcal {A}_p$ rests on the fact that every piece of information present on $\mathbf{PB }$ is either perfectly hiding or zero-knowledge. However, in the presence of an active adversary $\mathcal {A}_a$ the privacy of the scheme is not guaranteed: a corrupted worker could disclose all the client inputs. Nevertheless, in this scenario, we assert that the verifiability property still stands. In other words, $\mathcal {A}_a$ could leak the private inputs but is not able to tamper with the correctness of the function evaluation.

Our first result shows that protocol $\varPi _{\mathsf {PPAT}}^f$, executed with an ideal bulletin board, realizes the functionality $\mathcal {F}_{\mathcal {A}_p}^f$ in the presence of passive adversary $\mathcal {A}_p$, and has a perfectly private audit trail.

Theorem 1

Let $\varPi _\mathsf {C}:=(\mathsf {Gen}_\mathsf {C},\mathsf {Com},\mathsf {Verify})$ be a perfectly hiding commitment scheme and $\mathsf {\pi }_{\mathsf {cor}}$ and $\mathsf {\pi }_{\mathsf {ver}}$ be perfect zero-knowledge proofs. Then, for any set of corrupted clients, there is a simulator such that, for any environment, the views resulting from the following two situations are identical:

• interacting with the bulletin board, the clients and the worker playing the $\varPi _{\mathsf {PPAT}}^f$ protocol.

• interacting with the ideal functionality $\mathcal {F}_{\mathcal {A}_p}^f$ and the simulator.

The view of the environment includes its accesses to the bulletin board (controlled by the simulator in the second case), submitting the input $x_i$ to the clients (or to $\mathcal {F}_{\mathcal {A}_p}^f$), and obtaining the outcome y in return.

Proof

Informal. We proceed by a set of game hops to show that the view of the environment and the adversary is indistinguishable between the real execution of the protocol and the ideal execution simulating the functionality $\mathcal {F}_{\mathcal {A}_p}^f$. The key points are that

• 1. the commitments published on $\mathbf{PB }$ reveal no information whatsoever about the committed values.

• 2. the proofs of knowledge on $\mathbf{PB }$ are perfect zero-knowledge and cannot be used by an adversary to extract information.

• 3. the proof $\mathsf {\pi }_{\mathsf {cor}}$ present on $\mathbf{PB }$ computationally ensures the result soundness.

• 4. the three first points combined form a perfectly private audit trail of the function evaluation that is computationally sound.

The complete proof can be found in the full version of this paper.

Our second result shows that Protocol $\varPi _{\mathsf {PPAT}}^f$, executed with an ideal bulletin board, realizes the functionality $\mathcal {F}_{\mathcal {A}_a}^f$ in the presence of an active adversary $\mathcal {A}_a$ who controls the worker.

Theorem 2

Let $\varPi _\mathsf {C}:=(\mathsf {Gen}_\mathsf {C},\mathsf {Com},\mathsf {Verify})$ be a binding commitment scheme and $\mathsf {\pi }_{\mathsf {cor}}$ and $\mathsf {\pi }_{\mathsf {ver}}$ be computationally sound proofs. Then, for a corrupted worker and any set of corrupted clients, there is a simulator such that, for any environment, the views resulting from the two situations below are indistinguishable:

• interacting with the bulletin board, the clients and the corrupted worker playing the $\varPi _{\mathsf {PPAT}}^f$ protocol.

• interacting with the ideal functionality $\mathcal {F}_{\mathcal {A}_a}^f$ and the simulator.

The view of the environment includes its accesses to the bulletin board (controlled by the simulator in the second case), submitting the input $x_i$ to the clients (or to $\mathcal {F}_{\mathcal {A}_a}^f$), and obtaining the outcome y in return, and every communication that the corrupted worker would make.

Proof

Informal. The demonstration follows the same pattern of Theorem 1 with the major difference that the privacy of the inputs is no longer guaranteed due to the adversary ability to corrupt the worker. However, the soundness of the proof $\mathsf {\pi }_{\mathsf {cor}}$ remains ensuring the correctness of the result. We show that it is still essential that $\mathbf{PB }$ displays the computationally binding commitments of the clients. This condition enforces an adversary to produce a proof of knowledge on these commitments. As a result the audit trail present on $\mathbf{PB }$ is not perfectly hiding anymore but is still computationally sound.

The complete proof can be found in the full version of this paper.

3 Building Blocks for Perfectly Private Audit Trail

The interactions between the clients and the worker involve the exchange of private inputs and the publication on a Public Bulletin Board $\mathbf{PB }$ of some trail that will be used to perform further audit of the process. Depending on the properties one wants to achieve in different scenarios, we propose to use a primitive introduced by Cuvelier et al. in [22] called commitment consistent encryption. The primitive is a combination of an encryption scheme and a commitment scheme. It allows one to send its private inputs through a ciphertext while publicly committing on the same inputs for further public verification.

3.1 Commitment Consistent Encryption Scheme

A Commitment Consistent Encryption ($\mathsf {CCE}$) scheme is a traditional public key encryption scheme that offers an extra feature: from any $\mathsf {CCE}$ ciphertext, it is possible to derive a commitment on the encrypted message, and the private key can also be used to obtain an opening of that commitment.

Definition 2

(CC Encryption). A commitment consistent encryption scheme $\varPi$ is a tuple of efficient algorithms $(\mathsf {Gen}, \mathsf {Enc}, \mathsf {Dec}, \mathsf {DerivCom},$ $\mathsf {Open}, \mathsf {Verify})$ defined as follows:

• $\mathsf {Gen}(1^\lambda )$: Given a security parameter $\lambda$, output a triple $(\mathsf {pp},\mathsf {pk},\mathsf {sk})$, respectively the public parameters, the public key and the secret key.

• $\mathsf {Enc}_\mathsf {pk}(m)$: Output a ciphertext c which is an encryption using the public key $\mathsf {pk}$ of a message m chosen in the plaintext space $\mathbf {M}$ defined by $\mathsf {pp}$.

• $\mathsf {Dec}_\mathsf {sk}(c)$: From a ciphertext c, output a message m using the secret key $\mathsf {sk}$.

• $\mathsf {DerivCom}_\mathsf {pk}(c)$: Output a commitment d from a ciphertext c using $\mathsf {pk}$.

• $\mathsf {Open}_\mathsf {sk}(c)$: Output an auxiliary value o using the secret key $\mathsf {sk}$. This auxiliary value can be considered as part of an opening for a commitment.

• $\mathsf {Verify}_\mathsf {pk}(d,o,m)$: From a message m, a commitment d with respect to key $\mathsf {pk}$ and an auxiliary value o, output a bit. This algorithm checks the validity of the opening (m, o) with respect to d and $\mathsf {pk}$.

It is implicit that $\mathsf {pp}$ is given to each algorithm apart from $\mathsf {Gen}$.

• Correctness: for any $(\mathsf {pp},\mathsf {pk},\mathsf {sk})\leftarrow \mathsf {Gen}(1^\lambda )$, any message $m\in \mathbf {M}$ and any ciphertext $c\leftarrow \mathsf {Enc}_\mathsf {pk}(m)$, it holds with overwhelming probability in $\lambda$ that $\mathsf {Dec}_\mathsf {sk}(c)=m$ and that $\mathsf {Verify}_\mathsf {pk}(\mathsf {DerivCom}_\mathsf {pk}(c),\mathsf {Open}_\mathsf {sk}(c),\mathsf {Dec}_\mathsf {sk}(c))=1$.

The security properties that we can expect from the encryption part of the $\mathsf {CCE}$ scheme are the traditional ones. We refer to the work [22] for a more complete description of $\mathsf {CCE}$ scheme. This paper also presents a $\mathsf {CCE}$ scheme that is built from a Pedersen commitment and a Paillier encryption as well as two other optimal constructions of $\mathsf {CCE}$ based on elliptic curves.

In some settings such as e-voting, an homomorphic encryption scheme that allows threshold decryption is mandatory while in other settings, the encryption scheme could be superfluous when using a physically secure channel between the clients and the workers. In this last case, one may be just fine with a commitment scheme alone. However, in most cases, we are in an intermediate situation where the inputs are sent to the worker through a not-so-secure network where encryption is not a luxury. For this reason a $\mathsf {CCE}$ scheme comes in handy.

We note that, when encryption is used instead of a secure channel, we must make sure that the adversary cannot submit inputs that he actually ignores by copying $\mathsf {CCE}$ ciphertexts. This can be prevented by using the non-malleability offered by sigma proofs to prevent any re-randomization of commitments, and by declaring duplicate commitments invalid (see [22] for details).

For readability, in the rest of the paper, we do not differentiate the commitments obtained through the $\mathsf {DerivCom}$ algorithm from other commitments produced in the proofs below, and, without loss of generality, we assume that the $\mathsf {Com}$ algorithm stands either for the contraction of $\mathsf {DerivCom}(\mathsf {Enc})$ when a $\mathsf {CCE}$ scheme is used either for some commitment scheme when a secure channel is set up for the inputs transmission. In both cases, we assume a homomorphic perfectly hiding and computationally binding commitment scheme.

3.2 Non Interactive Zero-Knowledge Proof of Knowledge

The second tool that we need is non-interactive zero-knowledge proof of knowledge ($\mathsf {NIZKPK}$). Below we explicit the different relations for the proofs that we use in our construction.

The first $\mathsf {NIZKPK}$ is the classical or-proof of knowledge [23] denoted $\mathsf {\pi }_{\mathsf {or}} (d)$. Another kind of well-known $\mathsf {NIZKPK}$ is the proof of equality of discrete logarithms between two commitments [24] that we refer to as $\mathsf {\pi }_{\scriptscriptstyle \mathsf {DL}} (d_1,d_2)$. The proof of the opening of the commitment is denoted $\mathsf {\pi }_{\mathsf {ope}} (d)$. We also rely on proofs for multiplications $\mathsf {\pi }_{\mathsf {mul}} (d_1,d_2,d_3)$, on range proofs $\mathsf {\pi }_{\mathsf {ran}} (d, I)$ and on comparison proofs¹ $\mathsf {\pi }_{<} (d_1,d_2,d_3)$ which are essentially range proofs. We give the relations for these proofs respectively:

$$\begin{aligned}&R^{\mathsf {or}} :=\lbrace (d,(x,o)) \vert \mathsf {Verify}(d,o,x)=1 \wedge (x=0 \vee x=1) \rbrace \\&R^{\scriptscriptstyle \mathsf {DL}} := \lbrace ((d_1,d_2),(x,o_1,o_2)) \vert \mathsf {Verify}(d_1,o_1,x)=1 \wedge \mathsf {Verify}(d_2,o_2,x)=1 \rbrace \\&R^{\mathsf {ope}} :=\lbrace (d,(x,o)) \vert \mathsf {Verify}(d,o,x)=1 \rbrace \\&R^{\mathsf {mul}} := \lbrace ((d_1,d_2,d_3),(x_1,o_1,x_2,o_2,o_3)) \vert x_3=x_1x_2 \wedge _i \mathsf {Verify}(d_i,o_i,x_i)=1 \rbrace \\&R^{\mathsf {ran}} := \lbrace (d,(x,o)) \vert \mathsf {Verify}(d,o,x)=1 \wedge x\in I \rbrace \\&R^{<} := \lbrace ((d_1,d_2,d_3),(x_1,o_1,x_2,o_2,x_3,o_3)) \vert x_3=x_1<x_2 \wedge _i \mathsf {Verify}(d_i,o_i,x_i)=1 \rbrace \end{aligned}$$

The details of the $\varSigma$-protocols for relations $R^{\mathsf {mul}}$, $R^{\mathsf {ran}}$ and $R^{<}$ are given in the full version of this paper. Note that the soundness of the proof $\mathsf {\pi }_{\mathsf {mul}}$ relies on the binding property of the commitment scheme since $d_3$ could theoretically open to any value. A direct way to obtain a range proof that $x\in [0,2^{k+1}[$ is by composing k proofs $\mathsf {\pi }_{\mathsf {or}} (b_i)$ where $b_i$ is the binary decomposition of x.

3.3 Generic Construction of $\varPi _{\mathsf {PPAT}}^f$

Commitment consistent encryption and $\mathsf {NIZKPK}$ are the building blocks of protocol $\varPi _{\mathsf {PPAT}}^f$.

The protocol is fairly simple: each client computes a $c_i\leftarrow \mathsf {Enc}(x_i)$ of his private input. From $c_i$, $C_i$ derives a perfectly hiding commitment $d_i\leftarrow \mathsf {DerivCom}(c_i)$ and, computes a $\mathsf {\pi }_{\mathsf {ver}} (d_i)$, for example $\mathsf {\pi }_{\mathsf {or}} (d_i)$, $\mathsf {\pi }_{\mathsf {ran}} (d_i, I)$ or by default, $\mathsf {\pi }_{\mathsf {ope}} (d_i)$. Then, $C_i$ publishes $d_i$ and $\mathsf {\pi }_{\mathsf {ver}} (d_i)$ on $\mathbf{PB }$, and sends $c_i$ to $\mathcal {W}$. After having decrypted every $c_i$ to get the clients’ private inputs, $\mathcal {W}$ computes $y:=f(x_1,\ldots ,x_n)$. From the commitments published on $\mathbf{PB }$, $\mathcal {W}$ computes $d_y:=f(d_1,\ldots ,d_n)$ as well as the $\mathsf {NIZKPK}$-s for each operator of f (except for $+$ and − which are natural operators in the commitment space): the set of the $\mathsf {NIZKPK}$ and all the intermediary commitments created for the needs of the proofs are executed in parallel to form $\mathsf {\pi }_{\mathsf {cor}}$. $\mathcal {W}$ publishes y and $\mathsf {\pi }_{\mathsf {cor}}$ on $\mathbf{PB }$. Finally, each $C_i$ verifies the correctness of $\mathsf {\pi }_{\mathsf {cor}}$ in regards to y and the reconstruction of $d_y$.

As we will see in the next section, this is not the most efficient way to achieve the perfectly private audit trail since there are lots of cases where the verification of the output of the function can be done without recomputing the entire function in the commitment space.

4 Applications

Until now, we have seen how to generate a perfectly private audit trail of computation from the blueprint of any function. As we will see through several examples, there is a more direct way to provide the $\mathsf {\pi }_{\mathsf {cor}}$ that guarantees the correctness of the output. The main idea is that, once given the result of the function it is much simpler to verify that it is correct. For example, once you are told that 8128 is the square root of 66, 064, 384, it costs you only one squaring to agree while finding the square root by hand calculus is trickier.

In the following applications, we show how to use this trick to reduce the complexity of the proof for the client compared with the original complexity of the algorithm computing the result as it must be done in classical $\mathsf {SMC}$. We selected unrelated problems to illustrate the ease of application of our technique and we point out in the full version of this paper other examples that may turn into good candidates.

4.1 System of Linear Equations

The first application is solving a system of linear equations. It is involved as a subroutine in many algorithms as, among others, in the Lagrange polynomial interpolation or in linear programming techniques. In linear programming, the goal is to optimize a solution under a set of linear constraints. This kind of scenario fits very well in a multi-party setting. We illustrate it by an example in which a set of companies in a production line agree to cooperate in order to optimize the production of some goods but do not wish to divulge their internal work flow to each other. The gain for the companies is lower costs and the ability to reallocate resources. Nowadays, all the solutions impair the privacy in one way or another, thus preventing such benefits.

Consider the following system of linear equations L:

where $A\in \mathbf {M}^{m\times n}$, $B\in \mathbf {M}^{m\times 1}$, $\mathbf {M}$ is the coefficient space, and Z is the matrix of variables of dimension $(n\times 1)$. The unique solution, if it exists, is $Z_s=A^{-1}B$. When the matrix is not invertible, one might produce $Z_{nts}$ a non trivial solution of the homogeneous system $AZ=0$.

In a multi-party setting, the constraints are given by the clients. Here we consider K clients where $K=mn$. The clients are indexed by $i=(1,1),\ldots ,(m,n)$ as are the coefficients $\alpha _i$ of the matrix A. The simplest scenario is that $\alpha _i$ is the private input of client $C_i$ while the independent coefficients $b_j$ for $j=1,\ldots ,m$, are known to everyone.

Each $C_i$ computes $c_i\leftarrow \mathsf {Enc}(\alpha _i)$ and derives from it a commitment on $\alpha _i$: $d_i\leftarrow \mathsf {DerivCom}(c_i)$. The $d_i$-s are published on $\mathbf{PB }$ as well as a proof $\mathsf {\pi }_{\mathsf {ope}} (d_i)$ computed by $C_i$. The encryptions $c_i$ are passed on to $\mathcal {W}$. We can combine each $d_i$ on $\mathbf{PB }$ to form the matrix D which can be seen as a commitment on A. After having decrypted each $c_i$ to get $\alpha _i$, $\mathcal {W}$ computes the inverse matrix $A^{-1}$ with his favourite method and thus the solution $Z_s=A^{-1}B$. The worker then publishes $Z_s$ on $\mathbf{PB }$ along with $\mathsf {\pi }_{\mathsf {cor}}$. This proof consists of a list of m openings $o_1,\ldots ,o_m$ where $o_j$ is the opening of $b'_j=d_{j,1}z_1+\cdots + d_{j,n}z_n$. Indeed, to verify the result, each client computes $B':=DZ_s$ and checks that the opening of each entry of this (m, 1)-matrix is valid and that $B'$ opens on the values of B. In the case of a non trivial solution $Z_{nts}$ occurring when A is not invertible, the worker opens $B':=DZ_{nts}$ which must be a series of commitments on zero.

One might also want to include B in the private inputs of the clients. In this case, the $\mathsf {\pi }_{\mathsf {cor}}$ is a bit different. Instead of giving the openings $o_j$, $\mathcal {W}$ provides a $\mathsf {\pi }_{\scriptscriptstyle \mathsf {DL}} (b'_j,b_j)$ that $b'_j$ commits on the same value as $b_j$ for $j=1,\ldots ,m$.

$\mathsf {\pi }_{\mathsf {cor}}$ is Zero-Knowledge:

• Completeness: It is clear that, given $o_1,\ldots ,o_m$, any client can verify that $Z_s$ is indeed the solution of the linear system.

• Soundness: This relies on the computationally binding property of the commitment scheme.

• Perfect ZK: As the commitment scheme is perfectly hiding, the openings of the commitments must be uniformly distributed in the space of openings.

Complexity. For the client, the complexity cost is exactly linear in the number of clients. In fact, the complexity bottleneck of the protocol is how to find Z. Either by inverting A, by the Gauss-Jordan elimination or more efficiently by the LU decomposition method, computing $Z_s$ requires about $O(n^3)$ operations(or $O(n^{2.373}$ with the best current algorithm). It is also noteworthy that these algorithms often require branching when for example, searching the pivot in a row. However, when performed in $\mathsf {SMC}$, these operations may become costly.

4.2 Auctions

Another type of problem that benefits from our approach is electronic auctions. We consider a setting of simple auctions where n clients submit one bid each. The result of the auction consists of a list of the sorted bids. More precisely, each $C_i$ computes $c_i\leftarrow \mathsf {Enc}(x_i)$ where the bid $x_i\in I=[0,L[$. From $c_i$, $C_i$ derives $d_i\leftarrow \mathsf {DerivCom}(c_i)$ and computes $\mathsf {\pi }_{\mathsf {ran}} (d_i,I)$. While $c_i$ is sent to $\mathcal {W}$, each $C_i$ publishes $d_i$ and $\mathsf {\pi }_{\mathsf {ran}} (d_i,I)$ on $\mathbf{PB }$. $\mathcal {W}$ computes the sorted list $(x'_1,\ldots ,x'_n)$ from $(x_1,\ldots ,x_n)$ with his favourite algorithm. From the sorted list, $\mathcal {W}$ rearranges the $d_i$ to produce a sorted list of commitments $d'_1,\ldots ,d'_n$. Then, $\mathcal {W}$ computes $n-1$ commitments $e_{1},\ldots ,e_{n-1}$ where $e_i := d_i\ge d_{i+1}$ which requires $n-1$ proofs $\mathsf {\pi }_{\mathsf {ran}} (d_i-d_{i+1},\left] -L,L\right[)$ denoted $\pi _i$. Thus, $\mathsf {\pi }_{\mathsf {cor}}:=((e_1,o_1,\pi _1)\wedge \cdots \wedge (e_{n-1},o_{n-1},\pi _{n-1}))$ where $o_i$ is an opening of $r_i$ which must imply that $r_i$ commits on 1. $\mathcal {W}$ publishes $\mathsf {\pi }_{\mathsf {cor}}$ on $\mathbf{PB }$ along with $d'_1,\ldots ,d'_n$. Then, each client verifies $\mathsf {\pi }_{\mathsf {cor}}$ to validate the result of the auction.

Note that, while there is a strong guarantee for the client that the winner(s) of the auction are legitimate winner(s), the winning bid and every other bids remain perfectly private. However, if required, $\mathcal {W}$ could also have revealed the winning bids by publishing the openings of the commitments. It is possible to transform this protocol into a sorting protocol that does not reveal which client’s bid arrives in which position. This can be done by, first, randomizing the commitments on $\mathbf{PB }$ and, then, providing a proof of shuffle that the sorted list of commitments comes from the randomized list. The work of Terelius and Wilkström [25] proposes such an efficient technique that adapts our commitment consistent approach. In this way, one could use the protocol as a subroutine of an algorithm that needs sorting.

$\mathsf {\pi }_{\mathsf {cor}}$ is ZK: This is clear since $\mathsf {\pi }_{\mathsf {cor}}$ is formed by a series of $\mathsf {NIZKPK}$.

Complexity. As in the case of the linear system, the complexity for the client is linear in the number of clients. For the worker though, the highest complexity comes from the sorting algorithm (for example $O(n\log (n))$ in the case of Quicksort). However, as it is done on clear values, the cost is marginal compared with the linear number of range proofs to compute.

4.3 Shortest Path

In this third example, we aim at showing that realizing more complex protocols can be done without much difficulty. In the case of the shortest path, we consider a directed graph with m vertices and n weighted edges. The goal is to find the shortest path from a source node to a target node which is the path that minimizes the sum of the weights. We denote by $v_1,\ldots ,v_m$ the vertices, while $e^{i,j}_k$ is the edge from $v_i$ to $v_j$, numbered k in the edges list. Similarly, we denote $w^{i,j}_k$ the positive weight of edge $e^{i,j}_k$.

This problem has been studied in $\mathsf {SMC}$ since it offers a potential solution to privacy-preserving GPS guidance in which the guided person does not want to reveal its location to the service provider. In a multi-party setting involving more than two players, one can imagine the following scenario. A set of concurrent delivering companies possessing connections with spare room available for goods might be appealed to work together to offer a joined transport solution to a client without disclosing private information.

The Bellman-Ford algorithm solves the shortest path problem in O(mn) operations. This algorithm maintains two lists: a predecessors list $\varvec{pred}$ and a distances list $\varvec{dist}$. While the algorithm executes, $pred_i$ designates the predecessor vertex of $v_i$ while $dist_i$ stores the distance of $v_i$ which is the weight of the current shortest path from the source to $v_i$.

In a multi-party setting we assume that each client $C_i$ has $w_i$ as private input. It is possible to turn Bellman-Ford algorithm in its secure version using classical $\mathsf {SMC}$ or using our technique. As previously, the derived commitment $d_i\leftarrow \mathsf {DerivCom}(c_i)$ are published on $\mathbf{PB }$, while $\mathcal {W}$ gathers the $c_i\leftarrow \mathsf {Enc}(w_i)$ of the clients private inputs. Then $\mathcal {W}$ decrypts and computes the shortest path. The algorithm requires a supremum value denoted $\top$ which is the maximum weight a path might have plus one. We define $\top$ as $n.L-n+1$, where L is the bound on the weights of the edges: $w_i<L$. As a result, we also require $C_i$ to publish with $d_i$, a $\mathsf {\pi }_{\mathsf {ran}} (d_i,L)$ on $\mathbf{PB }$. This proof must later be verified by the other clients and $\mathcal {W}$.

Let us now focus on the computation of $\mathsf {\pi }_{\mathsf {cor}}$ by $\mathcal {W}$. This is done by computing Algorithm 1 on the commitments and by providing an $\mathsf {NIZKPK}$ when necessary.

The predecessor of a vertex is represented by a commitment to the number of the vertex (lines 2 and 8) as well as the commitments on 0 and $\top$ on lines 3, and 7. These commitments can be computed once and then reused when needed. Their openings should also be given in $\mathsf {\pi }_{\mathsf {cor}}$. The comparison on line 7 requires a $\mathsf {\pi }_{\mathsf {ran}}$ and the two multiplications on lines 8 require each a $\mathsf {\pi }_{\mathsf {mul}}$. All these proofs are aggregated in $\mathsf {\pi }_{\mathsf {cor}}$.

$\mathsf {\pi }_{\mathsf {cor}}$ is ZK: This is clear by the generic construction of $\mathsf {\pi }_{\mathsf {cor}}$ (see Sect. 3.3).

Complexity. The verification algorithm has exactly the same complexity as the algorithm itself since it is a secure version of it. As a result the complexity of the verification of the proof is O(mn) for the client. Of course, depending on the context, various shortest path algorithms exists some of which are more efficient than Bellman-Ford. However, we ignore if a verification proof simpler in terms of complexity than the best computation algorithm exists. Nevertheless, this example shows that it is always possible to obtain a complexity equal to the complexity of the algorithm.

5 Prototype Implementation

A generic implementation of the protocol has been realized in Python. The main objective was to create a simple framework to emulate the clients-worker interaction and measure the load of work of each party in different scenarios. Our entire code is available at https://github.com/mpfeppat/mpfeppat. We also provide the code of the applications tested in this paper to facilitate the reproduction of our results. In the full version of this paper, we point out precautions that must be taken prior to using an implementation of our technique. We indicate which part of the code on the client’s and on the worker’s side must be audited and how.

The implementation aims to be light and reasonably efficient by using optimized algorithms and techniques. Our implementation is a prototype. However it is already a good indicator of performance. Nevertheless, one might expect a nice efficiency gain when using optimized code in C for example. This should be worth for specifically designed applications. In this regard, we do not claim that we have the best known time results for our applications.

The $\mathsf {CCE}$ scheme of [22] is implemented through Elliptic Curves (EC). We denote $\mathbb {F}_p$ the prime field where p is a $\lambda$-bit prime. The Pedersen-like commitment part and the ElGamal-like encryption part of the $\mathsf {CCE}$ scheme are performed respectively in $G_1:=E(\mathbb {F}_p)$ and $G_2\subset E'(\mathbb {F}_{p^2})$, two prime order q groups where $E(\mathbb {F}_p), E'(\mathbb {F}_{p^2})$ are elliptic curves. Complete details are provided in the full version of this paper and the complexity analysis of our three test applications is given in the full version of this paper.

In Table 1, we list the cost of different tools we use in our algorithms. For each $\mathsf {NIZKPK}$, we split the cost between the computation and the verification. The proofs are computed in parallel whenever possible which imply that the computational cost of $\mathsf {\pi }_{\mathsf {cor}}$ is not always the sum of the cost of each intermediate proof but rather a fraction of this sum.

Several tests were performed on a standard laptop: Intel$^\circledR$ Core i5-3320M CPU @ 2.60 GHz $\times 4$ with 7.7 GB of RAM. For these tests, the security parameter $\lambda$ is 256-bit long. Even though this is the current security requirement for EC based cryptosystems, we argue that we do not need such a high security parameter for our protocol. Indeed, a polynomial time adversary that would be able to break the correctness of the scheme needs to run an attack against the binding property of the commitment scheme (in our case, break the $\mathsf {DDH}$ problem). However, at the time scale of the protocol execution, this attack has to be performed in a short amount of time. For this reason, we suspect that a smaller security parameter would still allow a high level of security and decrease the computational burden of the participants.

The time results including all the computations are presented in Table 2. The results show clearly the linearity in the number of clients in the first two applications while the complexity of the shortest path follows the quadratic complexity of the algorithm. The main limitations of efficiency might come from our use of Python and the generic Gmpy package for basic modular operations of addition and multiplication as these do not provide algebraic computations optimized for finite fields of a given characteristic. As a point of comparison, the auctions protocol of Rabin et al. [14] based on symmetric cryptography and cut-and-choose proofs achieve a 100 bids auctions with a security parameter of size 40. The worker needs 4.11 min to prepare the proof and the clients, less than one minute to verify it while the proof in itself weight for 1.45 GB.

Table 1. Complexity and size cost for primitives and $\mathsf {NIZKPK}$.

Table 2. Timings (in seconds) and proof size for the three applications – the proof sizes are computed for a security parameter $\lambda$ of 256-bit long.

6 Conclusion

Current progress and real world applications in the field of secure multi-party computations and multi-party verifiable computation are positive indicators for this branch of cryptography. Faster and reliable but also user-friendly solutions are provided to meet the needs of an emerging sector of activity.

This work aims at proposing a simple and efficient solution to evaluate multi-party function in a clients-worker setting where the clients want a strong guarantee over the correctness of the result. Our solution is based on perfectly hiding commitments posted on a public bulletin board for which a worker will be bound to and will provide a computationally sound proof of correctness. We combine this commitment with an encryption in a primitive called commitment consistent encryption to provide a generic and easy-to-set up protocol that is secure against passive adversary for the privacy and secure against active adversary for the correctness of the function evaluation. As a result, our protocol provides a perfectly private audit trail.

Moreover, we show that this setting allows the clients to gain in complexity for the verification of the proof when this verification is cheaper than the algorithm used to compute the result. As a side effect, the worker is able to use his own algorithm to compute the result of the function without disclosing the intellectual property of his algorithm. This is of particular interest when the worker is a company specialized in algorithmic optimization. We illustrate the ease of use of our technique by three – rather simple but already used in real world – applications. We also provide timing results measured on our prototype implementation that indicate efficiency even though we point out that improvements could be achieved with clever optimizations.