Encryption for low-end devices through computation offloading

Abstract

The application relates to a method for computing a probabilistic encryption scheme for encrypting a data item in an electronic device including: computing a plurality of random bit strings in a computation cluster; sending the computed plurality of random strings to the electronic device; generating a random string (r.sub.E) for using in the encryption scheme in the electronic device using a subset of the plurality of the random strings computed in the computation cluster and encrypting the data item using the random string computed in the electronic device. The present application also relates to a corresponding system and corresponding computer program product including one or more computer readable media having computer executable instructions for performing the steps of the method.

Claims

1. A method for computing a probabilistic encryption scheme for encrypting a data item in an electronic device comprising the steps of: a) computing a plurality of random bit strings in a computation cluster; b) sending the computed plurality of random strings to the electronic device; c) generating a random string rE for using in the encryption scheme in the electronic device using a subset of the plurality of the random strings computed in the computation cluster; and d) encrypting the data item using the random string computed in the electronic device, wherein generating the random string rE comprises recombining of the subset of the plurality of the random strings computed in the computation cluster, preferably using a recombination function c, wherein the plurality of random bit strings is processed with a randomness preparation function fin the computation cluster before sending to the electronic device, and wherein the generation of the random string for using in the encryption scheme in the electronic device is performed using the following function: rE=cf(r1),.f.rm),r), with rE being the random string for using in the encryption scheme, c being the recombination function, ri . . . rm being the plurality of random strings computed in the computation cluster and r being a random bit string generated in the electronic device, preferably a random bit string of length q-log 2(m) with m being the number of random strings sent from the computation cluster and q being a predefined parameter.

2. The method according to claim 1, further comprising the step of storing the plurality of random strings in a storage of the computation cluster.

3. The method according to claim 1, wherein the electronic device requests the plurality of random bit strings from the computation cluster.

4. The method according to claim 1, wherein the encryption scheme is a homomorphic encryption scheme, preferably an additively homomorphic encryption scheme, preferably an additively homomorphic encryption scheme.

5. The method according to claim 1, wherein the encryption scheme is an encryption scheme defined as follows: with d being the data item, the pair (g,n) being the key, R being the random string for using in the encryption scheme, g is a generator and n is the size of the plain text space.

6. A system for computing a probabilistic encryption scheme for encrypting a data item in an electronic device comprising: a computation cluster configured to compute a plurality of random bit strings and comprising a sending unit configured to send the computed plurality of random strings to the electronic device; the electronic device being configured to generate a random string for using in the encryption scheme using a subset of the plurality of the random strings computed in the computation cluster and the electronic device being further configured to encrypt the data item using the random string that it has computed, wherein the computation cluster is further configured to process the plurality of random bit strings with a function f before sending the plurality of random bit strings to the electronic device, and wherein the electronic device is further configured to generate the random string for using in the encryption scheme using the following function: with rE being the random string for using in the encryption scheme, ri . . . rm being the plurality of random strings computed in the computation cluster and r being a random bit string generated in the electronic device, preferably a random bit string of length q-log 2(m) with m being the number of random strings sent from the computation cluster and q being a predefined parameter.

7. The system according to claim 6, wherein the computation cluster further comprises a storage configured to store the plurality of random strings.

8. A computer readable media for computing a probabilistic encryption scheme for encrypting a data item in an electronic device comprising: computer executable instructions effective to: compute a plurality of random bit strings in a computation cluster; send the computed plurality of random strings to the electronic device; generate a random string for using in the encryption scheme in the electronic device using a subset of the plurality of the random strings computed in the computation cluster; and encrypt the data item using the random string computed in the electronic device; wherein the computer executable instructions are effective to: process the plurality of random bit strings with a function f before sending the plurality of random bit strings to the electronic device, and generate the random string for using in the encryption scheme using the following function: rE=c(f(r1), . . . , f(rmr), with rE being the random string for using in the encryption scheme, ri . . . rm being the plurality of random strings computed in the computation cluster and r being a random bit string generated in the electronic device, preferably a random bit string of length q-log 2(m) with m being the number of random strings sent from the computation cluster and q being a predefined parameter.

9. The method according to claim 1, wherein the plurality of random bit strings is processed with a randomness preparation function fin the computation cluster before sending to the electronic device.

10. The method according to claim 1, further comprising the step of storing the plurality of random strings in a storage of the computation cluster.

11. The method according to claim 1, further comprising the step of storing the plurality of random strings in a storage of the computation cluster.

12. The method according to claim 2, wherein the electronic device requests the plurality of random bit strings from the computation cluster.

13. The method according to claim 1, wherein the electronic device requests the plurality of random bit strings from the computation cluster.

14. The system according to claim 6, wherein the computation cluster further comprises a storage configured to store the plurality of random strings.

15. The system according to claim 6, wherein the computation cluster further comprises a storage configured to store the plurality of random strings.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The subject matter of the invention will be explained in more detail in the following text with reference to preferred exemplary embodiments which are illustrated in the attached drawings, in which:

(2) FIG. 1 schematically shows a system for computing an encryption scheme for encrypting a data item.

(3) The reference symbols used in the drawings, and their primary meanings, are listed in summary form in the list of designations. In principle, identical parts are provided with the same reference symbols in the figures.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

(4) FIG. 1 schematically shows a system for computing an encryption scheme for encrypting a data item.

(5) The system comprises an electronic device 100 and a computation cluster 200, hereinafter referred to as the cloud 200.

(6) The cloud 200 generates a plurality of random bit strings using a randomness preparation function f and stores them in a pool of the cloud 200. In this preferred embodiment, the plurality of random bit strings is generated by generating a plurality of random bits and applying the randomness preparation function f to the before generated random bits. However, it is understood by the skilled person that an appropriate randomness preparation function f can also generate a plurality of random bit strings ab initio, i.e. without generating a plurality of random bit strings before in a preceding step.

(7) As soon as an electronic device 100 requests a plurality of random bit strings, the cloud 200 sends the requested plurality of random bit strings to the electronic device 100. The electronic device 100 holds a data item d that it wants to encrypt.

(8) The device 100 receives a set of random bit strings f(r.sub.1), . . . f(r.sub.m). The device 100 then computes a random bit string r.sub.E that is used for encryption. According to this embodiment, the random bit string r.sub.E can be defined as follows: r.sub.E=c(f(r.sub.1), . . . , f(r.sub.m),r), where r is a random bit string of length q⋅log.sub.2(m), for some parameter q, that the device 100 generated itself.

(9) Next, the device 100 encrypts the data item d, using the random bit string r.sub.E, using the encryption key k and sends out and/or or stores the encrypted result E(d,k,r.sub.E).

(10) Thus, the device 100 still needs to produce some but significantly fewer random bits itself. More importantly, the device 100 still must perform some computations but the computations are not as expensive as encrypting the data item d on its own.

(11) In an exemplary embodiment, a homomorphic encryption scheme is used, i.e., an encryption scheme that offers some computational capabilities in the cipher text space without access to decryption keys.

(12) As an example, the Paillier encryption scheme [1] is considered, which encrypts a data item d as follows:
E(d,k,r)=g.sup.d⋅r.sup.n(mod n.sup.2),
where g is a so-called generator and n is the size of the plain text space.

(13) If g:=1+n, it can be shown that the encryption function becomes E(d,k,r)=(1+d⋅n)⋅r.sup.n (mod n.sup.2).

(14) The function f is therefore f(r)=r.sup.n (mod n.sup.2), i.e., an expensive exponentiation because both r and n are large numbers, and a reduction modulo n.sup.2.

(15) In fact, this exponentiation is the dominant factor in the encryption time. The function c(f(r.sub.1), . . . , f(r.sub.m),r)=c(r.sub.1.sup.n (mod n.sup.2), . . . , r.sub.m.sup.n (mod n.sup.2), r) is defined as follows: The bit string r is split into q pieces of length log.sub.2(m), which corresponds to q indices into the list of m random number strings f(r.sub.1), . . . , f(r.sub.m). The corresponding q bit strings are multiplied, i.e., f(r.sub.i1)⋅ . . . ⋅*r.sub.i1⋅ . . . ⋅r.sub.iq).sup.n. According to this exemplary embodiment of the present invention, the exponentiation in the encryption process (r.sup.n) is therefore transformed into q multiplications, which is less time-consuming and requires less computational power.

(16) There are m.sup.q ways to select q indices out of m, in particular with potential repetitions. For reasonable parameters, which reduce the computational effort at the device considerably, it is infeasible for the compute cluster to determine the random component that is actually used in the encryption.

(17) For the Paillier encryption scheme [1], a reasonable security can be achieved when choosing n, i.e. the product of two random prime numbers as a 1024-bit number.

(18) If q is set to 16 and m is set to 32, q⋅log.sub.2(m)=80 random bits are needed at the electronic device 100.

(19) This is roughly 8% of the 1024 random bits that would typically be used for r. Moreover, there are m.sup.q=2.sup.80 ways to choose q indices, which corresponds to 80-bit security. Thus, it is not feasible for the computation cluster 200 to determine the used random component.

(20) As far as the computation time is concerned, the exponentiation r.sup.n of 1024-bit numbers is replaced with the multiplication of q=16 1024-bit numbers.

(21) Experiments show that all multiplications together cost roughly 3% of the cost of the exponentiation. Thus, as the remaining steps in the encryption are not costly, the time to encrypt is reduced roughly by a factor of 30.

(22) The numbers even improve when increasing the security level: When n is a 2048-bit number, and q is set to 16 and m is set to 32, q⋅log.sub.2(m)=80 random bits are needed at the electronic device, which is roughly 4% of the number of random bits. The exponentiation r.sup.n of 2048-bit numbers even takes more than 100 times longer compared to the 8 multiplication of 2048-bit numbers.

(23) In addition, the device 100 must solely receive 32.1024 bit=4 KB to encrypt a single message, which takes 0.3125 ms to send over a 100 Mbit/s link. Therefore, up to 3200 data items can be encrypted per second.

(24) If 2048-bit numbers are used, 1600 encryptions are possible per second. Moreover, the present invention using this back-of-the-envelope calculation according to this embodiment ignores overhead due to the communication protocols, which reduces the feasible number of encryptions per second slightly.

(25) These numbers are summarized in the following table. The compute time and number of random bits are relative to the compute time and the number of random bits that would be necessary without our mechanism. Encryptions per second refer to communication over a 100 Mbit/s link between the device(s) and the compute cluster.

(26) TABLE-US-00001 Compute Random Encryptions Number size: q: m: time: bits: per second: 1024 (good security) 16 32 ≈3% ≈8% ≈3200 2048 (strong security) 16 32 ≈1% ≈4% ≈1600

(27) Thus, the present invention significantly reduces the computational overhead for encryption on the electronic device, making the encryption on the device 100 for many applications feasible, without sacrificing security to achieve this goal.

(28) While the invention has been described in detail in the drawings and foregoing description, such description is to be considered illustrative or exemplary and not restrictive. Variations to the disclosed embodiments can be understood and effected by those skilled in the art and practising the claimed invention, from a study of the drawings, the disclosure, and the appended claims. In the claims, the word “comprising” does not exclude other elements or steps, and the indefinite article “a” or “an” does not exclude a plurality. The mere fact that certain elements or steps are recited in distinct claims does not indicate that a combination of these elements or steps cannot be used to advantage, specifically, in addition to the actual claim dependency, any further meaningful claim combination shall be considered disclosed.

LIST OF DESIGNATIONS

(29) 100—Electronic device 200—Computation Cluster

REFERENCES

(30) [1]—Pascal Paillier, Public-Key Cryptosystems Based on Composite Degree Residuosity Classes, J. Stern (Ed.): EUROCRYPT'99, LNCS 1592, pp. 223-238, 1999. [2]—ElGamal, Taher. “A public key cryptosystem and a signature scheme based on discrete logarithms.” Advances in cryptology. Springer Berlin Heidelberg, 1984. [3]—Benaloh, Josh. “Dense probabilistic encryption.” Proceedings of the workshop on selected areas of cryptography, 1994. [4]—Damgard, Ivan and Jurik Mads. “A generalisation, a simplification and some applications of Paillier's probabilistic public-key system.” In Proc. 4th International Workshop on Practice and Theory in Public Key Cryptosystems, 2001. [5]—Okamoto, Tatsuaki; Uchiyama, Shigenori. “A new public-key cryptosystem as secure as factoring”. Advances in Cryptology—EUROCRYPT'98, 1998. [6]—Naccache, David and Stern, Jacques. “A new public key cryptosystem based on higher residues”. In Proc. 5th ACM Conference on Computer and Communications Security (CCS), pp. 59-66, 1998. [7]—Brakerski, Zvika, Craig Gentry, and Vinod Vaikuntanathan. “(Leveled) fully homomorphic encryption without bootstrapping.” In Proc. 3rd ACM Innovations in Theoretical Computer Science Conference, 2012. [8]—Gentry, Craig, Amit Sahai, and Brent Waters. “Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based.” Advances in Cryptology—CRYPTO 2013, 75-92, 2013. [9]—U.S. Pat. No. 6,081,597 A [10]—López-Alt, Adriana, Eran Tromer, and Vinod Vaikuntanathan. “On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption.” In Proc. 44th Annual ACM Symposium on Theory of Computing (STOC), 2012.