nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

Very-Efficient Simulatable Flipping of Many Coins into a Well

(and a New Universally-Composable Commitment Scheme)

verfasst von : Luís T. A. N. Brandão

Erschienen in: Public-Key Cryptography – PKC 2016

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

This paper presents new cryptographic protocols for a stand-alone simulatable two-party parallel coin-flipping (into a well) and a universally composable commitment scheme, with near optimal asymptotic communication rate, in the static and computational malicious model. The approach, denoted expand-mask-hash, uses in both protocols a pseudo-random generator (PRG) and a collision-resistant hash function (CR-Hash) to combine separate extractable commitments and equivocable commitments (associated with short bit-strings) into a unified extractable-and-equivocable property amplified to a larger target length, amortizing the cost of base commitments. The new stand-alone coin-flipping protocol is based on a simple augmentation of the traditional coin-flipping template. To the knowledge of the author, it is the first proposal shown to simultaneously be two-side-simulatable and have an asymptotic (as the target length increases) communication rate converging to two bits per flipped coin and computation rate per party converging to that of PRG-generating and CR-hashing a bit-string with the target length. The new universally composable commitment scheme has efficiency comparable to very recent state-of-the-art constructions – namely asymptotic communication rate as close to 1 as desired, for each phase (commit and open) – while following a distinct design approach. Notably it does not require explicit use of oblivious transfer and it uses an erasure encoding instead of stronger error correction codes.

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 Universally Composable Authentication and Key-Exchange with Global PKI

Nächstes Kapitel Robust Secret Sharing Schemes Against Local Adversaries

[ALSZ15]

Asharov, G., Lindell, Y., Schneider, T., Zohner, M.: More efficient oblivious transfer extensions with security for malicious adversaries. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 673–701. Springer, Heidelberg (2015). doi:10.1007/978-3-662-46800-5_26. Also at ia.cr/2015/061

[BCPV13]

Blazy, O., Chevalier, C., Pointcheval, D., Vergnaud, D.: Analysis and improvement of Lindell’s uc-secure commitment schemes. In: Jacobson, M., Locasto, M., Mohassel, P., Safavi-Naini, R. (eds.) ACNS 2013. LNCS, vol. 7954, pp. 534–551. Springer, Heidelberg (2013). doi:10.1007/978-3-642-38980-1_34. Also at ia.cr/2013123 CrossRef

[Bea96]

Beaver, D.: Adaptive zero knowledge and computational equivocation (extended abstract). In: STOC 1996, pp. 629–638. ACM, New York (1996). doi:10.1145/237814.238014

[BK15]

Barker, E., Kelsey, J.: Recommendation for Random Number Generation Using Deterministic Random Bit Generators, NIST SP800-90A Rev. 1, NIST-ITL-CSD, U.S. Department of Commerce, June 2015. doi:10.6028/NIST.SP.800-90Ar1

[Blu83]

Blum, M.: Coin flipping by telephone – a protocol for solving impossible problems. SIGACT News 15, 23–27 (1983). doi:10.1145/1008908.1008911. Appeared also at CRYPTO 1981CrossRef

[Bra13]

Brandão, L.T.A.N.: Secure two-party computation with reusable bit-commitments, via a cut-and-choose with forge-and-lose technique. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013, Part II. LNCS, vol. 8270, pp. 441–463. Springer, Heidelberg (2013). doi:10.1007/978-3-642-42045-0_23. Also at ia.cr/2013/577 CrossRef

[Can00]

Canetti, R.: Security and composition of multiparty cryptographic protocols. J. Cryptol. 13(1), 143–202 (2000). doi:10.1007/s001459910006. Also at ia.cr/1998/018 CrossRefMathSciNetMATH

[Can01]

Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: FOCS 2001, pp. 136–145. IEEE (2001). doi:10.1109/SFCS.2001.959888, Also at ia.cr/2000/067

[CDD+15]

Cascudo, I., Damgård, I., David, B., Giacomelli, I., Nielsen, J.B., Trifiletti, R.: Additively homomorphic UC commitments with optimal amortized overhead. In: Katz, J. (ed.) PKC 2015. LNCS, vol. 9020, pp. 495–515. Springer, Heidelberg (2015). doi:10.1007/978-3-662-46447-2_22. Also at ia.cr/2014/829

[CF01]

Canetti, R., Fischlin, M.: Universally composable commitments. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 19–40. Springer, Heidelberg (2001). doi:10.1007/3-540-44647-8_2. Also at ia.cr/2001/055 CrossRef

[CLOS02]

Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally composable two-party and multi-party secure computation. In: STOC 2002, pp. 494–503. ACM, New York (2002). doi:10.1145/509907.509980, Also at ia.cr/2002/140

[CR03]

Canetti, R., Rabin, T.: Universal composition with joint state. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 265–281. Springer, Heidelberg (2003). doi:10.1007/978-3-540-45146-4_16. Also at ia.cr/2002/047 CrossRef

[Cre03]

Di Crescenzo, G.: Equivocable and extractable commitment schemes. In: Cimato, S., Galdi, C., Persiano, G. (eds.) SCN 2002. LNCS, vol. 2576, pp. 74–87. Springer, Heidelberg (2003). doi:10.1007/3-540-36413-7_6 CrossRef

[Dam88]

Damgård, I.B.: Collision free hash functions and public key signature schemes. In: Price, W.L., Chaum, D. (eds.) EUROCRYPT 1987. LNCS, vol. 304, pp. 203–216. Springer, Heidelberg (1988). doi:10.1007/3-540-39118-5_19

[DCIO98]

Di Crescenzo, G., Ishai, Y., Ostrovsky, R.: Non-interactive and non-malleable commitment. In: STOC 1998, pp. 141–150. ACM, New York (1998). doi:10.1145/276698.276722

[DCKOS01]

Di Crescenzo, G., Katz, J., Ostrovsky, R., Smith, A.: Efficient and non-interactive non-malleable commitment. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 40–59. Springer, Heidelberg (2001). doi:10.1007/3-540-44987-6_4. Also at ia.cr/2001/032 CrossRef

[DCO99]

Di Crescenzo, G., Ostrovsky, R.: On concurrent zero-knowledge with pre-processing (extended abstract). In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 485–502. Springer, Heidelberg (1999). doi:10.1007/3-540-48405-1_31 CrossRef

[DDGN14]

Damgård, I., David, B., Giacomelli, I., Nielsen, J.B.: Compact VSS and efficient homomorphic UC commitments. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014, Part II. LNCS, vol. 8874, pp. 213–232. Springer, Heidelberg (2014). doi:10.1007/978-3-662-45608-8_12. Also at ia.cr/2014/370

[DL09]

Damgård, I., Lunemann, C.: Quantum-secure coin-flipping and applications. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 52–69. Springer, Heidelberg (2009). doi:10.1007/978-3-642-10366-7_4. Also at arXiv:0903.3118 CrossRef

[DN02]

Damgård, I.B., Nielsen, J.B.: Perfect hiding and perfect binding universally composable commitment schemes with constant expansion factor. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 581–596. Springer, Heidelberg (2002). doi:10.1007/3-540-45708-9_37. Also at ia.cr/2001/091 CrossRef

[DNO10]

Damgård, I., Nielsen, J.B., Orlandi, C.: On the necessary and sufficient assumptions for UC computation. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 109–127. Springer, Heidelberg (2010). doi:10.1007/978-3-642-11799-2_8. Also at ia.cr/2009/247 CrossRef

[DO10]

Damgård, I., Orlandi, C.: Multiparty computation for dishonest majority: from passive to active security at low cost. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 558–576. Springer, Heidelberg (2010). doi:10.1007/978-3-642-14623-7_30. Also at ia.cr/2010/318 CrossRef

[ElG85]

El Gamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. In: Blakely, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 10–18. Springer, Heidelberg (1985). doi:10.1007/3-540-39568-7_2 CrossRef

[FJNT16]

Frederiksen, T.K., Jakobsen, T.P., Nielsen, J.B., Trifiletti, R.: On the complexity of additively homomorphic UC commitments. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016-A. LNCS, vol. 9562, pp. 542–565. Springer, Heidelberg (2016). doi:10.1007/978-3-662-49096-9_23. Also at ia.cr/2015/694 CrossRef

[FLM11]

Fischlin, M., Libert, B., Manulis, M.: Non-interactive and re-usable universally composable string commitments with adaptive security. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 468–485. Springer, Heidelberg (2011). doi:10.1007/978-3-642-25385-0_25 CrossRef

[FS90]

Feige, U., Shamir, A.: Zero knowledge proofs of knowledge in two rounds. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 526–544. Springer, New York (1990). doi:10.1007/0-387-34805-0_46

[Fuj14]

Fujisaki, E.: All-but-many encryption. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8874, pp. 426–447. Springer, Heidelberg (2014). doi:10.1007/978-3-662-45608-8_23. Also at ia.cr/2012/379

[GIKW14]

Garay, J.A., Ishai, Y., Kumaresan, R., Wee, H.: On the complexity of UC commitments. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 677–694. Springer, Heidelberg (2014). doi:10.1007/978-3-642-55220-5_37 CrossRef

[GK96]

Goldreich, O., Kahan, A.: How to construct constant-round zero-knowledge proof systems for NP. J. Cryptol. 9(3), 167–189 (1996). doi:10.1007/BF00208001 CrossRefMathSciNetMATH

[GMS08]

Goyal, V., Mohassel, P., Smith, A.: Efficient two party and multi party computation against covert adversaries. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 289–306. Springer, Heidelberg (2008). doi:10.1007/978-3-540-78967-3_17 CrossRef

[Gol04]

Goldreich, O.: Foundations of Cryptography. Basic Applications, vol. 2. Cambridge University Press, New York (2004). doi:10.1017/CBO9780511721656. isbn: 9780521830843CrossRefMATH

[HILL99]

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

[HKE13]

Huang, Y., Katz, J., Evans, D.: Efficient secure two-party computation using symmetric cut-and-choose. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part II. LNCS, vol. 8043, pp. 18–35. Springer, Heidelberg (2013). doi:10.1007/978-3-642-40084-1_2. Also at ia.cr/2013/081 CrossRef

[HMQU06]

Hofheinz, D., Müller-Quade, J., Unruh, D.: On the (im-)possibility of extending coin toss. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 504–521. Springer, Heidelberg (2006). doi:10.1007/11761679_30. Also at ia.cr/2006/177 CrossRef

[Kra94]

Krawczyk, H.: Secret sharing made short. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 136–146. Springer, Heidelberg (1994). doi:10.1007/3-540-48329-2_12

[KS08]

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, Part II. LNCS, vol. 5126, pp. 486–498. Springer, Heidelberg (2008). doi:10.1007/978-3-540-70583-3_40 CrossRef

[Lin03]

Lindell, Y.: Parallel coin-tossing and constant-round secure two-party computation. J. Cryptol. 16(3), 143–184 (2003). doi:10.1007/s00145-002-0143-7. Also at ia.cr/2001/107 CrossRefMathSciNetMATH

[Lin11]

Lindell, Y.: Highly-efficient universally-composable commitments based on the DDH assumption. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 446–466. Springer, Heidelberg (2011). doi:10.1007/978-3-642-20465-4_25. Also at ia.cr/2011/180 CrossRef

[Lin13]

Lindell, Y.: Fast cut-and-choose based protocols for malicious and covert adversaries. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part II. LNCS, vol. 8043, pp. 1–17. Springer, Heidelberg (2013). doi:10.1007/978-3-642-40084-1_1. Also at ia.cr/2013/079 CrossRef

[Lin15]

Lindell, Y.: An efficient transform from sigma protocols to NIZK with a CRS and non-programmable random oracle. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015, Part I. LNCS, vol. 9014, pp. 93–109. Springer, Heidelberg (2015). doi:10.1007/978-3-662-46494-6_5. Also at ia.cr/2014/710

[LN11]

Lunemann, C., Nielsen, J.B.: Fully simulatable quantum-secure coin-flipping and applications. In: Nitaj, A., Pointcheval, D. (eds.) AFRICACRYPT 2011. LNCS, vol. 6737, pp. 21–40. Springer, Heidelberg (2011). doi:10.1007/978-3-642-21969-6_2. Also at ia.cr/2011/065 CrossRef

[LPS08]

Lindell, Y., Pinkas, B., Smart, N.P.: Implementing two-party computation efficiently with security against malicious adversaries. In: Ostrovsky, R., De Prisco, R., Visconti, I. (eds.) SCN 2008. LNCS, vol. 5229, pp. 2–20. Springer, Heidelberg (2008). doi:10.1007/978-3-540-85855-3_2 CrossRef

[Lub02]

Luby, M.: LT codes. In: FOCS 2002, pp. 271–280. IEEE (2002). doi:10.1109/SFCS.2002.1181950

[Nao91]

Naor, M.: Bit commitment using pseudorandomness. J. Cryptol. 4(2), 151–158 (1991). doi:10.1007/BF00196774 CrossRefMATH

[Nat15]

National Institute of Standards and Technology, SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions. FIPS Pub 202, NIST-ITL, U.S. Department of Commerce, August 2015. doi:10.6028/NIST.FIPS.202

[NY89]

Naor, M., Yung, M.: Universal one-way hash functions and their cryptographic applications. In: STOC 1989, pp. 33–43. ACM, New York (1989). doi:10.1145/73007.73011

[Ped92]

Pedersen, T.P.: Non-interactive and information-theoretic secure verifiable secret sharing. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 129–140. Springer, Heidelberg (1992). doi:10.1007/3-540-46766-1_9

[PW09]

Pass, R., Wee, H.: Black-box constructions of two-party protocols from one-way functions. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 403–418. Springer, Heidelberg (2009). doi:10.1007/978-3-642-00457-5_24 CrossRef

[Rab89]

Rabin, M.O.: Efficient dispersal of information for security, load balancing, and fault tolerance. J. ACM 36(2), 335–348 (1989). doi:10.1145/62044.62050 CrossRefMathSciNetMATH

[Rom90]

Rompel, J.: One-way functions are necessary and sufficient for secure signatures. In: STOC 1990, pp. 387–394. ACM, New York (1990). doi:10.1145/100216.100269

[Ros04]

Rosen, A.: A note on constant-round zero-knowledge proofs for NP. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 191–202. Springer, Heidelberg (2004). doi:10.1007/978-3-540-24638-1_11 CrossRef

[RS60]

Reed, I.S., Solomon, G.: Polynomial codes over certain finite fields. J. SIAM 8(2), 300–304 (1960). doi:10.1137/0108018 MathSciNetMATH

[Rus95]

Russell, A.: Necessary and sufficient conditions for collision-free hashing. J. Cryptol. 8(2), 87–99 (1995). doi:10.1007/BF00190757 MATH

[Sch91]

Schnorr, C.: Efficient signature generation by smart cards. J. Cryptol. 4(3), 161–174 (1991). doi:10.1007/BF00196725 CrossRefMathSciNetMATH

[SCP00]

De Santis, A., Di Crescenzo, G., Persiano, G.: Necessary and sufficient assumptions for non-interactive zero-knowledge proofs of knowledge for all NP relations. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol. 1853, pp. 451–462. Springer, Heidelberg (2000). doi:10.1007/3-540-45022-X_38 CrossRef

[Sha79]

Shamir, A.: How to share a secret. Commun. ACM 22(11), 612–613 (1979). doi:10.1145/359168.359176 CrossRefMathSciNetMATH

[Sho06]

Shokrollahi, A.: Raptor codes. IEEE Trans. Inf. Theory 52(6), 2551–2567 (2006). doi:10.1109/TIT.2006.874390 CrossRefMathSciNetMATH

[Sim98]

Simon, D.R.: Findings collisions on a one-way street: can secure hash functions be based on general assumptions? In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 334–345. Springer, Heidelberg (1998). doi:10.1007/BFb0054137 CrossRef

[SS11]

Shelat, A., Shen, C.: Two-output secure computation with malicious adversaries. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 386–405. Springer, Heidelberg (2011). doi:10.1007/978-3-642-20465-4_22. ia.cr/2011/533

[VZ12]

Vadhan, S., Zheng, C.J.: Characterizing pseudoentropy and simplifying pseudorandom generator constructions. In: STOC 2012, pp. 817–836. ACM, New York (2012). doi:10.1145/2213977.2214051

Titel: Very-Efficient Simulatable Flipping of Many Coins into a Well
verfasst von: Luís T. A. N. Brandão
Verlag: Springer Berlin Heidelberg
Buch: Public-Key Cryptography – PKC 2016
Print ISBN: 978-3-662-49386-1

Electronic ISBN: 978-3-662-49387-8

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-662-49387-8_12

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"