Top

Journal of Cryptology

Published in:

30-12-2015

Efficient One-Sided Adaptively Secure Computation

Authors: Carmit Hazay, Arpita Patra

Published in: Journal of Cryptology | Issue 1/2017

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Adaptive security is a strong security notion that captures additional security threats that are not addressed by static corruptions. For instance, it captures real-world scenarios where “hackers” actively break into computers, possibly while they are executing secure protocols. Studying this setting is interesting from both theoretical and practical points of view. A primary building block in designing adaptively secure protocols is a non-committing encryption (NCE) that implements secure communication channels in the presence of adaptive corruptions. Current constructions require a number of public key operations that grow linearly with the length of the message. Furthermore, general two-party protocols require a number of NCE calls that dependent both on the circuit size and on the security parameter. In this paper, we study the two-party setting in which at most one of the parties is adaptively corrupted, and demonstrate the feasibility of (1) NCE with constant number of public key operations for large message spaces, (2) oblivious transfer with constant number of public key operations for large sender’s input spaces, and (3) constant round secure computation protocols with an overall number of public key operations that is linear in the circuit size. Our study demonstrates that such primitives indeed exist in the presence of single corruptions without erasures, while this is not known for fully adaptive security under standard assumptions (where both parties may get corrupted). Our results are shown in the UC setting with a CRS setup.

previous article Obfuscating Conjunctions

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

Available only for authorised users

We note that this statement is valid regarding protocols that do not employ fully homomorphic encryptions (FHE). To this end, we only consider protocols that do not take the FHE approach. As a side note, it was recently observed in [39] that adaptive security is impossible for FHE satisfying compactness.

We stress that the semi-adaptive notion is incomparable to the one-sided notion since the former assumes that either one party is statically corrupted or none of the parties get corrupted.

The actual key pair used in the circuit garbling is derived from \((g^{a^0_i c_j},g^{a^1_i c_j})\) using an extractor. A universal hash function is used in [42] for this purpose, where the seeds for the function are picked by \(P_0\) before it knows \(\mathcal{J}\).

At this point \(P_0\) is committed to all the keys associated with the s circuits.

This notation covers many basic relations such as discrete logarithm and quadratic residuosity.

Note that the simulator returns the entire view for the proof from which we extract the first message.

R. Bendlin, I. Damgård, C. Orlandi, and S. Zakarias. Semi-homomorphic encryption and multiparty computation, in EUROCRYPT (2011), pp. 169–188.

D. Beaver. Plug and play encryption, in CRYPTO (1997), pp. 75–89.

D. Beaver, and S. Haber. Cryptographic protocols provably secure against dynamic adversaries, in EUROCRYPT (1992), pp. 307–323.

M. Bellare, D. Hofheinz, and S. Yilek. Possibility and impossibility results for encryption and commitment secure under selective opening, in EUROCRYPT (2009), pp. 1–35.

D. Beaver, S. Micali, and P. Rogaway. The round complexity of secure protocols (extended abstract), in STOC (1990), pp. 503–513.

R. Canetti. Universally composable security: a new paradigm for cryptographic protocols, in FOCS (2001), pp. 136–145.

R. Canetti, I. Damgård, S. Dziembowski, Y. Ishai, and T. Malkin. Adaptive versus non-adaptive security of multi-party protocols. J. Cryptology, 17(3):153–207, 2004.

R. Cramer, I. Damgård, and B. Schoenmakers. Proofs of partial knowledge and simplified design of witness hiding protocols, in CRYPTO (1994), pp. 174–187.

S.G. Choi, D. Dachman-Soled, T. Malkin, and H. Wee. Improved non-committing encryption with applications to adaptively secure protocols, in ASIACRYPT (2009), pp. 287–302.

10.

S.G. Choi, D. Dachman-Soled, T. Malkin, and H. Wee. Simple, black-box constructions of adaptively secure protocols, in TCC (2009), pp. 387–402.

11.

R. Canetti, and M. Fischlin. Universally composable commitments, in Proceedings of Advances in Cryptology—CRYPTO 2001, 21st Annual International Cryptology Conference, Santa Barbara, California, USA (Aug. 19–23, 2001), pp. 19–40.

12.

R. Canetti, U. Feige, O. Goldreich, and M. Naor. Adaptively secure multi-party computation, in STOC (1996), pp. 639–648.

13.

R. Canetti, S. Goldwasser, and O. Poburinnaya. Adaptively secure two-party computation from indistinguishability obfuscation, in TCC (2015), pp. 557–585.

14.

R. Canetti, S. Halevi, and J. Katz. Adaptively-secure, non-interactive public-key encryption, in TCC (2005), pp. 150–168.

15.

R. Canetti, Y. Lindell, R. Ostrovsky, and A. Sahai. Universally composable two-party and multi-party secure computation, in STOC (2002).

16.

R. Cramer, and V. Shoup. Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption, in EUROCRYPT (2002), pp. 45–64.

17.

Y. Dodis, R. Gennaro, J. Håstad, H. Krawczyk, and T. Rabin. Randomness extraction and key derivation using the CBC, cascade and HMAC modes, in CRYPTO (2004), pp. 494–510.

18.

I. Damgård, and Y. Ishai. Constant-round multiparty computation using a black-box pseudorandom generator, in CRYPTO (2005), pp. 378–394.

19.

I. Damgård, and M. Jurik. A length-flexible threshold cryptosystem with applications, in ACISP (2003), pp. 350–364.

20.

I. Damgård, M. Jurik, and J.B. Nielsen. A generalization of Paillier’s public-key system with applications to electronic voting. Int. J. Inf. Sec., 9(6):371–385, 2010.

21.

D. Dachman-Soled, J. Katz, and V. Rao. Adaptively secure, universally composable, multiparty computation in constant rounds, in TCC (2015), pp. 586–613.

22.

I. Damgård, and J.B. Nielsen. Improved non-committing encryption schemes based on a general complexity assumption, in CRYPTO (2000), pp. 432–450.

23.

I. Damgård, and J.B. Nielsen. Perfect hiding and perfect binding universally composable commitment schemes with constant expansion factor, in CRYPTO (2002), pp. 581–596.

24.

I. Damgård, and J.B. Nielsen. Universally composable efficient multiparty computation from threshold homomorphic encryption, in CRYPTO (2003), pp. 247–264.

25.

I. Damgård, V. Pastro, N.P. Smart, and S. Zakarias. Multiparty computation from somewhat homomorphic encryption, in CRYPTO (2012), pp. 643–662.

26.

O. Goldreich and A. Kahan. How to construct constant-round zero-knowledge proof systems for np. J. Cryptology, 9(3):167–190, 1996.

27.

O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game or a completeness theorem for protocols with honest majority, in STOC (1987), pp. 218–229.

28.

O. Goldreich. Foundations of Cryptography: Basic Tools. Cambridge University Press, 2001.

29.

S. Garg, and A. Polychroniadou. Two-round adaptively secure MPC from indistinguishability obfuscation, in TCC (2015), pp. 614–637.

30.

S. Garg, and A. Sahai. Adaptively secure multi-party computation with dishonest majority, in CRYPTO (2012), pp. 105–123.

31.

J.A. Garay, D. Wichs, and H.-S. Zhou. Somewhat non-committing encryption and efficient adaptively secure oblivious transfer, in CRYPTO (2009), pp. 505–523.

32.

J. Håstad, R. Impagliazzo, L.A. Levin, and M. Luby. A pseudorandom generator from any one-way function. SIAM J. Comput., 28(4):1364–1396, 1999.

33.

B. Hemenway, R. Ostrovsky, and A. Rosen. Non-committing encryption from \(\Phi \)-hiding, in TCC (2015), pp. 591–608.

34.

C. Hazay, and A. Patra. One-sided adaptively secure two-party computation, in TCC (2014), pp. 368–393.

35.

Y. Ishai, M. Prabhakaran, and A. Sahai. Founding cryptography on oblivious transfer—efficiently, in CRYPTO (2008), pp. 572–591.

36.

S. Jarecki, and A. Lysyanskaya. Adaptively secure threshold cryptography: Introducing concurrency, removing erasures, in EUROCRYPT (2000), pp. 221–242.

37.

J. Katz, and R. Ostrovsky. Round-optimal secure two-party computation, in CRYPTO (2004), pp. 335–354.

38.

J. Katz, A. Thiruvengadam, and H.-S. Zhou. Feasibility and infeasibility of adaptively secure fully homomorphic encryption, in Public Key Cryptography (2013), pp. 14–31.

39.

Y. Lindell. Adaptively secure two-party computation with erasures, in CT-RSA (2009), pp. 117–132.

40.

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

41.

Y. Lindell and B. Pinkas. Secure two-party computation via cut-and-choose oblivious transfer. J. Cryptology, 25(4):680–722, 2012.

42.

Y. Lindell and B. Pinkas. An efficient protocol for secure two-party computation in the presence of malicious adversaries. J. Cryptology, 28(2):312–350, 2015.

43.

J.B. Nielsen. Separating random oracle proofs from complexity theoretic proofs: the non-committing encryption case, in CRYPTO (2002), pp. 111–126.

44.

J.B. Nielsen, P.S. Nordholt, C. Orlandi, and S.S. Burra. A new approach to practical active-secure two-party computation, in CRYPTO (2012), pp. 681–700.

45.

M. Naor, and O. Reingold. Synthesizers and their application to the parallel construction of psuedo-random functions, in FOCS (1995), pp. 170–181.

46.

P. Paillier. Public-key cryptosystems based on composite degree residuosity classes, in EUROCRYPT (1999), pp. 223–238.

47.

C. Peikert, V. Vaikuntanathan, and B. Waters. A framework for efficient and composable oblivious transfer, in CRYPTO (2008), pp. 554–571.

48.

C.-P. Schnorr. Efficient identification and signatures for smart cards, in CRYPTO (1989), pp. 239–252.

49.

M.N. Wegman J.L. Carter. Universal classes of hash functions. Journal of Computer and System Sciences, 18(2):143–154, 1979.

50.

S. Wolf, and J. Wullschleger. Oblivious transfer is symmetric, in EUROCRYPT (2006), pp. 222–232.

51.

A.C. Yao. Protocols for secure computations (extended abstract), in FOCS (1982), pp. 160–164.

Title: Efficient One-Sided Adaptively Secure Computation
Authors: Carmit Hazay
Arpita Patra
Publication date: 30-12-2015
Publisher: Springer US
Published in: Journal of Cryptology / Issue 1/2017
Print ISSN: 0933-2790
Electronic ISSN: 1432-1378
DOI: https://doi.org/10.1007/s00145-015-9222-4

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 1/2017

Weak Locking Capacity of Quantum Channels Can be Much Larger Than Private Capacity

Dynamic Proofs of Retrievability Via Oblivious RAM

Non-malleable Coding Against Bit-Wise and Split-State Tampering

A Full Proof of the BGW Protocol for Perfectly Secure Multiparty Computation

Bounded Tamper Resilience: How to Go Beyond the Algebraic Barrier

Obfuscating Conjunctions

Premium Partner