A novel approach to public-coin concurrent zero-knowledge and applications on resettable security
|
摘要
Canetti, Lin and Paneth in TCC 2013 showed a O(log~(1+ε)n) rounds public-coin concurrent zeroknowledge argument system(CZK) based on the existence of collision resistant hash functions, which is currently known as round optimal public-coin CZK from standard assumptions. In this paper, we further address this problem and present an alternative construction of public-coin CZK argument system with succinct slot. The key technique involves a new variant of Barak's non-black-box simulate approach. In particular, the original protocol uses n commitments in each slot, while our construction uses one commitment in each slot. Through our simulation techniques, the simulator recovers any previous state needed for the probabilistically checkable proof(PCP) from the current committed state, which, in our view, may be of independent interest. Furthermore, the public-coin CZK argument system can be transformed into a resettable security protocol based on the one way functions assumption. Therefore, we present a new construction of the simultaneous resettable zero-knowledge argument system.
Canetti, Lin and Paneth in TCC 2013 showed a O(log~(1+ε)n) rounds public-coin concurrent zeroknowledge argument system(CZK) based on the existence of collision resistant hash functions, which is currently known as round optimal public-coin CZK from standard assumptions. In this paper, we further address this problem and present an alternative construction of public-coin CZK argument system with succinct slot. The key technique involves a new variant of Barak's non-black-box simulate approach. In particular, the original protocol uses n commitments in each slot, while our construction uses one commitment in each slot. Through our simulation techniques, the simulator recovers any previous state needed for the probabilistically checkable proof(PCP) from the current committed state, which, in our view, may be of independent interest. Furthermore, the public-coin CZK argument system can be transformed into a resettable security protocol based on the one way functions assumption. Therefore, we present a new construction of the simultaneous resettable zero-knowledge argument system.
Canetti, Lin and Paneth in TCC 2013 showed a O(log~(1+ε)n) rounds public-coin concurrent zeroknowledge argument system(CZK) based on the existence of collision resistant hash functions, which is currently known as round optimal public-coin CZK from standard assumptions. In this paper, we further address this problem and present an alternative construction of public-coin CZK argument system with succinct slot. The key technique involves a new variant of Barak's non-black-box simulate approach. In particular, the original protocol uses n commitments in each slot, while our construction uses one commitment in each slot. Through our simulation techniques, the simulator recovers any previous state needed for the probabilistically checkable proof(PCP) from the current committed state, which, in our view, may be of independent interest. Furthermore, the public-coin CZK argument system can be transformed into a resettable security protocol based on the one way functions assumption. Therefore, we present a new construction of the simultaneous resettable zero-knowledge argument system.
引文
1 Goldwasser S,Micali S,Rackoff C.The knowledge complexity of interactive proof systems.In:Proceedings of the17th Annual ACM Symposium on Theory of Computing,Providence,1989.186-208
2 Dwork C,Naor M,Sahai A.Concurrent zero-knowledge.In:Proceedings of the 30th Annual ACM Symposium on the Theory of Computing,Dallas,1998.409-418
3 Chung K M,Ostrovsky R,Pass R,et al.4-round resettably-sound zero knowledge.In:Proceedings of the 11th International Conference on Theory of Cryptography(TCC),San Diego,2014.192-216
4 Chongchitmate W,Ostrovsky R,Visconti I.Resettably-sound resettable zero knowledge in constant rounds.In:Proceedings of the 15th International Conference on Theory of Cryptography(TCC),Baltimore,2017.111-138
5 Chung K M,Pass R,Seth K.Non-black-box simulation from one-way functions and applications to resettable security.SIAM J Comput,2016,45:415-458
6 Ostrovsky R,Scafuro A,Venkitasubramaniam M.Resettably sound zero-knowledge arguments from OWFs-The(semi)black-box way.In:Proceedings of the 12th International Conference on Theory of Cryptography(TCC),Warsaw,2015.345-374
7 Benhamouda F,Lin H.k-round MPC from k-round OT via garbled interactive circuits.In:Proceedings of the37th Annual International Conference on the Theory and Applications of Cryptographic Techniques,Tel Aviv,2018.500-532
8 Garg S,Srinivasan A.Two-round multiparty secure computation from minimal assumptions.In:Proceedings of the37th Annual International Conference on the Theory and Applications of Cryptographic Techniques,Tel Aviv,2018.468-499
9 Ishai Y,Mittal M,Ostrovsky R.On the message complexity of secure multiparty computation.In:Proceedings of the 21st IACR International Conference on Practice and Theory of Public-Key Cryptography(PKC),Rio de Janeiro,2018.698-711
10 Badrinarayanan S,Goyal V,Jain A,et al.Round optimal concurrent MPC via strong simulation.In:Proceedings of the 15th International Conference(TCC),2017.743-775
11 Garg S,Kiyoshima S,Pandey O.A new approach to black-box concurrent secure computation.In:Proceedings of the37th Annual International Conference on the Theory and Applications of Cryptographic Techniques,Tel Aviv,2018.566-599
12 Broadnax B,D¨ottling N,Hartung G,et al.Concurrently composable security with shielded super-polynomial simulators.In:Proceedings of the 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques,Paris,2017.351-381
13 Badrinarayanan S,Khurana D,Ostrovsky R,et al.Unconditional UC-secure computation with(stronger-malicious)PUFs.In:Proceedings of the 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques,Paris,2017.382-411
14 Kiyoshima S,Lin H,Venkitasubramaniam M.A unified approach to constructing black-box UC protocols in trusted setup models.In:Proceedings of the 15th International Conference(TCC),Baltimore,2017.776-809
15 Richardson R,Kilian J.On the concurrent composition of zero-knowledge proofs.In:Proceedings of International Conference on the Theory and Application of Cryptographic Techniques,Prague,1999.415-431
16 Canetti R,Kilian J,Petrank E,et al.Black-box concurrent zero-knowledge requires??(logn)rounds.In:Proceedings of Annual ACM Symposium on Theory of Computing(STOC),Heraklion,2001.570-579
17 Prabhakaran M,Rosen A,Sahai A.Concurrent zero knowledge with logarithmic round-complexity.In:Proceedings of the 43rd Symposium on Foundations of Computer Science(FOCS),Vancouver,2002.366-375
18 Goldreich O,Kahan A.How to construct constant-round zero-knowledge proof systems for NP.J Cryptol,1996,9:167-190
19 Pass R,Dustin Tseng W L,Venkitasubramaniam M.Concurrent zero knowledge,revisited.J Cryptol,2014,27:45-66
20 Feige U,Shamir A.Witness indistinguishable and witness hiding protocols.In:Proceedings of the 22nd Annual ACMSymposium on Theory of Computing(STOC),Baltimore,1990.416-426
21 Barak B.How to go beyond the black-box simulation barrier.In:Proceedings of IEEE Symposium on Foundations of Computer Science(FOCS),2001.106-115
22 Pass R,Rosen A,Tseng W L D.Public-coin parallel zero-knowledge for NP.J Cryptol,2013,26:1-10
23 Canetti R,Lin H,Paneth O.Public-coin concurrent zero-knowledge in the global hash model.In:Proceedings of the10th Theory of Cryptography Conference,Tokyo,2013.80-99
24 Chung K,Lin H,Pass R.Constant-round concurrent zero knowledge from p-certificates.In:Proceedings of Annual IEEE Symposium on Foundations of Computer Science(FOCS),Berkeley,2013.50-59
25 Goyal V.Non-black-box simulation in the fully concurrent setting.In:Proceedings of Symposium on Theory of Computing Conference(STOC),Palo Alto,2013.221-230
26 Kiyoshima S.An alternative approach to non-black-box simulation in fully concurrent setting.In:Proceedings of the12th Theory of Cryptography Conference(TCC),Warsaw,2015.290-318
27 Pandey O,Prabhakaran M,Sahai A.Obfuscation-based non-black-box simulation and four message concurrent zero knowledge for NP.In:Proceedings of the 12th Theory of Cryptography Conference(TCC),Warsaw,2015.638-667
28 Chung K,Lin H,Pass R.Constant-round concurrent zero-knowledge from indistinguishability obfuscation.In:Proceedings of the 35th Annual Cryptology Conference(CRYPTO),Santa Barbara,2015.287-307
29 Kilian J,Petrank E.Concurrent and resettable zero-knowledge in poly-loalgorithm rounds.In:Proceedings of Annual ACM Symposium on Theory of Computing,Heraklion,2001.560-569
30 Barak B,Goldreich O,Sha G,et al.Resettably-sound zero-knowledge and its applications.In:Proceedings of IEEESymposium on Foundations of Computer Science(FOCS),2001.116-125
31 Bitansky N,Paneth O.On non-black-box simulation and the impossibility of approximate obfuscation.SIAM JComput,2015,44:1325-1383
32 Chung K M,Ostrovsky R,Pass R,et al.Simultaneous resettability from one-way functions.In:Proceedings of the54th Annual IEEE Symposium on Foundations of Computer Science(FOCS),Berkeley,2013.60-69
33 Deng Y,Goyal V,Sahai A.Resolving the simultaneous resettability conjecture and a new non-black-box simulation strategy.In:Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science(FOCS),Atlanta,2009.251-260
34 Cho C,Ostrovsky R,Scafuro A,et al.Simultaneously resettable arguments of knowledge.In:Proceedings of the 12th International Conference on Theory of Cryptography(TCC),Warsaw,2015.530-547
35 H?Astad J,Impagliazzo R,Levin L A,et al.A pseudorandom generator from any one-way function.SIAM J Comput,1999,28:1364-1396
36 Naor M.Bit commitment using pseudorandomness.J Cryptol,1991,4:151-158
37 Blum M.How to prove a theorem so no one else can claim it.In:Proceedings of the International Congress of Mathematicians,1986.1444-1451
38 Barak B,Goldreich O.Universal arguments and their applications.SIAM J Comput,2008,38:1661-1694
39 Bellare M,Yee B.Forward-security in private-key cryptography.In:Proceedings of The Cryptographers’Track at the RSA Conference,San Francisco,2003.1-18
2 Dwork C,Naor M,Sahai A.Concurrent zero-knowledge.In:Proceedings of the 30th Annual ACM Symposium on the Theory of Computing,Dallas,1998.409-418
3 Chung K M,Ostrovsky R,Pass R,et al.4-round resettably-sound zero knowledge.In:Proceedings of the 11th International Conference on Theory of Cryptography(TCC),San Diego,2014.192-216
4 Chongchitmate W,Ostrovsky R,Visconti I.Resettably-sound resettable zero knowledge in constant rounds.In:Proceedings of the 15th International Conference on Theory of Cryptography(TCC),Baltimore,2017.111-138
5 Chung K M,Pass R,Seth K.Non-black-box simulation from one-way functions and applications to resettable security.SIAM J Comput,2016,45:415-458
6 Ostrovsky R,Scafuro A,Venkitasubramaniam M.Resettably sound zero-knowledge arguments from OWFs-The(semi)black-box way.In:Proceedings of the 12th International Conference on Theory of Cryptography(TCC),Warsaw,2015.345-374
7 Benhamouda F,Lin H.k-round MPC from k-round OT via garbled interactive circuits.In:Proceedings of the37th Annual International Conference on the Theory and Applications of Cryptographic Techniques,Tel Aviv,2018.500-532
8 Garg S,Srinivasan A.Two-round multiparty secure computation from minimal assumptions.In:Proceedings of the37th Annual International Conference on the Theory and Applications of Cryptographic Techniques,Tel Aviv,2018.468-499
9 Ishai Y,Mittal M,Ostrovsky R.On the message complexity of secure multiparty computation.In:Proceedings of the 21st IACR International Conference on Practice and Theory of Public-Key Cryptography(PKC),Rio de Janeiro,2018.698-711
10 Badrinarayanan S,Goyal V,Jain A,et al.Round optimal concurrent MPC via strong simulation.In:Proceedings of the 15th International Conference(TCC),2017.743-775
11 Garg S,Kiyoshima S,Pandey O.A new approach to black-box concurrent secure computation.In:Proceedings of the37th Annual International Conference on the Theory and Applications of Cryptographic Techniques,Tel Aviv,2018.566-599
12 Broadnax B,D¨ottling N,Hartung G,et al.Concurrently composable security with shielded super-polynomial simulators.In:Proceedings of the 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques,Paris,2017.351-381
13 Badrinarayanan S,Khurana D,Ostrovsky R,et al.Unconditional UC-secure computation with(stronger-malicious)PUFs.In:Proceedings of the 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques,Paris,2017.382-411
14 Kiyoshima S,Lin H,Venkitasubramaniam M.A unified approach to constructing black-box UC protocols in trusted setup models.In:Proceedings of the 15th International Conference(TCC),Baltimore,2017.776-809
15 Richardson R,Kilian J.On the concurrent composition of zero-knowledge proofs.In:Proceedings of International Conference on the Theory and Application of Cryptographic Techniques,Prague,1999.415-431
16 Canetti R,Kilian J,Petrank E,et al.Black-box concurrent zero-knowledge requires??(logn)rounds.In:Proceedings of Annual ACM Symposium on Theory of Computing(STOC),Heraklion,2001.570-579
17 Prabhakaran M,Rosen A,Sahai A.Concurrent zero knowledge with logarithmic round-complexity.In:Proceedings of the 43rd Symposium on Foundations of Computer Science(FOCS),Vancouver,2002.366-375
18 Goldreich O,Kahan A.How to construct constant-round zero-knowledge proof systems for NP.J Cryptol,1996,9:167-190
19 Pass R,Dustin Tseng W L,Venkitasubramaniam M.Concurrent zero knowledge,revisited.J Cryptol,2014,27:45-66
20 Feige U,Shamir A.Witness indistinguishable and witness hiding protocols.In:Proceedings of the 22nd Annual ACMSymposium on Theory of Computing(STOC),Baltimore,1990.416-426
21 Barak B.How to go beyond the black-box simulation barrier.In:Proceedings of IEEE Symposium on Foundations of Computer Science(FOCS),2001.106-115
22 Pass R,Rosen A,Tseng W L D.Public-coin parallel zero-knowledge for NP.J Cryptol,2013,26:1-10
23 Canetti R,Lin H,Paneth O.Public-coin concurrent zero-knowledge in the global hash model.In:Proceedings of the10th Theory of Cryptography Conference,Tokyo,2013.80-99
24 Chung K,Lin H,Pass R.Constant-round concurrent zero knowledge from p-certificates.In:Proceedings of Annual IEEE Symposium on Foundations of Computer Science(FOCS),Berkeley,2013.50-59
25 Goyal V.Non-black-box simulation in the fully concurrent setting.In:Proceedings of Symposium on Theory of Computing Conference(STOC),Palo Alto,2013.221-230
26 Kiyoshima S.An alternative approach to non-black-box simulation in fully concurrent setting.In:Proceedings of the12th Theory of Cryptography Conference(TCC),Warsaw,2015.290-318
27 Pandey O,Prabhakaran M,Sahai A.Obfuscation-based non-black-box simulation and four message concurrent zero knowledge for NP.In:Proceedings of the 12th Theory of Cryptography Conference(TCC),Warsaw,2015.638-667
28 Chung K,Lin H,Pass R.Constant-round concurrent zero-knowledge from indistinguishability obfuscation.In:Proceedings of the 35th Annual Cryptology Conference(CRYPTO),Santa Barbara,2015.287-307
29 Kilian J,Petrank E.Concurrent and resettable zero-knowledge in poly-loalgorithm rounds.In:Proceedings of Annual ACM Symposium on Theory of Computing,Heraklion,2001.560-569
30 Barak B,Goldreich O,Sha G,et al.Resettably-sound zero-knowledge and its applications.In:Proceedings of IEEESymposium on Foundations of Computer Science(FOCS),2001.116-125
31 Bitansky N,Paneth O.On non-black-box simulation and the impossibility of approximate obfuscation.SIAM JComput,2015,44:1325-1383
32 Chung K M,Ostrovsky R,Pass R,et al.Simultaneous resettability from one-way functions.In:Proceedings of the54th Annual IEEE Symposium on Foundations of Computer Science(FOCS),Berkeley,2013.60-69
33 Deng Y,Goyal V,Sahai A.Resolving the simultaneous resettability conjecture and a new non-black-box simulation strategy.In:Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science(FOCS),Atlanta,2009.251-260
34 Cho C,Ostrovsky R,Scafuro A,et al.Simultaneously resettable arguments of knowledge.In:Proceedings of the 12th International Conference on Theory of Cryptography(TCC),Warsaw,2015.530-547
35 H?Astad J,Impagliazzo R,Levin L A,et al.A pseudorandom generator from any one-way function.SIAM J Comput,1999,28:1364-1396
36 Naor M.Bit commitment using pseudorandomness.J Cryptol,1991,4:151-158
37 Blum M.How to prove a theorem so no one else can claim it.In:Proceedings of the International Congress of Mathematicians,1986.1444-1451
38 Barak B,Goldreich O.Universal arguments and their applications.SIAM J Comput,2008,38:1661-1694
39 Bellare M,Yee B.Forward-security in private-key cryptography.In:Proceedings of The Cryptographers’Track at the RSA Conference,San Francisco,2003.1-18