The present invention relates to a method for storing data on a storage entity. The present invention further relates to a method for performing a proof of retrievability.

Further the present invention relates to a storage entity for storing data. Even further the present invention relates to a non-transitory computer readable medium storing a program causing a computer to execute a method for storing data on a storage entity.

Although applicable in general to any kind of storage entity, the present invention will be described with regard to cloud storage.

Cloud services are gaining increasing importance and applicability in a number of application domains, such as storage, computing services, etc. The "cloud" has recently gained several adopters among small and medium enterprises and large businesses that are mainly interested in fast development of new applications while minimizing the costs of both deployment and infrastructure management and maintenance.

Cost effectiveness is realized in the cloud through the integration of multi-tenancy solutions and storage efficiency solutions with efficient distributed algorithms that run on commodity hardware to ensure unprecedented levels of scalability and elasticity. The combination of multi-tenancy solutions with storage efficiency techniques, e.g., data deduplication enables drastic cost reductions. For instance, recent studies show that cross-user data deduplication can save storage costs by more than 50% in standard file systems, and by up to 90-95% for back-up applications as shown 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), 2015. Moreover, nearly three quarters of these savings could also be obtained by means of whole file deduplication.

The advent of cloud storage and computation services, however, introduces new threats to data security. Namely, in nearly all conventional cloud services, users lose control over their data and how data is processed or stored. For example, a permanent loss of customers' data in a cloud system due to lightning strikes that affect a local utility grid near a corresponding data center is possible. For example a conventional method which enables users to verify the integrity and availability of their outsourced data include Proofs of Retrievability (POR) is shown in the nonpatent literature of Frederik Armknecht, Jens-Matthias Bohli, Ghassan Karame, Zongren Liu, Christian Reuter, Outsourced Proofs of Retrievability, In Proceedings of the ACM Conference on Computer and Communications Security (ACM CCS), Arizona, USA, 2014. Said conventional method enables providing end-clients with the assurance that the data is retrievable.

Although these conventional methods can be effective in detecting data loss, they completely ignore storage-efficiency requirements, such as multi-tenancy and data deduplication, which are being widely utilized by existing cloud storage providers. Namely, conventional solutions assume a single trusted tenant, i.e. an honest verifier, who pre-processes the files to create tags using secret material before outsourcing them to the cloud, and later regularly performs verifications, e.g., POR on the pre-processed files and tags in order to react as early as possible in case of data loss. However, in practice, given that files are typically deduplicated across tenants, and different tenants do not tend to trust each other, tenants will be reluctant on sharing the secret material used to construct tags in POR/PDP.

On the other hand, solutions where each tenant constructs and stores his own tags in the cloud do not scale well with the number of tenants in the system. In this case, the storage overhead of the tags threatens to cancel out the benefits of data deduplication over popular objects; for instance, the storage overhead required to store the tags of files owned by 20 tenants is almost 200% when compared to the original file size. One of the problems addressed by embodiments of the invention is therefore to provide multi-tenant publicly-verifier proofs of retrievability. A further problem addressed by embodiments of the present invention is to enable proofs of retrievability in which tenants do not require to mutually trust each other. One of the further problems addressed by embodiments of the present invention to provide storage efficiency and a secure and easy implementation.

In an embodiment the present invention provides a method for storing data on a storage entity, 'SE',

comprising the steps of

a) computing a file identifier for a file to be stored on said SE

b) checking, by said SE, if the file has already been stored using said file identifier

c) generating a user-specific private and a user-specific public identifier d) updating or computing tags of said file by said client such that said updating or computing is homomorphic in the user-specific private identifier and in parts of said file

e) providing said user-specific public identifier said updated tags and a proof of possession of said secret identifier to said SE by said client

f) verifying, by said SE, said proof-of-possession

g) verifying validity of said tags

h) upon successful checking storing a public identifier for said file incorporating said user-specific public identifier and said updated tags by said SE

i) if the file has not already been stored, storing said file by said SE.

In a further embodiment the present invention provides a method for performing a proof of retrievability,

comprising the steps of

A) Downloading, by a client, a current verification key of a file stored on a storage entity according to the method of one of the claims 1 -8,

B) Verifying correctness of said verification key by reconstructing the current verification key using the last known verification key and the user-specific public identifiers incorporated into the verification key according to the method of one of the claims 1 -8 C) Upon successful verification performing a proof-of-retrievability with said current verification key.

In a further embodiment the present invention provides a storage entity for storing data according to the method of claim 1 , wherein a file together with a user- specific public identifier, a proof of possession and one or more file tags of said file is stored.

In a further embodiment the present invention provides a non-transitory computer readable medium storing a program causing a computer to execute a method for storing on a storage entity, 'SE', said method comprising the steps of

a) computing a file identifier for a file to be stored on said SE

b) checking, by said SE, if the file has already been stored using said file identifier

c) generating a user-specific private and a user-specific public identifier d) updating or computing tags of said file by said client such that said updating or computing is homomorphic in the user-specific private identifier and in parts of said file

e) providing said user-specific public identifier said updated tags and a proof of possession of said secret identifier to said SE by said client

f) verifying by said SE, said proof-of-possession

g) verifying validity of said tags

h) upon successful checking storing a public identifier for said file incorporating said user-specific public identifier and said updated tags by said SE

i) if the file has not already been stored, storing said file by said SE.

The terms "storage entity" and "client" refer in particular in the claims, preferably in the description each to a device or devices adapted to perform computing like a personal computer, a tablet, a mobile phone, a server, a router, a switch or the like and comprise 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 devices or entities 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. Further the devices or entities may be identical forming a single computing device. The devices or devices may also be instantiated as a virtual device running on a physical computing resource. Different devices may therefore be executed on said physical computing resource.

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

The term "part" in connection of a file may refer in particular in the claims, preferably in the description, to a division of said file into a plurality of file parts, sections, blocks or the like.

At least one embodiment of the present invention may have at least one of the following advantages:

deduplication is enables not only of the files but also of the proof retrievability tags across mutually untrusted tenants,

- different tenants do not require to share any secret material with each other, enhanced security since resistance against malicious proxy servers and cloud providers is enabled,

storage efficiency. Further features, advantages and further embodiments are described or may become apparent in the following:

Said user-specific public identifier and/or said user-specific secret identifier are computed as a public key/private key pair. This enable for example to provide in an easy way to proof-of-possession, for example by issuing the proof-of- possession based on the secret key for the public key.

The file may be encrypted and/or an information dispersal algorithm is applied on said file like erasure-coding prior to storing. This allows a secure pre-processing of the file to be stored. When encrypting the file then security is enhanced. When the file is erasure-coded then it can be easily utilized in a proof of retrievability ensuring extractability. The file identifier may be generated by computing a hash tree like a Merkle tree used for a proof-of-work and using the root of said hash tree as file identifier. This enables an easy generation of a unique file identifier. Further the Merkle tree can be used for a proof-of-work and thus a security is enhanced. For updating said file tags said file may be divided into blocks, each block comprising a number of sectors, preferably all blocks having the same number of sectors, wherein a file tag for each block is computed based on file elements, said file elements being computed based on a cryptographic hash function of said file and sector indices. This allows a reliable while secure updating of the file tags.

Said user-specific public identifier may be locally stored by a client as verification key. This enables a client in an easy way to perform a later proof-of-retrievability.

An oblivious key generation protocol may be used between said client and a trusted entity to generate a deterministic private identifier/public identifier pair. This ensures that the trusted entity does not learn any information about the file to be stored for which the keys are generated. Thus security is enhanced.

In case the file is already stored correctness of said updated tags may be checked based on already stored file elements of said file by said SE. This allows a fast and reliable verification.

For performing said proof-of-retrievability a random challenge may be computed and provided to said SE, said random challenge comprising one or more blocks of said file and a corresponding randomly generated integer and wherein said SE computes the file tags and the sum of the product of said randomly generated integer and the sector corresponding to said integer and wherein said client verifies retrievability of said data using said file tags and said sum to generate corresponding file elements and comparing said generated file elements with locally stored file elements. This allows a fast and reliable while easy to perform proof-of-retrievability.

There are several ways how to design and further develop the teaching of the present invention in an advantageous way. To this end it is to be referred to the patent claims subordinate to the independent claims on the one hand and to the following explanation of further embodiments of the invention by way of example, illustrated by the figure on the other hand. In connection with the explanation of the further embodiments of the invention by the aid of the figure, generally further embodiments and further developments of the teaching will be explained.

In the drawings

Fig. 1 shows a system according to an embodiment of the present invention;

Fig. 2 shows steps of a method according to a further embodiment of the present invention;

Fig. 3 shows steps of a method according to a further embodiment of the present invention and

Fig. 4 shows steps of a method according to a further embodiment of the present invention.

In Fig. 1 in a first step 1 an oblivious key establish mechanism between users and a trusted entity is provided. This oblivious key establishing method employs an oblivious protocol which is executed between the users and the trusted entity to generate the keys required for encrypting the files to be stored.

The trusted entity chooses two groups Π and Γ2 with order p, and a computable bilinear map e : Γ1 ^χ Γ2→ Γτ . Additionally, the trusted entity chooses a private key x e Z _p , and the corresponding public keys yi g ^x = e Π and V2 = g¾ e Γ2 . Let H* {0, 1} ^* → Π be a cryptographic hash function which maps bitstrings of arbitrary length to group elements in . Prior to storing a file M, the client computes h <- H* (M), blinds it by multiplying it with g , given a randomly chosen r e Z , and sends the blinded hash h to the trusted entity. The trusted entity derives the signature on the received message and sends the result back to the client, who computes the unblinded signature s and verifies that: e (s, g ₂ ) = e Qi ^x g ^x g^ ^rx , g ₂ ) = e(h, y ₂ ). The encryption key is then computed as the hash of the unblinded signature:

K <- H(s). The advantages of such a key generation method are inter alia:

^• Since the method on which the keys are relied upon is oblivious, it ensures that the trusted entity does not learn any information about the files, e.g. about the file hash during the process. On the other hand, this method enables the client to check the correctness of the computation performed by the trusted entity (i.e., verify the signature of the trusted entity). This verification enables to prevent a rational trusted entity from registering users of the same file to different file versions with reduced level of deduplication.

^• By involving the trusted entity in the key generation module, brute-force attacks on predictable messages can be slowed down by rate-limiting key-generation requests to trusted entity. The security provided by the embodiment is similar to Message-Locked-Encryption MLE scheme.

In summary this encryption key is used as file key to encrypt a file to be stored. Further in the following a group G of prime order p with generator g, and a computable efficient bilinear map e : G * G→ GT are agreed before the start of the protocol. Each user U participating is required to setup a key pair. The user chooses a private key sku = x e z , and the corresponding public key is then given by pku =g ^sku e G . U also needs to prove possession of the secret key in zero- knowledge. This can be achieved by issuing pop which represents a signature of the public verification key with the private signing key and can be checked by signature verification. Such a proof of possession is required to protect against a rogue-key attack, where an adversary forges the multi-signature of a group using an invalid key (i.e., a public key whose private key is unknown to the adversary).

To store a new file M, the user first has to pre-process M as follows. The U first encrypts the file using a deterministic file-key κ obtained from the server-aided key generation protocol. The resulting file is then encoded with an erasure code as required by the utilized POR (in order to provide extractability guarantees). The result is denoted by M.

When a user U wants to store the encoded file M, the user creates a unique identifier fid by building the Merkle Tree used for the proof-of-work PoW and taking the Merkle Root as the identifier. The server checks if the according file with identifier fid is already stored and responds this information to the user.

Now two cases need to be distinguished:

(i) the file has not been stored previously, and

(ii) the file is already stored.

In case of i) the following steps are performed:

The file is interpreted as n blocks, each is s sectors long. A sector is an element of Z with p being the order of G and is denoted by m with 1 < i < n, 1 < j < s. That is, the overall number of sectors in the file is n ^■ s. For each 1 < j < s a group element Uj e G is pseudo-randomly extracted from the file as Uj = f (H ( ), j) where H denotes a cryptographic hash function, and f a pseudo-random function mapping into the group, e.g. the BLS hash function. A file tag on each block i is computed as follows: i = (f(Q - n ^u 7 ^i] ) ^{sku (1)}

User U then sets δ = (pku , {uj } j= 1...S ) and tg = {σ, }, = 1... Π . The file M, the public key pku along with the proof of possession pop, and the file tags {σ, } i = 1...n are uploaded and stored by the server of the cloud provider. The user stores locally gpkiy = pku as the verification key for the file and the hash value H ( ) to be able to reconstruct the values {Uj } j=1...m later on. The server S verifies the validity of U's key by verifying pop. Furthermore the server S checks that the tags are indeed valid for the key pku by verifying: e (a g) ₌ ⁷ e (/(i) Π ₌₁ ^i} , pku) (2) If the key and tags are correct, the server S stores all received data ( , δ, tg). Moreover, the server S creates a log file that will provide the necessary information needed for any other user to verify that the keys are well formed. Here, pklog comprises information about the public key of the user and the proof of possession of the corresponding secret key, (pku, pop).

In case of ii) the file M is already stored and will be deduplicated, an Update protocol/method is executed in order to update the file tags on the fly, so that the new user U is also able to obtain guarantees from the POR protocol without the need to trust the correctness of the already stored tags. The new user U has already obtained M by encryption using the server-aided key generation and erasure coding as required for the POR protocol. The procedure Update proceeds similarly to Store in order to compute {σ, } , =1...n according to Equation 1. Here D, also computes M and the hash value H ( ). With the help of the hash value H ( ), the values {uj } j = 1...m are derived. Instead of uploading the full file, the new user U only sends (pku , popu , tg) to the sever S.

Upon reception of (pku , popu , tg), the server S checks the validity of pku using popu and checks correctness of the newly uploaded tag using Equation 2, based on the already stored values u, (which in case of need can be reconstructed from H ( ) by the server S.

If the verification succeeds, the server S updates the existing tags σ· as follows. The sever S combines the tags to form the new tags σ = σ· ^■ σ _£ . Due to the homomorphic properties, here of the BLS signature, the tags will be correctly formed for a key gpk _M = gpk _M ^■ pk _a , where pk _M is the previously stored verification key for the file and pku the public key uploaded by the user. Finally, the server S replaces the stored tags and key by σ , and gpk _M , respectively. The public key and the corresponding proof of possession of the new user (pku , popu ) are appended to pklog. In step 4) a proof-of-retrievability POR verification is performed between a user U and the server S of cloud provider.

To conduct POR on M, the user U downloads the current verification key gpkiy corresponding to M. First, to check the correctness of gpkiy, the user U retrieves pklog with the public keys and proof of possessions (pku , popu ) for all owners of the file M that joined after the last known key. Starting from the last known verification key gpk _M , the user U multiplies all verification keys pk e pklog and verifies gpk _{M =} gpkM ^■ U _pk e _P kiog Pk. Furthermore, for each pku ≡ log, the user U checks the validity of the key by verifying the proof popu, i.e. a correct signature of the respective public key. If the verification succeeds, the user U accepts gpkiy as the verification key for M, updates the verification key locally, and proceeds with the actual POR protocol as follows.

Fig. 2 shows steps of a method according to a further embodiment of the present invention.

In Fig. 2 a method for storing data on entities of a cloud provider is shown comprising the steps of

1 ) Computing file ID and sending it to the cloud provider.

2) If the file ID is stored, the file uploader downloads the latest public key, updates the tags using our homomorphic protocol. Finally, the file uploader updates the public key with his secret key, and uploads the newly corresponding public key and updated tags to the cloud.

3) The cloud checks the signature of possession on the public key of the file uploader, and if the verification passes, the cloud accepts the update and stores the updated public key and tags.

4) When an existing user wants to perform a POR verification (to check the remote integrity of the file), the user downloads the latest public key, verifies that his own private key is included in the public key, and then finally if all this verification succeeds, the user performs a POR with the cloud.

Fig. 3 shows steps of a method according to a further embodiment of the present invention.

In Fig. 3 steps of a method for storing data and a storage entity, 'SE' is shown. The method comprises the steps of

a) computing a file identifier for a file to be stored on said SE

b) checking, by said SE, if the file has already been stored using said file identifier

c) generating a user-specific private and a user-specific public identifier d) updating or computing tags of said file by said client such that said updating or computing is homomorphic in the user-specific private identifier and in parts of said file

e) providing said user-specific public identifier said updated tags and a proof of possession of said secret identifier to said SE by said client

f) verifying, by said SE, said proof-of-possession

g) verifying validity of said tags

h) upon successful checking storing a public identifier for said file incorporating said user-specific public identifier and said updated tags by said SE

i) if the file has not already been stored, storing said file by said SE.

Fig. 4 shows steps of a method according to a further embodiment of the present invention.

In Fig. 4 a method for performing a proof-of-retrievability is shown. The method comprises the steps of

A) Downloading by a client a current verification key of a file stored on a storage entity according to the method of one of the claims 1 -8,

B) Verifying correctness of said verification key by reconstructing the current verification key using the last known verification key and the user-specific public identifiers incorporated into the verification key according to the method of one of the claims 1 -8

C) Upon successful verification performing a proof-of-retrievability with said current verification key.

In summary at least one embodiment of the present invention may leverage key and message homomorphic properties of BLS (Boney Lynn Shacham) signatures for constructing a storage-efficient publicly verifiable multi-tenant proof-of- retrievability, e.g. tags are updated or computed such that said updating and computing is homomorphic in the user-specific private identifier and in the respective file parts. Embodiments of the present invention further enable a verification of tags updated by other untrusted tenants by verifying the inclusion of own ^' s private key in the aggregated public key. Further the present invention enables the deduplication of both the files and the proof-of-retrievablity tags across mutually trusted tenants.

Even further embodiments of the present invention do not require different tenants to share any secret material with each other.

Even further the embodiments of the present invention enables resistance against malicious proxy servers and cloud providers.

Many modifications and other embodiments of the invention set forth herein will come to mind to the one skilled in the art to which the invention pertains having the benefit of the teachings presented in the foregoing description and the associated drawings. Therefore, it is to be understood that the invention is not to be limited to the specific embodiments disclosed and that modifications and other embodiments are intended to be included within the scope of the appended claims. Although specific terms are employed herein, they are used in a generic and descriptive sense only and not for purposes of limitation.