Document Zbl 1518.94043 - zbMATH Open
(Public) verifiability for composable protocols without adaptivity or zero-knowledge. (English) Zbl 1518.94043
Ge, Chunpeng (ed.) et al., Provable and practical security. 16th international conference, ProvSec 2022, Nanjing, China, November 11–12, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13600, 249-272 (2022).
Summary: The Universal Composability (UC) framework [R. Canetti, in: Proceedings of the 42nd IEEE symposium on foundations of computer science, FOCS 2001, Las Vegas, NV, USA, October 14–17, 2001. Los Alamitos, CA: IEEE Computer Society 136–145 (2001; doi:10.1109/SFCS.2001.959888)] is the current standard for proving security of cryptographic protocols under composition. It allows to reason about complex protocol structures in a bottom-up fashion: any building block that is UC-secure can be composed arbitrarily with any other UC-secure construction while retaining their security guarantees. Unfortunately, some protocol properties such as the verifiability of outputs require excessively strong tools to achieve in UC. In particular, “obviously secure” constructions cannot directly be shown to be UC-secure, and verifiability of building blocks does not easily carry over to verifiability of the composed construction. In this work, we study Non-Interactive (Public) Verifiability of UC protocols, i.e. under which conditions a verifier can ascertain that a party obtained a specific output from the protocol. The verifier may have been part of the protocol execution or not, as in the case of public verifiability. We consider a setting used in a number of applications where it is ok to reveal the input of the party whose output gets verified and analyze under which conditions such verifiability can generically be achieved using “cheap” cryptographic primitives. That is, we avoid having to rely on adaptively secure primitives or heavy computational tools such as NIZKs. As Non-Interactive Public Verifiability is crucial when composing protocols with a public ledger, our approach can be beneficial when designing these with provably composable security and efficiency in mind.
For the entire collection see [Zbl 1515.68035].
MSC:
References:
| [1] | Alwen, J.; Ostrovsky, R.; Zhou, H-S; Zikas, V.; Gennaro, R.; Robshaw, M., Incoercible multi-party computation and universally composable receipt-free voting, Advances in Cryptology - CRYPTO 2015, 763-780 (2015), Heidelberg: Springer, Heidelberg · Zbl 1352.94024 · doi:10.1007/978-3-662-48000-7_37 |
| [2] | Andrychowicz, M., Dziembowski, S., Malinowski, D., Mazurek, L.: Secure multiparty computations on bitcoin. In: 2014 IEEE Symposium on Security and Privacy, pp. 443-458. IEEE Computer Society Press, May 2014 · Zbl 1448.91328 |
| [3] | Asharov, G.; Orlandi, C.; Wang, X.; Sako, K., Calling out cheaters: covert security with public verifiability, Advances in Cryptology - ASIACRYPT 2012, 681-698 (2012), Heidelberg: Springer, Heidelberg · Zbl 1292.94022 · doi:10.1007/978-3-642-34961-4_41 |
| [4] | Baum, C.; Damgård, I.; Orlandi, C.; Abdalla, M.; De Prisco, R., Publicly auditable secure multi-party computation, Security and Cryptography for Networks, 175-196 (2014), Cham: Springer, Cham · Zbl 1346.68084 · doi:10.1007/978-3-319-10879-7_11 |
| [5] | Baum, C.; David, B.; Dowsley, R.; Bonneau, J.; Heninger, N., Insured MPC: efficient secure computation with financial penalties, Financial Cryptography and Data Security, 404-420 (2020), Cham: Springer, Cham · Zbl 1459.94096 · doi:10.1007/978-3-030-51280-4_22 |
| [6] | Baum, C., David, B., Dowsley, R.: (Public) verifiability for composable protocols without adaptivity or zero-knowledge. Cryptology ePrint Archive, Paper 2020/207 (2020). https://eprint.iacr.org/2020/207 · Zbl 1518.94043 |
| [7] | Baum, C.; David, B.; Frederiksen, TK; Sako, K.; Tippenhauer, NO, P2DEX: privacy-preserving decentralized cryptocurrency exchange, Applied Cryptography and Network Security, 163-194 (2021), Cham: Springer, Cham · Zbl 1492.91444 · doi:10.1007/978-3-030-78372-3_7 |
| [8] | Baum, C.; Orsini, E.; Scholl, P.; Hirt, M.; Smith, A., Efficient secure multiparty computation with identifiable abort, Theory of Cryptography, 461-490 (2016), Heidelberg: Springer, Heidelberg · Zbl 1406.94025 · doi:10.1007/978-3-662-53641-4_18 |
| [9] | Baum, C.; Orsini, E.; Scholl, P.; Soria-Vazquez, E.; Micciancio, D.; Ristenpart, T., Efficient constant-round MPC with identifiable abort and public verifiability, Advances in Cryptology - CRYPTO 2020, 562-592 (2020), Cham: Springer, Cham · Zbl 07614580 · doi:10.1007/978-3-030-56880-1_20 |
| [10] | Bellare, M.; Hoang, VT; Rogaway, P.; Wang, X.; Sako, K., Adaptively secure garbling with applications to one-time programs and secure outsourcing, Advances in Cryptology - ASIACRYPT 2012, 134-153 (2012), Heidelberg: Springer, Heidelberg · Zbl 1292.94027 · doi:10.1007/978-3-642-34961-4_10 |
| [11] | Bentov, I.; Kumaresan, R.; Garay, JA; Gennaro, R., How to use bitcoin to design fair protocols, Advances in Cryptology - CRYPTO 2014, 421-439 (2014), Heidelberg: Springer, Heidelberg · Zbl 1335.94032 · doi:10.1007/978-3-662-44381-1_24 |
| [12] | Camenisch, J.; Dubovitskaya, M.; Rial, A.; Robshaw, M.; Katz, J., UC commitments for modular protocol design and applications to revocation and attribute tokens, Advances in Cryptology - CRYPTO 2016, 208-239 (2016), Heidelberg: Springer, Heidelberg · Zbl 1406.94031 · doi:10.1007/978-3-662-53015-3_8 |
| [13] | Camenisch, J., Lehmann, A., Neven, G., Samelin, K.: UC-secure non-interactive public-key encryption. In: IEEE CSF 2017 (2017) |
| [14] | Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: 42nd FOCS, pp. 136-145. IEEE Computer Society Press, October 2001 |
| [15] | Canetti, R.: Universally composable signature, certification, and authentication. In: CSFW 2004 (2004) |
| [16] | Canetti, R.; Dodis, Y.; Pass, R.; Walfish, S.; Vadhan, SP, Universally composable security with global setup, Theory of Cryptography, 61-85 (2007), Heidelberg: Springer, Heidelberg · Zbl 1129.94014 · doi:10.1007/978-3-540-70936-7_4 |
| [17] | Canetti, R.; Herzog, J.; Halevi, S.; Rabin, T., Universally composable symbolic analysis of mutual authentication and key-exchange protocols, Theory of Cryptography, 380-403 (2006), Heidelberg: Springer, Heidelberg · Zbl 1112.94025 · doi:10.1007/11681878_20 |
| [18] | Canetti, R., Jain, A., Scafuro, A.: Practical UC security with a global random oracle. In: Ahn, G.-J., Yung, M., Li, N. (eds.) ACM CCS 2014, pp. 597-608. ACM Press, November 2014 |
| [19] | Canetti, R.; Rabin, T.; Boneh, D., Universal composition with joint state, Advances in Cryptology - CRYPTO 2003, 265-281 (2003), Heidelberg: Springer, Heidelberg · Zbl 1122.94360 · doi:10.1007/978-3-540-45146-4_16 |
| [20] | Canetti, R.; Sarkar, P.; Wang, X.; Kiayias, A.; Kohlweiss, M.; Wallden, P.; Zikas, V., Blazing fast OT for three-round UC OT extension, Public-Key Cryptography - PKC 2020, 299-327 (2020), Cham: Springer, Cham · Zbl 1532.94035 · doi:10.1007/978-3-030-45388-6_11 |
| [21] | Canetti, R.; Sarkar, P.; Wang, X.; Moriai, S.; Wang, H., Efficient and round-optimal oblivious transfer and commitment with adaptive security, Advances in Cryptology - ASIACRYPT 2020, 277-308 (2020), Cham: Springer, Cham · Zbl 1511.94066 · doi:10.1007/978-3-030-64840-4_10 |
| [22] | Cascudo, I.; David, B.; Gollmann, D.; Miyaji, A.; Kikuchi, H., SCRAPE: scalable randomness attested by public entities, Applied Cryptography and Network Security, 537-556 (2017), Cham: Springer, Cham · Zbl 1521.94035 · doi:10.1007/978-3-319-61204-1_27 |
| [23] | Cascudo, I.; David, B.; Moriai, S.; Wang, H., ALBATROSS: publicly AttestabLe BATched randomness based on secret sharing, Advances in Cryptology - ASIACRYPT 2020, 311-341 (2020), Cham: Springer, Cham · Zbl 1511.94173 · doi:10.1007/978-3-030-64840-4_11 |
| [24] | Chen, J.; Micali, S., Algorand: a secure and efficient distributed ledger, Theor. Comput. Sci., 777, 155-183 (2019) · Zbl 1423.68152 · doi:10.1016/j.tcs.2019.02.001 |
| [25] | Cleve, R.: Limits on the security of coin flips when half the processors are faulty (extended abstract). In: 18th ACM STOC, pp. 364-369. ACM Press, May 1986 |
| [26] | Damgård, I.; Pastro, V.; Smart, N.; Zakarias, S.; Safavi-Naini, R.; Canetti, R., Multiparty computation from somewhat homomorphic encryption, Advances in Cryptology - CRYPTO 2012, 643-662 (2012), Heidelberg: Springer, Heidelberg · Zbl 1296.94104 · doi:10.1007/978-3-642-32009-5_38 |
| [27] | David, B.; Gaži, P.; Kiayias, A.; Russell, A.; Nielsen, JB; Rijmen, V., Ouroboros praos: an adaptively-secure, semi-synchronous proof-of-stake blockchain, Advances in Cryptology - EUROCRYPT 2018, 66-98 (2018), Cham: Springer, Cham · Zbl 1423.94066 · doi:10.1007/978-3-319-78375-8_3 |
| [28] | Garay, J.; Kiayias, A.; Leonardos, N.; Oswald, E.; Fischlin, M., The bitcoin backbone protocol: analysis and applications, Advances in Cryptology - EUROCRYPT 2015, 281-310 (2015), Heidelberg: Springer, Heidelberg · Zbl 1371.94636 · doi:10.1007/978-3-662-46803-6_10 |
| [29] | 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 |
| [30] | Ishai, Y.; Ostrovsky, R.; Zikas, V.; Garay, JA; Gennaro, R., Secure multi-party computation with identifiable abort, Advances in Cryptology - CRYPTO 2014, 369-386 (2014), Heidelberg: Springer, Heidelberg · Zbl 1335.94053 · doi:10.1007/978-3-662-44381-1_21 |
| [31] | Jafargholi, Z.; Oechsner, S.; Bhargavan, K.; Oswald, E.; Prabhakaran, M., Adaptive security of practical garbling schemes, Progress in Cryptology - INDOCRYPT 2020, 741-762 (2020), Cham: Springer, Cham · Zbl 1492.94125 · doi:10.1007/978-3-030-65277-7_33 |
| [32] | Kiayias, A.; Russell, A.; David, B.; Oliynykov, R.; Katz, J.; Shacham, H., Ouroboros: a provably secure proof-of-stake blockchain protocol, Advances in Cryptology - CRYPTO 2017, 357-388 (2017), Cham: Springer, Cham · Zbl 1407.94128 · doi:10.1007/978-3-319-63688-7_12 |
| [33] | Kiayias, A.; Zhou, H-S; Zikas, V.; Fischlin, M.; Coron, J-S, Fair and robust multi-party computation using a global transaction ledger, Advances in Cryptology - EUROCRYPT 2016, 705-734 (2016), Heidelberg: Springer, Heidelberg · Zbl 1371.94643 · doi:10.1007/978-3-662-49896-5_25 |
| [34] | Lindell, Y.; Pinkas, B., Secure two-party computation via cut-and-choose oblivious transfer, J. Cryptol., 25, 4, 680-722 (2012) · Zbl 1278.94056 · doi:10.1007/s00145-011-9107-0 |
| [35] | Nakamoto, S.: Bitcoin: a peer-to-peer electronic cash system (2008) |
| [36] | Nielsen, JB; Nordholt, PS; Orlandi, C.; Burra, SS; Safavi-Naini, R.; Canetti, R., A new approach to practical active-secure two-party computation, Advances in Cryptology - CRYPTO 2012, 681-700 (2012), Heidelberg: Springer, Heidelberg · Zbl 1296.94134 · doi:10.1007/978-3-642-32009-5_40 |
| [37] | Schoenmakers, B.; Veeningen, M.; Malkin, T.; Kolesnikov, V.; Lewko, AB; Polychronakis, M., Universally verifiable multiparty computation from threshold homomorphic cryptosystems, Applied Cryptography and Network Security, 3-22 (2015), Cham: Springer, Cham · Zbl 1459.68072 · doi:10.1007/978-3-319-28166-7_1 |
| [38] | Zahur, S.; Rosulek, M.; Evans, D.; Oswald, E.; Fischlin, M., Two halves make a whole - reducing data transfer in garbled circuits using half gates, Advances in Cryptology - EUROCRYPT 2015, 220-250 (2015), Heidelberg: Springer, Heidelberg · Zbl 1371.94662 · doi:10.1007/978-3-662-46803-6_8 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.