Delegation Computation Based on Re-randomizable Garbled Circuit

doi:10.3969/j.issn.1000-3428.2013.12.029

Abstract

Abstract: Garbled circuit can be sought for the protection of input and circuit privacy of user in delegation computation. After malicious worker is cheated by answering output which is the label output in previous computation when garbled circuit is reused, the security of computation is compromised. A Delegation computation scheme based on re-randomizable garbled circuit is proposed to solve the not be reusable problem of circuit. Taking advantage of additively homomorphic property of BHHO scheme to map 0-1 vectors to 0-1 vectors of the same length performed by two known affine transformations on vectors over Zp, random bit permutations are applied to each wire of garbled circuit, and wire label and four pairs of ciphertexts of gate are re-randomized. Theoretical analysis results show the scheme can effectively solve the security of garbled circuit, and delegation computation provides input and output privacy for client and verifiability of results.

Key words: delegation computation, re-randomizable garbled circuit, reusable, BHHO schem, cloud computing

摘要： 委托计算中的混淆电路用于保护用户输入输出的隐私，如果重复使用混淆电路进行计算，恶意计算方可能将上一次计算的标签输出作为输出，无法保证计算的安全性。为此，提出一种基于随机化混淆电路的委托计算方案。利用BHHO方案的加同态特性，通过群Zp上的2个已知映射变换将0-1向量映射为同样长度的0-1向量，为混淆电路的每根电线随机选择比特置换，重新随机化设置电线标签和门电路的4个密文对。理论分析结果表明，该方案能有效解决混淆电路重复计算的安全问题，并且实现委托计算的用户隐私保护和结果可验证性。

关键词: 委托计算, 随机化混淆电路, 可重用, BHHO方案, 云计算

CLC Number:

TP309.2

ZHAO Qing-song, XU Huan-liang. Delegation Computation Based on Re-randomizable Garbled Circuit[J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2013.12.029.

赵青松，徐焕良. 基于随机化混淆电路的委托计算[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2013.12.029.

/ / Recommend / Download Citations

URL: http://www.ecice06.com/EN/10.3969/j.issn.1000-3428.2013.12.029

http://www.ecice06.com/EN/Y2013/V39/I12/136

References

参考文献 [1] Babai L. Trading Group Theory for Randomness[C]//Proceed- ings of the 17th Annual ACM Symposium on Theory of Computing. New York, USA: ACM Press, 1985: 421-429. [2] Goldwasser S, Micali S, Racko C. The Knowledge Com- plexity of Interactive Proof Systems[J]. SIAM Journal on Computing, 1989, 18(1): 186-208. [3] Kilian J. A Note on Efficient Zero-knowledge Proofs and Arguments[C]//Proceedings of the 24th Annual ACM Symposium on Theory of Computing. New York, USA: ACM Press, 1992: 723-732. [4] Kilian J. Improved Efficient Arguments[C]//Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology. London, UK: Springer-Verlag, 1995: 311-324. [5] Micali S. Computationally Sound Proofs[J]. SIAM Journal on Computing, 2000, 30(4): 1253-1298. [6] Goldwasser S, Kalai Y T, Rothblum G N. Delegating Compu- tation: Interactive Proofs for Muggles[C]//Proceedings of the 40th Annual ACM Symposium on Theory of Computing. New York, USA: ACM Press, 2008: 113-122. [7] Gentry C. Fully Homomorphic Encryption Using Ideal Lat- tices[C]//Proceedings of the 41st Annual ACM Symposium on Theory of Computing. New York, USA: ACM Press, 2009: 169-178. [8] 靳方元, 朱艳琴, 罗喜召. 基于可验全同态加密的委托计算方案[J]. 计算机工程, 2012, 38(23): 150-153. [9] Yao A C. Protocols for Secure Computations[C]//Proceedings of the 23rd Annual Symposium on Foundations of Computer Science. Washington D. C., USA: IEEE Computer Society, 1982: 160-164. [10] Yao A C. How to Generate And Exchange Secrets[C]// Proceedings of the 27th Annual Symposium on Foundations of Computer Science. Washington D. C., USA: IEEE Computer Society, 1986: 162-167. [11] Gennaro R, Gentry G, Parno B. Non-interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers[C]//Proceedings of the 30th Annual Conference on Advances in Cryptology. Berlin, Germany: Springer-Verlag, 2010: 465-482. [12] Chung Kai-Min, Kalai Y T, Vadhan S P. Improved Delegation of Computation Using Fully Homomorphic Encryption[C]// Proceedings of the 30th Annual Cryptology Conference on Cryptology Advances. Berlin, Germany: Springer-Verlag, 2010: 483-501. [13] Goldwasser S, Kalai Y, Popa R A, et al. Reusable Garbled Circuits and Succinct Functional Encryption[C]//Proceedings of the 45th Annual ACM Symposium on Theory of Computing. New York, USA: ACM Press, 2013: 555-564. [14] Lindell Y, Pinkas B. A Proof of Security of Yao’s Protocol for Two-party Computation[J]. Journal of Cryptology, 2009, 22(2): 161-188. [15] Oded G. 密码学基础(第二卷)[M]. 温巧燕, 杨义先, 郭奋卓,等, 译. 北京: 人民邮电出版社, 2005. [16] Gentry C, Halevi S, Vaikuntanathan V. I-hop Homomorphic Encryption and Rerandomizable Yao Circuits[C]//Proceedings of the 30th Annual Conference on Advances in Cryptology. Santa Barbara, USA: IEEE Press, 2010: 155-172. [17] Boneh D, Halevi S, Hamburg M, et al. Circular-secure Encryption from Decision Diffie-Hellman[C]//Proceedings of the 28th Annual Conference on Cryptology Advances in Cryptology. Santa Barbara, USA: IEEE Press, 2008: 108-125. [18] Naor M, Segev G. Public-key Cryptosystems Resilient to Key Leakage[C]//Proceedings of the 29th Annual Conference on Advances in Cryptology. Santa Barbara, USA: IEEE Press, 2009: 18-35. 编辑陆燕菲

Please choose a citation manager

Content to export