[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()

Share：

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

Keywords:

Turing machine;  fully homomorphic encryption;  outsourced computation

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.

Common functions