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.
Key words：Turing machine; fully homomorphic encryption; outsourced computation
The delegator-worker model is suitable for cloud computing, where the device of the user (i.e., the delegator) has limited computing resources, and the user outsources his/her program and data to the cloud servers (i.e., the workers), which usually have excellent computing resources. When the privacy of data is very important, fully homomorphic encryption (FHE) schemes[1-3] are the best cryptographic candidates, which enable the workers to operate the ciphertext given by the delegator without the private key and decryption process. One of the drawbacks of FHE schemes is that they only support the computation model of the circuit or the Boolean function, which is less flexible than the common Turing-machine-based computation model. As early as 1979, Pippenger et al.[4] showed how to encode a Turing machine (TM) into a circuit. However, the size of the encoded circuit is O(NlogN), which is dependent on the worst runtime N of the original Turing machine.
Recently, Gentry et al.[5]proposed a new primitive model called the garbled random access machine (GRAM), which takes on the similar idea of the garbled circuit[6] but it is designed for random access machines. However, the GRAM needs to prepare as many garbled transition functions as runtime steps during the initialization by the delegator, which is still a large cost.
In this paper, we propose a reusable FHE-based scheme to describe and execute the Turing machine, where the size of the description is only dependent on the size of the transition function, and the whole work for the delegator is to encrypt some binary matrices bit-by-bit.
We use λ to denote the security parameter throughout, and use the negligible notation f(λ)≤negl(λ) to show a function f(λ)=O(λ-c) for every constant c>0.
We employ the fully homomorphic encryption scheme as the building block for our scheme, which usually consists of four algorithms KeyGen(λ), Enc(pk,m), Dec(sk,[[m]]) and Eval(pk,f,[[m0]],[[m1]],…), where the plaintext message space belongs to {0,1} and the abbreviation [[m]] denotes the ciphertext of the corresponding plaintext m. The correctness of such a scheme guarantees that Dec(sk,Eval(pk,f,[[m0]], [[m1]],…))=f(m0,m1,…), where f can be the mod-2 addition (denoted as ⨁), the mod-2 multiplication (denoted as ⊗) or any other expressions based on these two operations. Without loss of generality, we assume that the FHE scheme is semantically secure, which, for any polynomial-time algorithm A, satisfies
In this paper, we employ the FHE primitives as black-boxes and do not care about the implementation details. For simplicity, when we use ⨁ and ⊗ between ciphertexts, we imply the calling to Eval(·). The notation [[x]]≅[[y]] denotes the relationship Dec(sk,[[x]])=Dec(sk,[[y]]), as that in almost all FHE schemes, the decryption is perfect (which means that no error will occur in decryption). The notations [[m]] or their [[M]] for a binary vector m or a binary matrix M are their shortcuts for the encrypted vector or matrix of each element.
i.
For simplicity, we formalize a one-tape bound Turing machine as a 4-tuple M=(Q,Γ,δ,q0), where Q⊆{0,1}k is a set of states; Γ⊆{0,1}w is a set of symbols; δ: Q×Γ→Q×Γ×{Left, Right} is the transition function, which takes the current state qcurrent and current symbol of the tape head hcurrent as input, outputs the next state qnext, the symbol to write by the head houtput and the moving direction of the head (L represents one step left and R represents one step right), and it is usually represented as a table, of which each row has the form:
where q0∈Q is the initial state.
There may be some other configurations of a Turing machine in standard textbooks such as the blank symbol b∈Γ, input symbol set Σ⊆Γ\{b} and the final state set F⊆Q. We omit them for the following reasons: b and Σ can be directly taken into accounts when δ is designed, and F cannot be tested in a private outsourced scenario since it will leak the runtime of different inputs.
The input (and output) of such a Turing machine is a bound tape which consists of n cells. Each cell contains a w-bit binary string representing one symbol, and it is associated with an address of the length l=log2n, by which we can locate where the head is. Note that we do not offer an unbound tape since algorithms usually have boundaries of space.
A honest-but-curious (or semi-honest) worker always follows the algorithms that the delegator gives to him, but he also tries to learn something from the given data. Obviously, if we encrypt every part of a Turing machine as well as its tape using a fully homomorphic encryption scheme, the worker will learn nothing due to the semantic security of FHE. It is not trivial to build an executable Turing machine based on only mod-2 additions and mod-2 multiplications, so we give the details about how to encrypt such a machine, including the transition function, the states, the symbols, the directions as well as the tape with addresses.
2.1 Simulation of the tape
The tape itself can be viewed as an n×w matrix T, which can be encrypted directly as [[T]]. However, we also need to hide the moves of the head, which is simulated as the changes of a head position variable a∈{0,1}l (Recall that l=log2n). Obviously, a should be encrypted as [[a]] in the worker’s server, so we need an algorithm to read a cell of [[T]], given [[a]]. This is the task of a private information retrieval protocol. For the context of FHE, we refer readers to the details in Ref.[7]. Algorithm HeadRead is inspired by the algorithms in Ref.[7] with some modifications for our scenario, as shown in Algorithm 1.
Algorithm 1 HeadRead
Input: [[T]]={[[ti,j]]}∈{[[0]],[[1]]}n×w, [[a]]={[[aj]]}∈{[[0]],[[1]]}l.
Output: [[h]]={[[hj]]}∈{[[0]],[[1]]}w.
1 for b=0 to n-1 do
2 Encrypt b to yield [[b]]=([[b0]],…,[[bl-1]])∈{[[0]],[[1]]}l
⨁[[bj]]⨁[[1]])
4 end
5 for j=0 to w-1 do
⊗[[ti,j]])
7 end
8 return [[h]]
In short, lines 1-4 calculate [[dj]] for all the n cells, which satisfy [[da]]≅[[1]] and [[dj≠a]]≅[[0]]. These [[dj]] can be viewed as selectors of cells. Lines 5-7 make each row of [[T]] be checked by [[dj]] so that only the value of [[ta,j]] leaves in [[hj]]. Similarly, there is a HeadWrite algorithm to write the symbol [[h]] in [[T]] at the location [[a]] as shown in algorithm 2.
Algorithm 2 HeadWrite
Input: [[T]], [[a]], [[h]]=([[h0]],…, [[hw-1]])∈{[[0]],[[1]]}w.
Output: [[T]].
1 for b=0 to n-1 do
2 Encrypt b to yield [[b]]=([[b0]],…,[[bl-1]])∈{[[0]],[[1]]}l
⨁[[bj]]⨁[[1]])
4 end
5 for i=0 to n-1 do
⨁[[1]]
7 for j=0 to w-1 do
⊗[[ti,j]])⨁([[di]]⊗[[hj]])
9 end
10 end
11 return [[T]]
As we can see, lines 1-4 are identical to those of HeadRead and share the same functionality. Lines 5-10 make use of [[di]] and its negation 
i]] to implement the following functionality: When the cell is selected, the current data is replaced with the input [[hj]], and otherwise the original data keep unchanged.
Finally, we consider the move of the tape head. We assume that the leftmost cell of the tape has the address 0 and the rightmost cell of the tape has the address n-1. Then we encode the action “one step left” as [[1]] and the action “one step right” as [[0]], and then use the HeadMove algorithm as follows.
Algorithm 3 HeadMove
Input: The current address [[a]] and the direction [[dir]].
Output: The next address [[a′]].
1 [[dl-1]]←[[1]]
2 for i=0 to l-2 do
3 [[di]]←[[dir]]
4 end
5 [[d]]=([[d0]],…, [[dl-1]])
6 [[a′]]←FullAdder([[a]], [[d]])
7 return [[a′]]
Lines 1-4 make d=2l-1 when dir=1 (one step left) and d=1 when dir=0 (one step right), which are the two’s complements of ∓1 of l-bit integers exactly. Then we call the standard Boolean function of l-bit full adder to implement the decrement and increment of the address of the head.
2.2 Simulation of the transition function
The transition function is the kernel of the Turing machine. Applying the encoding of directions, each row of the table of the transition function δ becomes a pure (2k+2w+1)-bit binary string. Assuming that there are m rows in the table, we use an m×(2k+2w+1) matrix F to store it, which can be encrypted directly as [[F]]. Given the current state [[q]] and current symbol read by the head [[h]], we can use the following MoveStep algorithm to obtain the next state [[q′]], the output of the head [[h′]] and the direction of the move of the head [[dir]].
Algorithm 4 MoveStep
Input: [[F]]={[[fi,j]]}, [[q]]∈{[[0]],[[1]]}k, [[h]]∈{[[0]],[[1]]}w.
Output: [[q′]]∈{[[0]],[[1]]}k, [[h′]]∈{[[0]],[[1]]}w, [[dir]]∈{[[0]],[[1]]}.
[[b]] ← ([[q0]],…, [[qk-1]], [[h0]],…, [[hw-1]])
for i=0 to m-1 do
⨁[[bj]]⨁[[1]])
end
for j=0 to k+w do
⊗[[fi,k+w+j]])
end
[[q′]] ← ([[c0]],…, [[ck-1]]);[[h′]] ← ([[ck]],…, [[ck+w-1]]); [[dir]]←[[ck+w]]
return [[q′]], [[h′]], [[dir]]
The whole process is similar to the HeadRead algorithm, except for that we use the first k+w columns (the states and symbols; i.e. the inputs of δ) of [[F]] as addresses for matching instead of the natural row number, and use the last k+w+1 columns of [[F]] as contents.
2.3 Process of evaluation
Now a Turing machine and its tape can be described as [[T]], [[F]] as well as the encrypted initial state [[q0]]. As we mentioned before, while executing an encrypted Turing machine, we cannot let the worker check whether the machine halts. Instead, we specify a worst-case runtime N. Putting all the things together, we obtain the TMEval algorithm.
Algorithm 5 TMEval
Input: [[T]], [[F]], [[q0]], N.
Output: [[T]] and the final state [[q]].
1 [[q]]← [[q0]]/* the state register */
2 [[a]]←[[b0]]/* the head position register */
3 for i=1 to N do
4 [[h]]←HeadRead([[T]], [[a]]) /* the current input symbol */
5 [[q]], [[h]], [[dir]] ← MoveStep([[F]], [[q]], [[h]])
6 HeadWrite([[T]], [[a]], [[h]])
7 [[a]]←HeadMove([[a]], [[dir]])
8 end
9 return [[T]], [[q]]
Lines 4-7 represent a complete cycle of a single MoveStep of the evaluation of the Turing machine. If the delegator only wants a few bits of the tape, he can use HeadRead as a private information retrieval algorithm to achieve this.
3.1 Definition
We follow the definition of the formal description of outsourced computation schemes in Ref.[8]. An outsourced computation consists of the following three algorithms:
1) FuncKeyGen(F,λ)→(PK,SK) encodes the program F as the public key PK and outputs a secret key SK kept in the hands of the delegator. λ is the security parameter for verifiability.
2) ProbGenSK(x)→(σx,τx) encrypts the function input x as a public value σx and a private value τx.
3) ComputePK(σx)→σy computes the encrypted result of y=F(x), using PK and σx.
The privacy of outsourced computation schemes is defined by the experiment 
(F,λ) as shown in algorithm 6, where the oracle PubProbGenSK(·) calls ProbGenSK(·) to generate (σx,τx) and returns the public part σx[8].
Input: Adversary A, function F, security parameter λ.
Output: The result of experiement: “succ” or “fail”.
F←A(·); (PK,SK) ← FuncKeyGen(F,λ)
(x0,x1)←APubProbGen(·)(PK)
(σ0,τ0)←ProbGenSK(x0); (σ1,τ1)←ProbGenSK(x1)
“succ”
else output “fail”
end
Definition 1 A outsourced computation scheme is said to be private for a function F, if for any probabilistic polynomial time adversary A,
3.2 Our scheme
Now we present our outsourced computation scheme based on the encryptable Turing machine (ETM):
1) FuncKeyGen((F,q0,N),λ)→(PK,SK): (pk,sk)←KeyGen(λ), PK←(pk,[[F]],[[q0]],N),SK←(pk,sk).
2) ProbGenSK(X)→(σX,τX): σX←[[X]], τX←X.
3) ComputePK(σX)→σY: σY←TMEval([[X]],[[F]],[[q0]],N).
Theorem 1 If there exists a semantically-secure fully homomorphic encryption (KeyGen, Enc, Dec, Eval), then our outsourced computation scheme is private for all F.
Proof Assume that there is an adversary A satisfying
where ε is non-negligible. Then, we construct an adversary A′ for breaking the semantic security experiment of the FHE scheme with the challenger C′ as follows:
A′ first receives PK′ from C′, and then sends m0=0 and m1=1 to C′.
k. Now A′ interacts with A as the challenger. He/She answers the PubProbGenSK(·) oracle and FuncKeyGen using pk=pk′ and a random string as sk.
]. A′ always sends σX1 to A.
With the probability 1/2, Dec(σX1)=X1, and in this case, A will succeed in ε. With the rest probability 1/2, Dec(σX1) is 0, and in this case, A may not have the advantages leading to success, and in the worst case, A will succeed in negl(λ).
Let A′ output what A outputs, then in the worst case, we have
·
·
which leads to a contradiction of the semantic security of the FHE scheme. Therefore, no such A exists.
There are several general secure multi-party computation schemes that can efficiently compute arbitrary functions without leaking private data to other parties, such as Yao’s classical garbled circuit scheme[6], the recent distributed oblivious RAM scheme[9] and other similar schemes. However, all these schemes require the client (in our context, the delegator) to interactively communicate with the server(s) (in our context, the worker(s)) during the computation process, which is unacceptable in the outsourced computation scenario, in which the delegator merely sends the data to the worker and fetches the result from the worker later. To the best of our knowledge, this non-interactive general secure computation can be achieved by only the fully homomorphic encryption schemes.
So, we mainly compare our implementation of encryptable Turing machines to the 1970s’ oblivious Turing machine (OTM), as the latter is still widely used in recent FHE-based studies[10-11]. As we claimed above, in our proposal, the description of Turing machine F is not dependent on the worst-case runtime N. We summarize the comparisons in Tab.1.
Tab.1 Comparisons of different Turing-equivalent computation schemes
SchemeWorst-caseruntimeEncodedsizeOriginalTMNO(1)TM-to-circuitschemes[4]O(N)O(NlogN)ObliviousTM[4,10-11]O(NlogN)O(1)GRAM[5]O(N)O(N)OurschemeO(N)O(1)
We propose a scheme that enables semi-honest servers to execute Turing-equivalent computations on encrypted data, where the encoding of the Turing machine is independent of its inputs and running time. Future work will be to model the encryptable Turing machine against malicious adversaries, who may return incorrect result to the user, and the user must have some efficient method to discover this malicious behavior. It is always possible, since there are standard compilers[12], to compile any secure multi-party computation protocol against a semi-honest adversary to a more secure protocol against malicious adversaries. However, all these compilers lower the efficiency of the secure multi-party computation protocol enormously. We plan in the future to implement a scheme against malicious adversaries by utilizing the special structure of the encryptable Turing machine and thus, thereby, achieve a more accurate result.
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.
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.
DOI：10.3969/j.issn.1003-7985.2016.03.002
摘要：提出了一种可进行私密同态图灵等效计算的方案,该方案中图灵机的编码与图灵机的输入及图灵机的运行时间无关.设计了若干种基于全同态加密的隐私数据检索协议扩展,从而用全同态加密所允许的布尔电路运算实现了对图灵机纸带的读写和对图灵机转移函数的执行.此方案明显优于同样实现了图灵等效计算的图灵机-电路转换方案.在图灵机-电路转换方案中,图灵机的编码既依赖于输入数据,也依赖于最坏运行时间.本方案在安全外包计算的委托者-工作者模型中可高效地为委托者提供程序机密性和数据机密性以对抗半诚实工作者.
关键词：图灵机;全同态加密;外包计算
中图分类号：TP309.7
Received：2016-01-15.
Foundation item：The National Basic Research Program of China (973 Program) (No.2013CB338003).
Biographies：Fang Hao(1985—), male, graduate; Hu Aiqun(corresponding author), male, doctor, professor, aqhu@seu.edu.cn.