Abstract
We present an efficient implementation of the Orlandi protocol which is the first implementation of a protocol for multiparty computation on arithmetic circuits, which is secure against up to n − 1 static, active adversaries. An efficient implementation of an actively secure self-trust protocol enables a number of multiparty computation where one or more of the parties only trust himself. Examples includes auctions, negotiations, and online gaming. The efficiency of the implementation is largely obtained through an efficient implementation of the Paillier cryptosystem, also described in this paper.
Chapter PDF
Similar content being viewed by others
References
Cryptomatic A/S. PrimeInk ECC library v. 6.4.0, http://www.cryptomatic.com
Aumann, Y., Lindell, Y.: Security against covert adversaries: Efficient protocols for realistic adversaries. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 137–156. Springer, Heidelberg (2007)
Ben-David, A., Nisan, N., Pinkas, B.: FairplayMP: a system for secure multi-party computation. In: Ning, P., Syverson, P.F., Jha, S. (eds.) ACM Conference on Computer and Communications Security, pp. 257–266. ACM, New York (2008)
Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In: Simon, J. (ed.) [19], pp. 1–10
Benaloh, J.D.C.: Verifiable Secret-Ballot Elections. PhD thesis, Yale University (1978)
Bernstein, D.J., Lange, T.: eBACS: ECRYPT benchmarking of cryptographic systems, http://bench.cr.yp.to
Bogdanov, D., Laur, S., Willemson, J.: Sharemind: A framework for fast privacy-preserving computations. In: Jajodia, S., Lopez, J. (eds.) ESORICS 2008. LNCS, vol. 5283, pp. 192–206. Springer, Heidelberg (2008)
Bogetoft, P., Christensen, D.L., Damgård, I., Geisler, M., Jakobsen, T., Krøigaard, M., Nielsen, J.D., Nielsen, J.B., Nielsen, K., Pagter, J., Schwartzbach, M.I., Toft, T.: Secure multiparty computation goes live. In: Dingledine, R., Golle, P. (eds.) FC 2009. LNCS, vol. 5628, pp. 325–343. Springer, Heidelberg (2009)
Bogetoft, P., Damgård, I., Jakobsen, T.P., Nielsen, K., Pagter, J., Toft, T.: A practical implementation of secure auctions based on multiparty integer computation. In: Di Crescenzo, G., Rubin, A. (eds.) FC 2006. LNCS, vol. 4107, pp. 142–147. Springer, Heidelberg (2006)
Brauer, A.: On addition chains. Bulletin of the American Mathematical Society 45(10), 736–739 (1939)
Canetti, R.: Security and composition of multiparty cryptographic protocols. Journal of Cryptology 13(1), 143–202 (2000)
Canetti, R., Fischlin, M.: Universally composable commitments. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 19–40. Springer, Heidelberg (2001)
Chaum, D., Crépeau, C., Damgård, I.: Multiparty unconditionally secure protocols (extended abstract). In: Simon, J. (ed.) [19], pp. 11–19
Damgård, I., Geisler, M., Krøigaard, M., Nielsen, J.B.: Asynchronous multiparty computation: Theory and implementation. In: Jarecki, S., Tsudik, G. (eds.) PKC 2009. LNCS, vol. 5443, pp. 160–179. Springer, Heidelberg (2009)
Damgård, I., Geisler, M., Krøigard, M.: Homomorphic encryption and secure comparison. International Journal of Applied Cryptography 1(1), 22–31 (2008)
Dolev, D.: The byzantine generals strike again. Technical report, Stanford University, Stanford, CA, USA (1981)
Goldwasser, S., Micali, S.: Probabilistic encryption. Journal of Computer and System Sciences 28(2), 270–299 (1984)
Jakobsen, T.P., Makkes, M.X., Nielsen, J.D.: Efficient Implementation of the Orlandi Protocol Extended Version. Cryptology ePrint Archive, Report 2010/224 (2010), http://eprint.iacr.org/
In: STOC ’88: Proceedings of the twentieth annual ACM symposium on Theory of computing, May 1988. ACM, New York (1988)
Lee, P.J., Lim, C.H. (eds.): ICISC 2002. LNCS, vol. 2587. Springer, Heidelberg (2003)
Lim, C.H., Lee, P.J.: More flexible exponentiation with precomputation. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 95–107. Springer, Heidelberg (1994)
Lindell, Y., Pinkas, B., Smart, N.P.: Implementing two-party computation efficiently with security against malicious adversaries. In: Ostrovsky, R., De Prisco, R., Visconti, I. (eds.) SCN 2008. LNCS, vol. 5229, pp. 2–20. Springer, Heidelberg (2008)
Malkhi, D., Nisan, N., Pinkas, B., Sella, Y.: Fairplay - Secure Two-Party Computation System. In: USENIX Security Symposium, pp. 287–302. USENIX (2004)
Möller, B.: Improved techniques for fast exponentiation. In: Lee, Lim (eds.) [20], pp. 298–312
Montgomery, P.L.: Modular multiplication without trial division. Mathematics of computation 44(170), 519–521 (1985)
Naccache, D., Stern, J.: A new public-key cryptosystem. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 27–36. Springer, Heidelberg (1997)
Okamoto, T., Uchiyama, S.: A new public-key cryptosystem as secure as factoring. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 308–318. Springer, Heidelberg (1998)
Orlandi, C.: LEGO and Other Cryptographic Constructions - PhD Progress Report (March 2009), http://www.cs.au.dk/~orlandi/
Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999)
Paillier, P., Pointcheval, D.: Efficient public-key cryptosystems provably secure against active adversaries. In: Lam, K.-Y., Okamoto, E., Xing, C. (eds.) ASIACRYPT 1999. LNCS, vol. 1716, pp. 165–179. Springer, Heidelberg (1999)
Pedersen, T.P.: Non-interactive and information-theoretic secure verifiable secret sharing. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 129–140. Springer, Heidelberg (1992)
VIFF - The Virtual Ideal Functionality Framework, http://viff.dk
VIFFBench Framework, http://bitbucket.org/tpj/viffbench
Yao, A.C.-C.: How to generate and exchange secrets (extended abstract). In: Foundations of Computer Science, pp. 162–167. IEEE, Los Alamitos (1986)
Yen, S.M., Laih, C.S., Lenstra, A.K.: Multi-exponentiation. Computers and Digital Techniques 141(6), 325–326 (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jakobsen, T.P., Makkes, M.X., Nielsen, J.D. (2010). Efficient Implementation of the Orlandi Protocol. In: Zhou, J., Yung, M. (eds) Applied Cryptography and Network Security. ACNS 2010. Lecture Notes in Computer Science, vol 6123. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-13708-2_16
Download citation
DOI: https://doi.org/10.1007/978-3-642-13708-2_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-13707-5
Online ISBN: 978-3-642-13708-2
eBook Packages: Computer ScienceComputer Science (R0)