Method for re-keying an encrypted data file

0001The present invention relates to a method for re-keying an encrypted data file.

0002The present invention further relates to a system for re-keying an encrypted data file.

0003The present invention even further relates to an assist server, 'AS', for assisting re-keying encrypted and deduplicated of a data file. The present invention even further relates to a non-transitory computer readable medium storing a program causing a computer to execute a method for re-keying an encrypted data file.

0004Cloud storage is receiving increasing attention and importance recently, since the cloud offers users a cost-effective, convenient, and highly available storage service. Conventional clouds rely on cost effective techniques such as data compression and data deduplication in order to save storage costs. While data deduplication is beneficial as it considerably reduces the cost of storage, cloud users do not really benefit from this technique, since deduplication is typically performed by the cloud itself.

0005Conventional methods and systems, e.g. disclosed in the non patent literature of Mihir Bellare and Sriram Keelveedhi, Thomas Ristenpart, DupLESS: Server-Aided Encryption for Deduplicated Storage, Proceedings of Usenix Security 2013 or in the non-patent literature of Frederik Armknecht, Jens-Matthias Bohli, Ghassan Karame, Franck Youssef, Transparent Data Deduplication in the Cloud, In Proceedings of the ACM Conference on Computer and Communications Security (ACM CCS), (to appear) 2015 focus on techniques for performing deduplication over encrypted data or focus on the constructing proof of ownership to attest that a user indeed possesses a file which is deduplicated.

0006In detail conventional methods and systems for performing deduplication are mainly based on convergent encryption. Here, chunks are encrypted deterministically, using the hash of the chunk as an encryption key. It is known that convergent encryption is vulnerable to brute-force attacks, and can only achieve semantic security for unpredictable messages. If the adversary can guess the content of a chunk, then he can simply decrypt the chunk (since the encryption key is the chunk hash). This also offers an advantage for the adversary: i.e., the adversary is able to say that some ciphertext is or is not an encryption of corresponding plaintext.

0007To address this vulnerability, the conventional methods and systems disclosed in the non-patent literature of Mihir Bellare and Sriram Keelveedhi, Thomas Ristenpart, DupLESS: Server-Aided Encryption for Deduplicated Storage, Proceedings of Usenix Security 2013 and of Frederik Armknecht, Jens-Matthias Bohli, Ghassan Karame, Franck Youssef, Transparent Data Deduplication in the Cloud, In Proceedings of the ACM Conference on Computer and Communications Security (ACM CCS), (to appear) 2015 use server-aided message locked encryption (MLE). These conventional methods and systems rely on a dedicated key server to generate key for a message based on not only the message's content, but also based on the global key server secret that is independent of the message content and should be extremely hard to guess. This makes the resulting encryption semantically secure with respect to the cloud storage provider, who is storing the data. From the perspective of a proxy which can be queried by clients to assist them in deriving in an oblivious way a strong encryption keys for content to be deduplicated these schemes offer semantic security for unpredictable messages and convergent encryption security for predictable ones.

0008Both these schemes rely on an oblivious pseudo-random function (OPRF) to blind the hash sent by users; this prevents the key server to learn any information about the hash of the file to be stored by users.

0009However, conventional methods and systems do not do not address re-keying, in particular do not allow for efficient re-keying of already encrypted and deduplicated data Re-keying enables a minimization of information leakage, in case the key is leaked. Further re-keying enables to revoke access to the company network of malicious employees for instance, or employees who quit a company, thus security is increased. Re-keying by re-encrypting in case of a large data volume in such a case would simply be impractical due to time needed for decryption and reencryption.

0010Embodiments of the present invention therefore address the problem of providing re-keying, which can be easily implemented while enabling efficient re-keying of encrypted data.

0011In an embodiment the present invention provides a method for re-keying an encrypted data file according to claim 1.

0012In a further embodiment the present invention provides a system for re-keying an encrypted data file according to claim 3.

0013In a further embodiment the present invention provides an assist server, 'AS', for assisting re-keying encrypted and deduplicated of a data file according to claim 4.

0014In a further embodiment the present invention provides a non-transitory computer readable medium storing a program which, when executed by a computer, causes the computer to execute, as the assist server or as the client, a method for re-keying an encrypted data file according to claim 5.

0015At least one of the embodiments has at least one of the following advantages: By only updating partially the global secret for the data to be re-keyed and locally reencrypting the data that should be re-keyed this ensures an easy implementation since no change of protocol-layer functionality on a key server is necessary. Further efficiency is enhanced since only the data that should be re-keyed is affected without incurring any need of awareness from the clients.

0016The term "computing device", or "computing entity", "client device", "client", "operator 's device", "access device", "assist server", "storage entity", etc. refer in particular in the claims, preferably in the description each to a device adapted to perform computing like a personal computer, a tablet, a mobile phone, a server, or the like and comprises one or more processors having one or more cores and may be connectable to a memory for storing an application which is adapted to perform corresponding steps of one or more of the embodiments of the present invention. Any application may be software based and/or hardware based installed in the memory on which the processor(s) can work on. The computing devices, computing entities, etc. may be adapted in such a way that the corresponding steps to be computed are performed in an optimized way. For instance different steps may be performed in parallel with a single processor on different of its cores. Said devices, entities, etc. may each have one or more interfaces to communicate with the environment, e.g. other devices, humans, etc.

0017The term "computer readable medium" may refer to any kind of medium, which can be used together with a computation device or computer and on which information can be stored. Said information may be any kind of data which can be read into a memory of a computer. For example said information may include program code for executing with said computer. Examples of a computer readable medium are tapes, CD-ROMs, DVD-ROMs, DVD-RAMs, DVD-RWs, BluRay, DAT, MiniDisk, solid state disks SSD, floppy disks, SD-cards, CF-cards, memory-sticks, USB-sticks, EPROM, EEPROM or the like.

0018Said dedicated global private key is generated using an oblivious key generation protocol. This enhances further the security.

0019The client communicates with said assist server, 'AS', for key generation. This further enhances the security since the storage server is not included in the key generation process.

0020For exchanging key related information, a non-interactive oblivious key exchange protocol in form of a non-interactive Diffie-Hellman key exchange protocol is used. This enables to hide the chunk hash efficiently from the assist server. Thus, security is increased.

0021Said new private key is randomly generated by said AS. This enables in an easy way to provide a new private random key.

0022Said hash value is blinded. This ensures that the assist server or any other entity does not learn the hash value of the data chunk to be re-keyed.

0023Said AS maintains said key table. This enables that clients do not have to be aware of any re-keying.

0024A public key of said AS may be provided to the client via a trusted platform module connected to said client. This enhances the security since attacks where different clients do not share the same view on the existing server can be avoided. For example tamper resisting dongles or processor extensions to trusting computed can be used which store in read only memory public keys. These dongles, similar to trusted platform modules ensure that the public key never leaves the read only memory ROM and are also equipped with cryptographic procedures. The user then may have simply to invoke an application program interface of the tamper resisting dongle input the hash function and the dongle outputs the blinded public key.

0025In the drawings <dl id="dl0001"><dt>Fig. 1</dt><dd>shows a conventional key generation scheme;</dd><dt>Fig. 2</dt><dd>shows a further conventional key generation scheme;</dd><dt>Fig. 3</dt><dd>shows a system according to an embodiment of the present invention;</dd><dt>Fig. 4</dt><dd>shows part of steps of an example method not part of the present invention;</dd><dt>Fig. 5</dt><dd>shows part of steps of a method according to the present invention;</dd><dt>Fig. 6</dt><dd>shows part of steps of a method according to a further embodiment of the present invention; and</dd><dt>Fig. 7</dt><dd>shows part of steps of a method according to a further embodiment of the present invention.</dd></dl>

0026<figref idref="f0001">Fig. 1</figref> shows a conventional key generation scheme.

0027In <figref idref="f0001">Fig. 1</figref> an RSA key based generation scheme as disclosed in the non patent literature of Mihir Bellare and Sriram Keelveedhi, Thomas Ristenpart, DupLESS: Server-Aided Encryption for Deduplicated Storage, Proceedings of Usenix Security 2013 is shown.

0028<figref idref="f0002">Fig. 2</figref> shows a further conventional key generation scheme.

0029In <figref idref="f0002">Fig. 2</figref> a BLS-based key generation scheme as disclosed in the non patent literature of Frederik Armknecht, Jens-Matthias Bohli, Ghassan Karame, Franck Youssef, Transparent Data Deduplication in the Cloud, In Proceedings of the ACM Conference on Computer and Communications Security (ACM CCS), (to appear) 2015 is shown. A client hashes a file f and blinds it by multiplying it with g₁^r given a randomly chosen <maths id="math0001" num=""><math display="inline"><mi mathvariant="normal">r</mi><mo>∈</mo><msub><mi>ℤ</mi><mi mathvariant="normal">p</mi></msub></math><img file="EP3375129B1_D0001.tif" /></maths> and sends a blinded hash <i>ĥ</i> to the gateway. The gateway generates a signature as <i>ŝ</i> using the blinded hash value and a secret key x in <maths id="math0002" num=""><math display="inline"><msub><mi>ℤ</mi><mi mathvariant="normal">p</mi></msub></math><img file="EP3375129B1_D0002.tif" /></maths> and sends it back to the client. The client computes the unblended signature s and verifies that v₁ equals v₂ and then the encryption key k is computed as the hash of the unblended signature H(s). e is a bilinear map of two groups T₁, T₂ of order p, g₁, g₂ are generators of T₁, T₂ respectively and T₁ × T₂ → T_T is a paring function with the hash function: H: {0,1}*→T₁, the secret x in <maths id="math0003" num=""><math display="inline"><msub><mi>ℤ</mi><mi mathvariant="normal">p</mi></msub></math><img file="EP3375129B1_D0003.tif" /></maths> with corresponding public keys y₁ = g₁^x ; y₂ = g₂^x.

0030<figref idref="f0003">Fig. 3</figref> shows a system according to an embodiment of the present invention.

0031In <figref idref="f0003">Fig. 3</figref> a plurality of clients is shown. To store a file on cloud servers a client requests an encryption key using an oblivious protocol from an assisting server, for example by executing a non-interactive Diffie-Hellman key exchange protocol with the assisting server. The assisting server provides a key based on the corresponding key share for the file to be encrypted back to the client. The client then encrypts the file and stores it on a cloud server via the assisting server.

0032When then another client issues a request for re-keying for a given blinded hash based on the index output of the key exchange protocol with the key server - here the assisting server and the assisting server determines that the re-keying request is authentic, the assisting server updates the global private key dedicated to the data chunk or file in question by updating the entry indexed by the output of the key exchange protocol with the new randomly generated private key in a local data base available to the assisting server. Then a server-aided key generation protocol between the client and the assisting server is executed to output the encryption key for the client, preferably using an oblivious pseudo-random function based on the file hash and the generated random global key specific to each chunk. The client then re-encrypts the file with the obtained encryption key, i.e. steps 1) to 3) are performed again, and then deletes the old copy for example.

0033<figref idref="f0004">Fig. 4</figref> shows part of steps of the method according to a background example not forming part of the present invention.

0034In <figref idref="f0004">Fig. 4</figref> the proxy/gateway/assisting server is assumed to choose two groups ┌₁ and ┌₂ with order p, and a computable bilinear map e : ┌₁ × ┌₂ → ┌_T. Additionally, the proxy chooses n private keys <maths id="math0004" num=""><math display="inline"><msub><mi mathvariant="normal">x</mi><mn>1</mn></msub><mo>,</mo><mo>…</mo><mo>,</mo><msub><mi mathvariant="normal">x</mi><mi mathvariant="normal">n</mi></msub><mo>∈</mo><msub><mi>ℤ</mi><mi mathvariant="normal">p</mi></msub></math><img file="EP3375129B1_D0004.tif" /></maths>, and their corresponding public keys <maths id="math0005" num=""><math display="inline"><msubsup><mi>y</mi><mn>1</mn><mi>i</mi></msubsup><mo>=</mo><msubsup><mi>g</mi><mn>1</mn><msub><mi>x</mi><mi>i</mi></msub></msubsup><mo>∈</mo><msub><mi mathvariant="normal">Γ</mi><mn>1</mn></msub></math><img file="EP3375129B1_D0005.tif" /></maths> and <maths id="math0006" num=""><math display="inline"><msubsup><mi>y</mi><mn>2</mn><mi>i</mi></msubsup><mo>=</mo><msubsup><mi>g</mi><mn>2</mn><msub><mi>x</mi><mi>i</mi></msub></msubsup><mo>∈</mo><msub><mi mathvariant="normal">Γ</mi><mn>2</mn></msub></math><img file="EP3375129B1_D0006.tif" /></maths>. Let H* : {0, 1}* → ┌₁ be a cryptographic hash function which maps bitstrings of arbitrary length to group elements in ┌₁. Prior to storing a file or a chunk f, the client C computes h ← H*(f), blinds it by multiplying it with <maths id="math0007" num=""><math display="inline"><msubsup><mi>g</mi><mn>1</mn><mi>r</mi></msubsup></math><img file="EP3375129B1_D0007.tif" /></maths>, given a randomly chosen <maths id="math0008" num=""><math display="inline"><mi mathvariant="normal">r</mi><mo>∈</mo><msub><mi>ℤ</mi><mi mathvariant="normal">p</mi></msub></math><img file="EP3375129B1_D0008.tif" /></maths>, and sends the blinded hash <i>ĥ</i> to the gateway/proxy/assisting server. The assisting server derives the signature on the received message and sends the result back to the client C, who computes the unblinded signature s and verifies that: <maths id="math0009" num=""><math display="inline"><mi>e</mi><mfenced><mi>s</mi><msub><mi>g</mi><mn>2</mn></msub></mfenced><mo>=</mo><mi>e</mi><mfenced separators=""><msup><mi>h</mi><mi>x</mi></msup><msubsup><mi>g</mi><mn>1</mn><msub><mi mathvariant="italic">rx</mi><mi>i</mi></msub></msubsup><msubsup><mi>g</mi><mn>1</mn><mrow><mo>−</mo><msub><mi mathvariant="italic">rx</mi><mi>i</mi></msub></mrow></msubsup><mo>,</mo><msub><mi>g</mi><mn>2</mn></msub></mfenced><mo>=</mo><mi>e</mi><mfenced><mi>h</mi><msubsup><mi>y</mi><mn>2</mn><mi>i</mi></msubsup></mfenced></math><img file="EP3375129B1_D0009.tif" /></maths>.

0035The encryption key is then computed as the hash of the unblinded signature: k ← H(s). The properties of this example not forming part of the invention are as follows: <ul id="ul0001" list-style="dash" compact="compact"><li>The proxy/gateway/assisting server only keeps n keys, but does not have to keep track of which chunk has been re-keyed. Clients C have to be aware of that.</li><li>After a re-key request, the client should re-encrypt the old file with the new generated key, and delete it from S.</li><li>Here, only the chunks that should be re-keyed are affected. Deduplication may happen after that, as long as all clients are synchronized on how many re-key rounds have occurred for each chunk, preferably if there is a small number of chunks.</li></ul>

0036Thus <figref idref="f0004">Fig. 4</figref> provides a non-transparent re-keying procedure using the oblivious protocol of the non-patent literature of Frederik Armknecht, Jens-Matthias Bohli, Ghassan Karame, Franck Youssef, Transparent Data Deduplication in the Cloud, In Proceedings of the ACM Conference on Computer and Communications Security (ACM CCS), (to appear) 2015.

0037<figref idref="f0005">Fig. 5</figref> shows part of steps of the method according to the present invention.

0038The embodiment of <figref idref="f0005">Fig. 5</figref> shows the use of the oblivious protocol with a non-interactive Diffie-Hellman protocol. All clients are assumed to know the public key of the proxy y = g^x. Moreover, the proxy is assumed to store locally a dedicated key table containing tuples of the form: INDEX | Key. At the start, this table is empty. When a client wants to get a key for a give file f, the client computes the file hash h and y^h, and sends it to the proxy. The latter checks that the key table. If the row at index y^h is empty, then the proxy generates a new key x_i at random and proceeds with the oblivious protocol as shown in <figref idref="f0005">Fig. 5</figref>. If, on the other hand, the row exists, then the proxy simply fetches x_i and proceed. Any client can send a re-key request to any file/chunk. The client simply signs his request and includes the index y^h. The proxy checks that the signature is correct and that the client is authorized to ask for re-keying. If so, the proxy simply updates the row at index y^h with a new randomly generated key.

0039The properties of the embodiment of <figref idref="f0005">Fig. 5</figref> are inter alia as follows: <ul id="ul0002" list-style="dash"><li>Clients do not have to be aware of any re-keying attempt. They just contact the proxy, get the key and decrypt the file.</li><li>After a re-key request, the owner should re-encrypt the old file with the new generated key, and delete it from S.</li><li>Here, only the chunks that should be re-keyed are affected. Deduplication may happen after that, as long as all clients are synchronized on how many re-key rounds have occurred for each chunk.</li><li>This embodiment enables scaling with the number of clients.</li><li>This embodiment enables non-leakage of h to the proxy, i.e. it is infeasible for the proxy to compute the discrete logarithm xh of y^h = g^xh. This ensures that the proxy never learns h in the process.</li></ul>

0040<figref idref="f0006">Fig. 6</figref> shows part of steps of the method according of the further embodiment to the present invention.

0041In <figref idref="f0006">Fig. 6</figref> a method for re-keying is shown comprising the steps of <ol id="ol0001" compact="compact" ol-style=""><li>1) Requesting re-keying for a given blinded hash identifier, by the client sending an authenticated request message to an assisting server.</li><li>2) The assisting server authenticates the client and updates his share specific to the file being re-keyed.</li><li>3) The client re-encrypts the file with the new key derived obliviously from the updated server share and the file hash. The server does not learn the hash at all times.</li><li>4) When other clients want to access the aforementioned re-keyed and deduplicated file, they execute the same oblivious protocol to acquire obliviously the same key used to re-encrypt without the need for those clients to be aware of any re-keying request by other servers.</li></ol>

0042<figref idref="f0007">Fig. 7</figref> shows part of steps of the method according of the further embodiment to the present invention.

0043In <figref idref="f0007">Fig. 7</figref> a method for re-keying is shown comprising the steps of <ol id="ol0002" compact="compact" ol-style=""><li>1. Executing a non-interactive Diffie-Hellman key exchange protocol with the key server</li><li>2. Requesting re-keying based on the index output by the aforementioned key exchange protocol.</li><li>3. If the re-keying request is authentic, the server updates the global private key dedicated to the chunk/file in question by updating the entry indexed by output by the aforementioned key exchange protocol with a new randomly generated private key.</li><li>4. Executing a server-aided key generation protocol between users and the proxy to output encryption key, preferably using an oblivious pseudo-random function based on the file hash and the generated random global key specific to each chunk.</li><li>5. The user re-encrypts the file with the obtained encryption key and deletes the old copy.</li></ol>

0044In the above embodiments a number of clients that are interesting in storing their files at a storage provider S are provided. Further said storage provider S exposes to its clients a standard interface comprising a number of simple operations, such as storing a file, retrieving a file, deleting a file, generating a URL for sending HTTP commands for storage/retrieval, etc..

0045Further a proxy is provided which can be queried by clients to assist them in deriving in an oblivious way strong encryption keys for content to be deduplicated. S is assumed to deduplicate all exactly similar chunks that are stored by different users.

0046Said proxy P acts as an assisting key server. Inter alia proxy P helps clients derive a strong encryption key to encrypt content in such a way that clients encrypting the same file will end up generating the same key.

0047The clients and the proxy P are assumed to share per-user keys and credentials (e.g. client certificates). In particular, all communication between a client and the proxy is authenticated and, in the case of need, encrypted based on a secure encryption algorithm Enc and a cryptographic hash function H.

0048In one or more of the aforementioned embodiments the same public key of the server is assumed to be available to all clients. To avoid any attack where different clients do not share the same view on the server key, trusted computing principles can be used. For example, tamper resistant dongles (or processor extensions to trusted computing) can be used, which store in read only memory (ROM) the public key g^s. These dongles, similar to trusted platform modules (TPMs), ensure that the public key g^s never leaves ROM and also are equipped with cryptographic algorithms. The user simply has to invoke an API of the dongle, inputting the hash function, and the output would be g^sh.

0049In summary embodiments of the present invention address the problem of re-keying by only updating partially the global secret of the key server for the data to be re-keyed, and locally re-encrypting on the storage entity the data that should be re-keyed. This ensures no change of protocol-layer functionality on the key server, but supports re-keying.

0050The present invention further enables indexing of global keys used to assist a chunk-based deduplication files based on the output of a non-interactive Diffie-Hellman protocol hiding the file hash. Even further the present invention enables an easy implementation such that can be used with existing oblivious based server assisted encrypted deduplication techniques.

0051At least one embodiment of the present invention has at least one of the following advantages: High security is enabled as well as high efficiency since only deduplicated data that should be re-keyed is affected without incurring any need of awareness from a client. The present invention enables therefore an efficient re-keying of encrypted deduplicated data such that information leakage in case the key is leaked is minimized and access of malicious employees for example can be revoked.