BACKGROUND OF THE INVENTION
Field of the invention
The present invention generally relates t o protecting confidentiality of a file
distributed and stored at a plurality of storage service providers. In particular, it
concerns cloud storage. Cloud storage is a model of networked online storage
where data is stored in virtualized pools of storage which are generally hosted by
third parties. Hosting companies operate large data centers, and people who
require their data t o be hosted buy or lease storage capacity from them. The data
centre operators, in the background, virtualize the resources according to the
requirements of the customer and expose them as storage pools, which the
customers can themselves use to store files or data objects. Physically, the
resource may span across multiple servers.
If no precaution is taken, all the stored data can be accessed by the cloud
operator who can potentially use it with a malicious intent (e.g. reselling the
information to the client's competitors). Furthermore, even if the cloud operator
is honest, the confidentiality of stored data can be compromised by attackers who
have greater interest in attacking data centers which aggregate data of several
companies and users rather than attacking a single enterprise network. Therefore
there is a need to protect the confidentiality of data at a storage service provider.
Description of the prior art
One known solution consists in encrypting the data before outsourcing its storage.
The drawback of this solution is that it is resource consuming (encryption for
storage and decryption for retrieval). Additionally it requires a key management
process to keep trace of the keys used to encrypt each data packet. It further
implies to securely store the keys, because it gives full access to the data if the
key is leaked.
Another known solution consists in segmenting data in several chunks and store
the chunk respectively at different storage service providers so that none of them
has access t o the full data. This solution has the drawback that each storage
service provider has access t o the chunk that it stores. So it can still derive some
confidential information from it. A countermeasure is to further encrypt each
chunk, with the drawback of the previous solution.
Another known solution is described in the article of PAULO F OLIVERA ET AL:
"Trusted Storage over Untrusted Networks", GLOBECOM 2010, 2010 IEEE
GLOBAL TELECOMMUNICATIONS CONFERENCE, IEEE, PISCATAWAY, NJ, USA, 6
December 2010. It comprises the steps of:
- choosing a security parameter n, and segmenting the file in n chunks S ,...,S n;
- randomly choosing n coefficients a with j = 1,..., n, all a being different from
each other;
- then generating n2 coefficients a for i = 1,..., n and j = 1,..., n, by generating a
Vandermonde matrix (a 1 );
- computing n linear combinations C = a . S + ... + ay.S + ... + a n. Sn
for i = 1 n;
- choosing two different storage service providers and storing a portion of the
linear combinations at the first storage service provider and the other linear
combinations at the second storage service provider.
The randomly chosen n coefficients a with j = 1,..., n, are different and
independent from each other; but most of the n2 coefficients a are not
independent from each other because they are obtained by generating a
Vandermonde matrix (a 1 ).
The aim of the present invention is t o provide a more secure technical solution for
protecting confidentiality of data distributed and store on a plurality of storage
service providers.
This can be solved by applying, the methods according t o the invention.
SUMMARY OF THE INVENTION
A first object of the invention is a method for protecting confidentiality of a file
distributed and stored at a plurality of storage service providers comprising the
steps of:
- choosing a security parameter n,
- segmenting the file in n chunks S ,...,Sn,
- choosing n2 coefficients a for i = 1 n and j = 1 n,
- verifying that the vectors aii,...,a n, for i = 1,..., n, are linearly independent,
otherwise generating the coefficients again,
- computing n linear combinations C = a S + ... + a .S + ... + a n. Sn,
for i = 1, n,
- choosing n storage service providers O , On among said plurality of storage
service provider,
- generating n file identifiers \D' ID' n designating said file,
- storing the combination C at the storage service provider O in association with
the file identifier ID' , for i = 1, n,
- storing the file identifier ID' and the provider identifier O , for i = 1,..., n, in a
file descriptor corresponding t o the file, this file descriptor being stored in a local
memory,
- and storing the set of coefficients a^, a n so that it can be re-associated with
the combination C , for i = 1, n;
characterized in that it further comprises the steps of:
- randomly choosing said n2 coefficients for i = 1,..., n and j = 1,..., n,
- verifying that the vectors aii,...,a n, for i = 1,..., n, are linearly independent,
otherwise generating the coefficients again,
- randomly choosing n super-coefficients a a' , ... , a' n for j = 1 n,
- computing a linear over-combination O = a C + ... + a' .Cj + ... + a' n.Cn ,
- and storing the over-combination OC and the coefficients a a' , ... , a' n for
j = 1, ..., n.
The fact of computing linear combinations C of all the chunks of the file to be
distributed and stored, and then storing the combinations respectively at a
plurality of storage service providers, protects the confidentiality of the file
without requiring encryption or key management, because it is necessary to get all
the combinations for retrieving any chunk of the original file. So the providers
cannot extract any information from these combinations unless all the n providers
collude. The fact of using n2 randomly chosen coefficients and an overcombination
improves the security.
According to a first peculiar embodiment of the method for protecting
confidentiality of a file distributed and stored at a plurality of storage service
providers, storing the set of coefficients a^, a n, so that it can be re-associated
with the combination C , for i = 1,..., n, comprises the step of storing them at the
storage service provider Oj, in association with the combination C and the file
identifier I D'j , for i = 1,..., n.
According to a second first peculiar embodiment of the method for protecting
confidentiality of a file distributed and stored at a plurality of storage service
providers, storing the set of coefficients a , a n, so that it can be re-associated
with the combination Cj, for i = 1 n, comprises the steps of:
- storing the set of coefficients a ,..., a n, at the storage service provider Ok, in
association with a combination Ck and a file identifier ID' k , for i = 1,..., n and for
k lying between 1 and n, including 1 and n, and being different of i ;
- and storing a permutation enabling to re-associate the set of coefficients a ,...,
a n and the combination Cj, for i = 1 n, in said file descriptor corresponding to
the file (F), and being stored in said local memory.
According to a third peculiar embodiment of the method for protecting
confidentiality of a file distributed and stored at a plurality of storage service
providers, storing the set of coefficients a ,..., an so that it can be re-associated
with the combination Cj, for i = 1,..., n, comprises the step of storing the set of
coefficients a ,..., a n in association with a file identifier I D'j and a provider
identifier Oj, for i = 1,..., n, in said file descriptor corresponding to the file, and
being stored in said local memory.
Another object of the invention is a method for retrieving a file that has been
protected by the method according to the invention , that comprises the steps of:
- reading n file identifiers \D' ID' n designating said file, and reading provider
identifiers , On, in a file descriptor corresponding t o the file, this file
descriptor being stored in a local memory,
- sending the n file identifiers \D' ID' n respectively to the storage service
providers designated by the provider identifiers , On ,
- receiving n combinations C , Cn, from the providers designated by the
provider identifiers , On ,
- retrieving n sets of coefficients a , a n, for i = 1, n, that respectively
correspond to the n combinations C , Cn,
- associating each combination C with the corresponding set of coefficients a^,
ajn, for i = 1, n,
- computing the inverse of a matrix composed of the n set of coefficients aii,...,ai n,
for i = 1,..., n, for obtaining another matrix composed of n sets of coefficients b 1 ,
...,b n, for i = 1, n,
- then computing n chunks Si, Sn of said file F as:
S = b .C + ... + b .C + ... + b n.Cn for i = 1, n,
- then re-assembling the chunks Si, Sn to reconstruct the file F;
characterized in that it further comprises the steps of:
- reading an over-combination O and coefficients a a' ... , a' n
for j = 1, n,
- computing the inverse of a matrix composed of n-1 sets of coefficients
aii,...,a n, for i = 1, n-1 and a set of coefficients (a a + ... + a' .a + ... +
a' n.anj ) for j = 1, n, for obtaining another matrix composed of n sets of
coefficients b 1 , ...,b n, for i = 1, n,
- then computing n chunks Si, Sn of said file (F) as:
S = b .C + ... + b .C + ... + bin-i.Cn-1 + b n.OC' for i = 1, n,
- then re-assembling the chunks Si, Sn to reconstruct the file (F).
According to a first peculiar embodiment of the method for retrieving a file,
retrieving n sets of coefficients a ...,a n for i = 1, n, that respectively
correspond to the n combinations Ci, Cn , comprises the step of receiving
them from the providers designated by the provider identifiers , On .
And associating each combination Ci with a corresponding set of coefficients a^,
a n, for i = 1, n, comprises the step of directly associating the combination Ci with
the set of coefficients a^, a n.
According to a second peculiar embodiment of the method for retrieving a file,
retrieving n sets of coefficients aii,...,a n for i = 1, n that respectively
correspond to the n combinations Ci, Cn, comprises the step of receiving them
from the providers designated by the provider identifiers , On ;
And associating each combination C with a corresponding set of coefficients a^,
a n, for i = 1, n comprises the steps of:
- reading a permutation in the file descriptor corresponding to said file,
- and applying the permutation to the sets of coefficients a ,...,ain, for i = 1,..., n,
so that each combination C is associated with the corresponding set of
coefficients a ,...,ain, for i = 1,..., n.
According to a third peculiar embodiment of the method for retrieving a file,
retrieving n sets of coefficients aii ,...,a n, for i = 1, n that respectively
correspond to the n combinations C , Cn, comprises the step of reading them
in the file descriptor corresponding to said file,
and wherein associating each combination with a corresponding set of
coefficients a ,...,ain, for i = 1,..., n comprises the step of directly associating the
set of coefficients a ,...,a n to the combination Cj, for i = 1,..., n.
Another objet of the invention is a method for protecting confidentiality of a file
distributed and stored at a plurality of storage service providers, peculiarly well
suited in situations where the storage is performed once but retrieval is performed
many times or by many entities. It comprises the steps of:
- choosing a security parameter n,
- segmenting the file in n chunks S ,...,S n,
- randomly choosing n2 coefficients a for i = 1 n and j = 1 n,
- verifying that the vectors aii ,...,a n, for i = 1,..., n, are linearly independent,
otherwise generating the coefficients again,
- computing n linear combinations C = a S + ... + a .S + ... + airi .Sn, for i = 1, n,
- choosing n storage service providers Oj, On among said plurality of storage
service provider,
- generating n file identifiers \D' ID' n designating said file,
- storing the combination C at the storage service provider O in association with
the file identifier ID'j , for i = 1, n,
- storing the file identifier ID'j and the provider identifier Oj, for i = 1, n, in a
file descriptor corresponding t o the file, this file descriptor being stored in a local
memory,
- computing the inverse of a matrix composed of the n set of coefficients
a ,...,ain, for i = 1,..., n, for obtaining another matrix composed of n sets of
coefficients bii ,..., b n, for i = 1,..., n,
- and storing the set of coefficients b 1 , b n so that it can be re-associated with
the combination C , for i = 1, n.
Another objet of the invention is a method for retrieving a file that has been
protected by this last method. It comprises the steps of:
- reading n file identifiers ID' , ID' n designating said file, and reading provider
identifiers , On, in a file descriptor corresponding to the file (F), this file
descriptor being stored in a local memory,
- sending the n file identifiers \D' ID' n respectively to the storage service
providers designated by the provider identifiers , On ,
- receiving n combinations C , Cn, from these providers designated by the
provider identifiers , On ,
- retrieving n sets of coefficients b 1 , b n, for i = 1, n that respectively
correspond to the n combinations C , Cn,
- associating each combination C with the corresponding set of coefficients b 1 ,
b n for i = 1, ..·, n,
- computing chunks S , Sn of said file as:
S = b .C + ... + b .C + ... + bin. C n for i = 1 n,
- then re-assembling the chunks S , Sn to reconstruct the file F.
Other features and advantages of the present invention will become more
apparent from the following detailed description of embodiments of the present
invention, when taken in conjunction with the accompanying drawings.
BRIEF DESCRIPTION OF THE DRAWINGS
In order to illustrate in detail features and advantages of embodiments of the
present invention, the following description will be with reference to the
accompanying drawings. If possible, like or similar reference numerals designate
the same or similar components throughout the figures thereof and description, in
which:
- Figure 1 illustrates first steps that are common t o three embodiments of the
method for protecting a file, according to the invention.
- Figures 2, 3, 4 respectively illustrate steps that are specific to three
embodiments of the method for protecting a file, according to the invention.
- Figure 5, 6, 7 respectively illustrate three embodiments of the method for
retrieving a file that has been protected according t o the invention.
- Figure 8 illustrates first steps that are common to three other embodiments of
the method for protecting a file, according to the invention, these embodiments
being peculiarly well suited in situations where the storage is performed once but
retrieval is performed many times or by many entities.
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS
Figure 1 illustrates steps that are common to three embodiments of the method
for protecting a file, according to the invention. For instance, we consider a user
who has a storage constrained device (e.g. a mobile phone, or a tablet) and wants
to outsource the storage of large files. We assume that the user knows m available
storage service providers that he/she can use because he/she already has
accounts there and associated contracts.
The proposed method requires the following means in the device:
1/ Means for associating a unique identifier ID to each file F to be distributed and
stored at storage service providers. This process could potentially be complex but
it can use the path of the file, or tags, or any other known method compatible
with file system architectures.
21 Input means enabling a user to choose a security parameter n. This parameter
can be different for each file: A bigger value of n involves more computation but
also more security. So the values of n can be chosen according to the wanted level
of confidentiality such as: restricted, confidential, secret...
3) Computing means executing a program comprising computer-executable
instructions for performing the proposed method.
Step 1: The user chooses a security parameter n, lower than or equal to the
number m of available storage service providers.
Step 2: The computing means segment the file F in n chunks Si, Sn. The chunks
must comprise a same number of bits. The number of bits per chunk is the
smallest integer which is bigger than size(F)/n and is a multiple of the size p of
the field in which the operation takes place (the same field as the one where the
coefficients are chosen). This process implies a padding of the file in order to have
n chunks of the same size. Any standard padding algorithm can be used to perform
this task.
Step 3: The computing means randomly choose n2 coefficients a for i = 1, n
and j = 1, n. Then the computing means verify that the chosen vectors
(aii,...,a n) for i = 1...n, are linearly independent, otherwise they generate the
coefficients again (A set of vectors is linearly independent if and only if the only
representations of the zero vector as linear combinations of its elements are
trivial solutions).
Step 4: The computing means compute n linear combinations as:
C = a 1 . S +...+a . S +...+a n. Sn for i = 1, n
Step 5: The computing means choose n storage service providers where the
combinations will be stored (n is lower or equal to m). They choose them among
the m available storage services providers, as a function of the identifier ID of the
file to be stored and protected. They supply the respective identifiers , On
designating the chosen storage service providers. There are many possibilities to
perform the selection: a random selection is the easiest, but the criterion of
choice could also take performance (load balancing), cost (pricing at each
provider) or security (reputation of providers) into account, to have a better
selection policy. Depending on the selection policy, one particular provider could
be the local host itself, and a given provider could be chosen more than once
(although this would decrease security).
The next steps can be made according t o three variants called step 6a, step 6b,
step 6c that are respectively illustrated by figures 2, 3, 4.
Figure 2 illustrates Step 6a wherein:
- The computing means generate a new unique file identifier ID', also designating
the file F, but different of the local file identifier ID, as a function of the local
identifier ID. This function should not allow to recover ID given ID', hence it is
essentially a one way function, for example a hash function. This new file
identifier ID' will be exposed to all the storage service providers.
- The computing means send, to a provider O , for i = 1, n:
-- a combination C
-- the set of coefficients aii ,...,a n,
-- and the file identifier ID'.
- The provider O , stores the combination C , and the set of coefficients aii ,...,a n, in
association with the file identifier ID'.
- The computing means locally store, in a local memory LM, a very simple file
descriptor for the file F: This file descriptor comprises the file identifier ID'
designating the file F, and the provider identifiers , On designating the
chosen storage service providers.
According to an improvement of this variant a, it is also possible to replace the
unique file identifier ID' by different file identifiers ID' i, ID' n , for the same file
F. These file identifiers ID' i, ID' n are respectively stored at the n chosen
providers respectively, and in the file descriptor corresponding to the file F, in the
local memory LM. This improvement makes the combinations more difficult to link
in case of providers' collusion.
Figure 3 illustrates Step 6b wherein:
- The computing means generate a new file identifier ID', also designating the file
F, but different of the local file identifier ID, as a function of the local identifier
ID, by aone way function, for example a hash function. This new file identifiers ID'
will be exposed t o all the storage service providers.
- The computing means send, to a provider O , for i = 1, n:
-- the new file identifier ID' designating the file F,
-- the combination C ,
-- and a set of coefficients ak 1 ,..., akn corresponding to another
combination Ck for k lying between 1 and n, including 1 and n, and being
different of i .
The set of coefficients ak 1 ,..., akn is determined by a permutation s applied to the
vectors (a^, a n) for i = 1, n:
(ak 1 ,..., akn) = (a0(n) ,..., a (n , a (n n) = coefficients corresponding to the
combination C (
On the other hand, for i = 1, n, the combination C ( is stored in association
with the set of coefficients a^, a n at the provider O ( . The computing means
define the permutation s on the integers from 1 to n. Basically this permutation
can be represented as an array (s( 1 ),..., s(i' ), ..., s(h)) containing all the integers
between 1 and n but in a non-ordered way.
- The computing means store, at provider Oi for i = 1, n, in association:
-- the new file identifier ID' designating the file F,
-- the combination C ,
-- and a set of coefficients ak 1 ,..., akn.
- The computing means locally store, in a local memory LM, a very simple file
descriptor for the file F. This file descriptor comprises:
-- the identifier ID' designating the file F,
-- the identifiers , On of the chosen storage service providers,
-- and the permutation s (e.g. in the form of an array as explained previously).
According t o an improvement of this variant a, it is also possible t o replace the
unique file identifier ID' by different file identifiers ID' i, ID' n , for the same file
F. These file identifiers ID' i, ID' n are respectively stored at the n chosen
providers respectively, and in the file descriptor corresponding to the file F, in the
local memory LM. This improvement makes the combinations more difficult to link
in case of providers' collusion.
Figure 4 illustrates step 6c wherein:
- The computing means generate different file identifiers I Ί , ID' n , for the
same file F, as a function of the local identifier ID, by a one way function, for
example a hash function- The computing means send, to a provider Oi the file
identifier ID' and the combination C , for i = 1, n, but they do not send any set
of coefficients.
- According to this variant c, the computing means locally store a larger file
descriptor, in the local memory LM. For i = 1,..., n, this file descriptor comprises
triplets, each triplet comprising for i = 1, n:
- an identifier ID' designating the file F,
- a service provider identifier O ,
- and the set of coefficients a^,..., a n that was used to construct the
combination C .
Figures 5, 6, 7 respectively illustrate three embodiments of the method for
retrieving a file that has been protected according to the invention. The retrieving
can be done according to three variants a, b, c corresponding to the variants 6a,
6b, 6c of step 6, described above for protecting the file.
Figure 5 illustrates the variant a:
To reconstruct the file F, the computing means of the device request a
combination and the set of coefficients corresponding to this combination, from
each of the n chosen storage service providers (in any order).
Step 5 1: The computing means read the file identifier ID' and the provider
identifiers , On registered in the file descriptor corresponding to the file F, in
the local memory LM. They send the identifier ID' to the storage service providers
Step 52: Then the computing means receive, from the provider O , for
i = 1,..., n:
- the combination Ci,
- and the corresponding set of coefficients aii,...,a n .
The combination Ci is directly associated to the set of coefficients aii,...,a n, for
the process of retrieving the file F.
Step 53: Then the computing means compute the inverse of the matrix A = (ay),
and obtain a matrix B = (by). Then they compute the original chunks as:
S = b .C + ... + by.Cj + ... + bn.Cn for i = 1, n.
Step 54: Then the computing means re-assemble the chunks Si, Sn and possibly
removes the padding to reconstruct the file F.
Note that if different identifiers ID' i, ID' n have been respectively stored at each
provider, for a same file F, the retrieval method is modified , since it comprises a
modified step 5 1 consisting in reading the different identifiers ID' i, ID' n in the
file descriptor, stored in the local memory LM, and respectively sending the
identifiers ID' i, ID' n to the n chosen providers, instead of sending the unique
identifier ID' .
Figure 6 illustrates the variant b:
To reconstruct the file F, the computing means of the device request a
combination and a set of coefficients, from each of the n chosen storage service
providers (in any order). But they must re-associate each combination with the
corresponding set of coefficients that was used for computing this combination,
since this combination and this set of coefficients were not stored at a same
storage service provider. The permutation s must be used again because the
combination C ( (corresponding to the set of coefficients stored by O ) is stored at
the provider O ( .
Step 61:
- The computing means read the file identifier ID' , the provider identifiers ,
On, and the permutation s, registered in the file descriptor corresponding to the
file F, in the local memory LM.
- They send the identifier ID' to the n storage service providers designated by the
provider identifiers , On.
- They receive, from the provider O for i = 1 n:
-- the combination C ,
-- and the set of coefficients , ( n
Step 62: Then they re-associate the combinations Ci and the corresponding set of
coefficients aii ,...,a n, for i = 1 n, by means of the permutation s.
Step 63: Then they compute the inverse of the matrix A = (a ), and obtain a
matrix B = (b ), and they compute the original chunks as:
S = b .C + ... + bij. Cj + ... + bn.Cn for i = 1 n.
Step 64: Then they reconstruct the file F by assembling then n chunks S , Sn
and possibly removing the padding.
Figure 7 illustrates the variant c:
To reconstruct the file F, the computing means of the device request a
combination and a set of coefficients corresponding to this combination, from
each of the n chosen storage service providers (in any order).
Step 7 1: The computing means read the file identifiers ID' 1, ID'n, and the
provider identifiers , On registered in the file descriptor corresponding to the
file F, in the local memory LM.
They send the file identifier ID' to the provider O for i = 1, n (The n
identifiers \D' ID' n are different one from another).
In response, the computing means receive the combination C from the provider
Step 72: They read the coefficients a^, a n in the local memory LM. The
combination C is directly associated t o the set of coefficients aii ,...,a n, for I = 1,
n.
Step 73: Then they compute the inverse of the matrix A = (a ), and obtain a
matrix B = (bj ). Then they compute the n original chunks as:
S = b .C + ... + b .C + ... + bjn.Cn for i = 1, n.
Step 74: Then they reconstruct the file F by assembling the n chunks S , Sn and
possibly removing the padding.
Security:
In every variant, a basic security of the scheme lays in the fact that it is
impossible to recover any chunk S without all the combinations C , Cn. Hence
the only possibility for operators t o break the confidentiality of the file F, is to
collude all together.
The variants a, b and c provide different levels of security, in the event of all n
operators are colluding:
- Variant a: If they collude all together, they obtain all the combinations and all
the sets of coefficients, then they can retrieve the full file F.
- Variant b: If they collude all together, they obtain all the combinations and the
coefficients but without knowing the correspondence between combinations and
sets of coefficients. In order to retrieve F, they must try all the n! correspondence
possibilities. If n is large enough, the processing cost becomes prohibitive in
practice.
- Variant c: If they collude all together, they obtain the combinations but they
don't know the sets of coefficients, so they cannot retrieve the file F, unless they
try all possible sets of coefficients, which proves to be computationally infeasible
(if each coefficient lies in a field of size p, there are p possibilities, so a careful
choice of p and n can easily make this value out of reach for processing
capabilities). This variant c offers the highest level of security; however it also
requires that the device stores the coefficients locally, whereas in variants a and
b the device does not have to store any additional information.
Resilience (optional improvement):
The only weakness of the method is that if one operator O loses (or corrupts) a
combination C , then it becomes impossible to retrieve the file F.
A first improvement, in order to circumvent this drawback, consists in generating
not n but n + k combinations and storing them at n + k operators. Then retrieving
any n combinations out of the n + k combinations is possible and sufficient to
reconstruct the file F. This means that it is possible to recover from the failure of
up to k storage service providers.
When storing at n + k operators, the security remains the same: At least n
operators have to collude to break the scheme. This solution applies well to the
variants a and c.
A different improvement for variant c, in order to circumvent this drawback,
consists in generating at least one additional combination (that we call overcombination)
on-the-fly; this can be performed without requiring to reconstitute
the original file F. An over-combination OC is a linear combination of the
combinations C for i = 1, n. This improvement comprises the steps of:
- randomly choosing a set of n coefficients a' (that we call super-coefficients)
for j = 1, n,
- computing a linear over-combination OC = a C + ... + a' .Cj + ... + a' n.Cn ,
- and storing the over-combination OC and the n super-coefficients a' .
The n super-coefficients a' and the over-combination OC can be generated and
stored by any entity comprising computing means and a memory. We call it
"orchestrator" because it manages the retrieving of the combinations and overcombinations
for ensuring resiliency. The orchestrator can be located at any place
in the network:
- It can be at a different cloud service provider, or possibly collocated with
one of the n storage service providers used for storing the combinations C for i
= 1,..., n.
- It may be in the user device
- It can also be in between the user device and the storage operators, for
example in a set-top box.
Functionally, the orchestrator is an intermediary in charge of managing
availability of the data without being necessarily trusted by the source. This
solution hence suits variant c very well, and the orchestrator is given the n
combinations , C Cn without the coefficients a^, a n for i = 1, n.
Retrieving the original file F is performed by a method similar to the method
described above because a linear over-combination OC = a + ... + a' .Cj + ... +
a'n. Cn is also a linear combination of the segments S\ for i = 1, n. Indeed C =
a .S + ... + ay .Sj + ... + ajn. Sn, for i = 1, n. The corresponding coefficients in
terms of the segments S\ are thus obtained by multiplying the coefficients a' of
the over-combination OC in terms of Cj, and the coefficients a of the
combinations C in terms of segments Sj.
We can express the over-combination OC in term of the segments S as follows:
C'= (a a + ... + a' .a + ... + a' n.ani).Si + ... + (a a + ... + a' .a + ... + a'n.a nj).Sj +
... + (a' .a + ... + a' .a n + ... + a' n.ann).Sn for i = 1, n
So the retrieving can be done by inverting a matrix.
For instance, the orchestrator that manages resiliency of the data in the cloud
comprises a memory for storing the combinations , ... , , Cn, and computing
means for:
- generating n super-coefficients a ..., a' n,
- and computing a super-combination OC = a + ... + a'j.Cj + ... + a' n.Cn .
(Optionally it can generate a plurality of sets of super-coefficients for computing a
plurality of super-combinations: one over-combination enables to circumvent the
loss of only one storage service provider, while k over-combinations enable to
circumvent the loss of k storage service providers). The over-combination OC is
then stored at a different storage provider. The orchestrator monitors the
availability of the combinations stored at the storage providers. Whenever the
Orchestrator detects a faulty storage operator, it generates an additional overcombination
and stores it at another storage provider.
For retrieving the original file F, the user device requests the retrieving of file F
(designated by an identifier ID') from the orchestrator.
The orchestrator requests the n combinations respectively from the n storage
operators.
- If the n storage operators are normally working, the orchestrator receives the n
combinations , ... , C Cn . The orchestrator forwards them to the user device.
This latter can reconstruct the file F as explained above.
- If one of the n storage operators is not working anymore, the orchestrator
receives n-1 combinations d , ... , C Cn-i because the storage provider that
stored the combination Cn has failed. Then the orchestrator forwards them to the
user device, along with an over-combination OC (fetched from the corresponding
storage provider) and the super-coefficients a ..., a' n.
The computing means of the user device retrieve all the segments Si, Sn by:
- Inverting the matrix constituted by the coefficients of the retrieved fragments
which are either directly the (a ) for j = 1, n for a chunk C or the (a a + ... +
a' .a + ... + a' n.anj ) for j = 1,..., n, for an over-combination OC With the inversion
the computing mean obtains another matrix composed of n sets of coefficients
b 1 , b n, for = 1, n.
- Then computing n chunks S , Sn of said file F as
S = b -C + ... + b .C + ... + bjn .O for i = 1 n.
- Then re-assembling the chunks S , Sn and removing padding to reconstruct the
file F.
The computation presented before with one over-combination can be generalized
to the case of a plu rality of over-combinations in a straightforward way. M supercombinations
enable t o cover the cases where up t o M storage operators have
failed . If k storage operators have failed (with k< M), n-k chunks (and n-k sets of
coefficients) and k over-combinations (with their associated coefficients) are used
for the matrix inversion. Since an over-combination can be expressed as an
original combination, by the formula C' = (a a + ... + + ... + a' n.an ) .S + ... +
(a a + ... + a' .a + ... + + ... + (a a + ... + a'i. a n + ... + a'n. ann). Sn for i
= 1, n, there is no difficulty t o use over-combinations instead of lost
combinations, both are processed in the same way.
The variant b, on the contrary, is strictly designed with n combinations and n2
coefficients for n chunks. Resilience to the loss of a combination could be
provided by another method, through redundancy or error coding but not as an
intrinsic feature of the proposed method .
Performance trade-off (optional improvement):
A key aspect of the proposed method is its efficiency and the fact that it
conciliates security and performance. To further stress on this aspect, we can
offer an additional trade-off in the computation between the user who stores the
data (we will call it the source for simplicity) and the users who retrieve the data
(we wi ll call them fetchers as they are not necessarily the same as the one who
stores the data). In the above described embodiments, the source performs the
combination and the fetchers perform the reconstruction which implies a matrix
inversion, so the efforts are halved between the source and the fetchers.
However, we can also propose that the source computes the combinations and
additionally pre-computes the inverse matrix and directly stores the coefficients
b of the inverse matrix instead of the direct coefficients a , at the storage
service providers or at the local memory LM. This will then enable fetchers to
retrieve directly the inverse matrix and perform a simple matrix multiplication to
reconstruct the file F. Hence this mode of operation increases the computation
burden on the source but drastically decreases it for the fetchers, and is therefore
well suited in situations where the storage is performed once but retrieval is
performed many times or by many entities. This mode of operation is compatible
with all three approaches (a), (b) and (c).
Figure 8 illustrates first steps that are common to three embodiments of the
method for protecting a file, according to the invention, these embodiments being
peculiarly well suited in situations where the storage is performed once but
retrieval is performed many times or by many entities. The first steps are
modified in order to pre-compute the inverse matrix and directly store the
coefficients by of the inverse matrix instead of the direct coefficients ay. A step 4'
is introduced between the step 3 providing the n2 coefficients a ay, ann, and
the step 6a, or 6b, or 6c storing these coefficients, either at the providers or at
the local memory LM.
As concerns retrieving the file F, the reconstruction steps 53, 63, 73 are modified
by suppressing the computation of the inverse of the matrix A = (ay), since the
computing means directly receive a matrix B = (by) either from the providers or
from the local memory LM.
A final remark concerns the local memory LM to store file descriptors that the
device has to store in all three variants (although they have different sizes and
contain different information). There are multiple possibilities to store these
descriptors, which meet different security levels. The descriptors could indeed be
stored:
- in a tamper-proof hardware such as a smart card,
- on a local removable storage device (e.g. USB key, portable hard-drive, ...) that
would be removed after the descriptor has been stored, in order to physically
prevent further access to it,
- in a secured storage space managed by an Internet Service provider (e.g. on the
set-top box),
- on a simple local storage device (e.g. laptop's hard-drive),
- at yet another storage service provider, e.g. in the cloud.
The first two options are particularly relevant for very secret documents in
combination with variant c, while the last one should not be used except for not
so sensitive data in combination with variant a, and with some guarantee that this
last provider will not collude with the previous ones.
THERE IS CLAIMED:
1) Method for protecting confidentiality of a file (F) distributed and stored at a
plurality of storage service providers, comprising the steps of:
- choosing ( 1 ) a security parameter n,
- segmenting (2) the file in n chunks S ,...,S n,
- choosing (3) n2 coefficients a for i = 1 n and j = 1 n,
- verifying (3) that the vectors aii,...,a n, for i = 1,..., n, are linearly independent,
otherwise generating the coefficients again,
- computing (4) n linear combinations C = a S + ... + a .S + ... + a n. Sn,
for i = 1, n,
- choosing (5) n storage service providers O , On among said plurality of storage
service provider,
- generating (6a; 6b; 6c) n file identifiers \D' ID' n designating said file (F),
- storing (6a; 6b; 6c) the combination C at the storage service provider O in
association with the file identifier ID' , for i = 1, n,
- storing the file identifier ID' and the provider identifier O , for i = 1,..., n, in a
file descriptor corresponding to the file (F), this file descriptor being stored in a
local memory (LM),
- and storing the set of coefficients a^, a n so that it can be re-associated with
the combination C , for i = 1, n;
characterized in that it further comprises the steps of:
- randomly choosing (3) said n2 coefficients a for i = 1,..., n and j = 1,..., n,
- verifying (3) that the vectors aii,...,a n, for i = 1,..., n, are linearly independent,
otherwise generating the coefficients again,
- randomly choosing n super-coefficients a a'j, ... , a' n for j = 1 n,
- computing a linear over-combination O = a C + ... + a' .Cj + ... + a' n.Cn ,
- and storing the over-combination OC and the coefficients a a'j, ... , a' n for
j = 1, n.
2) Method according to claim 1, wherein storing the set of coefficients a^, a n,
so that it can be re-associated with the combination C , for i = 1, n, comprises
the step of storing them (6a) at the storage service provider O , in association with
the combination C and the file identifier ID' , for i = 1, n.
3) Method according to claim 1, wherein storing the set of coefficients a^, a n,
so that it can be re-associated with the combination C for i = 1, n, comprises
the steps of:
- storing (6b) the set of coefficients a^, a n, at the storage service provider Ok,
in association with a combination Ck and a file identifier ID' k , for i = 1, n and
for k lying between 1 and n, including 1 and n, and being different of i ;
- and storing (6b) a permutation (s) enabling to re-associate the set of coefficients
a^, a n and the combination C for i = 1, n, in said file descriptor
corresponding to the file (F), and being stored in said local memory (LM).
4 ) Method according to claim 1, wherein storing the set of coefficients a^, a n
so that it can be re-associated with the combination C for i = 1, n, comprises
the step of storing the set of coefficients a^,..., a n in association with a file
identifier ID' and a provider identifier O , for i = 1, n, in said file descriptor
corresponding to the file (F), and being stored in said local memory (LM).
5) Method according to one of the claims 1-4, wherein the n file identifiers
ID' , ID'n are the same (ID') for a given file (F).
6) Method for retrieving a file (F) distributed and stored at a plurality of storage
service providers, comprising the steps of:
- reading (51 ) n file identifiers ID' , ID' n designating said file, and reading
provider identifiers , On, in a file descriptor corresponding to the file (F), this
file descriptor being stored in a local memory (LM),
- sending (51 ) the n file identifiers \D' ID' n respectively to the storage service
providers designated by the provider identifiers , On ,
- receiving (51 ) n combinations C , Cn, from the providers designated by the
provider identifiers , On ,
- retrieving n sets of coefficients a^, a n, for i = 1, n, that respectively
correspond to the n combinations C , Cn,
- associating (52; 62; 72) each combination with the corresponding set of
coefficients a^, a n, for i = 1, n,
- computing (53; 63; 73) the inverse of a matrix composed of the n set of
coefficients aii,...,ai n, for i = 1,..., n, for obtaining another matrix composed of n
sets of coefficients bii,...,b n, for i = 1, n,
- then computing n chunks Si, Sn of said file (F) as:
S = b .C + ... + bij.Cj + ... + b n.Cn for i = 1, n,
- then re-assembling (54; 64; 74) the chunks Si, Sn to reconstruct the file F;
characterized in that it further comprises the steps of:
- reading an over-combination O and coefficients a a' ... , a' n
for j = 1, n,
- computing the inverse of a matrix composed of n-1 sets of coefficients
aii,...,a n, for i = 1, n-1 and a set of coefficients (a a + ... + a' .a + ... +
a' n.anj ) for j = 1, n, for obtaining another matrix composed of n sets of
coefficients b , ...,b n, for i = 1, n,
- then computing n chunks Si, Sn of said file (F) as:
S = b .C + ... + bij.Cj + ... + bin-i.Cn-1 + b n.OC' for i = 1, n,
- then re-assembling the chunks Si, Sn to reconstruct the file (F).
7) Method according to claim 6, wherein retrieving n sets of coefficients aii,...,a n
for i = 1, n that respectively correspond to the n combinations Ci, Cn,
comprises the step of receiving (51 ) them from the providers designated by the
provider identifiers , On ,
And wherein associating (52) each combination Ci with a corresponding set of
coefficients a^, ain, for i = 1, n, comprises the step of directly associating the
combination Ci with the set of coefficients a^, a n.
8) Method according to claim 6, wherein retrieving n sets of coefficients aii,...,a n
for i = 1, n that respectively correspond to the n combinations Ci, Cn,
comprises the step of receiving (51 ) them from the providers designated by the
provider identifiers , On ;
and wherein associating (62) each combination C with a corresponding set of
coefficients a^, ain, for i = 1, n comprises the steps of:
- reading a permutation (s) in the file descriptor corresponding to said file (F),
- and applying the permutation to the sets of coefficients aii,...,ai n, for i = 1,..., n,
so that each combination C is associated with the corresponding set of
coefficients aii,...,ai n, for i = 1,..., n.
9) Method according to claim 6, wherein retrieving n sets of coefficients aii,...,a n,
for i = 1, n that respectively correspond to the n combinations Ci, Cn,
comprises the step of reading them in the file descriptor corresponding to said
file (F),
and wherein associating (72) each combination C with a corresponding set of
coefficients aii,...,ai n, for i = 1,..., n comprises the step of directly associating the
set of coefficients aii,...,a n to the combination Cj, for i = 1,..., n.
10) Method according to one of the claims 6-9, wherein said n file identifiers ID'i,
ID' n are identical (ID') for a given file (F).
11) Method for protecting confidentiality of a file (F) distributed and stored at a
plurality of storage service providers, comprising the steps of:
- choosing ( 1 ) a security parameter n,
- segmenting (2) the file in n chunks Si, ...,Sn,
- randomly choosing (3) n2 coefficients a for i = 1, n and j = 1, n,
- verifying (3) that the vectors a^, ...,a n, for i = 1, n, are linearly independent,
otherwise generating the coefficients again,
- computing (4) n linear combinations C = a S + ... + ay.S + ... + airi .Sn,
for i = 1, n,
- choosing (5) n storage service providers Oj, On among said plurality of storage
service provider,
- generating (6a; 6b; 6c) n file identifiers ID'i, ID' n designating said file (F),
- storing (6a; 6b; 6c) the combination C at the storage service provider O in
association with the file identifier ID'i , for i = 1, n,
- storing the file identifier ID'i and the provider identifier Oj, for i = 1, n, in a
file descriptor corresponding to the file (F), this file descriptor being stored in a
local memory (LM),
- computing (4' ) the inverse of a matrix composed of the n set of coefficients
a ,...,ain, for i = 1,..., n, for obtaining another matrix composed of n sets of
coefficients bii ,...,b n, for i = 1,..., n,
- and storing the set of coefficients b 1 , b n so that it can be re-associated with
the combination C , for i = 1, n;
characterized in that it further comprises the steps of:
- randomly choosing (3) said n2 coefficients a for i = 1, n and j = 1, n,
- and verifying (3) that the vectors a^, ...,a n, for i = 1, n, are linearly
independent, otherwise generating the coefficients again.
12 ) Method according to claim 11, wherein storing the set of coefficients b^,..., b n
so that it can be re-associated with the combination Cj, for i = 1,..., n, comprises
the step of storing them (6a) at the storage service provider Oj, in association with
the combination C and the file identifier ID'j , for i = 1,..., n.
13) Method according to claim 11, wherein storing the set of coefficients b , b n
so that it can be re-associated with the combination Cj, for i = 1, n, comprises
the steps of:
- storing (6b) the set of coefficients b b n at the storage service provider Ok, in
association with a combination Ck and a file identifier ID' k , for i = 1,..., n and for
k lying between 1 and n, including 1 and n, and being different of i ;
- and storing (6b) a permutation (s) enabling to re-associate the set of coefficients
b ,..., bjn and the combination Cj, for i = 1,..., n, in said file descriptor
corresponding to the file (F), and being stored in said local memory (LM).
14 ) Method according to claim 11, wherein storing the set of coefficients b^,..., b n
so that it can be re-associated with the combination Cj, for i = 1,..., n, comprises
the step of storing the set of coefficients b^,..., b n in association with the file
identifier ID' i and the provider identifier ID'j, for i = 1,..., n, in said file descriptor
corresponding to the file (F), and being stored in said local memory (LM).
15) Method according t o one of the claims 11- 14 , wherein the n file identifiers
ID' , ID'n are the same for a given file (F).
16) Method for retrieving a file (F) distributed and stored at a plurality of storage
service providers, comprising the steps of:
- reading (51 ) n file identifiers \D' ID' n designating said file, and reading
provider identifiers , On, in a f i le descriptor corresponding t o the file (F), this
file descriptor being stored in a local memory (LM),
- sending (51 ) the n file identifiers \D' ID' n respectively to the storage service
providers designated by the provider identifiers , On ,
- receiving (51 ) n combinations C , Cn, from these providers designated by the
provider identifiers , On ,
- retrieving n sets of coefficients b 1 , b n, for i = 1, n that respectively
correspond to the n combinations C , Cn,
- associating (52; 62; 72) each combination with the corresponding set of
coefficients b 1 , b n, for i = 1, n,
- computing (53; 63; 73) chunks S , Sn of said file (F) as:
S = b .C + ... + b .C + ... + b n.Cn for i = 1 n,
- then re-assembling (54; 64; 74) the chunks S , Sn to reconstruct the file F.
17) Method according to claim 16, wherein retrieving n sets of coefficients
a ,...,a n for i = 1, n that respectively correspond to the n combinations C ,
Cn, comprises the step of receiving (51 ) them from the providers designated by the
provider identifiers , On ,
and wherein associating (52) each combination C with a corresponding set of
coefficients b 1 , b n for i = 1, n, comprises the step of directly associating the
combination C with the set of coefficients b 1 , b n.
18) Method according to claim 16, wherein retrieving n sets of coefficients b ,...,
b n for i = 1, n that respectively correspond to the n combinations C , Cn,
comprises the step of receiving (51 ) them from the providers designated by the
provider identifiers , On ;
and wherein associating (62) each combination C with a corresponding set of
coefficients b , b n for i = 1, n comprises the steps of:
- reading a permutation (s) in the file descriptor corresponding to said file (F),
- and applying the permutation to the sets of coefficients b b n for i = 1,..., n,
so that each combination C is associated with the corresponding set of
coefficients b b n for i = 1,..., n.
19) Method according to claim 16, wherein retrieving n sets of coefficients b ,...,
b n for i = 1, n that respectively correspond t o the n combinations C , Cn,
comprises the step of reading them in the file descriptor corresponding to said
file (F),
and wherein associating (72) each combination C with a corresponding set of
coefficients for i = 1, n comprises the step of directly associating the set of
coefficients b , b n to the combination C , for i = 1, n.
20) Method according t o one of the claims 16 - 19, wherein said n file identifiers
ID' , ID'n are identical ( ID' ) for a given file (F).
2 1) A digital data storage medium storing a set of machine executable program
instructions, which, when executed on a computer, cause the computer to
perform all the method steps of a method according to one of the claims 1-20
22) A computer program product comprising computer-executable instructions for
performing a method when the program is run on a computer, the method
comprising the steps of one of the claims 1-20.
AMENDED CLAIMS
received by the International Bureau on 23 August 20 3
1) Method for protecting confidentiality of a file (F) distributed and stored at a
plurality of storage service providers, comprising the steps of:
- choosing ( 1 ) a security parameter n,
- segmenting (2) the file in n chunks S ,...,Sn,
- choosing (3) n2 coefficients a for i = 1,..., n and j = 1,..., n,
- verifying (3) that the vectors a , , , for i = 1,..., n, are linearly independent,
otherwise generating the coefficients again,
- computing (4) n linear combinations = a .S + ... + a j .S + ... + a .Sn,
for i = 1, n,
- choosing (5) n storage service providers Oj, O among said plurality of storage
service provider,
- generating (6a; 6b; 6c) n file identifiers \D' ID' designating said file (F),
- storing (6a; 6b; 6c) the combination at the storage service provider Oj in
association with the file identifier ID'j , for i = 1, n,
- storing the file identifier ID'j and the provider identifier O , for i = 1,..., n, in a
file descriptor corresponding to the file (F), this file descriptor being stored in a
local memory (LM),
- and storing the set of coefficients ai a so that it can be re-associated with
the combination C for i = 1, n;
wherein choosing (3) n coefficients a for i = 1,..., n and j = 1,..., n, comprises
the steps of:
- randomly choosing (3) said n2 coefficients for i = 1,..., n and j = 1,..., n,
- verifying (3) that the vectors a ,..., a , for i = 1,..., n, are linearly independent,
otherwise generating the coefficients again,
- randomly choosing n super-coefficients a a' , ... , a'n for = 1, ..., n,
- computing a linear over-combination O = a C + ... + a' .C + ... + a' .C ,
- and storing the over-combination OC and the coefficients a' a' ... , a' for
j = 1, n;
and wherein storing the set of coefficients a , a n, so that it can be reassociated
with the combination , for i = 1, n, comprises the steps of:
- storing (6b) the set of coefficients a , a n, at the storage service provider Ok,
in association with a combination Ck and a file identifier ID' k , for i = 1, n and
for k lying between 1 and n, including 1 and n, and being different of i ;
- and storing (6b) a permutation (s ) enabling to re-associate the set of coefficients
a ·, ajn and the combination , for i = 1, n, in said file descriptor
corresponding to the file (F), and being stored in said local memory (LM).
2) Method according to claim 1, wherein storing the set of coefficients a , ain,
so that it can be re-associated with the combination C for i = 1, n, comprises
the step of storing them (6a) at the storage service provider 0 , in association with
the combination C and the file identifier ID' , for i = 1, n.
3) Method according to claim 1, wherein storing the set of coefficients », a n
so that it can be re-associated with the combination C , for i = 1, n, comprises
the step of storing the set of coefficients an, ..., a,n in association with a file
identifier ID', and a provider identifier 0 , for i = 1, n, in said file descriptor
corresponding to the file (F), and being stored in said local memory (LM).
4) Method according to one of the claims 1-3, wherein the n file identifiers
ID' , ID'n are the same (ID' ) for a given file (F).
5) Method for retrieving a file (F) distributed and stored at a plurality of storage
service providers, comprising the steps of:
- reading (51 ) n file identifiers I , ID' n designating said file, and reading
provider identifiers 0 On, in a file descriptor corresponding to the file (F), this
file descriptor being stored in a local memory (LM),
- sending (51 ) the n file identifiers \D , ID' n respectively to the storage service
providers designated by the provider identifiers O , On ,
- receiving (51 ) n combinations Ci , Cn, from the providers designated by the
provider identifiers 0 On ,
- retrieving n sets of coefficients a , ain, for i = 1, n, that respectively
correspond to the n combinations Cn,
- associating (52; 62; 72) each combination with the corresponding set of
coefficients a», a , for i = 1, n,
- computing (53; 63; 73) the inverse of a matrix composed of the n set of
coefficients ai ...,a in> for i = 1, ..., n, for obtaining another matrix composed of n
sets of coefficients b^,...,^, for i = 1, n,
- then computing n chunks S S of said file (F) as:
Sj = bji.Ci + ... + b .C + ... + bjn.Cn for = 1, n,
- then re-assembling (54; 64; 74) the chunks S , S to reconstruct the file F,
- reading an over-combination O and coefficients a a'j, ... , a'n
for j = 1, n,
- computing the inverse of a matrix composed of n-1 sets of coefficients
ai ,...,a i , for i = 1, n-1 and a set of coefficients a . + ... + a*j. a j + ... +
a' .anj ) for j = 1, n, for obtaining another matrix composed of n sets of
coefficients b , ...,b n, for i = 1, n,
- then computing n chunks S , Sn of said file (F) as:
S = b .Ci + ... + bi .Cj + ... + bjn.i.C n- + bjn.O for i = 1, n,
- then re-assembling the chunks S, , S to reconstruct the file (F);
wherein retrieving n sets of coefficients aii , ...,a in for i = 1, n that respectively
correspond to the n combinations Ci, C„, comprises the step of receiving (51 )
them from the providers designated by the provider identifiers , O ;
and wherein associating (62) each combination C with a corresponding set of
coefficients af , ain, for i = 1, n comprises the steps of:
- reading a permutation (s) in the file descriptor corresponding to said file (F),
- and applying the permutation to the sets of coefficients for i = 1, ..., n,
so that each combination is associated with the corresponding set of
coefficients a ,...,ajn, for i = 1 n.
6) Method according to claim 5, wherein retrieving n sets of coefficients a ,...,aj n
for i = 1, n that respectively correspond to the n combinations Cn,
comprises the step of receiving (51 ) them from the providers designated by the
provider identifiers Oi, O ,
And wherein associating (52) each combination Ci with a corresponding set of
coefficients a , a,n, for i = 1, n, comprises the step of directly associating the
combination Ci with the set of coefficients a , ai .
7) Method according to claim 5, wherein retrieving n sets of coefficients a^,...,a in,
for i = 1, n that respectively correspond to the n combinations C Cn,
comprises the step of reading them in the file descriptor corresponding to said
file (F),
and wherein associating (72) each combination with a corresponding set of
coefficients aji,...,a in, for i = 1,..., n comprises the step of directly associating the
set of coefficients aji,...,a to the combination C for i = 1,..., n.
8) Method according to one of the claims 5-7, wherein said n file identifiers \D'
ID'n are identical (ID') for a given file (F).
9) Method for protecting confidentiality of a file (F) distributed and stored at a
plurality of storage service providers, comprising the steps of:
- choosing ( 1 ) a security parameter n,
- segmenting (2) the file in n chunks S ...,Sn,
- randomly choosing (3) n2 coefficients ajj for i = 1, n and j = 1, n,
- verifying (3) that the vectors a,i, ...,a in, for i = 1, n, are linearly independent,
otherwise generating the coefficients again,
- computing (4) n linear combinations = a S + ... + ajj .S + ... + a,n.S ,
for i = 1, n,
- choosing (5) n storage service providers Oi, On among said plurality of storage
service provider,
- generating (6a; 6b; 6c) n file identifiers \D' ID' designating said file (F),
- storing (6a; 6b; 6c) the combination C, at the storage service provider O, in
association with the file identifier ID' , for i = 1, n,
- storing the file identifier ID' and the provider identifier Oj, for i = 1, n, in a
file descriptor corresponding to the file (F), this file descriptor being stored in a
local memory (LM),
- computing (4') the inverse of a matrix composed of the n set of coefficients
aji,...,a n, for i = 1,..., n, for obtaining another matrix composed of n sets of
coefficients b n r i = 1,..., n,
- and storing the set of coefficients b , bi so that it can be re-associated with
the combination , for i = 1, n,
- randomly choosing (3) said n coefficients a for i = 1, n and = 1, n,
- and verifying (3) that the vectors a , ...,a , for i = 1, n, are linearly
independent, otherwise generating the coefficients again;
wherein storing the set of coefficients b , b so that it can be re-associated
with the combination Cj, for i = 1, n, comprises the steps of:
- storing (6b) the set of coefficients bn,..., b n at the storage service provider Ok, in
association with a combination Ck and a file identifier ID' k , for i = 1,..., n and for
k lying between 1 and n, including 1 and n, and being different of i;
- and storing (6b) a permutation (s) enabling to re-associate the set of coefficients
bn,..., bin and the combination C for i = 1,..., n, in said file descriptor
corresponding to the file (F), and being stored in said local memory (LM).
10) Method according to claim 9, wherein storing the set of coefficients bn,..., bin
so that it can be re-associated with the combination C for i = 1,..., n, comprises
the step of storing them (6a) at the storage service provider Oj, in association with
the combination C j and the file identifier ID'j , for i = 1,..., n.
11) Method according to claim 9, wherein storing the set of coefficients bn,..., bin
so that it can be re-associated with the combination Cj, for i = 1,..., n, comprises
the step of storing the set of coefficients bn, ..., bin in association with the file
identifier ID'i and the provider identifier ID'j, for i = 1,..., n, in said file descriptor
corresponding to the file (F), and being stored in said local memory (LM).
12) Method according to one of the claims 9-1 1, wherein the n file identifiers \D'
ID'n are the same for a given file (F).
13) Method for retrieving a file (F) distributed and stored at a plurality of storage
service providers, comprising the steps of:
- reading (51 ) n file identifiers I , ID' n designating said file, and reading
provider identifiers O , On, in a file descriptor corresponding to the file (F), this
file descriptor being stored in a local memory (LM),
- sending (51 ) the n file identifiers \D , ID' respectively to the storage service
providers designated by the provider identifiers O , O ,
- receiving (51 ) n combinations Ci, C , from these providers designated by the
provider identifiers O , On ,
- retrieving n sets of coefficients b , bi , for i = 1, n, that respectively
correspond to the n combinations Ci, Cn,
- associating (52; 62; 72) each combination with the corresponding set of
coefficients bn, b , for i = 1, n,
- computing (53; 63; 73) chunks S , S of said file (F) as:
S = b .C + ... + bjj .C + ... + n. n for i = 1,..., n,
- then re-assembling (54; 64; 74) the chunks S , S to reconstruct the file F;
wherein retrieving n sets of coefficients bn, ..., bi for i = 1, n that respectively
correspond to the n combinations C , C , comprises the step of receiving (51 )
them from the providers designated by the provider identifiers , On ;
and wherein associating (62) each combination with a corresponding set of
coefficients b 1 , b for i = 1, n comprises the steps of:
- reading a permutation (s) in the file descriptor corresponding to said file (F),
- and applying the permutation to the sets of coefficients bn,..., b for i = 1,..., n,
so that each combination C is associated with the corresponding set of
coefficients b ,..., bin for i = 1,..., n.
14) Method according to claim 13, wherein retrieving n sets of coefficients
aji,...,a for i = 1, n that respectively correspond to the n combinations Ci,
C , comprises the step of receiving (51 ) them from the providers designated by the
provider identifiers Oi, On ,
and wherein associating (52) each combination with a corresponding set of
coefficients b , b n for i = 1, n, comprises the step of directly associating the
combination with the set of coefficients bn, bjn .
15) Method according to claim 13, wherein retrieving n sets of coefficients b , ...,
bin for i = 1, n that respectively correspond to the n combinations Ci, Cn,
comprises the step of reading them in the file descriptor corresponding to said
file (F),
and wherein associating (72) each combination with a corresponding set of
coefficients for i = 1, n comprises the step of directly associating the set of
coefficients b», bin to the combination , for i = 1, n.
16) Method according to one of the claims 13 - 15, wherein said n file identifiers
ID',, ID'n are identical (ID') for a given file (F).
17) A digital data storage medium storing a set of machine executable program
instructions, which, when executed on a computer, cause the computer to
perform all the method steps of a method according to one of the claims 1-16
18) A computer program product comprising computer-executable instructions for
performing a method when the program is run on a computer, the method
comprising the steps of one of the claims 1-16.