nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

More Efficient Universal Circuit Constructions

verfasst von : Daniel Günther, Ágnes Kiss, Thomas Schneider

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

A universal circuit (UC) can be programmed to simulate any circuit up to a given size n by specifying its program bits. UCs have several applications, including private function evaluation (PFE). The asymptotical lower bound for the size of a UC is proven to be \(\varOmega (n\log n)\). In fact, Valiant (STOC’76) provided two theoretical UC constructions using so-called 2-way and 4-way constructions, with sizes\(~5n\log _2n\) and \(4.75n\log _2n\), respectively. The 2-way UC has recently been brought into practice in concurrent and independent results by Kiss and Schneider (EUROCRYPT’16) and Lipmaa et al. (Eprint 2016/017). Moreover, the latter work generalized Valiant’s construction to any k-way UC.

In this paper, we revisit Valiant’s UC constructions and the recent results, and provide a modular and generic embedding algorithm for any k-way UC. Furthermore, we discuss the possibility for a more efficient UC based on a 3-way recursive strategy. We show with a counterexample that even though it is a promising approach, the 3-way UC does not yield an asymptotically better result than the 4-way UC. We propose a hybrid approach that combines the 2-way with the 4-way UC in order to minimize the size of the resulting UC. We elaborate on the concrete size of all discussed UC constructions and show that our hybrid UC yields on average 3.65% improvement in size over the 2-way UC. We implement the 4-way UC in a modular manner based on our proposed embedding algorithm, and show that our methods for programming the UC can be generalized for any k-way construction.

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 Instantaneous Decentralized Poker

Nächstes Kapitel Efficient Scalable Constant-Round MPC via Garbled Circuits

There also exist PFE protocols with linear complexity \(\mathcal {O}(n)\) which are based on public-key primitives [KM11, MS13, MSS14]. However, the concrete complexity of these protocols is worse than that of the protocols based on (mostly) symmetric-key primitives, i.e., the OT-based PFE protocols of [MS13, BBKL17] or PFE using UCs.

Our hybrid UC is orthogonal to that of [KS16], who combine Valiant’s UC with building blocks from [KS08b] for the inputs and outputs.

For the sake of simplicity, we denote this graph with \(U_n(\varGamma _d)\) instead of \(U(\varGamma _d(n))\).

We note that for \(k \ge 3\), there exist Head\((k-1), \ldots , \) Head(1) blocks. These are used for one n, e.g., Head(1) when \(n=k+1\), and Head\((k-1)\) when \(n=2k\). For simplicity, we consider these as special recursion base numbers in our calculations.

[AMPR14]

Afshar, A., Mohassel, P., Pinkas, B., Riva, B.: Non-interactive secure computation based on cut-and-choose. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 387–404. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-55220-5_22 CrossRef

[Att14]

Attrapadung, N.: Fully secure and succinct attribute based encryption for circuits from multi-linear maps. Cryptology ePrint Archive, Report 2014/772 (2014). http://ia.cr/2014/772

[BBKL17]

Bicer, O., Bingol, M.A., Kiraz, M.S., Levi, A.: Towards practical PFE: an efficient 2-party private function evaluation protocol based on half gates. Cryptology ePrint Archive, Report 2017/415 (2017). http://ia.cr/2017/415

[BD02]

Beauquier, B., Darrot, É.: On arbitrary size Waksman networks and their vulnerability. Parallel Proces. Lett. 12(3–4), 287–296 (2002)MathSciNetCrossRef

[BFK+09]

Barni, M., Failla, P., Kolesnikov, V., Lazzeretti, R., Sadeghi, A.-R., Schneider, T.: Secure evaluation of private linear branching programs with medical applications. In: Backes, M., Ning, P. (eds.) ESORICS 2009. LNCS, vol. 5789, pp. 424–439. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-04444-1_26 CrossRef

[BNP08]

Ben-David, A., Nisan, N., Pinkas, B.: FairplayMP: a system for secure multi-party computation. In: CCS 2008, pp. 257–266. ACM (2008)

[BOKP15]

Banescu, S., Ochoa, M., Kunze, N., Pretschner, A.: Idea: benchmarking indistinguishability obfuscation – a candidate implementation. In: Piessens, F., Caballero, J., Bielova, N. (eds.) ESSoS 2015. LNCS, vol. 8978, pp. 149–156. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-15618-7_12

[BPSW07]

Brickell, J., Porter, D.E., Shmatikov, V., Witchel, E.: Privacy-preserving remote diagnostics. In: CCS 2007, pp. 498–507. ACM (2007)

[DSZ15]

Demmler, D., Schneider, T., Zohner, M.: ABY - a framework for efficient mixed-protocol secure two-party computation. In: NDSS 2015. The Internet Society (2015). Code: http://encrypto.de/code/ABY

[FAZ05]

Frikken, K.B., Atallah, M.J., Zhang, C.: Privacy-preserving credit checking. In: Electronic Commerce (EC 2005), pp. 147–154. ACM (2005)

[FGP14]

Fiore, D., Gennaro, R., Pastro, V.: Efficiently verifiable computation on encrypted data. In: CCS 2015, pp. 844–855. ACM (2014)

[FVK+15]

Fisch, B., Vo, B., Krell, F., Kumarasubramanian, A., Kolesnikov, V., Malkin, T., Bellovin, S.M.: Malicious-client security in blind seer: a scalable private DBMS. In: IEEE S&P 2015, pp. 395–410. IEEE (2015)

[GGH+13a]

Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: FOCS 2013, pp. 40–49. IEEE (2013)

[GGH+13b]

Garg, S., Gentry, C., Halevi, S., Sahai, A., Waters, B.: Attribute-based encryption for circuits from multilinear maps. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 479–499. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40084-1_27 CrossRef

[GHV10]

Gentry, C., Halevi, S., Vaikuntanathan, V.: i-hop homomorphic encryption and rerandomizable Yao circuits. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 155–172. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_9 CrossRef

[GKS17]

Günther, D., Kiss, Á., Schneider, T.: More efficient universal circuit constructions. Cryptology ePrint Archive, Report 2017/798 (2017). http://ia.cr/2017/798

[HKK+14]

Huang, Y., Katz, J., Kolesnikov, V., Kumaresan, R., Malozemoff, A.J.: Amortizing garbled circuits. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8617, pp. 458–475. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44381-1_26 CrossRef

[Kő31]

Kőnig, D.: Gráfok és mátrixok. Matematikai és Fizikai Lapok 38, 116–119 (1931)

[KM11]

Katz, J., Malka, L.: Constant-round private function evaluation with linear complexity. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 556–571. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25385-0_30 CrossRef

[KR11]

Kamara, S., Raykova, M.: Secure outsourced computation in a multi-tenant cloud. In: IBM Workshop on Cryptography and Security in Clouds (2011)

[KS08a]

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

[KS08b]

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

[KS16]

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

[LMS16]

Lipmaa, H., Mohassel, P., Sadeghian, S.S.: Valiant’s universal circuit: improvements, implementation, and applications. Cryptology ePrint Archive, Report 2016/017 (2016). http://ia.cr/2016/017

[LP09]

Lovász, L., Plummer, M.D.: Matching Theory. AMS Chelsea Publishing Series. American Mathematical Society, Providence (2009)CrossRefMATH

[LR15]

Lindell, Y., Riva, B.: Blazing fast 2PC in the offline/online setting with security for malicious adversaries. In: CCS 2015, pp. 579–590. ACM (2015)

[MNPS04]

Malkhi, D., Nisan, N., Pinkas, B., Sella, Y.: Fairplay - secure two-party computation system. In: USENIX Security 2004, pp. 287–302. USENIX (2004)

[MS13]

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

[MSS14]

Mohassel, P., Sadeghian, S., Smart, N.P.: Actively secure private function evaluation. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8874, pp. 486–505. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45608-8_26

[NPS99]

Naor, M., Pinkas, B., Sumner, R.: Privacy preserving auctions and mechanism design. In: ACM Conference on Electronic Commerce (EC 1999), pp. 129–139. ACM (1999)

[NSMS14]

Niksefat, S., Sadeghiyan, B., Mohassel, P., Sadeghian, S.S.: ZIDS: a privacy-preserving intrusion detection system using secure two-party computation protocols. Comput. J. 57(4), 494–509 (2014)CrossRef

[OI05]

Ostrovsky, R., Skeith, W.E.: Private searching on streaming data. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 223–240. Springer, Heidelberg (2005). https://doi.org/10.1007/11535218_14 CrossRef

[PKV+14]

Pappas, V., Krell, F., Vo, B., Kolesnikov, V., Malkin, T., Geol Choi, S., George, W., Keromytis, A.D., Bellovin, S.: Blind seer: a scalable private DBMS. In: IEEE S&P 2014, pp. 359–374. IEEE (2014)

[Sch08]

Schneider, S.: Practical secure function evaluation. Master’s thesis, University Erlangen-Nürnberg, Germany, February 2008

[Sha49]

Shannon, C.: The synthesis of two-terminal switching circuits. Bell Labs Tech. J. 28(1), 59–98 (1949)MathSciNetCrossRef

[SS08]

Sadeghi, A.-R., Schneider, T.: Generalized universal circuits for secure evaluation of private functions with application to data classification. In: Lee, P.J., Cheon, J.H. (eds.) ICISC 2008. LNCS, vol. 5461, pp. 336–353. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-00730-9_21 CrossRef

[TS15]

Tillich, S., Smart, N.: Circuits of basic functions suitable for MPC and FHE (2015). https://www.cs.bris.ac.uk/Research/CryptographySecurity/MPC/

[Val76]

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

[Wak68]

Waksman, A.: A permutation network. J. ACM 15(1), 159–163 (1968)MathSciNetCrossRefMATH

[Weg87]

Wegener, I.: The complexity of Boolean functions. Wiley-Teubner (1987)

[Yao86]

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

[Zim15]

Zimmerman, J.: How to obfuscate programs directly. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 439–467. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46803-6_15

Titel: More Efficient Universal Circuit Constructions
verfasst von: Daniel Günther
Ágnes Kiss
Thomas Schneider
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_16

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