nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Overlaying Conditional Circuit Clauses for Secure Computation

verfasst von : W. Sean Kennedy, Vladimir Kolesnikov, Gordon Wilfong

Erschienen in: Advances in Cryptology – ASIACRYPT 2017

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We improve secure function evaluation (SFE) by optimizing circuit representation of the function and designing new SFE protocols.

(1)

We propose a heuristic for constructing a circuit \(C_0\), universal for a given set of Boolean circuits \(\mathcal {S}= \{C_1,...,C_k\}\). Namely, given each \(C_i\), we view it as a directed acyclic graph (DAG) \(D_i\) by ignoring the Boolean gate functions of \(C_i\). We embed \(D_1, ..., D_k\) in a new DAG \(D_0\), such that each \(C_i\) can be obtained by a corresponding programming of \(D_0\) (i.e. by assignment of Boolean gates to the nodes of \(D_0\)). DAG \(D_0\), viewed as a Boolean circuit with unprogrammed gates, is the \(\mathcal {S}\)-universal circuit \(C_0\).

(2)

Our heuristic often produces \(C_0\) significantly smaller than Valiant’s universal circuit or a circuit incorporating all \(C_1,...,C_k\). Exploiting this, we construct new Garbled Circuit (GC) and GMW-based SFE protocols, which are particularly efficient for circuits with if/switch clauses.

Our GMW protocol evaluates 8-input Boolean gates at the same cost as the usual 2-input gates. This advances general GMW-based SFE, and is particularly useful for circuits with if/switch conditional clauses.

Experimentally, for a switch containing 32 simple circuits, our construction resulted in \(\approx 6.1\times \) smaller circuit \(C_0\). This directly translates into \(\approx 6.1\times \) improvement in GMW SFE computing this switch. Recent state-of-the-art generic circuit optimizations from hardware design adapted to SFE report \(10-20\%\) circuit (garble table) reduction.

Our SFE is in the semi-honest model, and is compatible with Free-XOR. We further show that optimal embedding is NP-hard.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Efficient Scalable Constant-Round MPC via Garbled Circuits

Nächstes Kapitel JIMU: Faster LEGO-Based Secure Computation Using Additive Homomorphic Hashes

See related work in Sect. 1.3 for discussion on the high costs of sublinear PIR for smaller-size DBs.

We could reduce the set of considered circuit gates, e.g., by eliminating the OR gate and implementing it with AND and XOR gates. This would present us with the trade off between more efficient gate processing and potentially larger circuits. Alternatively, we could consider a larger gate basis and have costlier gate processing. We defer exploration of these trade-offs as future work.

For some pairs of circuits our heuristic may produce a container circuit of size greater than \(|C_1| + |C_2|\). In this case, we will simply take \(C_0\) to include both \(C_1\) and \(C_2\).

A directed graph is weakly connected if replacing all edges with undirected edges yields a connected graph, that is, every pair of nodes in the graph is connected by some path.

Recall, for simplicity we did not explicitly include the standard permute-and-point table row pointers in our protocol. We assume the evaluator knows decryption of which row to use, e.g. via using the standard permute-and-point technique.

We remark that in all our experiments we use circuits that have fan in at most 2. A standard reduction allows us to eliminate gates of fan in exactly 1. In our experiments we use cost and size interchangeably, since they are closely related.

It would be more general to include the size of Valiant’s universal circuit in the expansion metric definition. For s defined as the size of a universal circuit for all circuits of size up to \(\max \{|C_i|\}\), set EM \(m = \frac{|C_0| - \max \{|C_1|,..,|C_{32}|\}}{\min \{s,|C_1|+..+|C_{32}|\}}\). However, in our experiments and clause numbers, s is much larger than \(|C_1|+..+|C_{32}|\), so we omit this complication in this writeup.

Asharov, G., Lindell, Y., Schneider, T., Zohner, M.: More efficient oblivious transfer and extensions for faster secure computation. In: Sadeghi, A-R., Gligor, V.D., Yung, M. (eds.) ACM CCS 2013, pp. 535–548. ACM Press, November 2013

Cachin, C., Micali, S., Stadler, M.: Computationally private information retrieval with polylogarithmic communication. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 402–414. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48910-X_28 CrossRef

Damgård, I., Jurik, M.: A length-flexible threshold cryptosystem with applications. In: Safavi-Naini, R., Seberry, J. (eds.) ACISP 2003. LNCS, vol. 2727, pp. 350–364. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-45067-X_30 CrossRef

Damgård, I., Jurik, M.: A generalisation, a simplification and some applications of paillier’s probabilistic public-key system. In: Kim, K. (ed.) PKC 2001. LNCS, vol. 1992, pp. 119–136. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44586-2_9 CrossRef

Demmler, D., Dessouky, G., Koushanfar, F., Sadeghi, A-R., Schneider, T., Zeitouni, S.: Automated synthesis of optimized circuits for secure computation. In: Ray, I., Li, N., Kruegel, C. (eds.) ACM CCS 2015, pp. 1504–1517. ACM Press, October 2015

Dessouky, G., Koushanfar, F., Sadeghi, A.-R., Schneider, T., Zeitouni, S., Zohner, M.: Pushing the communication barrier in secure computation using lookup tables. In: 24 Annual Network and Distributed System Security Symposium (NDSS 2017). The Internet Society, 26 February–1 March 2017. (to appear)

Fisch, B.A., Vo, B., Krell, F., Kumarasubramanian, A., Kolesnikov, V., Malkin, T., Bellovin, S.M.: Malicious-client security in blind seer: a scalable private DBMS. In: 2015 IEEE Symposium on Security and Privacy, pp. 395–410. IEEE Computer Society Press, May 2015

Franz, M., Holzer, A., Katzenbeisser, S., Schallhart, C., Veith, H.: CBMC-GC: an ANSI C compiler for secure two-party computations. In: Cohen, A. (ed.) CC 2014. LNCS, vol. 8409, pp. 244–249. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-54807-9_15 CrossRef

Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34(3), 596–615 (1987)MathSciNetCrossRef

10.

Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Co., San Francisco (1979)MATH

11.

Goldreich, O.: Foundations of Cryptography: Volume 2, Basic Applications, 2nd edn. Cambridge University Press, Cambridge (2009)MATH

12.

Goldreich, O., Micali, S., Wigderson, A.: How to play ANY mental game or A completeness theorem for protocols with honest majority. In: Aho, A. (ed.) 19th ACM STOC, pp. 218–229. ACM Press, May 1987

13.

Goldreich, O., Ostrovsky, R.: Software protection and simulation on oblivious RAMs. J. ACM 43(3), 431–473 (1996)MathSciNetCrossRefMATH

14.

Ishai, Y., Kilian, J., Nissim, K., Petrank, E.: Extending oblivious transfers efficiently. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 145–161. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45146-4_9 CrossRef

15.

Kiss, Á., Schneider, T.: Valiant’s universal circuit is practical. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 699–728. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49890-3_27 CrossRef

16.

Kolesnikov, V., Kumaresan, R.: Improved OT extension for transferring short secrets. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 54–70. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40084-1_4 CrossRef

17.

Kolesnikov, V., Mohassel, P., Rosulek, M.: FleXOR: flexible garbling for XOR gates that beats free-XOR. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8617, pp. 440–457. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44381-1_25 CrossRef

18.

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). https://doi.org/10.1007/978-3-540-70583-3_40 CrossRef

19.

Kolesnikov, V., Schneider, T.: A practical universal circuit construction and secure evaluation of private functions. In: Tsudik, G. (ed.) FC 2008. LNCS, vol. 5143, pp. 83–97. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85230-8_7 CrossRef

20.

Lindell, Y., Pinkas, B.: A proof of security of Yao’s protocol for two-party computation. J. Cryptol. 22(2), 161–188 (2009)MathSciNetCrossRefMATH

21.

Lipmaa, H.: An oblivious transfer protocol with log-squared communication. In: Zhou, J., Lopez, J., Deng, R.H., Bao, F. (eds.) ISC 2005. LNCS, vol. 3650, pp. 314–328. Springer, Heidelberg (2005). https://doi.org/10.1007/11556992_23 CrossRef

22.

Lipmaa, H., Mohassel, P., Sadeghian, S.: Valiant’s universal circuit: Improvements, implementation, and applications. Cryptology ePrint Archive, Report 2016/017 (2016). http://eprint.iacr.org/2016/017

23.

Mohassel, P., Sadeghian, S.: How to hide circuits in MPC an efficient framework for private function evaluation. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 557–574. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38348-9_33 CrossRef

24.

Ostrovsky, R., Skeith, W.E.: A survey of single-database private information retrieval: techniques and applications. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 393–411. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-71677-8_26 CrossRef

25.

Pappas, V., Krell, F., Vo, B., Kolesnikov, V., Malkin, T., Choi, S.G., George, W., Keromytis, A.D., Bellovin, S.: Blind seer: a scalable private DBMS. In: 2014 IEEE Symposium on Security and Privacy, pp. 359–374. IEEE Computer Society Press, May 2014

26.

Paus, A., Sadeghi, A.-R., Schneider, T.: Practical secure evaluation of semi-private functions. In: Abdalla, M., Pointcheval, D., Fouque, P.-A., Vergnaud, D. (eds.) ACNS 2009. LNCS, vol. 5536, pp. 89–106. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-01957-9_6 CrossRef

27.

Pinkas, B., Schneider, T., Smart, N.P., Williams, S.C.: Secure two-party computation is practical. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 250–267. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-10366-7_15 CrossRef

28.

Robertson, N., Seymour, P.D.: Graph minors. I. excluding a forest. J. Comb. Theor. Ser. B 35(1), 39–61 (1983)

29.

Songhori, E.M., Hussain, S.U., Sadeghi, A-R., Schneider, T., Koushanfar, F.: TinyGarble: Highly compressed and scalable sequential garbled circuits. In: 2015 IEEE Symposium on Security and Privacy, pp. 411–428. IEEE Computer Society Press, May 2015

30.

Valiant, L.G.: Universal circuits (preliminary report). In: STOC, pp. 196–203. ACM Press, New York (1976)

31.

Verma, R.M., Reyner, S.W.: An analysis of a good algorithm for the subtree problem, correlated. SIAM J. Comput. 18(5), 906–908 (1989)MathSciNetCrossRefMATH

32.

Wang, X., Gordon, S.D., McIntosh, A., Katz, J.: Secure computation of MIPS machine code. In: Askoxylakis, I., Ioannidis, S., Katsikas, S., Meadows, C. (eds.) ESORICS 2016. LNCS, vol. 9879, pp. 99–117. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-45741-3_6 CrossRef

33.

Yao, A.C-C.: How to generate and exchange secrets (extended abstract). In: 27th FOCS, pp. 162–167. IEEE Computer Society Press, October 1986

34.

Zahur, S., Rosulek, M., Evans, D.: Two halves make a whole. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 220–250. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46803-6_8

Titel: Overlaying Conditional Circuit Clauses for Secure Computation
verfasst von: W. Sean Kennedy
Vladimir Kolesnikov
Gordon Wilfong
Verlag: Springer International Publishing
Buch: Advances in Cryptology – ASIACRYPT 2017
Print ISBN: 978-3-319-70696-2

Electronic ISBN: 978-3-319-70697-9

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-70697-9_18

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner