基于可重随机化混淆电路的可验证计算
|
摘要
Yao的混淆电路可用于客户端将函数计算外包给服务器,并可验证其正确性.然而,混淆电路仅能使用1次.Gennaro等人组合使用全同态加密和混淆电路,可实现客户端和服务器在多次输入上重用混淆电路.但是,所有已知的全同态加密在效率的提高上似乎仍有很大的空间,并且需要较强的困难性假设.另一方面,Gennaro等人的方案只能在敌手不能对客户端发起任何数量的验证查询这种较弱的模型下被证明是安全的.部分同态加密的困难性假设要弱于全同态加密,虽然只支持数量有限的同态操作,但比全同态加密运行速度更快、更加紧凑.提出了一个使用加同态加密的可验证计算方案.它基于DDH假设,能够容忍任意数量的恶意验证查询,采用的主要技术是可重随机化的混淆电路.该技术可以实现重随机化的混淆电路分布与原有的混淆电路分布在计算上是不可区分的.另外,也给出了一种使用可重随机化的混淆电路构造密码转置防火墙方案,称为可重用密码转置防火墙.也就是说,混淆电路可生成1次,接下来,密码转置防火墙可安全地重随机化和重用多次.
Yao's garbled circuit allows a client to outsource a function computation to a server with verifiablity. Unfortunately, the garbled circuit suffers from a one-time usage. The combination of fully homomorphic encryption(FHE) and garbled circuits enables the client and the server to reuse the garbled circuit with multiple inputs(Gennaro et al.). However, there still seems to be a long way to go for improving the efficiency of all known FHE schemes and it need much stronger security assumption. On the other hand, the construction is only proven to be secure in a weaker model where an adversary can not issue any number of verification queries to the client. Somewhat homomorphic encryption schemes, whose assumptions are much weaker than the FHE schemes, support a limited number of homomorphic operations. However, they can be much faster and more compact than the FHE schemes. In this work, a verifiable computation scheme is presented which can tolerate any number of malicious verification queries with additively homomorphic encryption. The proposed technique comes from the construction of re-randomizable garbled circuits in which the distribution of the original garbled circuit is computationally indistinguishable from the re-randomized garbled circuit. The proposed scheme is based on the decisional Diffie-Hellman(DDH) assumption. A technique solution is also given to construct cryptographic reverse firewalls, which is called reusable cryptographic reverse firewalls, using re-randomizable garbled circuits. Namely, the solution allows garbled circuits to be generated once and then securely re-randomized for many times on cryptographic reverse firewalls.
Yao's garbled circuit allows a client to outsource a function computation to a server with verifiablity. Unfortunately, the garbled circuit suffers from a one-time usage. The combination of fully homomorphic encryption(FHE) and garbled circuits enables the client and the server to reuse the garbled circuit with multiple inputs(Gennaro et al.). However, there still seems to be a long way to go for improving the efficiency of all known FHE schemes and it need much stronger security assumption. On the other hand, the construction is only proven to be secure in a weaker model where an adversary can not issue any number of verification queries to the client. Somewhat homomorphic encryption schemes, whose assumptions are much weaker than the FHE schemes, support a limited number of homomorphic operations. However, they can be much faster and more compact than the FHE schemes. In this work, a verifiable computation scheme is presented which can tolerate any number of malicious verification queries with additively homomorphic encryption. The proposed technique comes from the construction of re-randomizable garbled circuits in which the distribution of the original garbled circuit is computationally indistinguishable from the re-randomized garbled circuit. The proposed scheme is based on the decisional Diffie-Hellman(DDH) assumption. A technique solution is also given to construct cryptographic reverse firewalls, which is called reusable cryptographic reverse firewalls, using re-randomizable garbled circuits. Namely, the solution allows garbled circuits to be generated once and then securely re-randomized for many times on cryptographic reverse firewalls.
引文
[1]Kilian J.A note on efficient zero-knowledge proofs and arguments(extended abstract).In:Proc.of the 24th Annual ACM Symp.on Theory of Computing.ACM Press,1992.723-732.
[2]Micali S.CS proofs(extended abstract).In:Proc.of the 35th Annual Symp.on Foundations of Computer Science.IEEE Press,1994.436-453.
[3]Gennaro R,Gentry C,Parno B.Non-interactive verifiable computing:Outsourcing computation to untrusted workers.In:Rabin T,ed.Proc.of the 30th Annual Cryptology Conf.(CRYPTO 2010).Heidelberg:Springer-Verlag,2010.465-482.
[4]Applebaum B,Ishai Y,Kushilevitz E.From secrecy to soundness:efficient verification via secure computation.In:Abramsky S,et al.,eds.Proc.of the 37th Int’l Colloquium on Automata,Languages,and Programming(ICALP 2010).Heidelberg:SpringerVerlag,2010.152-163.
[5]Asharov G,Jain A,Lopez-Alt A,Tromer E,Vaikuntanathan V,Wichs D.Multiparty computation with low communication,computation and interaction via threshold FHE.In:Pointcheval D,Johansson T,eds.Proc.of the 31st Annual Int’l Conf.on the Theory and Applications of Cryptographic Techniques(EUROCRYPT 2012).Heidelberg:Springer-Verlag,2012.483-501.
[6]Ben-Sasson E,Chiesa A,Genkin D,Tromer E,Virza M.SNARKs for C:Verifying program executions succinctly and in zero knowledge.In Canetti R,Garay JA,eds.Proc.of the 33rd Annual Cryptology Conf.(CRYPTO 2013).Heidelberg:Springer-Verlag,2013.99-108.
[7]Choi SG,Katz J,Kumaresan R,Cid C.Multi-client non-interactive verifiable computation.In Sahai A,ed.Proc.of the 10th Theory of Cryptography Conf.(TCC 2013).Heidelberg:Springer-Verlag,2013.499-518.
[8]Chung KM,Kalai YT,Liu FH,Raz R.Memory delegation.In Rogaway P,ed.Proc.of the 31st Annual Cryptology Conf.(CRYPTO 2011).Heidelberg:Springer-Verlag,2011.151-168.
[9]Chung KM,Kalai Y,Vadhan S.Improved delegation of computation using fully homomorphic encryption.In:Rabin T,ed.Proc.of the 30th Annual Cryptology Conf.(CRYPTO 2010).Heidelberg:Springer-Verlag,2010.483-501.
[10]Fiore D,Gennaro R,Pastro V.Efficiently verifiable computation on encrypted data.In:Proc.of the 21st ACM Conf.on Computer and Communications Security(CCS 2014).ACM Press,2014.844-855.
[11]Ananth P,Chandran N,Goyal V,Kanukurthi B,Ostrovsky R.Achieving privacy in verifiable computation with multiple serversWithout FHE and without pre-processing.In:Krawczyk H,ed.Proc.of the 20th Int’l Conf.on Practice and Theory of Public-Key Cryptography(PKC 2014).Heidelberg:Springer-Verlag,2014.149-166.
[12]Badrinarayanan S,Goyal V,Jain A,Sahai A.Verifiable functional encryption.In:Cheon J,Takagi T,eds.Proc.of the 22nd Annual Int’l Conf.on the Theory and Applications of Cryptology and Information Security(ASIACRYPT 2016).Heidelberg:SpringerVerlag,2016.557-587.
[13]Lindell Y,Pinkas B.A proof of security of Yao’s protocol for two-party computation.Journal of Cryptology,2009,22(2):161-188.
[14]Yao AC.Protocols for secure computations(extended abstract).In:Shamir A,ed.Proc.of the 23rd Annual Symp.on Foundations of Computer Science.IEEE Press,1982.160-164.
[15]Goldwasser S,Kalai Y,Popa RA,Vaikuntanathan V,Zeldovich N.Reusable garbled circuits and succinct functional encryption.In:Proc.of the 45th Annual ACM Symp.on Theory of Computing(STOC 2013).ACM Press,2013.555-564.
[16]Agrawal S.Stronger security for reusable garbled circuits,general definitions and attacks.In:Katz J,Shacham H,eds.Proc.of the37th Annual Cryptology Conf.(CRYPTO 2017).Heidelberg:Springer-Verlag,2017.3-35.
[17]Gentry C.Fully homomorphic encryption using ideal lattices.In:Proc.of the 41st Annual ACM Symp.on Theory of Computing(STOC 2009).ACM Press,2009.169-178.
[18]Brakerski Z,Vaikuntanathan V.Lattice-based FHE as secure as PKE.In:Proc.of the 5th Conf.on Innovations in Theoretical Computer Science.ACM Press,2014.1-12.
[19]Gentry C,Halevi S,Vaikuntanathan V.I-hop homomorphic encryption and re-randomizable Yao circuits.In:Rabin T,ed.Proc.of the 30th Annual Cryptology Conf.(CRYPTO 2010).Heidelberg:Springer-Verlag,2010.155-172.
[20]Halevi S,Lindell Y,Pinkas B.Secure computation on the Web:Computing without simultaneous interaction.In:Rogaway P,ed.Proc.of the 31st Annual Cryptology Conf.(CRYPTO 2011).Heidelberg:Springer-Verlag,2011.132-150.
[21]Atallah MJ,Pantazopoulos KN,Rice JR.Secure outsourcing of scientific computations.Advances in Computers,2002,(54):215-272.
[22]Kilian J.Founding cryptography on oblivious transfer.In:Proc.of the 20th Annual ACM Symp.on Theory of Computing.ACMPress,1988.20-31.
[23]Mironov I,Stephens-Davidowitz N.Cryptographic reverse firewalls.In:Oswald E,Fischlin M,eds.Proc.of the 34th Annual Int’l Conf.on the Theory and Applications of Cryptographic Techniques(EUROCRYPT 2015).Heidelberg:Springer-Verlag,2015.657-686.
[24]Boneh D,Halevi S,Hamburg M,Ostrovsky R.Circular-secure encryption from decision Diffie-Hellman.In:Wagner D,ed.Proc.of the 28th Annual Cryptology Conf.(CRYPTO 2008).Heidelberg:Springer-Verlag,2008.108-125.
[25]Barak B,Garg S,Kalai YT,Paneth O,Sahai A.Protecting obfuscation against algebraic attacks.In:Nguyen PQ,Oswald E,eds.Proc.of the 33rd Annual Int’l Conf.on the Theory and Applications of Cryptographic Techniques(EUROCRYPT 2014).Heidelberg:Springer-Verlag,2014.221-238.
[26]Lindell Y.How to simulate it-A tutorial on the simulation proof technique.IACR Cryptology ePrint Archive:Report 2016/046(2016),2016.http://eprint.iacr.org/2016/046.pdf
[27]Bellare M,Hoang VT,Rogaway P.Adaptively secure garbling with applications to one-time programs and secure outsourcing.In:Wang X,Sako K,eds.Proc.of the 18th Int’l Conf.on the Theory and Application of Cryptology and Information Security(ASIACRYPT 2012).Heidelberg:Springer-Verlag,2012.134-153.
[28]Aiello W,Ishai Y,Reingold O.Priced oblivious transfer:How to sell digital goods.In:Pfitzmann B,ed.Proc.of the 20th Annual Int’l Conf.on the Theory and Applications of Cryptographic Techniques(EUROCRYPT 2011).Heidelberg:Springer-Verlag,2001.119-135.
[29]Naor M,Pinkas B.Efficient oblivious transfer protocols.In:Proc.of the 12th Annual ACM-SIAM Symp.on Discrete Algorithms.ACM Press,2001.448-457.
[2]Micali S.CS proofs(extended abstract).In:Proc.of the 35th Annual Symp.on Foundations of Computer Science.IEEE Press,1994.436-453.
[3]Gennaro R,Gentry C,Parno B.Non-interactive verifiable computing:Outsourcing computation to untrusted workers.In:Rabin T,ed.Proc.of the 30th Annual Cryptology Conf.(CRYPTO 2010).Heidelberg:Springer-Verlag,2010.465-482.
[4]Applebaum B,Ishai Y,Kushilevitz E.From secrecy to soundness:efficient verification via secure computation.In:Abramsky S,et al.,eds.Proc.of the 37th Int’l Colloquium on Automata,Languages,and Programming(ICALP 2010).Heidelberg:SpringerVerlag,2010.152-163.
[5]Asharov G,Jain A,Lopez-Alt A,Tromer E,Vaikuntanathan V,Wichs D.Multiparty computation with low communication,computation and interaction via threshold FHE.In:Pointcheval D,Johansson T,eds.Proc.of the 31st Annual Int’l Conf.on the Theory and Applications of Cryptographic Techniques(EUROCRYPT 2012).Heidelberg:Springer-Verlag,2012.483-501.
[6]Ben-Sasson E,Chiesa A,Genkin D,Tromer E,Virza M.SNARKs for C:Verifying program executions succinctly and in zero knowledge.In Canetti R,Garay JA,eds.Proc.of the 33rd Annual Cryptology Conf.(CRYPTO 2013).Heidelberg:Springer-Verlag,2013.99-108.
[7]Choi SG,Katz J,Kumaresan R,Cid C.Multi-client non-interactive verifiable computation.In Sahai A,ed.Proc.of the 10th Theory of Cryptography Conf.(TCC 2013).Heidelberg:Springer-Verlag,2013.499-518.
[8]Chung KM,Kalai YT,Liu FH,Raz R.Memory delegation.In Rogaway P,ed.Proc.of the 31st Annual Cryptology Conf.(CRYPTO 2011).Heidelberg:Springer-Verlag,2011.151-168.
[9]Chung KM,Kalai Y,Vadhan S.Improved delegation of computation using fully homomorphic encryption.In:Rabin T,ed.Proc.of the 30th Annual Cryptology Conf.(CRYPTO 2010).Heidelberg:Springer-Verlag,2010.483-501.
[10]Fiore D,Gennaro R,Pastro V.Efficiently verifiable computation on encrypted data.In:Proc.of the 21st ACM Conf.on Computer and Communications Security(CCS 2014).ACM Press,2014.844-855.
[11]Ananth P,Chandran N,Goyal V,Kanukurthi B,Ostrovsky R.Achieving privacy in verifiable computation with multiple serversWithout FHE and without pre-processing.In:Krawczyk H,ed.Proc.of the 20th Int’l Conf.on Practice and Theory of Public-Key Cryptography(PKC 2014).Heidelberg:Springer-Verlag,2014.149-166.
[12]Badrinarayanan S,Goyal V,Jain A,Sahai A.Verifiable functional encryption.In:Cheon J,Takagi T,eds.Proc.of the 22nd Annual Int’l Conf.on the Theory and Applications of Cryptology and Information Security(ASIACRYPT 2016).Heidelberg:SpringerVerlag,2016.557-587.
[13]Lindell Y,Pinkas B.A proof of security of Yao’s protocol for two-party computation.Journal of Cryptology,2009,22(2):161-188.
[14]Yao AC.Protocols for secure computations(extended abstract).In:Shamir A,ed.Proc.of the 23rd Annual Symp.on Foundations of Computer Science.IEEE Press,1982.160-164.
[15]Goldwasser S,Kalai Y,Popa RA,Vaikuntanathan V,Zeldovich N.Reusable garbled circuits and succinct functional encryption.In:Proc.of the 45th Annual ACM Symp.on Theory of Computing(STOC 2013).ACM Press,2013.555-564.
[16]Agrawal S.Stronger security for reusable garbled circuits,general definitions and attacks.In:Katz J,Shacham H,eds.Proc.of the37th Annual Cryptology Conf.(CRYPTO 2017).Heidelberg:Springer-Verlag,2017.3-35.
[17]Gentry C.Fully homomorphic encryption using ideal lattices.In:Proc.of the 41st Annual ACM Symp.on Theory of Computing(STOC 2009).ACM Press,2009.169-178.
[18]Brakerski Z,Vaikuntanathan V.Lattice-based FHE as secure as PKE.In:Proc.of the 5th Conf.on Innovations in Theoretical Computer Science.ACM Press,2014.1-12.
[19]Gentry C,Halevi S,Vaikuntanathan V.I-hop homomorphic encryption and re-randomizable Yao circuits.In:Rabin T,ed.Proc.of the 30th Annual Cryptology Conf.(CRYPTO 2010).Heidelberg:Springer-Verlag,2010.155-172.
[20]Halevi S,Lindell Y,Pinkas B.Secure computation on the Web:Computing without simultaneous interaction.In:Rogaway P,ed.Proc.of the 31st Annual Cryptology Conf.(CRYPTO 2011).Heidelberg:Springer-Verlag,2011.132-150.
[21]Atallah MJ,Pantazopoulos KN,Rice JR.Secure outsourcing of scientific computations.Advances in Computers,2002,(54):215-272.
[22]Kilian J.Founding cryptography on oblivious transfer.In:Proc.of the 20th Annual ACM Symp.on Theory of Computing.ACMPress,1988.20-31.
[23]Mironov I,Stephens-Davidowitz N.Cryptographic reverse firewalls.In:Oswald E,Fischlin M,eds.Proc.of the 34th Annual Int’l Conf.on the Theory and Applications of Cryptographic Techniques(EUROCRYPT 2015).Heidelberg:Springer-Verlag,2015.657-686.
[24]Boneh D,Halevi S,Hamburg M,Ostrovsky R.Circular-secure encryption from decision Diffie-Hellman.In:Wagner D,ed.Proc.of the 28th Annual Cryptology Conf.(CRYPTO 2008).Heidelberg:Springer-Verlag,2008.108-125.
[25]Barak B,Garg S,Kalai YT,Paneth O,Sahai A.Protecting obfuscation against algebraic attacks.In:Nguyen PQ,Oswald E,eds.Proc.of the 33rd Annual Int’l Conf.on the Theory and Applications of Cryptographic Techniques(EUROCRYPT 2014).Heidelberg:Springer-Verlag,2014.221-238.
[26]Lindell Y.How to simulate it-A tutorial on the simulation proof technique.IACR Cryptology ePrint Archive:Report 2016/046(2016),2016.http://eprint.iacr.org/2016/046.pdf
[27]Bellare M,Hoang VT,Rogaway P.Adaptively secure garbling with applications to one-time programs and secure outsourcing.In:Wang X,Sako K,eds.Proc.of the 18th Int’l Conf.on the Theory and Application of Cryptology and Information Security(ASIACRYPT 2012).Heidelberg:Springer-Verlag,2012.134-153.
[28]Aiello W,Ishai Y,Reingold O.Priced oblivious transfer:How to sell digital goods.In:Pfitzmann B,ed.Proc.of the 20th Annual Int’l Conf.on the Theory and Applications of Cryptographic Techniques(EUROCRYPT 2011).Heidelberg:Springer-Verlag,2001.119-135.
[29]Naor M,Pinkas B.Efficient oblivious transfer protocols.In:Proc.of the 12th Annual ACM-SIAM Symp.on Discrete Algorithms.ACM Press,2001.448-457.