nach oben

Journal of Cryptology

Erschienen in:

22.05.2019

What Security Can We Achieve Within 4 Rounds?

verfasst von: Carmit Hazay, Muthuramakrishnan Venkitasubramaniam

Erschienen in: Journal of Cryptology | Ausgabe 4/2019

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Katz and Ostrovsky (Crypto 2004) proved that five rounds are necessary for stand-alone general black-box constructions of secure two-party protocols and at least four rounds are necessary if only one party needs to receive the output. Recently, Ostrovsky, Richelson and Scafuro (Crypto 2015) proved optimality of this result by showing how to realize stand-alone, secure two-party computation under general assumptions (with black-box proof of security) in four rounds where only one party receives the output, and an extension to five rounds where both parties receive the output. In this paper, we study the question of what security is achievable for stand-alone two-party protocols within four rounds and show the following results:

A 4-round two-party protocol for coin-tossing that achieves 1 / p-security (i.e., simulation fails with probability at most \(1/p+{\mathsf {negl}}\)), in the presence of malicious corruptions.

A 4-round two-party protocol for general functionalities where both parties receive the output, that achieves 1 / p-security and privacy in the presence of malicious adversaries corrupting one of the parties, and full security in the presence of non-aborting malicious adversaries corrupting the other party.

A 3-round oblivious-transfer protocol that achieves 1 / p-security against arbitrary malicious senders, while simultaneously guaranteeing a meaningful notion of privacy against malicious corruptions of either party.

Finally, we show that the simulation-based security guarantees for our 3-round protocols are optimal by proving that 1 / p-simulation security is impossible to achieve against both parties in three rounds or less when requiring some minimal guarantees on the privacy of their inputs.

Vorheriger Artikel Constant-Round Maliciously Secure Two-Party Computation in the RAM Model

Nächster Artikel Making Masking Security Proofs Concrete (Or How to Evaluate the Security of Any Leaking Device), Extended Version

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

Nur mit Berechtigung zugänglich

A message is considered ill-formed if the recipient of the message rejects the message.

By fully secure, we mean standard simulation-based security.

A semi-malicious adversary is allowed to invoke a corrupted party with arbitrary chosen input and random tape, but otherwise follows the protocol specification honestly as a passive adversary.

More precisely, the real view can be obtained by first selecting \(D_a\) with probability \(\delta \) and \(D_b\) otherwise, and then the selecting a random view in the particular distribution.

In order to ensure correctness, we can make sure that the computed function additionally outputs a MAC so that the sender is assured of the output the receiver sends. Alternatively, the output can also be encrypted (in case of an asymmetric function) under the sender’s key, which the receiver can relay back to the sender.

This is possible because for indices outside J it has the correct witness, and for indices in J it has witnesses corresponding to both inputs of the receiver.

We can consider some canonical representation of elements in \(D_i\) in \(\{0,1\}^*\).

We assume without loss of generality that D outputs 1 with higher probability in the game \({\mathsf {Game}}_b\).

In this reduction, we will consider an adversary \(\mathcal{A}^*\) and distinguisher \(\mathcal{D}^*\). \(\mathcal{A}^*\) will incorporate \(\mathrm{Rec}^*\) and simulates everything internally except the forward the messages in the ith instance externally (the auxiliary input will provide the inputs for the sender in all the other OT instances that are not forwarded).

For simplicity, we present the proof with PRF’s. However, to get an unconditional result as stated in the lemma, we can rely on m-wise independent hash-function family where m is polynomially related to the expected running time of the simulator \(\mathcal{S}\).

Namely, on any input query to the random function, \(\mathcal{P}^*\) checks if the query has already been asked and produces the same answer in this case. Otherwise, it samples and feeds a uniform output and records the query/answer pair.

This is not entirely accurate as \(\mathcal{P}^*\) does not know the actual randomness used by the external verifier since this is a private-coin protocol. Nevertheless, it is possible to formally prove that conditioned on \(\mathcal{P}^*\) guessing correctly, \(\mathcal{P}^*\) convinces the external verifier with probability equal to the probability \(\mathcal{S}\) outputs a convincing view in the internal emulation, i.e., close to q.

It is possible to extend this argument to expected polynomial-time simulators by using a Markov argument.

We can consider some canonical representation of elements in \(D_i\) in \(\{0,1\}^*\).

P. Ananth, A. R. Choudhuri, A. Jain, A new approach to round-optimal secure multiparty computation, in CRYPTO (2017), pp. 468–499

Y. Aumann, Y. Lindell. Security against covert adversaries: Efficient protocols for realistic adversaries. J. Cryptology, 23(2). 281–343 (2010)MathSciNetCrossRef

N. Asokan, V. Shoup, M. Waidner, Optimistic fair exchange of digital signatures. IEEE J. Sel. Areas Commun. 18(4), 593–610 (2000)CrossRef

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

D. Beaver, Foundations of secure interactive computing, in CRYPTO (1991), pp. 377–391

S. Badrinarayanan, V. Goyal, A. Jain, Y. T. Kalai, D. Khurana, A. Sahai. Promise zero knowledge and its applications to round optimal mpc. IACR Cryptol. ePrint Arch. 2017, 1088 (2017)MATH

S. Badrinarayanan, V. Goyal, A. Jain, D. Khurana, A. Sahai, Round optimal concurrent MPC via strong simulation, in TCC (2017), pp. 743–775

S. Badrinarayanan, V. Goyal, A. Jain, Y. T. Kalai, D. Khurana, A. Sahai, Promise zero knowledge and its applications to round optimal MPC, in CRYPTO (2018), pp. 459–487

Z. Brakerski, S. Halevi, A. Polychroniadou, Four round secure computation without setup, in TCC (2017), pp. 645–677

10.

I. Bentov, R. Kumaresan, How to use bitcoin to design fair protocols, in CRYPTO (2014), pp. 421–439CrossRef

11.

F. Benhamouda, H. Lin, k-round multiparty computation from k-round oblivious transfer via garbled interactive circuits, in EUROCRYPT (2018), pp. 500–532

12.

M. Blum, How to prove a theorem so no one else can claim it, in Proceedings of the International Congress of Mathematicians, USA, pp. 1444–1451

13.

B. Barak, A. Sahai, How to play almost any mental game over the net—concurrent composition via super-polynomial simulation. IACR Cryptol. ePrint Arch., 106 (2005)

14.

R. Canetti, Security and composition of multiparty cryptographic protocols. J. Cryptol. 13(1), 143–202 (2000)MathSciNetCrossRef

15.

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

16.

D. Chaum, J.-H. Evertse, J. van de Graaf, An improved protocol for demonstrating possession of discrete logarithms and some generalizations, in EUROCRYPT (1987), pp. 127–141

17.

R. Cleve, Limits on the security of coin flips when half the processors are faulty (extended abstract), in STOC (1986), pp. 364–369

18.

R. Canetti, H. Lin, R. Pass, Adaptive hardness and composable security in the plain model from standard assumptions, in FOCS (2010), pp. 541–550

19.

K.-M. Chung, E. Lui, R. Pass, From weak to strong zero-knowledge and applications, in TCC (2015), pp. 66–92

20.

M. Ciampi, R. Ostrovsky, L. Siniscalchi, I. Visconti, Round-optimal secure two-party computation from trapdoor permutations, in TCC (2017), pp. 678–710

21.

J. Doerner, Y. Kondi, E. Lee, A. Shelat. Secure two-party threshold ECDSA from ECDSA assumptions, in IEEE Symposium on Security and Privacy, SP (2018), pp. 980–997

22.

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

23.

S. Even, O. Goldreich, A. Lempel. A randomized protocol for signing contracts. Commun. ACM 28(6), 637–647 (1985)MathSciNetCrossRef

24.

M. Fischlin, Trapdoor commitment schemes and their applications. Ph.D. Thesis (2001)

25.

T. K. Frederiksen, Y. Lindell, V. Osheter, B. Pinkas, Fast distributed RSA key generation for semi-honest and malicious adversaries, in CRYPTO (2018), pp. 331–361

26.

U. Feige, A. Shamir, Witness indistinguishable and witness hiding protocols, in STOC (1990), pp. 416–426

27.

T. El Gamal, A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theory, 31(4), 469–472 (1985)MathSciNetCrossRef

28.

O. Goldreich, H. Krawczyk, On the composition of zero-knowledge proof systems. SIAM J. Comput., 25(1), 169–192 (1996)MathSciNetCrossRef

29.

S. Dov Gordon, J. Katz, Partial fairness in secure two-party computation, in EUROCRYPT (2010), pp. 157–176

30.

J. A. Garay, J. Katz, B. Tackmann, V. Zikas, How fair is your protocol?: A utility-based approach to protocol optimality, in PODC (2015), pp. 281–290

31.

O. Goldreich, L. A. Levin, A hard-core predicate for all one-way functions, in STOC (1989), pp. 25–32

32.

S. Garg, P. Mukherjee, O. Pandey, A. Polychroniadou, The exact round complexity of secure computation. In M. Fischlin, J.S. Coron, editors, Advances in Cryptology - EUROCRYPT, 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8–12, 2016, Proceedings, Part II, pages 448–476. Springer, Berlin, Heidelberg (2016)

33.

S. Goldwasser, S. Micali, R. L. Rivest, A “paradoxical” solution to the signature problem (extended abstract), in FOCS (1984), pp. 441–448

34.

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

35.

O. Goldreich, Foundations of cryptography: Vol. 2, Basic Applications (Cambridge University Press, New York, 2004)CrossRef

36.

S. Garg, A. Srinivasan, Two-round multiparty secure computation from minimal assumptions, in EUROCRYPT (2018), pp. 468–499

37.

I. Haitner, Semi-honest to malicious oblivious transfer—the black-box way, in TCC (2008), pp. 412–426

38.

S. Halevi, C. Hazay, A. Polychroniadou, M. Venkitasubramaniam. Round-optimal secure multi-party computation, in CRYPTO (2018), pp. 488–520

39.

I. Haitner, Y. Ishai, E. Kushilevitz, Y. Lindell, E. Petrank, Black-box constructions of protocols for secure computation. SIAM J. Comput. 40(2), 225–266 (2011)MathSciNetCrossRef

40.

S. Halevi, Y. T. Kalai, Smooth projective hashing and two-message oblivious transfer. J. Cryptol. 25(1), 158–193 (2012)MathSciNetCrossRef

41.

C. Hazay, G. L. Mikkelsen, T. Rabin, T. Toft, Efficient RSA key generation and threshold Paillier in the two-party setting, in CT-RSA (2012), pp. 313–331

42.

C. Hazay, P. Scholl, E. Soria-Vazquez, Low cost constant round MPC combining BMR and oblivious transfer, in ASIACRYPT (2017), pp. 598–628

43.

Y. Ishai, E. Kushilevitz, R. Ostrovsky, M. Prabhakaran, A. Sahai, Efficient non-interactive secure computation, in EUROCRYPT (2011), pp. 406–425

44.

Y. Ishai, E. Kushilevitz, R. Ostrovsky, A. Sahai, Zero-knowledge proofs from secure multiparty computation. SIAM J. Comput. 39(3), 1121–1152 (2009)MathSciNetCrossRef

45.

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

46.

M. Keller, E. Orsini, P. Scholl, MASCOT: faster malicious arithmetic secure computation with oblivious transfer, in CCS (2016), pp. 830–842

47.

Y. Lindell, Parallel coin-tossing and constant-round secure two-party computation, in CRYPTO (2001), pp. 171–189

48.

Y. Lindell, A. Nof, Fast secure multiparty ECDSA with practical distributed key generation and applications to cryptocurrency custody, in CCS (2018), pp. 1837–1854

49.

S. Micali, Simple and fast optimistic protocols for fair electronic exchange, in PODC (2003), pp. 12–19

50.

T. Moran, M. Naor, G. Segev, An optimally fair coin toss, in TCC (2009), pp. 1–18

51.

S. Micali, R. Pass, A. Rosen, Input-indistinguishable computation, in FOCS (2006), pp. 367–378

52.

S. Micali, P. Rogaway, Secure computation (abstract), in CRYPTO (1991), pp. 392–404

53.

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

54.

M. Naor, B. Pinkas, Efficient oblivious transfer protocols, in SODA (2001), pp. 448–457

55.

R. Ostrovsky, S. Richelson, A. Scafuro, Round-optimal black-box two-party computation, in CRYPTO (2015), pp. 339–358

56.

R. Pass, Simulation in quasi-polynomial time, and its application to protocol composition, in EUROCRYPT (2003), pp. 160–176

57.

T. P. Pedersen, Non-interactive and information-theoretic secure verifiable secret sharing, in CRYPTO (1991), pp. 129–140

58.

M. Prabhakaran, A. Sahai, New notions of security: achieving universal composability without trusted setup, in STOC (2004), pp. 242–251

59.

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

60.

R. Pass, H. Wee, Black-box constructions of two-party protocols from one-way functions, in TCC (2009), pp. 403–418

61.

A. Shamir, How to share a secret. Commun. ACM 22(11), 612–613 (1979)MathSciNetCrossRef

62.

A. C.-C. Yao, Theory and applications of trapdoor functions (extended abstract), in FOCS (1982), pp. 80–91

63.

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

Titel: What Security Can We Achieve Within 4 Rounds?
verfasst von: Carmit Hazay
Muthuramakrishnan Venkitasubramaniam
Publikationsdatum: 22.05.2019
Verlag: Springer US
Erschienen in: Journal of Cryptology / Ausgabe 4/2019
Print ISSN: 0933-2790
Elektronische ISSN: 1432-1378
DOI: https://doi.org/10.1007/s00145-019-09323-1

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"

Weitere Artikel der Ausgabe 4/2019

Fully Secure Functional Encryption with a Large Class of Relations from the Decisional Linear Assumption

Updating Key Size Estimations for Pairings

Cryptanalysis of NORX v2.0

Making Masking Security Proofs Concrete (Or How to Evaluate the Security of Any Leaking Device), Extended Version

Constant-Round Maliciously Secure Two-Party Computation in the RAM Model

Nonlinear Invariant Attack: Practical Attack on Full SCREAM, iSCREAM, and Midori64