Patent Description:
Cloud computing, e.g. in the computation cluster, provides access to a shared pool of configurable and inexpensive computing and storage resources. Cloud computing providers offer various capabilities to store and process data. In an industrial context, cloud computing can provide the monitoring and measurement of data produced by low-end devices available for later retrieval and for resource-intensive processing.

However, cloud computing requires trust both in the cloud provider and in the confidentiality of the connection transmitting the data into the cloud. As a consequence, many users are reluctant to entrust the cloud with their data, despite the potential benefits.

In order to solve the trust issue, customers can encrypt their data before sending it to the cloud. If the data should also be processed in the cloud, then commonly used encryptions schemes, e.g. AES, DES, or blowfish, require the data to be decrypted before it can be processed.

Thus, generally, either the user stores the encryption keys in the cloud where the cloud provider could illicitly use the keys to decrypt the data. Alternatively, the user downloads the encrypted data from the cloud, decrypts it and processes it locally. However, in this case the computational resources of the cloud are not utilized. If homomorphic encryption schemes are used, then the data can be processed in the cloud without providing decryption keys to the cloud provider. In other words, it is possible to compute key performance indices and carry out computations for trend analysis and fleet management efficiently even if the cloud provider stores data in encrypted form.

However, low-end devices producing valuable data to be sent to cloud providers are equipped with limited computing resources. In particular, they may not have the computational power for the encryption. Apart from the encryption process itself, the creation of randomness for the encryption is also computationally expensive. It is thus an objective to use encryption to protect data coming from many low-end devices.

The journal contribution of <NPL> relates to the problem of using untrusted and potentially malicious cryptographic helpers and aims at providing a formal security definition for securely outsourcing computations from a computationally limited device to an untrusted helper.

The journal contribution of <NPL>, relates to protocols aimed at speeding up fixed-base variable-exponent exponentiation and variable-base fixed-exponent exponentiation using an untrusted computational resource.

The journal contribution of <NPL>. Birkhäuser, Basel aims at establishing the security of some discrete logarithm based signature schemes making use of a certain generator.

These and other objectives are achieved by a method, a system and a computer program product according to the independent claims. Preferred embodiments are evident from the dependent patent claims.

The present invention refers to a mechanism that allows resource-constrained computational devices to outsource cryptographic operations to a cloud.

The present invention targets probabilistic encryption schemes, which use random bits in the encryption process.

The invention enables strong protection of data that is produced and sent out by low-end devices. Examples for such low-end devices are protection devices, flow meters, merging units, e.g. merging sensor, or the like. To this end, the device according to the present invention offloads the task of computing randomness and computationally intensive parts of the encryption process to more powerful machines running in a computation cluster.

Normally, the computational cost of using encryption at the device level is often prohibitively high. However, the present invention allows a cost effective encryption at the device level, which is an enabler for remote data storage and processing of confidential customer data.

The first key property of the invention is that the computational overhead due to encryption is reduced significantly, potentially reducing it by <NUM>-<NUM>%, and the amount of randomness that must be generated by the devices reduces substantially as well, by <NUM>% or more.

The second key property of the invention is that the computation cluster only must be trusted to carry out the computation correctly and to generate randomness of high quality. The computation cluster cannot decrypt the data that is subsequently encrypted by the devices. Therefore, there is no need to trust the computation cluster to keep any data confidential, including the encryption material for the devices.

The present invention refers to a method that leverages the large computational power of a computation cluster to lower the burden on low-end devices. To this end, it basically uses a combination of two steps: the pre-computation of encryption parts in the cloud, i.e. a computation cluster, and re-combination of these parts in the electric device which is not capable or barely capable of computing the encryption parts.

Generally, in probabilistic encryption schemes, some randomness is used to encrypt data, i.e., encryption is a function E: (D x K x R) -> C that takes the data to be encrypted D, the key K, and random bits R as input and produces the cipher text C.

For some functions, another function f: R->R' is applied to the pure random bits before mixing them with the key and the data to produce the cipher text. In the present invention, the generation of the random bits and the computation of the function f are offloaded to the computation cluster. In particular, these operations are not just offloaded but pre-computed before they are needed for encryption: Preferably, the computation cluster computes and stores many strings of pre-computed bits in a pool/storage.

In theory, if a device requests such a random bit string, the computation cluster could retrieve one single string and send it to the device. The string would then be deleted at the computation cluster, i.e., the same bits would never reused. This procedure would ensure that random bits can be retrieved from the computation cluster without introducing a large delay.

However, the problem with sending only one single string is that the computation cluster knows all random bits, which can be used to try to break the encryption and to jeopardize the encryption scheme. The re-combination according to the present invention of the present invention solves this problem as follows.

Instead of computing a single string of random bits, preferably processed by f, the computation cluster computes many such strings, applies the function f to each string, and returns them to the device.

The electronic device uses another function c to combine a subset of the received bit strings into the bit string that it actually uses for encryption. Therefore, unless the computation cluster guesses the random bits that the device has used as input for the function c, which is almost impossible, it is computationally infeasible for the computation cluster to deduce the random bit string that is used in the encryption.

The advantage of this scheme is that the corresponding combination function c, carried out in the electric device, is computationally much cheaper than function f, carried out in the computational cluster, both in terms of the computational complexity as well as the number of random bits that are used.

The invention relates to a method for computing a probabilistic encryption scheme for encrypting a data item in an electronic device. The invention comprises the steps of:.

In other words, encrypting the data item is performed by using the random string computed in the electronic device and an encryption key k.

Preferably, the electric device has limited computational resources and/or is preferably not capable of computing the plurality of random bit strings.

Preferably, 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.

Preferably, the plurality of random bit strings is processed with a randomness preparation function f in the computation cluster before sending to the electronic device.

The generation of the random string for using in the encryption scheme in the electronic device is performed using the following function: <MAT> with rE being the random string for using in the encryption scheme, c being the recombination function, r<NUM>. 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<NUM>(m) with m being the number of random strings sent from the computation cluster and q being a predefined parameter. In other words, the function f is based on modular exponentiation and is defined as follows:.

Preferably, the method further comprises the step of storing the plurality of random strings in a storage of the computation cluster.

Preferably, the electronic device requests the plurality of random bit strings from the computation cluster.

The encryption scheme an additively homomorphic encryption scheme defined as follows: <MAT> 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.

The invention also relates to a computer program product comprising one or more computer readable media having computer executable instructions for performing the steps of any of the aforementioned methods.

The invention also relates to a system for computing a probabilistic encryption scheme for encrypting a data item in an electronic device according to claim <NUM>.

Preferably, the computation cluster further comprises a storage configured to store the plurality of random strings.

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:
<FIG> schematically shows a system for computing an encryption scheme for encrypting a data item.

The reference symbols used in the drawings, and their primary meanings, are listed in summary form in the list of designations.

<FIG> schematically shows a system for computing an encryption scheme for encrypting a data item.

The system comprises an electronic device <NUM> and a computation cluster <NUM>, hereinafter referred to as the cloud <NUM>.

The cloud <NUM> generates a plurality of random bit strings using a randomness preparation function f and stores them in a pool of the cloud <NUM>. 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.

As soon as an electronic device <NUM> requests a plurality of random bit strings, the cloud <NUM> sends the requested plurality of random bit strings to the electronic device <NUM>. The electronic device <NUM> holds a data item d that it wants to encrypt.

The device <NUM> receives a set of random bit strings f(r<NUM>),. The device <NUM> then computes a random bit string rE that is used for encryption. According to this embodiment, the random bit string rE can be defined as follows:
rE = c(f(r<NUM>),. ,f(rm),r), where r is a random bit string of length q•log<NUM>(m), for some parameter q, that the device <NUM> generated itself.

Next, the device <NUM> encrypts the data item d, using the random bit string rE, using the encryption key k and sends out and/or or stores the encrypted result E(d,k,rE).

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

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.

According to the invention, the Paillier encryption scheme [<NUM>] is considered, which encrypts a data item d as follows: <MAT> where g is a so-called generator and n is the size of the plain text space.

If g := <NUM> + n, it can be shown that the encryption function becomes E(d,k,r) = (<NUM>+d•n) • rn (mod n<NUM>).

The function f is therefore f(r) = rn (mod n<NUM>), i.e., an expensive exponentiation because both r and n are large numbers, and a reduction modulo n<NUM>.

In fact, this exponentiation is the dominant factor in the encryption time. The function c(f(rq),. ,f(rm),r) = c(r<NUM>n (mod n<NUM>),. ,rmn (mod n<NUM>), r) is defined as follows: The bit string r is split into q pieces of length log<NUM>(m), which corresponds to q indices into the list of m random number strings f(r<NUM>),. The corresponding q bit strings are multiplied, i.e., f(ri1) •. •f(riq) = (ri1•. According to this exemplary embodiment of the present invention, the exponentiation in the encryption process (rn) is therefore transformed into q multiplications, which is less time-consuming and requires less computational power.

There are mq 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.

For the Paillier encryption scheme [<NUM>], a reasonable security can be achieved when choosing n, i.e. the product of two random prime numbers as a <NUM>-bit number.

If q is set to <NUM> and m is set to <NUM>, q•log<NUM>(m) = <NUM> random bits are needed at the electronic device <NUM>.

This is roughly <NUM>% of the <NUM> random bits that would typically be used for r. Moreover, there are mq = <NUM><NUM> ways to choose q indices, which corresponds to <NUM>-bit security. Thus, it is not feasible for the computation cluster <NUM> to determine the used random component.

As far as the computation time is concerned, the exponentiation rn of <NUM>-bit numbers is replaced with the multiplication of q=<NUM><NUM>-bit numbers.

Experiments show that all multiplications together cost roughly <NUM>% 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 <NUM>.

The numbers even improve when increasing the security level: When n is a <NUM>-bit number, and q is set to <NUM> and m is set to <NUM>, q•log<NUM>(m) = <NUM> random bits are needed at the electronic device, which is roughly <NUM>% of the number of random bits. The exponentiation rn of <NUM>-bit numbers even takes more than <NUM> times longer compared to the <NUM> multiplication of <NUM>-bit numbers.

In addition, the device <NUM> must solely receive <NUM>•<NUM> bit= 4KB to encrypt a single message, which takes <NUM> to send over a <NUM> Mbit/s link. Therefore, up to <NUM> data items can be encrypted per second.

If <NUM>-bit numbers are used, <NUM> 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.

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 100Mbit/s link between the device(s) and the compute cluster.

Thus, the present invention significantly reduces the computational overhead for encryption on the electronic device, making the encryption on the device <NUM> for many applications feasible, without sacrificing security to achieve this goal.

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. 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.

Claim 1:
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 i r<NUM>, ..., rm, m being the number of random bit strings, in a computation cluster; and processing the plurality of random bit strings with a randomness preparation function f in the computation cluster to obtain a plurality of processed random bit strings f(r<NUM>), ..., f(rm);
b) sending, by the computation cluster, the processed plurality of random bit strings (f(r<NUM>), ..., f(rm)) to the electronic device;
c) generating, by the electronic device, a random string rE for using in the probabilistic encryption scheme in the electronic device using a subset of the plurality of the random bit strings computed in the computation cluster; and
d) encrypting the data item using the random string rE generated in the electronic device; and wherein generating the random string rE consists in recombining of the subset of the plurality of processed random bit strings using a recombination function c; and wherein the generation of the random string rE for using in the encryption scheme in the electronic device is performed using the following function: <MAT> and r being a random bit string generated in the electronic device of length q•log<NUM>(m) with q being a predefined parameter;
and wherein the probabilistic encryption scheme is defined as follows: <MAT> 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;
and wherein the function f is based on modular exponentiation and defined as f(r)=rn (mod n<NUM>); and c(f(r<NUM>),...,f(rm),r) is defined so as to split the random bit string r into q pieces of length log<NUM>(m) which corresponds to q indices into the list of the m processed random bit strings f(r<NUM>),...,f(rm) and to multiply the corresponding q processed random bit strings, thereby obtaining the random string rE.