A Scheme for Delegating Program Executions without Disclosing Secret Values

Shinsuke Tamura, Shuji Taniguchi

  Open Access OPEN ACCESS  Peer Reviewed PEER-REVIEWED

A Scheme for Delegating Program Executions without Disclosing Secret Values

Shinsuke Tamura1,, Shuji Taniguchi1

1School of Engineering, University of Fukui, Fukui, Japan

Abstract

A scheme that enables entities to delegate accomplishments of their secret tasks to others under complicated conditions is proposed. The proposed scheme exploits multidimensional array based encryption functions, and different from schemes that exploit public key based fully homomorphic encryption functions, it can handle real numbers in the same way as integers. Also, it enables entities to define complicated calculation algorithms as computer programs that are easy to develop and efficient to execute. In addition, together with data encryption, data redundancy and test data insertion principles it disables relevant entities to accomplish tasks dishonestly.

At a glance: Figures

Cite this article:

  • Tamura, Shinsuke, and Shuji Taniguchi. "A Scheme for Delegating Program Executions without Disclosing Secret Values." Information Security and Computer Fraud 2.2 (2014): 21-27.
  • Tamura, S. , & Taniguchi, S. (2014). A Scheme for Delegating Program Executions without Disclosing Secret Values. Information Security and Computer Fraud, 2(2), 21-27.
  • Tamura, Shinsuke, and Shuji Taniguchi. "A Scheme for Delegating Program Executions without Disclosing Secret Values." Information Security and Computer Fraud 2, no. 2 (2014): 21-27.

Import into BibTeX Import into EndNote Import into RefMan Import into RefWorks

1. Introduction

Advances in information and communication technologies had been making every kind of activities in our society highly convenient and efficient. For example, cloud computing systems enable companies to outsource even their core tasks and to quickly launch new businesses without maintaining their own permanent computation resources that are expensive and require long development time. However, these companies must be aware that they are facing serious threats at the same time. Namely, cloud computing resources can easily gather secrets of companies that outsource their task accomplishments. Therefore, people cannot reap full benefits from advancing information and communication technologies, e.g. companies in the above still must accomplish their important tasks by themselves to make their competitiveness sustainable.

Theoretically, fully homomorphic encryption functions can remove the above inconveniences. Namely, to ask cloud computing server S to calculate function f(X1, X2, ---, XN) of values X1, X2, ---, XN, client P encrypts X1, X2, ---, XN to E(k, X1), E(k, X2), ---, E(k, XN) by encryption key k of fully homomorphic encryption function E(k, x), and S calculates f(E(k, X1), E(k, X2), ---, E(k, XN)). Then because E(k, x) is fully homomorphic, P can reconstruct f(X1, X2, ---, XN) by decrypting f(E(k, X1), E(k, X2), ---, E(k, XN)), on the other hand, S that does not know decryption key k-1 cannot know any of X1, X2, ---, XN or f(X1, X2, ---, XN).

However, although long time had passed since schemes for delegating function calculations to others without disclosing relevant data were proposed [2, 3, 4], many schemes including most recent fully homomorphic encryption function based ones [7, 8] are still impractical; they require cumbersome operations for handling real numbers that appear in most business and engineering applications. Also, client P must define calculation algorithms as complicated logic circuits instead of computer programs because server S cannot determine whether conditions about jumps and loops in the programs are satisfied or not when relevant values are encrypted.

To enable entities to delegate their secret task executions under complicated conditions, this paper proposes an MA-based scheme that exploits multidimensional array based (MA-based) encryption functions. MA-based encryption function E(k, x) is both additive and multiplicative, i.e. relations E(k, x)+E(k, y) = E(k, x+y) and E(k, x)E(k, y) = E(k, xy) hold, and it can handle real numbers as same as integers. In addition, MA-based encryption functions can be made order preserving, in other words, entities can determine whether relation xy holds or not even from encryption forms E(k, x) and E(k, y). Therefore, by the proposed scheme server S can easily calculate various functions of integers and real numbers, e.g. polynomials and maximums/minimums, etc. without knowing their values, and at the same time, client P can communicate complicated calculation algorithms to server S by computer programs that are much easier to develop and much more efficient to execute when compared with logic circuits.

About the integrity of calculation results, several schemes to protect programs from dishonest executions had been proposed, e.g. in one of them client P asks multiple servers to carry out same calculations and detects dishonesties when these servers respond differently, and in another scheme P makes programs complicated so that other entities cannot analyze the programs to modify them consistently [5]. However in the former scheme, P must ask the calculations to many servers if possibilities in which different servers conspire are considered, and in the latter scheme still other entities can easily replace programs with ones that they had developed by themselves even if the original programs are difficult to analyze. Although schemes based on fully homomorphic encryption functions are also proposed to maintain the integrity of calculation results [8], they are not practical enough as same as the base schemes for delegating function calculations. Therefore in this paper, data encryption, data redundancy and test data insertion principles are combined with the MA-based scheme. Namely, client P provides the data for server S while encrypting them by MA-based encryption functions, duplicating same data and inserting test data about which calculation results are known in advance. Here, MA-based encryption functions are probabilistic, i.e. even same data are encrypted to different values, therefore S cannot identify duplicated data or test data among ones given from P. This means P can detect dishonest calculations of S by the facts that S returns different values or wrong values for same data or test data respectively.

2. Overall Behaviors of the Scheme

Figure 1 shows the configuration of a system that exploits the proposed scheme. It consists of clients and servers, and client P shows values of its data items while encrypting them by its secret encryption key to ask servers to accomplish its secret tasks. On the other hand, server S maintains programs that correspond to algorithms for accomplishing the tasks, where these programs are developed by P itself or other entities including servers.

Figure 1. Configuration of a system that exploits an MA-based scheme

Important things are encryption functions are MA-based that are both additive and multiplicative and as will be discussed later MA-based encryption functions can be made order preserving. Therefore, when the programs calculate functions of encrypted values given by P, P can obtain plain function values by decrypting the calculation results, provided that the functions are simple ones, e.g. polynomials and maximums/minimums. Also, S can evaluate conditional statements in the programs without decrypting values encrypted by P. Then, P can ask S to calculate functions of its secret data with minimum interactions between S even if calculation conditions are complicated. Here, P can also conceal its identities if anonymous communication channels [1, 6, 9] are used, and S can collect fees from P even if P is anonymous by using anonymous credit card systems for example [10].

But without additional mechanisms servers and clients can behave maliciously, e.g. servers may calculate functions incorrectly or replace the programs with wrong ones, and on the other hand, clients may intentionally provide servers with wrong data. To protect clients and servers from malicious behaviors of others P configures its encryption data as shown in Fig. 2. In the figure, E(k, x; px) is an MA-based encryption function, px is a random factor to make E(k, x) probabilistic, k is a secret key of P, and P encrypts value Xj of its j-th data item to E(k, Xj; pj). But it does not inform S of E(k, Xj; pj) individually, instead, P gives S a sequence of encrypted values {E(k, X1; p1), E(k, X2; p2), ---, E(k, Xj; pj), ---, E(k, Xj; pj*), ---, E(k, Th; pTh), ---, E(k, XN; pN)}. Here, E(k, Xj; pj) and E(k, Xj; pj*) take different values despite that they are encryption forms of same Xj because E(k, x; px) is probabilistic, and P knows the calculation result corresponding to test data Th in advance. Then, S cannot identify same data item or test data item values in the input sequence, and as a result, P can detect S’s dishonesties as facts that S calculates different values or incorrect values for same data items or test data items respectively.

About dishonesties of client P, {S(d1║d2, TPR+1KwCwR)W, h(E(k, x; p))R} in Figure 2 is an anonymous signature of client P on encryption form E(k, x; p), i.e. only P can generate it consistently but no one except P can identify the entity that had generated it. Then, server S can convince anyone that it had certainly received encryption form E(k, x; p) from a legitimate entity, at the same time provided that it is honest, P can conceal its identity from S.

Figure 2. A data sequence client P provides for server S

3. MA-based Encryption Functions

Because fully homomorphic encryption functions are asymmetric public key based [7, 8], they are not convenient enough especially for handling real numbers that appear frequently in many business and engineering applications. But it must be noted that the entity which encrypts and decrypts data item values secrets of client P in Figure 1 is P itself, therefore encryption function E(k, x; px) in the figure does not need to be public key based. Then, implementation of both additive and multiplicative encryption function E(k, x; px) that can handle real numbers as same as integers becomes easy. It is also straightforward to make E(k, x; px) order preserving,

In the following notation E(k, x) is used instead of E(k, x; px) when confusions can be avoided.

3.1. 1-dimensional Representation

Multidimensional array based (MA-based) encryption function E(k, x) that is both additive and multiplicative can be constructed as below [10]. Let E(k, x) be a function that transforms real number x to vector {x(1), x(2), ---, x(z)} so that relation a1x(1)+a2x(2)+ --- +azx(z) = x holds for a set of real number coefficients {a1, a2, --- az} that are secrets of client P. Then, vector E(k, x) is an encryption form of x; although P that knows coefficients {a1, --- az} can easily calculate x from {x(1), ---, x(z)}, it is not straightforward to know x from them without knowing the coefficients. Here, it must be noted that some of coefficients ah1, ah2, --- ahm may have value 0, and this means x(h1), x(h2), ---, x(hm) are dummy elements that can have any values. Also, E(k, x) = E(k, x; px) is probabilistic, i.e. 2-vectors {x(1), ---, x(z)} and {y(1), ---, y(z)} are decrypted to same real number x even if {x(1), ---, x(z)} ≠ {y(1), ---, y(z)}, provided that relations a1x(1)+ --- +azx(z) = x and a1y(1)+ --- +azy(z) = x hold.

About secureness of encryption function E(k, x), apparently it is weak against plain text attacks. But client P can protect its secrets from others because data item values are encrypted and decrypted by P itself, i.e. P never discloses secret values in their plain forms. In detail, for entities that do not know values of coefficients {a1, a2, --- az} or plain and encryption form pairs, every real number has equal possibility to be a decryption form of vector {x(1), ---, x(z)}.

3.2. Multidimensional Representation

E(k, x) in the above is apparently additive, i.e. relation E(k, x)+E(k, y) = E(k, x+y) holds. E(k, x) can be made both additive and multiplicative when it is extended from vector {x(1), ---, x(z)} to n-dimensional array {x(i1, i2, ---, in)} as follow.

Firstly, 1-dimensional encryption form E1(k, x) = {x(1), x(2), ---, x(z)} can be extended to 2-dimensional array E2(k, x) = <{x(1, 1), x(1, 2), ---, x(1, z)}, {x(2, 1), x(2, 2), ---, x(2, z)}, ---, {x(z, 1), x(z, 2), ---, x(z, z)}> by defining values {x(j, 1), x(j, 2), ---, x(j, z)} so that relation x(j) = a1x(j, 1)+a2x(j, 2)+ --- +azx(j, z) holds for each element x(j) (in addition to E(k, x) notation En(k, x) is also used for representing an n-dimensional encryption form of x). Namely, E2(k, x) is decrypted to a1{a1x(1, 1)+a2x(1, 2)+ --- + azx(1, z)} + a2{a1x(2, 1)+a2x(2, 2)+ --- +azx(2, z)} + --- + az{a1x(z, 1)+a2x(z, 2)+ --- +azx(z, z)} = a1x(1)+a2x(2)+ --- +azx(z) = x. Where x(j, h) can have any value when coefficient ah is 0, i.e. x(j, h) is a dummy element as in the previous subsection. In the same way n-dimensional extension of E(k, x) can be defined as an n-dimensional array En(k, x) = {x(i1, i2, ---, in)}, i.e. it is decrypted to x according to equation (1).

(1)

Now, addition and multiplication can be defined in a set of encryption forms. Firstly, product of Er(k, x) = {x(i1, ---, ir)} and En(k, y) = {y(q1, ---, qn)} is (r+n)-dimensional array {z(i1, ---, ir, q1, ---, qn)} = {x(i1, ---, ir)y(q1, ---, qn)}. For example, product of E1(k, x) = {x(1), ---, x(z)} and E1(k, y) = {y(1), ---, y(z)} is 2-dimensional array <{x(1)y(1), x(1)y(2), ---, x(1)y(z)}, {x(2)y(1), x(2)y(2), ---, x(2)y(z)}, ---, {x(z)y(1), x(z)y(2), ---, x(z)y(z)}>, where it is apparent that product {x(i)y(q)} is decrypted to xy. About addition, r-dimensional encryption form Er(k, x) = {x(i1, ---, ir)} can be transformed to an n-dimensional one (n > r) by multiplying (n-r)-dimensional encryption form En-r(k, 1), i.e. product Er(k, x)En-r(k, 1) = {x*(i1, ---, in)} is an n-dimensional array and it is decrypted to x1 = x. Then, because {x*(i1, ---, in)+y(i1, ---, in)} is decrypted to x+y, MA-based encryption functions become both additive and multiplicative provided that addition of r-dimensional and n-dimensional encryption forms Er(k, x) = {x(i1, ---, ir)} and En(k, y) = {y(i1, ---, in)} is defined as {x*(i1, ---, in)+y(i1, ---, in)}. Here, it is apparent that x and y in the above can have real number values as well as integer values. Also, because disclosed plain and encryption form pair is only {1, En-r(k, 1)}, still plain text attacks are difficult enough.

While exploiting the above additive and multiplicative property client P can ask server S to calculate polynomial functions of {X1, X2, ---, XN} without disclosing values{X1, X2, ---, XN}. For example, f(X1, X2, X3) = X12X2 + X23X3 can be calculated as follows. Firstly while using secret encryption key k, P encrypts X1, X2 and X3 to E1(k, X1), E1(k, X2) and E1(k, X3) as 1-dimensional arrays and informs S of them together with encryption form E1(k, 1) that it prepared in advance. After that S calculates E1(k, X1)2E1(k, X2) = E3(k, X12X2) and E1(k, X2)3E1(k, X3) = E4(k, X23X3) as 3-dimensional and 4-dimensional arrays respectively, and transforms E3(k, X12X2) to 4-dimensional array E3(k, X12X2)E1(k, 1) = E4(k, X12X2) to add it to E4(k, X23X3). Then, P can calculate X12X2 + X23X3 by decrypting E4(k, X12X2)+E4(k, X23X3) by its secret decryption key k-1.

3.3. Preserving Orders

Provided that order is defined between x and y and between their encryption forms E(k, x) and E(k, y), encryption function E(k, x) is called order preserving when relation E(k, x) ≤ E(k, y) implies xy. MA-based encryption function E(k, x) can be made order preserving as follows.

For 1-dimensional encryption forms, client P defines secret positive constant real number λ and element position p in encryption forms (P may reveal position p to others), and to encrypt values x and y assigns values λx and λy to elements x(p) and y(p) in vectors E1(k, x) = {x(1), ---, x(z)} and E1(k, y) = {y(1), ---, y(z)} respectively. Where, other elements {x(1), ---, x(p-1), x(p+1), ---, x(z)} and {y(1), ---, y(p-1), y(p+1), ---, y(z)} are defined so that a1x(1)+ --- +ap-1x(p-1)+ap+1x(p+1)+ --- +azx(z) = (1-apλ)x and a1y(1)+ --- +ap-1y(p-1)+ap+1y(p+1)+ --- +azy(z) = (1-apλ)y hold when coefficient ap ≠ 0 of course. Then, provided that the order between encryption forms E1(k, x) and E1(k, y) is defined in a way that relation x(p) ≤ y(p) implies E1(k, x) ≤ E1(k, y), encryption function E1(k, x) becomes order preserving, and as a consequence, if client P informs server S of element position p in vectors, S can determine whether xy or not by comparing x(p) and y(p). But S cannot know x or y from x(p) or y(p) because λ is known only to P. Here, P can assign different values to p and λ for different encryptions if required, and in the reminder, x(p) and y(p), i.e. the p-th elements of E1(k, x) and E1(k, y), are called order-indicators of E1(k, x) and E1(k, y).

In a case where n-dimensional encryption forms En(k, x) = {x(i1, ---, in)} and En(k, y) = {y(i1, ---, in)} are compared, firstly it must be noted that both En(k, x) and En(k, y) are generated as products of the lower dimensional encryption forms, therefore if all 1-dimensional encryption forms that constitute the products are constructed as in the above, (p, p, ---, p)n-th elements of En(k, x) and En(k, y) have values λnx and λny respectively, where (p, p, ---, p)n represents element positions in n-dimensional arrays. Then, server S can decide whether xy or not by comparing (p, p, ---, p)n-th elements of En(k, x) and En(k, y) without decrypting them, i.e. En(k, x) and En(k, y) preserve the order between x and y, and (p, p, ---, p)n-th elements of encryption forms constitute order indicators.

But in a case when n-dimensional and r-dimensional encryption forms En(k, x) = {x(i1, ---, in)} and Er(k, u) = {u(i1, ---, ir)} are compared (n > r), because λnλr, their order indicators x(p, ---, p)n = λnx and u(p, ---, p)r = λru may not preserve the order. To compare them, En(k, x) and Er(k, u) must be transformed to same dimensional encryption forms. Although additional considerations are required to protect the scheme from plain text attacks as will be discussed later, this can be achieved by multiplying En(k, x) and Er(k, u) by appropriate dimensional encryption forms which are prepared by client P in advance. For example, provided that Em1(k, v1), Em2(k, 1/v1), Em3(k, v2), Em4(k, v3) and Em5(k, 1/v2v3) are m1, m2, m3, m4 and m5 dimensional encryption forms and relation n+m1+m2 = r+m3+m4+m5 = m holds, En(k, x)Em1(k, v1)Em2(k, 1/v1) = Em(k, x) and Er(k, u)Em3(k, v2)Em4(k, v3)Em5(k, 1/v2v3) = Em(k, u) are same dimensional encryption forms of x and u, and their (p, ---, p)m-th elements have values (λnx)(λm1v1)(λm2/v1) = λmx and (λru)(λm3v2)(λm4v3)(λm5/v2v3) = λmu, respectively. This means S that know element position p can determine whether xy or not without decrypting either En(k, x) or Er(k, u).

Because E(k, x) is a MA-based encryption function, it is also additive and multiplicative. In addition, provided that En(k, x) = {x(i1, ---, in)} and En(k, y) = {y(i1, ---, in)} are n-dimensional encryption forms of x and y, when values λnx and λny are assigned to their (p, ---, p)n-th elements, the (p, ---, p)n-th element of En(k, x)+En(k, y) = En(k, x+y) has value λn(x+y), and this means the order is preserved even when encryption forms are added. In the same way, provided that (p, ---, p)n-th and (p, ---, p)r-th elements of n-dimensional and r-dimensional encryption forms En(k, x) = {x(i1, ---, in)} and Er(k, y) = {y(i1, ---, ir)} have values λnx and λry respectively, the (p, ---, p)n+r-th element of En(k, x)Er(k, y) = En+r(k, xy) has value λn+rxy, i.e. the order is preserved also when encryption forms are multiplied.

A problem is that order indicators include clues to know decrypted values of encryption forms. Namely, entities can know values λx and λy from E(k, x) and E(k, y) if they know the position of order indicators which makes plain text attacks easier although it is not straightforward to calculate x and y from λx and λy. A fortunate thing is theoretically anyone cannot calculate x from E(k, x) without knowing decryption key k-1 even if it gathers numbers of encryption form and order indicator pairs.

In detail, although any entity can obtain relations λ{a1x1(1)+ --- +azx1(z)} = λx1 = x1(p), λ{a1x2(1)+ --- +azx2(z)} = λx2 = x2(p), ---, λ{a1xw(1)+ --- +azxw(z) = λxw = xw(p) from encryption forms E(k, x1), E(k, x2), ---, E(k, xw) that include order indicators x1(p), x2(p), ---, xw(p), and the entity may be able to calculate {λa1, λa2, ---, λaz} as {δ1, δ2, ---, δz} by solving simultaneous linear equations, it cannot know coefficients {a1, a2, ---, az} or λ because any set of real numbers {a1*, a2*, ---, az*, λ*} that satisfies relations λ*a1* = δ1, λ*a2* = δ2, ---, λ*az* = δz is consistent. But, values {δ1, δ2, ---, δz} enable entities to know ratios among coefficients which are good clues to decrypt encryption forms, e.g. ratios among {a1, a2, ---, az} and 1-plain and encryption form pair enable any entity to decrypt all encryption forms. Therefore, client P must restrict values that are encrypted by order preserving encryption functions to selected ones as will be discussed in the next section. Also, P must conceal correspondences between order preserving encryption forms of same values in different dimensions. When n-dimensional and r-dimensional order preserving encryption forms En(k, x) and Er(k, x) of same value x are available (n > r), it is easy to calculate secret real constant λ. Because order indicators of En(k, x) and Er(k, x) take values λnx and λrx respectively, it is trivial to calculate λ from relation λn-r = λnx/λrx.

4. Describing Calculation Algorithms

As in the previous section, client P in Fig. 1 can successfully delegate calculations of simple functions (e.g. polynomials) of integers and real numbers X1, X2, ---, XN to server S without disclosing their values. P can also calculate maximums and minimums of its secret values if encryption function E(k, x) is order preserving, and when encryption forms E(k, 1/X1), ---, E(k, 1/XN) are prepared in addition to E(k, X1), ---, E(k, XN), calculations of wider variety of functions become possible. Here, P protects encryption forms from plain text attacks by not disclosing plain and encryption form pairs except specific ones and by limiting encryption forms with order preserving features to selected ones.

But even if individual functions are simple, usually S is asked to calculate numbers of functions for many data in complicated and varying conditions, and P must inform S of these conditions with minimum interactions between S. Namely, if P and S need to frequently interact with each other to communicate calculation conditions of individual functions, benefits of the outsourcing totally vanish, as a result P may calculate functions by itself. To reduce interactions between P and S, in schemes based on public key fully homomorphic encryption functions, P communicates calculation algorithms by logic circuits, but logic circuits are complicated and cumbersome to develop and not efficient enough to execute. The proposed scheme makes calculation algorithms easy to develop and efficient to execute by describing them as usual computer programs instead of logic circuits, as a result, in the proposed scheme complicated calculation conditions are represented as combinations of conditional jumps and loops. Then, to execute the programs S must be able to determine whether conditions are satisfied or not based on encrypted values.

Order preserving MA-based encryption function E(k, x) enables S to execute conditional statements based on encrypted values, if all values included in conditions are numerical ones. Namely, if P encrypts X and Y to E(k, X) and E(k, Y), from them S can not only calculate polynomial functions of X and Y but also can determine whether relation XY holds or not without knowing X or Y. Here, even if computer programs are developed by P itself and P does not disclose plain forms of its secret values, S can know positions of order indicators by analyzing the programs, i.e. conditional statements directly compare order indicators of encryption forms. Also, to add or compare n-dimensional and r-dimensional encryption forms En(k, X) and Er(k, Y) (n ≠ r), computer programs generate same dimensional arrays Em(k, X) and Em(k, Y), and this means S can obtain at least one different dimensional order preserving encryption form pair {En(k, X), Em(k, X)} or {Er(k, Y), Em(k, Y)} which enables S to calculate X and Y, as discussed in the previous section. Therefore to protect its secrets from plain text attacks, P must restrict variables that are encrypted by order preserving encryption functions only to the ones that are included in conditional statements (in the remaining, variables that are encrypted by order preserving encryption functions are called order preserving variables). In addition, to disable S to decrypt encryption forms from pair {En(k, X), Em(k, X)} or {Er(k, Y), Em(k, Y)}, mechanisms to conceal correspondences between different dimensional order preserving encryption forms of same values are necessary.

About the mechanism to restrict order preserving variables to selected ones, fortunately, E(k, x1)+E(k, x2) and E(k, x1)E(k, x2), addition and multiplication of MA-based encryption forms, are decrypted to x1+x2 and x1x2 respectively regardless that E(k, x1) and E(k, x2) are order preserving or not. Therefore, by using single encryption key k, P can encrypt x1 and x2 so that relations E(k, x1)+E(k, x2) = E(k, x1+x2) and E(k, x1)E(k, x2) = E(k, x1x2) hold while making E(k, x1) order preserving and E(k, x2) not order preserving. Namely, P can restrict order preserving variables to the ones relating to conditional statements while maintaining additive and multiplicative features. In addition, P can define different values λ1, λ2, ---, λM as constant λ of order indicators. This means except ones that are included in same conditional statements no one other than P can know order indicators corresponding to individual constants λ1, λ2, ---, λM. As a result, server S cannot calculate {λja1, λja2, ---, λjaz} for any j even if it obtains numbers of order preserving encryption forms, i.e. it cannot know ratios among coefficients {a1, a2, ---, az}. Mechanisms to remove appearances of different dimensional order preserving encryption forms of same values, in other words to conceal correspondences between different dimensional order preserving encryption forms of same values, can be implemented in 2 ways as below.

The 1st way is to prepare multiple encryption forms for each relevant value. For example, to add or compare E(k, XY) and E(k, XZ), and E(k, XZ) and E(k, Y3), in addition to encryption forms E1(k, X, λ), E1(k, Y, λ) and E1(k, Z, λ) client P prepares E2(k, X, μ2), E1(k, Y, μ) and E1(k, Z, μ), where notation En(k, x, λn) represents an n-dimensional encryption form of x with order indicator value λnx. Then, server S calculates E2(k, XY, λ2) = E1(k, X, λ)E1(k, Y, λ) and E2(k, XZ, λ2) = E1(k, X, λ)E1(k, Z, λ) to add or compare E(k, XY) and E(k, XZ). On the other hand to add or compare E(k, XZ) and E(k, Y3), S calculates E3(k, XZ, μ3) = E2(k, X, μ2)E1(k, Z, μ) and E3(k, Y3, μ3) = E1(k, Y, μ)3. Namely, although S may know different encryption forms of same values {E1(k, X, λ), E2(k, X, μ2)}, {E1(k, Y, λ) E1(k, Y, μ)}, {E1(k, Z, λ), E1(k, Z, μ)} and {E2(k, XZ, λ2), E3(k, XZ, μ3)}, it cannot calculate X, Y, Z or XZ from them because order indicators of corresponding encryption forms are calculated based on different unknown constants λ and μ.

In the 2nd mechanism to add or compare different dimensional order preserving encryption forms En(k, X) and Er(k, Y), P prepares set {Ep(1)(k, W1), Ep(2)(k, W2), ---, Ep(Q)(k, WQ)}, encryption forms of secret numbers W1, W2, ---, WQ in advance, and instead of En(k, X) and Er(k, Y) computer programs calculate En(k, Xc) and Er(k, Yc). After that they calculate En(k, Xc)Ep(n1)(k, Wn1)Ep(2)(k, Wn2)---Ep(nV)(k, WnV) = Em(k, X) and Er(k, Yc)Ep(r1)(k, Wr1)Ep(r2)(k, Wr2)---Ep(tT)(k, WrT) = Em(k, Y), and finally adds or compares Em(k, X) and Em(k, Y). Here, programs must choose encryption forms {Ep(n1)(k, Wn1), ---, Ep(nV)(k, WnV)} and {Ep(r1)(k, Wr1), ---, Ep(rT)(k, WrT)} from set {Ep(1)(k, W1), ---, Ep(Q)(k, WQ)} so that relations XcWn1---WnV = X, YcWr1---WrT = Y, n+n1+ --- +nV = m and r+r1+ --- +rT = m hold of course. Then, P can remove appearances of different dimensional encryption forms of X and Y, i.e. encryption form pairs {En(k, X), Em(k, X)} and {Er(k, Y), Em(k, Y)}. Here, provided that E1(k, x) has value λx as its order indicator, S can obtain pairs of order indicators {λnXc, λmXcWn1Wn2---WnV} and {λrYc, λmYcWr1Wr2---WrT}, but S that does not know X, Xc, Wn1, ---, WnV, Y, Yc, Wr1,---WrT cannot calculate λ from them. But to avoid intense and sophisticated communications between P and S, values Xc and Yc and encryption forms {Ep(1)(k, W1), ---, Ep(Q)(k, WQ)} in the above must be generated and included in programs by P itself.

As above, client P can restrict variables to which order preserving encryption functions are applied to only ones that relate to conditional statements, and it can also protect encryption forms from plain text attacks even in environments where different dimensional order preserving encryption forms Er(k, X) and Em(k, Y) are added or compared.

5. Features of the Proposed Scheme

As discussed in previous sections, while exploiting secret key MA-based encryption functions, the proposed scheme successfully enables client P to delegate calculations of polynomials, maximums/minimums, etc. of values to server S while preserving secrets about the values. About the efficiency, although required computation volumes increase as numbers of elements in encryption forms increase, it is still practical when orders of polynomials are not too high. In detail, when x and y are encrypted to 1-dimensional arrays {x(1), x(2), ---, x(z)} and {y(1), y(2), ---, y(z)} for example, S must calculate x(i)+y(i) for each x(i) and y(i) in {x(1), x(2), ---, x(z)} and {y(1), y(2), ---, y(z)} to calculate x+y, and as a worse thing, numbers of elements in encryption forms increase as dimensions of arrays increase. But if orders of polynomials are not high, numbers of elements in encryption forms can be restricted, e.g. when each value is encrypted to 30-elements 1-dimensional array and orders of the polynomials do not exceed 4, the number of elements in each encryption form is less than or equal to (30)4 (< 1,000,000). Provided that T is the computation volume for calculating polynomials of plain values, this means the computation volume of the scheme does not exceed 106T which is comparable to volumes required for handling large but not extremely large arrays (e.g. 1,000 x 1,000 2-dimensional or 100 x 100 x 100 3-dimensional arrays) appear in typical numerical simulations.

About secureness of the scheme, although MA-based encryption functions are weak against plain text attacks, entities can preserve their secrets because the scheme does not disclose data values in their plain forms. Provided that client P can assign U different values to each coefficient ai, server S must examine U30 different possibilities to decrypt the above 1-dimensional encryption form {x(1), X(2), ---, x(30)} to a1x(1)+a2x(2)+ --- +azx(30) = x, and U is large enough because each ai is a real number.

When compared with schemes based on public key based encryption functions including most recent fully homomorphic encryption functions [7, 8], the proposed scheme is more practical as below. Firstly, the proposed scheme can handle real numbers that frequently appear in business and engineering applications easily totally in the same way as integers. Secondly, because MA-based encryption functions can have order preserving features, clients can communicate calculation algorithms to servers by usual computer programs instead of logic circuits. As a consequence, developments of calculation algorithms become easy even under complicated conditions. In addition, server S can execute computer programs more efficiently than simulating behaviors of complicated logic circuits.

Although not so efficient, the proposed scheme enables client P to delegate also calculations of general logical functions of its secret values to server S. Namely, S can calculate encryption forms of NOT, AND, OR of logical values from values encrypted by P as follows, and general logical functions can be constructed by combining NOT, AND, OR components. In the following u and v are real numbers, and they are regarded as true or false when their values are 1 or 0.

- NOT component Construction of NOT component is straight forward, i.e. when encryption form E(k, u) is given, the NOT component simply calculates E(k, 1)-E(k, u), i.e. E(k, 1)-E(k, u) is decrypted to (1–u) that corresponds to NOT of u. Where, client P informs server S of E(k, 1) in advance.

- AND component E(k, u) AND E(k,v) can be calculated simply as E(k, u)E(k, v). Namely, E(k, u)E(k, v) = E(k, uv) is decrypted to uv which becomes 1 only when both u and v are 1.

- OR component OR component is constructed by using AND and NOT components based on relation {u OR v} = NOT{(NOT u) AND (NOT v)}, i.e. E(k, u) AND E(k, v) is calculated as E(k, 1)-{E(k, 1)-E(k, u)}{E(k, 1)-E(k, v)}.

But it must be noted that AND component is implemented as a product of 2-logical values, and this means that encryption forms of logical functions may include high dimensional arrays. As a consequence, P and S must handle large number of elements, which decreases the efficiency of calculations. About plain text attacks, client P can successfully protect its encryption forms because encryption and plain form pair that P must disclose is only {E(k, 1), 1}.

6. Protecting Calculations from Malicious Entities

6.1. Protecting Clients

Server S in the previous section may behave dishonestly, i.e. S may return wrong calculation results to client P. P can protect itself from dishonest servers by exploiting 3 principles, i.e. data encryption, data redundancy and test data insertion.

The following mechanisms assume that client P provides server S with a series of values {X1, X2, ---, XN} and corresponding to these inputs S returns a series of calculation results {R1, R2, ---, RN} to P. But according to the data encryption principle, P encrypts the values to {E(k, X1), ---, E(k, XN)} by probabilistic MA-based encryption function E(k, x) and S calculates encryption forms {E(k, R1), ---, E(k, RN)} to be decrypted by P as discussed already. Then to protect P from dishonest servers, the data redundancy principle randomly inserts encryption forms {E(k, X*h1), ---, E(k, X*hQ)} that are decrypted to {Xh1, ---, XhQ} in input series {E(k, X1), ---, E(k, XN)}. As a result, to behave dishonestly server S, which does not know the correspondence between encryption forms E(k, Xhj) and E(k, X*hj) in the input series, must take risks of returning E(k, Rhj) and E(k, R*hj) that are decrypted to different values as calculation results corresponding to E(k, Xhj) and E(k, X*hj).

However, redundant encryption forms cannot protect P when S modifies programs, i.e. although modified programs may generate wrong calculation results, they produce results that are decrypted to a same value for each pair E(k, Xhj) and E(k, X*hj). To disable S to dishonestly modify the programs, the test data insertion principle randomly inserts encrypted test data E(k, T1), E(k, T2), ---, E(k, TQ) at secret positions in input series {E(k, X1), ---, E(k, XN)}. Namely, P provides S with series {E(k, X1), ---, E(k, Xn1-1), E(k, T1), E(k, Xn1+1), ---, E(k, Xn2-1), E(k, T2), E(k, Xn2+1), ---, E(k, XN)}. Where, P knows correct calculation result tj of each test value Tj. Then if S modifies the programs, they produce a result that is different from tj for test encryption form E(k, Tj). Of course S tries to use original programs for E(k, Tj), but it cannot identify E(k, Tj) in the input series because E(k, x) is probabilistic.

6.2. Protecting Servers

As server S disturbed client P’s business by having returned wrong calculation results, P may disturb S’s business by claiming that S is dishonest despite S is honest. Servers can protect themselves from dishonest clients by exploiting anonymous signatures.

To protect it from P’s dishonesty, S receives program AP and encrypted data item value E(k, XP) from P with anonymous signatures {S(d1║d2, (TPR+1KwCwR)Wmod B), h(AP)Rmod B} and {S(d1║d2, (TPR+1KwCwR)Wmod B), h(E(k, XP)Rmod B)}, and accepts them when the signatures are consistent. Where, B is a publicly known appropriate sufficiently large integer, R, W and w are P’s secret integers, TP is an integer assigned to P, and Kw and Cw are integers P calculates as Kw = kwmod B and Cw = cwmod B based on publicly known constant integers k and c and secret integer w. Under these settings, provided that d1 and d2 are different signing keys of an authority (this authority does not need to be S), anonymous credential S(d1║d2, TPR+1KwCwR) represents signature pair {S(d1, TPR+1KwCwR), S(d2, TPR+1KwCwR)} (to simplify notations mod B is omitted in the following). Namely, only P that knows integers R can prove the validity and the ownership of its showing credential S(d1║d2, TPR+1KwCwR)W by successfully decomposing (TPR+1KwCwR)W into {TPW, TPRW, KwW, CwRW}. On the other hand, no one except P can identify P from S(d1║d2, TPR+1KwCwR)W, because P never discloses R and it changes form S(d1║d2, TPR+1KwCwR) that had given from the authority to S(d1║d2, TPR+1KwCwR)W by its secret integer W when it shows the credential [11].

About the anonymous signature, h(x) is a hash function, i.e. for a given signature {S(d1║d2, TPR+1KwCwR)W, h(x)R} no one can generate y so that h(y) becomes equal to h(x). Then together with the fact that only P who knows R can calculate h(x)R from h(x), S can prove that program AP and encrypted data value E(k, XP) were certainly provided by a legitimate entity (i.e. P). But different from usual digital signatures, validities and ownerships of the above anonymous signatures must be proved by their owners themselves. Here, although P never discloses R to others, anonymous credential S(d1║d2, TPR+1KwCwR)W forces P to honestly calculate h(AP)R and h(E(k, XP))R from h(XP) and h(E(k, XP)) [11].

In detail, at a time when P claims AP and E(k, XP) are not the ones that it had provided, S calculates hash values h(AP) and h(E(k, XP)) from AP and E(k, XP). Then, because no one can modify AP or E(k, XP) while maintaining their hash values as h(AP) or h(E(k, XP)), and only P can calculate h(AP)R and h(E(k, XP))R from h(AP) and h(E(k, XP)), S can convince anyone that it certainly had received AP and E(k, XP) from an entity that is claiming S is dishonest, when P calculates h(AP)R and h(E(k, XP))R from h(AP), h(E(k, XP)) and credential S(d1║d2, TPR+1KwCwR)W that includes P’s secret R. Of course P may provide AP and E(k, XP) as {S(d1║d2, (TQU+1KvCvU)V), h(AP)U} and {S(d1║d2, (TPU+1KvCvU)V), h(E(k, XP)U)} while stealing or borrowing credential S(d1║d2, TPU+1KvCvU) from others to claim AP and E(k, XP) are not correct, but S does not accept them if the credential is a stolen one because P does not know U. In a case where S(d1║d2, TPU+1KvCvU) is a borrowed one, P or an entity that had lent the credential to P must calculate h(AP)U and h(E(k, XP)U honestly. Also if P is dishonest, S can identify it even if P is anonymous. On the other hand, P can conceal its secret R from S if it is honest, in other words, honest P can preserve its anonymity.

7. Conclusion

While exploiting MA-based encryption functions, a scheme that enables entities to delegate calculations of simple functions including polynomials and maximums/ minimums of values to others without disclosing secrets about the values is proposed. Distinctive features of the scheme are it can handle real numbers in the same way as integers and it enables entities to define complicated calculation algorithms as computer programs. About the efficiency, the scheme is practical enough when orders of polynomials are not too high.

References

[1]  Chaum, D., “Untraceable electronic mail, return address and digital pseudonyms,” Communications of the ACM, 24 (2). 84-88. 1981.
In article      CrossRef
 
[2]  Yao, A. C., How to generate and exchange secrets,” Proc. of the 27th IEEE Symposium on Foundations of Computer Science, 162-167. 1986.
In article      
 
[3]  Goldreich, O., Micali, M. and Wigderson, A., “How to play any mental game,” Proc. of 19th ACM Symposium on Theory of Computing, 218-229. 1987.
In article      
 
[4]  Naor, M., Pinkas, B. and Sumner, R., “Privacy preserving auctions and mechanism design,” 1st ACM Conference on Electronic Commerse, 129-139. 1999.
In article      
 
[5]  Ogiso, T., Sakabe, Y., Soshi, M. and Miyaji, A., “Software obfuscation on a theoretical basis and its implementation,” IEICE Trans. Fundamentals, E86-A, (1), 176-186. 2003.
In article      
 
[6]  Golle, P. and Jakobsson, M., “Reusable anonymous return channels,” Proc. of the 2003 ACM Workshop on Privacy in the Electronic Society, 94-100. 2003.
In article      
 
[7]  Gentry, C. “Fully homomorphic encryption using ideal lattices,” Proc. of Symposium on theory of computing –STOC 2009, 169-178. 2009.
In article      
 
[8]  Chung, K., Kalai, Y. and Vadhan, S., “Improved Delegation of Computation Using Fully Homomorphic Encryption,” CRYPT 2010, LNCS 6223, 483-501. 2010.
In article      
 
[9]  Haddad, H, Tamura, S., Taniguchi, S. and Yanase, T., “Development of anonymous networks based on symmetric key encryptions,” Journal of Networks, 6 (11), 1533-1542. 2011.
In article      CrossRef
 
[10]  Tamura, S., Anonymous Security Systems and Applications: Requirements and Solutions, Information Science Reference, 2012.
In article      CrossRef
 
[11]  Tamura, S. and Taniguchi, S., “Enhanced Anonymous Tag Based Credentials,” Information Security and Computer Fraud, 2 (1), 10-20, 2014.
In article      
 
comments powered by Disqus
  • CiteULikeCiteULike
  • MendeleyMendeley
  • StumbleUponStumbleUpon
  • Add to DeliciousDelicious
  • FacebookFacebook
  • TwitterTwitter
  • LinkedInLinkedIn