Constant-round leakage-resilient zero-knowledge from collision resistance. (English) Zbl 1487.94126
Summary: In this paper, we present a constant-round leakage-resilient zero-knowledge argument system for NP under the assumption of the existence of collision-resistant hash function families. That is, using a collision-resistant hash function, we construct a constant-round zero-knowledge argument system that has the following zero-knowledge property: even against any cheating verifier that obtains an arbitrary amount of leakage on the prover’s internal secret state, a simulator can simulate the verifier’s view by obtaining the same amount of leakage on the witness. Previously, leakage-resilient zero-knowledge proofs/arguments for NP were constructed only under a relaxed security definition [S. Garg et al., Lect. Notes Comput. Sci. 6841, 297–315 (2011; Zbl 1288.68081)] or under the DDH assumption [O. Pandey, ibid. 8349, 146–166 (2014; Zbl 1323.94133)]. Our leakage-resilient zero-knowledge argument system satisfies an additional property that it is simultaneously leakage-resilient zero-knowledge, meaning that both zero-knowledge and soundness hold in the presence of leakage.
Keywords:
zero-knowledge; leakage resilience; non-black-box simulation; instance-dependent commitmentReferences:
| [1] | P. Ananth, V. Goyal, O. Pandey, Interactive proofs under continual memory leakage, in CRYPTO (2014), pp. 164-182 · Zbl 1334.68076 |
| [2] | R. Anderson, M. Kuhn, Tamper resistance: a cautionary note, in WOEC (1996), pp. 1-11 |
| [3] | B. Barak, How to go beyond the black-box simulation barrier, in FOCS (2001), pp. 106-115 |
| [4] | Brassard, Gilles; Chaum, David; Crépeau, Claude, Minimum disclosure proofs of knowledge, Journal of Computer and System Sciences, 37, 2, 156-189 (1988) · Zbl 0656.68109 · doi:10.1016/0022-0000(88)90005-0 |
| [5] | N. Bitansky, R. Canetti, S. Halevi, Leakage-tolerant interactive protocols, in TCC (2012), pp. 266-284 · Zbl 1296.94088 |
| [6] | F. Benhamouda, A. Degwekar, Y. Ishai, T. Rabin, On the local leakage resilience of linear secret sharing schemes, in CRYPTO (2018), pp. 531-561 · Zbl 1444.94119 |
| [7] | N. Bitansky, D. Dachman-Soled, H. Lin, Leakage-tolerant computation with input-independent preprocessing, in CRYPTO (2014), pp. 146-163 · Zbl 1334.68078 |
| [8] | Barak, Boaz; Goldreich, Oded, Universal arguments and their applications, SIAM Journal on Computing, 38, 5, 1661-1694 (2008) · Zbl 1180.94047 · doi:10.1137/070709244 |
| [9] | E. Boyle, S. Garg, A. Jain, Y.T. Kalai, A. Sahai, Secure computation against adaptive auxiliary information, in CRYPTO (2013), pp. 316-334 · Zbl 1310.94132 |
| [10] | E. Boyle, S. Goldwasser, A. Jain, Y.T. Kalai, Multiparty computation secure against continual memory leakage, in STOC (2012), pp. 1235-1254 · Zbl 1286.94060 |
| [11] | E. Boyle, S. Goldwasser, Y.T. Kalai, Leakage-resilient coin tossing. Distrib. Comput.27(3), 147-164 (2014) · Zbl 1291.68427 |
| [12] | R. Canetti, S. Goldwasser, O. Poburinnaya, Adaptively secure two-party computation from indistinguishability obfuscation, in TCC (2015), pp. 557-585 · Zbl 1382.94077 |
| [13] | R. Canetti, Y. Lindell, R. Ostrovsky, A. Sahai, Universally composable two-party and multi-party secure computation, in STOC (2002), pp. 494-503 · Zbl 1192.94112 |
| [14] | Chung, Kai-min; Pass, Rafael; Seth, Karn, Non-black-box simulation from one-way functions and applications to resettable security, SIAM J. Comput., 45, 2, 415-458 (2016) · Zbl 1384.94045 · doi:10.1137/130946083 |
| [15] | R. Canetti, O. Poburinnaya, M. Venkitasubramaniam, Better two-round adaptive multi-party computation, in PKC (2017), pp. 396-427 · Zbl 1400.94130 |
| [16] | R. Canetti, O. Poburinnaya, M. Venkitasubramaniam, Equivocating Yao: constant-round adaptively secure multiparty computation in the plain model, in STOC (2017), pp. 497-509 · Zbl 1369.68206 |
| [17] | D. Dachman-Soled, J. Katz, V. Rao, Adaptively secure, universally composable, multiparty computation in constant rounds, in TCC (2015), pp. 586-613 · Zbl 1382.94086 |
| [18] | D. Dachman-Soled, F.-H. Liu, H.-S. Zhou, Leakage-resilient circuits revisited - optimal number of computing components without leak-free hardware, in EUROCRYPT (2015), pp. 131-158 · Zbl 1326.94084 |
| [19] | Damgård, Ivan; Pedersen, Torben P.; Pfitzmann, Birgit, Statistical secrecy and multibit commitments, IEEE Trans. Inf. Theory, 44, 3, 1143-1151 (1998) · Zbl 0906.94016 · doi:10.1109/18.669255 |
| [20] | U. Feige, A. Shamir, Zero knowledge proofs of knowledge in two rounds, in CRYPTO (1989), pp. 526-544 · Zbl 0722.68045 |
| [21] | V. Goyal, Y. Ishai, H.K. Maji, A. Sahai, A.A. Sherstov, Bounded-communication leakage resilience via parity-resilient circuits, in FOCS (2016) |
| [22] | S. Garg, A. Jain, A. Sahai, Leakage-resilient zero knowledge, in CRYPTO (2011), pp. 297-315 · Zbl 1288.68081 |
| [23] | Goldreich, Oded; Kahan, Ariel, How to construct constant-round zero-knowledge proof systems for NP, J. Cryptol., 9, 3, 167-190 (1996) · Zbl 0855.68085 · doi:10.1007/BF00208001 |
| [24] | Goldwasser, Shafi; Micali, Silvio; Rackoff, Charles, The knowledge complexity of interactive proof systems, SIAM Journal on Computing, 18, 1, 186-208 (1989) · Zbl 0677.68062 · doi:10.1137/0218012 |
| [25] | O. Goldreich, Foundations of Cryptography: Volume 1, Basic Tools (Cambridge University Press, August 2001) · Zbl 1007.94016 |
| [26] | O. Goldreich, Foundations of Cryptography: Volume 2, Basic Applications (Cambridge University Press, May 2004) · Zbl 1068.94011 |
| [27] | S. Garg, A. Polychroniadou, Two-round adaptively secure MPC from indistinguishability obfuscation, in TCC (2015), pp. 614-637 · Zbl 1382.94108 |
| [28] | Håstad, Johan; Impagliazzo, Russell; Levin, Leonid A.; Luby, Michael, A pseudorandom generator from any one-way function, SIAM Journal on Computing, 28, 4, 1364-1396 (1999) · Zbl 0940.68048 · doi:10.1137/S0097539793244708 |
| [29] | I. Haitner, M.-H. Nguyen, S.J. Ong, O. Reingold, S.P. Vadhan, Statistically hiding commitments and statistical zero-knowledge arguments from any one-way function. SIAM J. Comput.39(3), 1153-1218 (2009) · Zbl 1195.94057 |
| [30] | P.C. Kocher, Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems, in CRYPTO (1996), pp. 104-113 · Zbl 1329.94070 |
| [31] | Y.T. Kalai, L. Reyzin, A survey of leakage-resilient cryptography. Cryptology ePrint Archive, Report 2019/302 (2019). https://eprint.iacr.org/2019/302 |
| [32] | Lindell, Yehuda; Zarosim, Hila, Adaptive zero-knowledge proofs and adaptively secure oblivious transfer, Journal of Cryptology, 24, 4, 761-799 (2011) · Zbl 1251.94034 · doi:10.1007/s00145-010-9072-z |
| [33] | Naor, Moni, Bit commitment using pseudorandomness, Journal of Cryptology, 4, 2, 151-158 (1991) · Zbl 0731.68033 · doi:10.1007/BF00196774 |
| [34] | M. Naor, M. Yung, Universal one-way hash functions and their cryptographic applications, in STOC (1989), pp. 33-43 |
| [35] | R. Ostrovsky, G. Persiano, I. Visconti, Impossibility of black-box simulation against leakage attacks, in CRYPTO (2015), pp. 130-149 · Zbl 1336.94068 |
| [36] | O. Pandey, Achieving constant round leakage-resilient zero-knowledge, in TCC (2014), pp. 146-166 · Zbl 1323.94133 |
| [37] | Pass, Rafael; Rosen, Alon, Concurrent nonmalleable commitments, SIAM Journal on Computing, 37, 6, 1891-1925 (2008) · Zbl 1275.94034 · doi:10.1137/060661880 |
| [38] | Pass, Rafael; Rosen, Alon, New and improved constructions of nonmalleable cryptographic protocols, SIAM Journal on Computing, 38, 2, 702-752 (2008) · Zbl 1161.94007 · doi:10.1137/060671553 |
| [39] | R. Pass, H. Wee, Black-box constructions of two-party protocols from one-way functions, in TCC (2009), pp. 403-418 · Zbl 1213.94126 |
| [40] | J.-J. Quisquater, D. Samyde, Electromagnetic analysis (EMA): measures and counter-measures for smart cards, in E-smart (2001), pp. 200-210 · Zbl 1003.68609 |
| [41] | A. Srinivasan, P.N. Vasudevan, Leakage resilient secret sharing and applications, in CRYPTO (2019), pp. 480-509 · Zbl 1509.94167 |
| [42] | A.C.-C. Yao, How to generate and exchange secrets (extended abstract), in FOCS (1986), pp. 162-167 |
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.
