A domain-specific programming language for secure multiparty computation

ABSTRACT

We present a domain-specific programming language for Secure Multiparty Computation (SMC).

Information is a resource of vital importance and considerable economic value to individuals, public administration, and private companies. This means that the confidentiality of information is crucial, but at the same time significant value can often be obtained by combining confidential information from various sources. This fundamental conflict between the benefits of confidentiality and the benefits of information sharing may be overcome using the cryptographic method of SMC where computations are performed on secret values and results are only revealed according to specific protocols

We identify the key linguistic concepts of SMC and bridge the gap between high-level security requirements and low-level cryptographic operations constituting an SMC platform, thus improving the efficiency and security of SMC application development. The language is implemented in a prototype compiler that generates Java code exploiting a distributed cryptographic runtime.

REFERENCES

• 1: Martín Abadi , Anindya Banerjee , Nevin Heintze , Jon G. Riecke, A core calculus of dependency, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.147-160, January 20-22, 1999, San Antonio, Texas, United States [doi>10.1145/292540.292555]
• 2: Martín Abadi , Andrew D. Gordon, A calculus for cryptographic protocols: the spi calculus, Proceedings of the 4th ACM conference on Computer and communications security, p.36-47, April 01-04, 1997, Zurich, Switzerland [doi>10.1145/266420.266432]
• 3: Johan Agat, Transforming out timing leaks, Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.40-53, January 19-21, 2000, Boston, MA, USA [doi>10.1145/325694.325702]
• 4: Torben Amtoft, Sruthi Bandhakavi, and Anindya Banerjee. A logic for information flow analysis of pointer programs. Technical Report CIS TR 2005-1, Kansas State University, July 2005.
• 5: Torben Amtoft , Sruthi Bandhakavi , Anindya Banerjee, A logic for information flow in object-oriented programs, Conference record of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.91-102, January 11-13, 2006, Charleston, South Carolina, USA
• 6: Manual Barbosa and Daniel Page. On the automatic construction of indistinguishable operations. In IMA Int. Conf., pages 233--247, 2005.
• 7: Daniel J. Bernstein. Cache-timing attacks on AES, 2004.
• 8: Peter Bogetoft, Ivan Damgård, Thomas Jakobsen, Kurt Nielsen, Jakob Pagter, and Tomas Toft. Secure computing, economy, and trust: A generic solution for secure auctions with real-world applications. Technical Report RS-05-18, BRICS, June 2005. 37 pp.
• 9: Peter Bogetoft, Ivan Damgård, Thomas Jakobsen, Kurt Nielsen, Jakob Pagter, and Tomas Toft. A practical implementation of secure auctions based on multiparty integer computation. In Proc. of Financial Cryptography, volume 4107 of LNCS. Springer-Verlag, 2006.
• 10: David Brumley , Dan Boneh, Remote timing attacks are practical, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.48 n.5, p.701-716, 5 August 2005 [doi>10.1016/j.comnet.2005.01.010]
• 11: R. Canetti, Universally Composable Security: A New Paradigm for Cryptographic Protocols, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.136, October 14-17, 2001
• 12: David Clark, Sebastian Hunt, and Pasquale Malacaria. Quantitative analysis of the leakage of confidential data. J. Theoretical Computer Science, 59(3):1--14, January 2004.
• 13: Patrick Cousot , Radhia Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.238-252, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512973]
• 14: Ivan Damgård, Matthias Fitzi, Eike Kiltz, Jesper Buus Nielsen, and Tomas Toft. Unconditionally secure constant-rounds multi-party computation for equality, comparison, bits and exponentiation. In Proc. Theory of Cryptography Conference, volume 3876 of LNCS, pages 285--304. Springer-Verlag, May 2006.
• 15: Dorothy E. Denning, A lattice model of secure information flow, Communications of the ACM, v.19 n.5, p.236-243, May 1976 [doi>10.1145/360051.360056]
• 16: Dorothy E. Denning , Peter J. Denning, Certification of programs for secure information flow, Communications of the ACM, v.20 n.7, p.504-513, July 1977 [doi>10.1145/359636.359712]
• 17: Pablo Giambiagi , Mads Dam, On the secure implementation of security protocols, Science of Computer Programming, v.50 n.1-3, p.73-99, March 2004 [doi>10.1016/j.scico.2004.01.002]
• 18: Joseph A. Goguen and José Meseguer. Security policies and security models. In Proc. IEEE Symp. on Security and Privacy, pages 11--20. IEEE Computer Society Press, 1982.
• 19: Nevin Heintze , Jon G. Riecke, The SLam calculus: programming with secrecy and integrity, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.365-377, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268976]
• 20: Thomas Jakobsen and Strange From. Secure multi-party computation on integers. Master's thesis, Department of Computer Science, DAIMI, University of Aarhus, Denmark, July 2005.
• 21: Paul C. Kocher, Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems, Proceedings of the 16th Annual International Cryptology Conference on Advances in Cryptology, p.104-113, August 18-22, 1996
• 22: Boris Köpf and David A. Basin. Timing-sensitive information flow analysis for synchronous systems. In Proc. European Symp. on Research in Computer Security, pages 243--262, 2006.
• 23: Vijay Krishna. Auction Theory. Academic Press, 2002.
• 24: Peng Li , Steve Zdancewic, Downgrading policies and relaxed noninterference, Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.158-170, January 12-14, 2005, Long Beach, California, USA
• 25: Dahlia Malkhi , Noam Nisan , Benny Pinkas , Yaron Sella, Fairplay—a secure two-party computation system, Proceedings of the 13th conference on USENIX Security Symposium, p.20-20, August 09-13, 2004, San Diego, CA
• 26: Heiko Mantel and David Sands. Controlled declassification based on intransitive noninterference. In Proc. of the ASIAN Symposium on Programming Languages and Systems, volume 3303 of LNCS, pages 129--145, Taipei, Taiwan, November 4¿6 2004. Springer-Verlag.
• 27: Ana Almeida Matos , Gerard Boudol, On Declassification and the Non-Disclosure Policy, Proceedings of the 18th IEEE workshop on Computer Security Foundations, p.226-240, June 20-22, 2005 [doi>10.1109/CSFW.2005.21]
• 28: Andrew C. Myers , Barbara Liskov, Protecting privacy using the decentralized label model, ACM Transactions on Software Engineering and Methodology (TOSEM), v.9 n.4, p.410-442, Oct. 2000 [doi>10.1145/363516.363526]
• 29: Janus Dam Nielsen and Michael I. Schwartzbach. The SMCL Language Specification. Technical Report RS-07-9, BRICS, April 2007.
• 30: Flemming Nielson , Hanne R. Nielson , Chris Hankin, Principles of Program Analysis, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
• 31: François Pottier , Vincent Simonet, Information flow inference for ML, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.319-330, January 16-18, 2002, Portland, Oregon
• 32: Andrei Sabelfeld and Andrew Myers. Language-based information-flow security. IEEE J. on Selected Areas in Communications, 21, 2003.
• 33: Andrei Sabelfeld and Andrew Myers. A model for delimited information release. In Proc. of the International Symposium on Software Security, volume 3233 of LNCS, pages 174--191. Springer-Verlag, October 2004.
• 34: Andrei Sabelfeld , David Sands, A Per Model of Secure Information Flow in Sequential Programs, Proceedings of the 8th European Symposium on Programming Languages and Systems, p.40-58, March 22-28, 1999
• 35: Andrei Sabelfeld , David Sands, Probabilistic Noninterference for Multi-Threaded Programs, Proceedings of the 13th IEEE workshop on Computer Security Foundations, p.200, July 03-05, 2000
• 36: Andrei Sabelfeld , David Sands, Dimensions and Principles of Declassification, Proceedings of the 18th IEEE workshop on Computer Security Foundations, p.255-269, June 20-22, 2005 [doi>10.1109/CSFW.2005.15]
• 37: Marius C. Silaghi. SMC: Secure Multiparty Computation language, 2004. http://www.cs.fit.edu/msilaghi/SMC/tutorial.html.
• 38: Geoffrey Smith , Dennis Volpano, Secure information flow in a multi-threaded imperative language, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.355-364, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268975]
• 39: Tomas Toft. Progress report - Secure Integer Computation with Applications in Economics., July 2005.
• 40: Terkel K. Tolstrup and Flemming Nielson. Analyzing for Absence of Timing Leaks in VHDL. In Dieter Gollmann and Jan Jürjens, editors, Proc. International Workshop on Issues in the Theory of Security, March 2006.
• 41: Terkel K. Tolstrup, Flemming Nielson, and Hanne Riis Nielson. Information Flow Analysis for VHDL. In Victor E. Malyshkin, editor, Proc. International Conference on Parallel Computing Technologies, volume 3606 of LNCS, pages 79--98. Springer-Verlag, September 2005.
• 42: Arie van Deursen , Paul Klint , Joost Visser, Domain-specific languages: an annotated bibliography, ACM SIGPLAN Notices, v.35 n.6, p.26-36, June 2000 [doi>10.1145/352029.352035]
• 43: Dennis M. Volpano , Geoffrey Smith, A Type-Based Approach to Program Security, Proceedings of the 7th International Joint Conference CAAP/FASE on Theory and Practice of Software Development, p.607-621, April 14-18, 1997
• 44: D. Volpano , G. Smith, Probabilistic Noninterference in a Concurrent Language, Proceedings of the 11th IEEE workshop on Computer Security Foundations, p.34, June 09-11, 1998
• 45: Dennis Volpano , Cynthia Irvine , Geoffrey Smith, A sound type system for secure flow analysis, Journal of Computer Security, v.4 n.2-3, p.167-187, Jan. 1996
• 46: Andrew Chi-Chih Yao. Protocols for secure computations (extended abstract). In Proc. IEEE Symp. on Foundations of Computer Science, pages 160--164, 1982.
• 47: Steve Zdancewic. A type system for robust declassification. In Proc. of the Mathematical Foundations of Programming Semantics, March 2003.
• 48: Steve Zdancewic , Andrew C. Myers, Robust Declassification, Proceedings of the 14th IEEE workshop on Computer Security Foundations, p.5, June 11-13, 2001
• 49: Steve Zdancewic , Lantian Zheng , Nathaniel Nystrom , Andrew Myers, Secure Program Partitioning, Cornell University, Ithaca, NY, 2001

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

General Terms:
Design, Languages, Security

Keywords:
SMCL, analysis, design, implementation