[1] Fang Hao, Hu Aiqun,. A secure outsourced Turing-equivalent computation schemeagainst semi-honest workers using fully homomorphic encryption [J]. Journal of Southeast University (English Edition), 2016, 32 (3): 267-271. [doi:10.3969/j.issn.1003-7985.2016.03.002]
Copy
A secure outsourced Turing-equivalent computation schemeagainst semi-honest workers using fully homomorphic encryption(
)
基于全同态加密的抵抗半诚实工作者的 安全外包图灵等效计算方案
)Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]
- Volumn:
- 32
- Issue:
- 2016 3
- Page:
- 267-271
- Research Field:
- Computer Science and Engineering
- Publishing date:
- 2016-09-20
Info
- Title:
- A secure outsourced Turing-equivalent computation schemeagainst semi-honest workers using fully homomorphic encryption
- 基于全同态加密的抵抗半诚实工作者的 安全外包图灵等效计算方案
- Author(s):
- Fang Hao, Hu Aiqun
- School of Information Science and Engineering, Southeast University, Nanjing 210096, China
- PACS:
- TP309.7
- DOI:
- 10.3969/j.issn.1003-7985.2016.03.002
- Abstract:
- A scheme that can realize homomorphic Turing-equivalent privacy-preserving computations is proposed, where the encoding of the Turing machine is independent of its inputs and running time. Several extended private information retrieval protocols based on fully homomorphic encryption are designed, so that the reading and writing of the tape of the Turing machine, as well as the evaluation of the transition function of the Turing machine, can be performed by the permitted Boolean circuits of fully homomorphic encryption schemes. This scheme overwhelms the Turing-machine-to-circuit conversion approach, which also implements the Turing-equivalent computation. The encoding of a Turing-machine-to-circuit conversion approach is dependent on both the input data and the worst-case runtime. The proposed scheme efficiently provides the confidentiality of both program and data of the delegator in the delegator-worker model of outsourced computation against semi-honest workers.
- 提出了一种可进行私密同态图灵等效计算的方案, 该方案中图灵机的编码与图灵机的输入及图灵机的运行时间无关.设计了若干种基于全同态加密的隐私数据检索协议扩展, 从而用全同态加密所允许的布尔电路运算实现了对图灵机纸带的读写和对图灵机转移函数的执行.此方案明显优于同样实现了图灵等效计算的图灵机-电路转换方案.在图灵机-电路转换方案中, 图灵机的编码既依赖于输入数据, 也依赖于最坏运行时间.本方案在安全外包计算的委托者-工作者模型中可高效地为委托者提供程序机密性和数据机密性以对抗半诚实工作者.
References:
[1] Gentry C. Fully homomorphic encryption using ideal lattices[C]//Proceedings of the 41st Annual ACM Symposium on Theory of Computing. Bethesda, USA, 2009: 169.
[2] Brakerski Z, Gentry C, Vaikuntanathan V.(Leveled)fully homomorphic encryption without bootstrapping[C]//Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. Cambridge, USA, 2012: 309-325.
[3] Gentry C, Sahai A, Waters B. Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based[C]//Advances in Cryptology—CRYPTO 2013. Berlin, Germany: Springer, 2013: 75-92.
[4] Pippenger N, Fischer M J. Relations among complexity measures[J]. Journal of the ACM, 1979, 26(2): 361-381. DOI:10.1145/322123.322138.
[5] Gentry C, Halevi S, Lu S, et al. Garbled RAM revisited[C]//Advances in Cryptology—EUROCRYPT 2014. Berlin, Germany: Springer, 2014: 405-422.
[6] Yao A C C. Protocols for secure computations[C]//23rd Annual Symposium on Foundations of Computer Science. Chicago, USA, 1982: 160-164.
[7] Yi X, Kaosar M G, Paulet R, et al. Single-database private information retrieval from fully homomorphic encryption[J].IEEE Transactions on Knowledge and Data Engineering, 2013, 25(5): 1125-1134. DOI:10.1109/tkde.2012.90.
[8] Gennaro R, Gentry C, Parno B. Non-interactive verifiable computing: Outsourcing computation to untrusted workers[C]//Advances in Cryptology—CRYPTO 2010. Berlin, Germany: Springer, 2010: 465-482. DOI:10.1007/978-3-642-14623-7_25.
[9] Lu S, Ostrovsky R. Distributed oblivious RAM for secure two-party computation[C]//10th Theory of Cryptography Conference. Tokyo, Japan, 2013: 377-396. DOI:10.1007/978-3-642-36594-2_22.
[10] Goldwasser S, Kalai Y T, Popa R A, et al. How to run turing machines on encrypted data[C]//Advances in Cryptology—CRYPTO 2013. Berlin, Germany: Springer, 2013: 536-553.
[11] Boyle E, Chung K M, Pass R. On extractability obfuscation[C]//11th Theory of Cryptography Conference. San Diego, USA, 2014:52-73. DOI:10.1007/978-3-642-54242-8_3.
[12] Chung K M, Kalai Y, Vadhan S. Improved delegation of computation using fully homomorphic encryption[C]//Advances in Cryptology—CRYPTO 2010. Berlin, Germany: Springer, 2010: 483-501. DOI:10.1007/978-3-642-14623-7_26.
Memo
- Memo:
-
Biographies: Fang Hao(1985—), male, graduate; Hu Aiqun(corresponding author), male, doctor, professor, aqhu@seu.edu.cn.
Foundation item: The National Basic Research Program of China(973 Program)(No.2013CB338003).
Citation: Fang Hao, Hu Aiqun. A secure outsourced Turing-equivalent computation scheme against semi-honest workers using fully homomorphic encryption[J].Journal of Southeast University(English Edition), 2016, 32(3):267-271.DOI:10.3969/j.issn.1003-7985.2016.03.002.