Possibility and impossibility results for selective decommitments. (English) Zbl 1258.94038
Summary: The selective decommitment problem can be described as follows: assume that an adversary receives a number of commitments and then may request openings of, say, half of them. Do the unopened commitments remain secure? Although this question arose more than twenty years ago, no satisfactory answer could be presented so far. We answer the question in several ways:
- 1.
- If simulation-based security is desired (i.e., if we demand that the adversary’s output can be simulated by a machine that does not see the unopened commitments), then security is not provable for noninteractive or perfectly binding commitment schemes via black-box reductions to standard cryptographic assumptions. However, we show how to achieve security in this sense with interaction and a non-black-box reduction to one-way permutations.
- 2.
- If only indistinguishability of the unopened commitments from random commitments is desired, then security is not provable for (interactive or noninteractive) perfectly binding commitment schemes, via black-box reductions to standard cryptographic assumptions. However, any statistically hiding scheme does achieve security in this sense.
- –
- Essentially, an encryption scheme must be non-committing in order to achieve provable security against an adaptive adversary.
- –
- When implemented with our secure commitment scheme, the interactive proof for graph 3-coloring due to becomes zero-knowledge under parallel composition.
MSC:
| 94A60 | Cryptography |
References:
| [1] | Barak, B., How to go beyond the black-box simulation barrier, 42th Annual Symposium on Foundations of Computer Science, Proceedings of FOCS 2001, 106-115 (2001), Los Alamitos: IEEE Computer Society, Los Alamitos |
| [2] | Barak, B.; Goldreich, O., Universal arguments and their applications, 17th Annual IEEE Conference on Computational Complexity, Proceedings of CoCo 2002, 194-203 (2002), Los Alamitos: IEEE Computer Society, Los Alamitos |
| [3] | Barak, B.; Prabhakaran, M.; Sahai, A., Concurrent non-malleable zero-knowledge, 47th Annual Symposium on Foundations of Computer Science, Proceedings of FOCS 2006, 345-354 (2006), Los Alamitos: IEEE Computer Society, Los Alamitos |
| [4] | Beaver, D.; Feigenbaum, J., Plug and play encryption, Advances in Cryptology, Proceedings of CRYPTO ’91, 75-89 (1992), Berlin: Springer, Berlin · Zbl 0882.94014 |
| [5] | Bellare, M.; Rogaway, P., Random oracles are practical: a paradigm for designing efficient protocols, 1st ACM Conference on Computer and Communications Security, Proceedings of CCS 1993, 62-73 (1993), New York: Assoc. Comput. Math., New York |
| [6] | Bellare, M.; Rogaway, P.; de Santis, A., Optimal asymmetric encryption—how to encrypt with RSA, Advances in Cryptology, Proceedings of EUROCRYPT ’94, 92-111 (1995), Berlin: Springer, Berlin · Zbl 0881.94010 |
| [7] | Bellare, M.; Hofheinz, D.; Yilek, S.; Joux, A., Possibility and impossibility results for encryption and commitment secure under selective opening, Advances in Cryptology, Proceedings of EUROCRYPT 2009, 1-35 (2009), Berlin: Springer, Berlin · Zbl 1239.94033 |
| [8] | M. Blum, Coin flipping by telephone, in Advances in Cryptology, A Report on CRYPTO 81, ed. by A. Gersho. ECE Report, vol. 82-04 (University of California, Electrical and Computer Engineering, 1982), pp. 11-15 |
| [9] | Canetti, R., Universally composable security: a new paradigm for cryptographic protocols, 42th Annual Symposium on Foundations of Computer Science, Proceedings of FOCS 2001, 136-145 (2001), Los Alamitos: IEEE Computer Society, Los Alamitos |
| [10] | Canetti, R.; Fischlin, M.; Kilian, J., Universally composable commitments, Advances in Cryptology, Proceedings of CRYPTO 2001, 19-40 (2001), Berlin: Springer, Berlin · Zbl 1002.94528 |
| [11] | Canetti, R.; Feige, U.; Goldreich, O.; Naor, M., Adaptively secure multi-party computation, Twenty-Eighth Annual ACM Symposium on Theory of Computing, Proceedings of STOC 1995, 639-648 (1996), New York: Assoc. Comput. Math., New York · Zbl 0922.68048 |
| [12] | Canetti, R.; Dwork, C.; Naor, M.; Ostrovsky, R.; Kaliski, B. S. Jr., Deniable encryption, Advances in Cryptology, Proceedings of CRYPTO ’97, 90-104 (1997), Berlin: Springer, Berlin · Zbl 0882.94019 |
| [13] | Canetti, R.; Kilian, J.; Petrank, E.; Rosen, A., Concurrent zero-knowledge requires \(\tilde{\Omega}(\log n)\) rounds, 33th Annual ACM Symposium on Theory of Computing, Proceedings of STOC 2001, 570-579 (2001), New York: Assoc. Comput. Math., New York · Zbl 1317.68064 |
| [14] | Canetti, R.; Halevi, S.; Katz, J.; Kilian, J., Adaptively-secure, non-interactive public-key encryption, Theory of Cryptography, Proceedings of TCC 2005, 150-168 (2005), Berlin: Springer, Berlin · Zbl 1079.94537 |
| [15] | Canetti, R.; Dodis, Y.; Pass, R.; Walfish, S.; Vadhan, S., Universally composable security with global setup, Theory of Cryptography, Proceedings of TCC 2007, 61-85 (2007), Berlin: Springer, Berlin · Zbl 1129.94014 |
| [16] | Cramer, R.; Shoup, V., Design and analysis of practical public-key encryption schemes secure against chosen ciphertext attack, SIAM J. Comput., 33, 1, 167-226 (2003) · Zbl 1045.94013 · doi:10.1137/S0097539702403773 |
| [17] | Damgård, I.; Arge, L.; Cachin, C.; Jurdzinski, T.; Tarlecki, A., A “proof-reading” of some issues in cryptography, Automata, Languages and Programming, 34th International Colloquium, Proceedings of ICALP 2007, 2-11 (2007), Berlin: Springer, Berlin · Zbl 1171.94342 |
| [18] | Damgård, I.; Nielsen, J. B.; Bellare, M., Improved non-committing encryption schemes based on general complexity assumptions, Advances in Cryptology, Proceedings of CRYPTO 2000, 432-450 (2000), Berlin: Springer, Berlin · Zbl 0989.68509 |
| [19] | Damgård, I. B.; Pedersen, T. P.; Pfitzmann, B.; Stinson, D. R., On the existence of statistically hiding bit commitment schemes and fail-stop signatures, Advances in Cryptology, Proceedings of CRYPTO ’93, 250-265 (1994), Berlin: Springer, Berlin · Zbl 0873.94017 |
| [20] | Dodis, Y.; Oliveira, R.; Pietrzak, K.; Shoup, V., On the generic insecurity of the full domain hash, Advances in Cryptology, Proceedings of CRYPTO 2005, 449-466 (2005), Berlin: Springer, Berlin · Zbl 1145.94440 |
| [21] | Dolev, D.; Dwork, C.; Naor, M., Non-malleable cryptography, Twenty-Third Annual ACM Symposium on Theory of Computing, Proceedings of STOC 1991, 542-552 (1991), New York: Assoc. Comput. Math., New York |
| [22] | Dwork, C.; Naor, M.; Reingold, O.; Stockmeyer, L., Magic functions, J. ACM, 50, 6, 852-921 (2003) · Zbl 1325.68034 · doi:10.1145/950620.950623 |
| [23] | Dwork, C.; Naor, M.; Sahai, A., Concurrent zero-knowledge, J. ACM, 51, 6, 851-898 (2004) · Zbl 1125.94031 · doi:10.1145/1039488.1039489 |
| [24] | Feige, U.; Shamir, A., Witness indistinguishability and witness hiding protocols, Twenty-Second Annual ACM Symposium on Theory of Computing, Proceedings of STOC 1990, 416-426 (1990), New York: Assoc. Comput. Math., New York |
| [25] | Gennaro, R.; Micali, S.; Bugliese, M.; Preneel, B.; Sassone, V.; Wegener, I., Independent zero-knowledge sets, Automata, Languages and Programming, 33th International Colloquium, Proceedings of ICALP 2006, 34-45 (2006), Berlin: Springer, Berlin · Zbl 1133.94344 |
| [26] | Goldreich, O., Foundations of Cryptography—Volume 1 (Basic Tools) (2001), Cambridge: Cambridge University Press, Cambridge · Zbl 1007.94016 |
| [27] | Goldreich, O.; Krawczyk, H., On the composition of zero-knowledge proof systems, SIAM J. Comput., 25, 1, 169-192 (1996) · Zbl 0841.68112 · doi:10.1137/S0097539791220688 |
| [28] | Goldreich, O.; Micali, S.; Wigderson, A., Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems, J. ACM, 38, 1, 691-729 (1991) · Zbl 0799.68101 |
| [29] | Haitner, I.; Holenstein, T.; Reingold, O., On the (im)possibility of key dependent encryption, Theory of Cryptography, Proceedings of TCC 2009, 202-219 (2009), Berlin: Springer, Berlin · Zbl 1213.94105 |
| [30] | Haitner, I.; Reingold, O., Statistically-hiding commitment from any one-way function, 39th Annual ACM Symposium on Theory of Computing, Proceedings of STOC 2007, 1-10 (2007), New York: Assoc. Comput. Math., New York · Zbl 1232.68043 |
| [31] | Haitner, I.; Hoch, J. J.; Reingold, O.; Segev, G., Finding collisions in interactive protocols—a tight lower bound on the round complexity of statistically-hiding commitments, 48th Annual Symposium on Foundations of Computer Science, Proceedings of FOCS 2007, 669-679 (2007), Los Alamitos: IEEE Computer Society, Los Alamitos |
| [32] | B. Hemenway, R. Ostrovsky, Re-randomizable encryption implies selective opening security. IACR ePrint Archive, Feb. 2009 |
| [33] | D. Hofheinz, J. Müller-Quade, D. Unruh, Universally composable zero-knowledge arguments and commitments from signature cards. Tatra Mt. Math. Publ. 93-103 (2007) · Zbl 1240.94071 |
| [34] | Hsiao, C.-Y.; Reyzin, L.; Franklin, M. K., Finding collisions on a public road, or do secure hash functions need secret coins?, Advances in Cryptology, Proceedings of CRYPTO 2004, 92-105 (2004), Berlin: Springer, Berlin · Zbl 1104.94025 |
| [35] | Impagliazzo, R.; Rudich, S., Limits on the provable consequences of one-way permutations, Twenty-First Annual ACM Symposium on Theory of Computing, Proceedings of STOC 1989, 44-61 (1989), New York: Assoc. Comput. Math., New York |
| [36] | Kilian, J.; Petrank, E., Concurrent and resettable zero-knowledge in poly-logarithmic rounds, 33th Annual ACM Symposium on Theory of Computing, Proceedings of STOC 2001, 560-569 (2001), New York: Assoc. Comput. Math., New York · Zbl 1317.68076 |
| [37] | Naor, M., Bit commitment using pseudo-randomness, J. Cryptol., 4, 2, 151-158 (1991) · Zbl 0731.68033 · doi:10.1007/BF00196774 |
| [38] | Naor, M.; Yung, M., Universal one-way hash functions and their cryptographic applications, Twenty-First Annual ACM Symposium on Theory of Computing, Proceedings of STOC 1989, 33-43 (1989), New York: Assoc. Comput. Math., New York |
| [39] | Nielsen, J. B.; Yung, M., Separating random oracle proofs from complexity theoretic proofs: the non-committing encryption case, Advances in Cryptology, Proceedings of CRYPTO 2002, 111-126 (2002), Berlin: Springer, Berlin · Zbl 1027.68601 |
| [40] | Prabhakaran, M.; Rosen, A.; Sahai, A., Concurrent zero knowledge with logarithmic round complexity, 43th Annual Symposium on Foundations of Computer Science, Proceedings of FOCS 2002, 366-375 (2002), Los Alamitos: IEEE Computer Society, Los Alamitos |
| [41] | Reingold, O.; Trevisan, L.; Vadhan, S. P.; Naor, M., Notions of reducibility between cryptographic primitives, Theory of Cryptography, Proceedings of TCC 2004, 1-20 (2004), Berlin: Springer, Berlin · Zbl 1197.94202 |
| [42] | Richardson, R.; Kilian, J.; Stern, J., On the concurrent composition of zero-knowledge proofs, Advances in Cryptology, Proceedings of EUROCRYPT ’99, 415-431 (1999), Berlin: Springer, Berlin · Zbl 0932.68046 |
| [43] | Shoup, V.; Kilian, J., OAEP reconsidered, Advances in Cryptology, Proceedings of CRYPTO 2001, 239-259 (2001), Berlin: Springer, Berlin · Zbl 1002.94519 |
| [44] | Simon, D. R.; Nyberg, K., Finding collisions on a one-way street: can secure hash functions be based on general assumptions?, Advances in Cryptology, Proceedings of EUROCRYPT ’98, 334-345 (1998), Berlin: Springer, Berlin · Zbl 0919.94032 |
| [45] | Wee, H.; Vadhan, S., One-way permutations, interactive hashing and statistically hiding commitments, Theory of Cryptography, Proceedings of TCC 2007, 419-433 (2007), Berlin: Springer, Berlin · Zbl 1129.94039 |
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.
