Two-message witness indistinguishability and secure computation in the plain model from new assumptions. (English) Zbl 1417.94040
Takagi, Tsuyoshi (ed.) et al., Advances in cryptology – ASIACRYPT 2017. 23rd international conference on the theory and applications of cryptology and information security, Hong Kong, China, December 3–7, 2017. Proceedings. Part III. Cham: Springer. Lect. Notes Comput. Sci. 10626, 275-303 (2017).
Summary: We study the feasibility of two-message protocols for secure two-party computation in the plain model, for functionalities that deliver output to one party, with security against malicious parties. Since known impossibility results rule out polynomial-time simulation in this setting, we consider the common relaxation of allowing super-polynomial simulation.{
}We first address the case of zero-knowledge functionalities. We present a new construction of two-message zero-knowledge protocols with super-polynomial simulation from any (sub-exponentially hard) game-based two-message oblivious transfer protocol, which we call Weak OT. As a corollary, we get the first two-message WI arguments for NP from (sub-exponential) DDH. Prior to our work, such protocols could only be constructed from assumptions that are known to imply non-interactive zero-knowledge protocols (NIZK), which do not include DDH.{
}We then extend the above result to the case of general single-output functionalities, showing how to construct two-message secure computation protocols with quasi-polynomial simulation from Weak OT. This implies protocols based on sub-exponential variants of several standard assumptions, including decisional Diffie Hellman (DDH), quadratic residuosity assumption, and \(N\)-th residuosity assumption. Prior works on two-message protocols either relied on some trusted setup (such as a common reference string) or were restricted to special functionalities such as blind signatures. As a corollary, we get three-message protocols for two-output functionalities, which include coin-tossing as an interesting special case. For both types of functionalities, the number of messages (two or three) is optimal.{
}Finally, motivated by the above, we further study the Weak OT primitive. On the positive side, we show that Weak OT can be based on any semi-honest 2-message OT with a short second message. This simplifies a previous construction of Weak OT from the \(N\)-th residuosity assumption. We also present a construction of Weak OT from witness encryption (WE) and injective one-way functions, implying the first construction of two-message WI arguments from WE. On the negative side, we show that previous constructions of Weak OT do not satisfy simulation-based security even if the simulator can be computationally unbounded.
For the entire collection see [Zbl 1380.94008].
For the entire collection see [Zbl 1380.94008].
MSC:
| 94A60 | Cryptography |
References:
| [1] | Afshar, A.; Mohassel, P.; Pinkas, B.; Riva, B.; Nguyen, PQ; Oswald, E., Non-interactive secure computation based on cut-and-choose, Advances in Cryptology - EUROCRYPT 2014, 387-404, 2014, Heidelberg: Springer, Heidelberg · Zbl 1332.94053 · doi:10.1007/978-3-642-55220-5_22 |
| [2] | Aiello, B.; Ishai, Y.; Reingold, O.; Pfitzmann, B., Priced oblivious transfer: how to sell digital goods, Advances in Cryptology — EUROCRYPT 2001, 119-135, 2001, Heidelberg: Springer, Heidelberg · Zbl 0981.94042 · doi:10.1007/3-540-44987-6_8 |
| [3] | Badrinarayanan, S., Goyal, V., Jain, A., Khurana, D., Sahai, A.: Round optimal concurrent MPC via strong simulation. In: TCC (2017) |
| [4] | Barak, B., Lindell, Y., Vadhan, S.P.: Lower bounds for non-black-box zero knowledge. In: Proceedings of 44th Symposium on Foundations of Computer Science, FOCS 2003, 11-14 October 2003, Cambridge, MA, USA, pp. 384-393. IEEE Computer Society (2003). doi:10.1109/SFCS.2003.1238212 |
| [5] | Barak, B., Prabhakaran, M., Sahai, A.: Concurrent non-malleable zero knowledge. In: Proceedings of 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006, 21-24 October 2006, Berkeley, California, USA, pp. 345-354. IEEE Computer Society (2006). doi:10.1109/FOCS.2006.21 |
| [6] | Barak, B., Sahai, A.: How to play almost any mental game over the net - concurrent composition via super-polynomial simulation. In: Proceedings of 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005, 23-25 October 2005, Pittsburgh, PA, USA, pp. 543-552. IEEE Computer Society (2005). doi:10.1109/SFCS.2005.43 |
| [7] | Biham, E., Advances in Cryptology - EUROCRYPT 2003, 2003, Heidelberg: Springer, Heidelberg · Zbl 1020.00023 · doi:10.1007/3-540-39200-9 |
| [8] | Blum, M., Feldman, P., Micali, S.: Non-interactive zero-knowledge and its applications (extended abstract). In: STOC (1988) |
| [9] | Cachin, C.; Camenisch, J.; Kilian, J.; Müller, J.; Montanari, U.; Rolim, JDP; Welzl, E., One-round secure computation and secure autonomous mobile agents, Automata, Languages and Programming, 512-523, 2000, Heidelberg: Springer, Heidelberg · Zbl 0973.94545 · doi:10.1007/3-540-45022-X_43 |
| [10] | Canetti, Ran; Halevi, Shai; Katz, Jonathan, A Forward-Secure Public-Key Encryption Scheme, Lecture Notes in Computer Science, 255-271, 2003, Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg · Zbl 1037.68532 |
| [11] | Canetti, R., Lin, H., Pass, R.: Adaptive hardness and composable security in the plain model from standard assumptions. In: 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 23-26 October 2010, Las Vegas, Nevada, USA, pp. 541-550. IEEE Computer Society (2010). doi:10.1109/FOCS.2010.86 |
| [12] | Chung, K.M., Lui, E., Mahmoody, M., Pass, R.: Unprovable security of two-message zero knowledge. Cryptology ePrint Archive, Report 2012/711 (2012) |
| [13] | Dachman-Soled, D., Jain, A., Kalai, Y.T., Lopez-Alt, A.: On the (in)security of the fiat-shamir paradigm, revisited. Cryptology ePrint Archive, Report 2012/706 (2012) |
| [14] | Damgård, I.; Jurik, M.; Kim, K., A generalisation, a simpli.cation and some applications of paillier’s probabilistic public-key system, Public Key Cryptography, 119-136, 2001, Heidelberg: Springer, Heidelberg · Zbl 0987.94032 · doi:10.1007/3-540-44586-2_9 |
| [15] | Döttling, N.; Fleischhacker, N.; Krupp, J.; Schröder, D.; Robshaw, M.; Katz, J., Two-message, oblivious evaluation of cryptographic functionalities, Advances in Cryptology - CRYPTO 2016, 619-648, 2016, Heidelberg: Springer, Heidelberg · Zbl 1406.94046 · doi:10.1007/978-3-662-53015-3_22 |
| [16] | Feige, U.; Lapidot, D.; Shamir, A., Multiple noninteractive zero knowledge proofs under general assumptions, SIAM J. Comput., 29, 1-28, 1999 · Zbl 1018.94015 · doi:10.1137/S0097539792230010 |
| [17] | Garg, S., Gentry, C., Sahai, A., Waters, B.: Witness encryption and its applications. In: STOC (2013) |
| [18] | Garg, S.; Goyal, V.; Jain, A.; Sahai, A.; Pointcheval, D.; Johansson, T., Concurrently secure computation in constant rounds, Advances in Cryptology - EUROCRYPT 2012, 99-116, 2012, Heidelberg: Springer, Heidelberg · Zbl 1297.94069 · doi:10.1007/978-3-642-29011-4_8 |
| [19] | Garg, S.; Mukherjee, P.; Pandey, O.; Polychroniadou, A.; Fischlin, M.; Coron, J-S, The exact round complexity of secure computation, Advances in Cryptology - EUROCRYPT 2016, 448-476, 2016, Heidelberg: Springer, Heidelberg · Zbl 1371.94637 · doi:10.1007/978-3-662-49896-5_16 |
| [20] | Garg, S.; Rao, V.; Sahai, A.; Schröder, D.; Unruh, D.; Rogaway, P., Round optimal blind signatures, Advances in Cryptology - CRYPTO 2011, 630-648, 2011, Heidelberg: Springer, Heidelberg · Zbl 1290.94075 · doi:10.1007/978-3-642-22792-9_36 |
| [21] | Goldreich, O.; Krawczyk, H.; Paterson, MS, On the composition of zero-knowledge proof systems, Automata, Languages and Programming, 268-282, 1990, Heidelberg: Springer, Heidelberg · Zbl 0766.68033 · doi:10.1007/BFb0032038 |
| [22] | Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or a completeness theorem for protocols with honest majority. In: Proceedings of the 19th Annual ACM Symposium on Theory of Computing, New York, New York, USA. pp. 218-229 (1987). doi:10.1145/28395.28420 |
| [23] | Goldreich, O.; Oren, Y., Definitions and properties of zero-knowledge proof systems, J. Cryptol., 7, 1, 1-32, 1994 · Zbl 0791.94010 · doi:10.1007/BF00195207 |
| [24] | Goyal, V.: Positive results for concurrently secure computation in the plain model. In: FOCS (2012) |
| [25] | Groth, J.; Ostrovsky, R.; Sahai, A.; Dwork, C., Non-interactive zaps and new techniques for NIZK, Advances in Cryptology - CRYPTO 2006, 97-111, 2006, Heidelberg: Springer, Heidelberg · Zbl 1129.94024 · doi:10.1007/11818175_6 |
| [26] | Groth, J.; Ostrovsky, R.; Sahai, A.; Vaudenay, S., Perfect non-interactive zero knowledge for NP, Advances in Cryptology - EUROCRYPT 2006, 339-358, 2006, Heidelberg: Springer, Heidelberg · Zbl 1129.94025 · doi:10.1007/11761679_21 |
| [27] | Halevi, S.; Kalai, YT, Smooth projective hashing and two-message oblivious transfer, J. Cryptology, 25, 1, 158-193, 2012 · Zbl 1272.94033 · doi:10.1007/s00145-010-9092-8 |
| [28] | Hazay, C.; Venkitasubramaniam, M.; Zikas, V.; Prisco, R., What security can we achieve within 4 rounds?, Security and Cryptography for Networks, 486-505, 2016, Cham: Springer, Cham · Zbl 1435.94130 · doi:10.1007/978-3-319-44618-9_26 |
| [29] | Horvitz, O.; Katz, J.; Menezes, A., Universally-composable two-party computation in two rounds, Advances in Cryptology - CRYPTO 2007, 111-129, 2007, Heidelberg: Springer, Heidelberg · Zbl 1215.94052 · doi:10.1007/978-3-540-74143-5_7 |
| [30] | Impagliazzo, R., Levin, L.A., Luby, M.: Pseudo-random generation from one-way functions (extended abstracts). In: Johnson, D.S. (ed.) Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14-17, 1989, Seattle, Washigton, USA, pp. 12-24. ACM (1989). doi:10.1145/73007.73009 |
| [31] | Ishai, Y.; Kushilevitz, E.; Ostrovsky, R.; Prabhakaran, M.; Sahai, A.; Paterson, KG, Efficient non-interactive secure computation, Advances in Cryptology - EUROCRYPT 2011, 406-425, 2011, Heidelberg: Springer, Heidelberg · Zbl 1290.94151 · doi:10.1007/978-3-642-20465-4_23 |
| [32] | Ishai, Y.; Paskin, A.; Vadhan, SP, Evaluating branching programs on encrypted data, Theory of Cryptography, 575-594, 2007, Heidelberg: Springer, Heidelberg · Zbl 1156.94354 · doi:10.1007/978-3-540-70936-7_31 |
| [33] | Ishai, Y.; Prabhakaran, M.; Sahai, A.; Wagner, D., Founding cryptography on oblivious transfer – efficiently, Advances in Cryptology - CRYPTO 2008, 572-591, 2008, Heidelberg: Springer, Heidelberg · Zbl 1183.94037 · doi:10.1007/978-3-540-85174-5_32 |
| [34] | Jain, A.; Kalai, YT; Khurana, D.; Rothblum, R.; Katz, J.; Shacham, H., Distinguisher-dependent simulation in two rounds and its applications, Advances in Cryptology - CRYPTO 2017, 158-189, 2017, Cham: Springer, Cham · Zbl 1409.94880 · doi:10.1007/978-3-319-63715-0_6 |
| [35] | Katz, J.; Ostrovsky, R.; Franklin, M., Round-optimal secure two-party computation, Advances in Cryptology - CRYPTO 2004, 335-354, 2004, Heidelberg: Springer, Heidelberg · Zbl 1104.94027 · doi:10.1007/978-3-540-28628-8_21 |
| [36] | Khurana, D.; Sahai, A., Two-message non-malleable commitments from standard sub-exponential assumptions, IACR Cryptol. ePrint Arch., 2017, 291, 2017 |
| [37] | Lindell, Y.; Naor, M., Lower bounds for concurrent self composition, Theory of Cryptography, 203-222, 2004, Heidelberg: Springer, Heidelberg · Zbl 1176.94069 · doi:10.1007/978-3-540-24638-1_12 |
| [38] | Naor, M., Pinkas, B.: Efficient oblivious transfer protocols. In: Kosaraju, S.R. (ed.) Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 7-9 January 2001, Washington, DC, USA, pp. 448-457. ACM/SIAM (2001). http://dl.acm.org/citation.cfm?id=365411.365502 · Zbl 0991.94045 |
| [39] | Pass, Rafael, Simulation in Quasi-Polynomial Time, and Its Application to Protocol Composition, Lecture Notes in Computer Science, 160-176, 2003, Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg · Zbl 1037.68536 |
| [40] | Prabhakaran, M., Sahai, A.: New notions of security: achieving universal composability without trusted setup. In: Babai, L. (ed.) Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, 13-16 June 2004, pp. 242-251. ACM (2004). doi:10.1145/1007352.1007394 · Zbl 1192.94124 |
| [41] | Yao, A.C.: How to generate and exchange secrets (extended abstract). In: 27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27-29, pp. 162-167 (1986). doi:10.1109/SFCS.1986.25 |
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.
