Paper 2015/339

Certificate Validation in Secure Computation and Its Use in Verifiable Linear Programming

Sebastiaan de Hoogh, Berry Schoenmakers, and Meilof Veeningen


For many applications of secure multiparty computation it is natural to demand that the output of the protocol is verifiable. Verifiability should ensure that incorrect outputs are always rejected, even if all parties executing the secure computation collude. Since the inputs to a secure computation are private, and potentially the outputs are private as well, adding verifiability is in general hard and costly. In this paper we focus on privacy-preserving linear programming as a typical and practically relevant case for verifiable secure multiparty computation. We introduce certificate validation as an effective technique for achieving verifiable linear programming. Rather than verifying the computation proper, which involves many iterations of the simplex algorithm, we extend the output of the secure computation with a certificate. The certificate allows for efficient and direct validation of the correctness of the output. The overhead incurred by the computation of the certificate is marginal. For the validation of a certificate we design particularly efficient distributed-prover zero-knowledge proofs, fully exploiting the fact that we can use ElGamal encryption for this purpose, hence avoiding the use of more elaborate cryptosystems such as Paillier encryption. We also formulate appropriate security definitions for our approach, and prove security for our protocols in this model, paying special attention to ensuring properties such as input independence. By means of several experiments performed in a real multi-cloud-provider environment, we show that the overall performance for verifiable linear programming is very competitive, incurring minimal overhead compared to protocols providing no correctness guarantees at all.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
secret sharingthreshold cryptographyzero knowledge
Contact author(s)
meilof veeningen @ philips com
2015-12-21: revised
2015-04-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sebastiaan de Hoogh and Berry Schoenmakers and Meilof Veeningen},
      title = {Certificate Validation in Secure Computation and Its Use in Verifiable Linear Programming},
      howpublished = {Cryptology ePrint Archive, Paper 2015/339},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.