Constant-Round Leakage-Resilient Zero-Knowledge from Collision Resistance
Tóm tắt
In this paper, we present a constant-round leakage-resilient zero-knowledge argument system for
$$\mathcal {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
$$\mathcal {NP}$$
were constructed only under a relaxed security definition (Garg et al., in: CRYPTO’11, pp 297–315, 2011) or under the DDH assumption (Pandey, in: TCC’14, pp 146–166, 2014). 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.
Tài liệu tham khảo
P. Ananth, V. Goyal, O. Pandey, Interactive proofs under continual memory leakage, in CRYPTO (2014), pp. 164–182
R. Anderson, M. Kuhn, Tamper resistance: a cautionary note, in WOEC (1996), pp. 1–11
B. Barak, How to go beyond the black-box simulation barrier, in FOCS (2001), pp. 106–115
G. Brassard, D. Chaum, C. Crépeau, Minimum disclosure proofs of knowledge. J. Comput. Syst. Sci. 37(2), 156–189 (1988)
N. Bitansky, R. Canetti, S. Halevi, Leakage-tolerant interactive protocols, in TCC (2012), pp. 266–284
F. Benhamouda, A. Degwekar, Y. Ishai, T. Rabin, On the local leakage resilience of linear secret sharing schemes, in CRYPTO (2018), pp. 531–561
N. Bitansky, D. Dachman-Soled, H. Lin, Leakage-tolerant computation with input-independent preprocessing, in CRYPTO (2014), pp. 146–163
B. Barak, O. Goldreich, Universal arguments and their applications, SIAM J. Comput. 38(5), 1661–1694 (2008)
E. Boyle, S. Garg, A. Jain, Y.T. Kalai, A. Sahai, Secure computation against adaptive auxiliary information, in CRYPTO (2013), pp. 316–334
E. Boyle, S. Goldwasser, A. Jain, Y.T. Kalai, Multiparty computation secure against continual memory leakage, in STOC (2012), pp. 1235–1254
E. Boyle, S. Goldwasser, Y.T. Kalai, Leakage-resilient coin tossing. Distrib. Comput. 27(3), 147–164 (2014)
R. Canetti, S. Goldwasser, O. Poburinnaya, Adaptively secure two-party computation from indistinguishability obfuscation, in TCC (2015), pp. 557–585
R. Canetti, Y. Lindell, R. Ostrovsky, A. Sahai, Universally composable two-party and multi-party secure computation, in STOC (2002), pp. 494–503
K. Chung, R. Pass, K. Seth, Non-black-box simulation from one-way functions and applications to resettable security. SIAM J. Comput. 45(2), 415–458 (2016)
R. Canetti, O. Poburinnaya, M. Venkitasubramaniam, Better two-round adaptive multi-party computation, in PKC (2017), pp. 396–427
R. Canetti, O. Poburinnaya, M. Venkitasubramaniam, Equivocating Yao: constant-round adaptively secure multiparty computation in the plain model, in STOC (2017), pp. 497–509
D. Dachman-Soled, J. Katz, V. Rao, Adaptively secure, universally composable, multiparty computation in constant rounds, in TCC (2015), pp. 586–613
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
I. Damgård, T.P. Pedersen, B. Pfitzmann, Statistical secrecy and multibit commitments. IEEE Trans. Inf. Theory 44(3), 1143–1151 (1998)
U. Feige, A. Shamir, Zero knowledge proofs of knowledge in two rounds, in CRYPTO (1989), pp. 526–544
V. Goyal, Y. Ishai, H.K. Maji, A. Sahai, A.A. Sherstov, Bounded-communication leakage resilience via parity-resilient circuits, in FOCS (2016)
S. Garg, A. Jain, A. Sahai, Leakage-resilient zero knowledge, in CRYPTO (2011), pp. 297–315
O. Goldreich, A. Kahan, How to construct constant-round zero-knowledge proof systems for NP. J. Cryptol. 9(3), 167–190 (1996)
S. Goldwasser, S. Micali, C. Rackoff, The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 186–208 (1989)
O. Goldreich, Foundations of Cryptography: Volume 1, Basic Tools (Cambridge University Press, August 2001)
O. Goldreich, Foundations of Cryptography: Volume 2, Basic Applications (Cambridge University Press, May 2004)
S. Garg, A. Polychroniadou, Two-round adaptively secure MPC from indistinguishability obfuscation, in TCC (2015), pp. 614–637
J. Håstad, R. Impagliazzo, L.A. Levin, M. Luby, A pseudorandom generator from any one-way function. SIAM J. Comput. 28(4), 1364–1396 (1999)
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)
P.C. Kocher, Timing attacks on implementations of Diffie–Hellman, RSA, DSS, and other systems, in CRYPTO (1996), pp. 104–113
Y.T. Kalai, L. Reyzin, A survey of leakage-resilient cryptography. Cryptology ePrint Archive, Report 2019/302 (2019). https://eprint.iacr.org/2019/302
Y. Lindell, H. Zarosim, Adaptive zero-knowledge proofs and adaptively secure oblivious transfer. J. Cryptol. 24(4), 761–799 (2011)
M. Naor, Bit commitment using pseudorandomness. J. Cryptol. 4(2), 151–158 (1991)
M. Naor, M. Yung, Universal one-way hash functions and their cryptographic applications, in STOC (1989), pp. 33–43
R. Ostrovsky, G. Persiano, I. Visconti, Impossibility of black-box simulation against leakage attacks, in CRYPTO (2015), pp. 130–149
O. Pandey, Achieving constant round leakage-resilient zero-knowledge, in TCC (2014), pp. 146–166
R. Pass, A. Rosen, Concurrent nonmalleable commitments. SIAM J. Comput. 37(6), 1891–1925 (2008)
R. Pass, A. Rosen, New and improved constructions of nonmalleable cryptographic protocols. SIAM J. Comput. 38(2), 702–752 (2008)
R. Pass, H. Wee, Black-box constructions of two-party protocols from one-way functions, in TCC (2009), pp. 403–418
J.-J. Quisquater, D. Samyde, Electromagnetic analysis (EMA): measures and counter-measures for smart cards, in E-smart (2001), pp. 200–210
A. Srinivasan, P.N. Vasudevan, Leakage resilient secret sharing and applications, in CRYPTO (2019), pp. 480–509
A.C.-C. Yao, How to generate and exchange secrets (extended abstract), in FOCS (1986), pp. 162–167