Secure multi-party computation: information flow of outputs and game theory. (English) Zbl 1444.68014
Maffei, Matteo (ed.) et al., Principles of security and trust. 6th international conference, POST 2017, held as part of the European joint conferences on theory and practice of software, ETAPS 2017, Uppsala, Sweden, April 22–29, 2017. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 10204, 71-92 (2017).
Summary: Secure multiparty computation enables protocol participants to compute the output of a public function of their private inputs whilst protecting the confidentiality of their inputs. But such an output, as a function of its inputs, inevitably leaks some information about input values regardless of the protocol used to compute it. We introduce foundations for quantifying and understanding how such leakage may influence input behaviour of deceitful protocol participants as well as that of participants they target. Our model captures the beliefs and knowledge that participants have about what input values other participants may choose. In this model, measures of information flow that may arise between protocol participants are introduced, formally investigated, and experimentally evaluated. These information-theoretic measures not only suggest advantageous input behaviour to deceitful participants for optimal updates of their beliefs about chosen inputs of targeted participants. They also allow targets to quantify the information-flow risk of their input choices. We show that this approach supports a game-theoretic formulation in which deceitful attackers wish to maximise the information that they gain on inputs of targets once the computation output is known, whereas the targets wish to protect the privacy of their inputs.
For the entire collection see [Zbl 1360.68017].
For the entire collection see [Zbl 1360.68017].
MSC:
| 68M14 | Distributed systems |
| 68M25 | Computer security |
| 91A80 | Applications of game theory |
| 94A17 | Measures of information, entropy |
| 94A60 | Cryptography |
References:
| [1] | Asharov, G., Lindell, Y.: A full proof of the BGW protocol for perfectly secure multiparty computation. Cryptology ePrint Archive, Report 2011/136 (2011) · Zbl 1370.94480 |
| [2] | Avis, D., Rosenberg, G.D., Savani, R., Von Stengel, B.: Enumeration of Nash equilibria for two-player games. Econ. Theor. 42(1), 9-37 (2010) · Zbl 1182.91013 · doi:10.1007/s00199-009-0449-x |
| [3] | Baum, C., Damgård, I., Toft, T., Zakarias, R.: Better preprocessing for secure multiparty computation. In: Manulis, M., Sadeghi, A.-R., Schneider, S. (eds.) ACNS 2016. LNCS, vol. 9696, pp. 327-345. Springer, Cham (2016). doi:10.1007/978-3-319-39555-5_18 · Zbl 1346.68085 · doi:10.1007/978-3-319-39555-5_18 |
| [4] | Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation. In: Proceedings of STOC, pp. 1-10. ACM (1988) |
| [5] | Bogetoft, P., et al.: Secure multiparty computation goes live. In: Dingledine, R., Golle, P. (eds.) Financial Cryptography and Data Security. LNCS, vol. 5628. Springer, Heidelberg (2009) · Zbl 1417.94045 · doi:10.1007/978-3-642-03549-4_20 |
| [6] | Cachin, C.: Entropy measures and unconditional security in cryptography. Ph. D thesis, Diss. Techn. Wiss. ETH Zürich, Nr. 12187 (1997). Ref.: Maurer, U., Korref, Massey, J.L. (1997) |
| [7] | Chaum, D., Crépeau, C., Damgard, I.: Multiparty unconditionally secure protocols. In: Proceedings of STOC, pp. 11-19. ACM (1988) |
| [8] | Clark, D., Hunt, S., Malacaria, P.: A static analysis for quantifying information flow in a simple imperative language. J. Comput. Secur. 15(3), 321-371 (2007) · doi:10.3233/JCS-2007-15302 |
| [9] | Michael, M.R., Myers, A.C., Schneider, F.B.: Quantifying information flow with beliefs. J. Comput. Secur. 17(5), 655-701 (2009) · doi:10.3233/JCS-2009-0353 |
| [10] | Cramer, R., Damgård, I., Nielsen, J.B.: Secure Multiparty Computation and Secret Sharing. Cambridge University Press, Cambridge (2015) · Zbl 1322.68003 · doi:10.1017/CBO9781107337756 |
| [11] | Damgård, I., Pastro, V., Smart, N., Zakarias, S.: Multiparty computation from somewhat homomorphic encryption. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 643-662. Springer, Heidelberg (2012). doi:10.1007/978-3-642-32009-5_38 · Zbl 1296.94104 · doi:10.1007/978-3-642-32009-5_38 |
| [12] | Dorothy, D.E.: A lattice model of secure information flow. Commun. ACM 19(5), 236-243 (1976) · Zbl 0322.68034 · doi:10.1145/360051.360056 |
| [13] | Dima, C., Enea, C., Gramatovici, R.: Nondeterministic noninterference and deducible information flow. Technical report, Citeseer (2006) |
| [14] | Wenliang, D., Atallah, M.J.: Secure multi-party computation problems, their applications: a review and open problems. In: Proceedings of the Workshop on New Security Paradigms, pp. 13-22. ACM (2001) |
| [15] | Goldreich, O., Micali, S., Wigderson, A.: How to play ANY mental game. In: Proceedings of STOC 1987, pp. 218-229. ACM (1987) |
| [16] | Joshi, R., Leino, K.R.M.: A semantic approach to secure information flow. Sci. Comput. Program. 37(1), 113-138 (2000) · Zbl 0954.68052 · doi:10.1016/S0167-6423(99)00024-6 |
| [17] | Kolesnikov, V., Schneider, T.: Improved garbled circuit: free XOR gates and applications. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol. 5126, pp. 486-498. Springer, Heidelberg (2008). doi:10.1007/978-3-540-70583-3_40 · Zbl 1155.94374 · doi:10.1007/978-3-540-70583-3_40 |
| [18] | Lindell, Y., Pinkas, B.: A proof of security of yao’s protocol for two-party computation. J. Cryptology 22(2), 161-188 (2009) · Zbl 1159.94364 · doi:10.1007/s00145-008-9036-8 |
| [19] | Lindell, Y., Pinkas, B.: Secure multiparty computation for privacy-preserving data mining. J. Priv. Confidentiality 1(1), 5 (2009) · Zbl 0989.68506 |
| [20] | Malacaria, P.: Algebraic foundations for quantitative information flow. Math. Struct. Comput. Sci. 25(02), 404-428 (2015) · Zbl 1361.68081 · doi:10.1017/S0960129513000649 |
| [21] | Malone, D., Sullivan, W.: Guesswork is not a substitute for entropy. Slides (2005) |
| [22] | Mardziel, P., Magill, S., Hicks, M., Srivatsa, M.: Dynamic enforcement of knowledge-based security policies. In: IEEE 24th Computer Security Foundations Symposium, pp. 114-128. IEEE (2011) |
| [23] | Massey, J.L.: Guessing and entropy. In: Proceedings of the IEEE International Symposium on Information Theory, p. 204. IEEE (1994) |
| [24] | McIver, A., Morgan, C.: A probabilistic approach to information hiding. Programming Methodology. Monographs in Computer Science, pp. 441-460. Springer, Heidelberg (2003) · Zbl 1030.68010 · doi:10.1007/978-0-387-21798-7_20 |
| [25] | Alvim, M.S., Chatzikokolakis, K., Palamidessi, C., Smith, G.: Measuring information leakage using generalized gain functions. In: IEEE 25th Computer Security Foundations Symposium, pp. 265-279. IEEE (2012) |
| [26] | Nair, D.G., Binu, V.P., Kumar, G.S.: An improved e-voting scheme using secret sharing based secure multi-party computation. arXiv preprint arXiv:1502.07469 (2015) |
| [27] | Nielsen, J.B., Nordholt, P.S., Orlandi, C., Burra, S.S.: A new approach to practical active-secure two-party computation. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 681-700. Springer, Heidelberg (2012). doi:10.1007/978-3-642-32009-5_40 · Zbl 1296.94134 · doi:10.1007/978-3-642-32009-5_40 |
| [28] | Phan, Q-S., Malacaria, P., Păsăreanu, C.S., d’Amorim, M.: Quantifying information leaks using reliability analysis. In: Proceedings of the International SPIN Symposium on Model Checking of Software, pp. 105-108. ACM (2014) |
| [29] | Shamir, A.: How to share a secret. CACM 22(11), 612-613 (1979) · Zbl 0414.94021 · doi:10.1145/359168.359176 |
| [30] | Shannon, C.E., Weaver, W.: The Mathematical Theory of Communication. University of Illinois Press, Urbana (1949) · Zbl 0041.25804 |
| [31] | Smart, N.P.: Cryptography Made Simple. Springer, Heidelberg (2016) · Zbl 1401.94002 · doi:10.1007/978-3-319-21936-3 |
| [32] | Smith, G.: Principles of secure information flow analysis. In: Christodorescu, M., Jha, S., Maughan, D., Song, D., Wang, C. (eds.) Malware Detection. Advances in Information Security, vol. 27, pp. 291-307. Springer, Heidelberg (2007) · doi:10.1007/978-0-387-44599-1_13 |
| [33] | Smith, G.: On the foundations of quantitative information flow. In: Alfaro, L. (ed.) FoSSaCS 2009. LNCS, vol. 5504, pp. 288-302. Springer, Heidelberg (2009). doi:10.1007/978-3-642-00596-1_21 · Zbl 1234.68101 · doi:10.1007/978-3-642-00596-1_21 |
| [34] | Smith, G.: Quantifying information flow using min-entropy. In: Eighth International Conference on Quantitative Evaluation of Systems, pp. 159-167. IEEE (2011) |
| [35] | Smith, G.: Recent developments in quantitative information flow (invited tutorial). In: Proceedings of the 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pp. 23-31. IEEE Computer Society (2015) · Zbl 1331.03003 |
| [36] | Volpano, D., Irvine, C., Smith, G.: A sound type system for secure flow analysis. J. Comput. Secur. 4(2-3), 167-187 (1996) · doi:10.3233/JCS-1996-42-304 |
| [37] | Yasuoka, H. · Zbl 1359.68201 · doi:10.1016/j.tcs.2013.07.031 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
