INTRODUCTION
As more information becomes available in digital format, enormous quantities of data are created. With the increasing requirement to both temporarily and permanently retain information, the secure storage technique is attracting much attention. In a data storage system, the storage medium for preserving the information is an important target to a malicious attacker. Once the attacker breaks the system, he can gain unauthorized information, disclose some valuable secrets or prevent the access of legitimate users. In order to avoid these risks, the researchers have proposed many potential systems for securing stored information, such as NASD (Gobioff et al., 1999, 1997), PASIS (Ganger et al., 2001; Wylie et al., 2000), CFS (Blaze, 1993), SNAD (Freeman and Miller, 2000; Miller et al., 2001) and PLUTUS (Kallahalla et al., 2003) and so on. Moreover, all these researches come into being a field of computer research. Currently, the major target of a secure storage system is ensuring information confidentiality, integrity and availability without substantially degrading performance.
Kallahalla et al. (2003) present a secure storage scheme, PLUTUS, in 2003. The primary goal of the scheme is to provide file owners with direct control over authorizing access to their files as well as scalable key management. Key revocation is a major problem in secure storage system. Due to the proliferation of keys and the use of file groups, the key revocation is very complicated. Since several files in the file system are encrypted with the same key, key revocation will result in mass reencryption.
However, Kallahalla et al. (2003) designed a key rotation scheme to alleviate the negative effects. The key rotation scheme can make the updated secret key relate to the previous versions. For the user of PLUTUS, when he is allowed access to a certain reencrypted files using given filegroup key, then he can generate previous versions from the given key. In other words, any valid user can regenerate the matching key for a given file if he has the latest filegroup key. Therefore, we call the key rotate scheme designed by Kallahalla Forward Key Rotate (FKR) scheme.
The security of the FKR presented by Kallahalla et al. (2003) is based on the RSA. However, limited by the prime generation technique, producing a pair of suitable keys used in RSA scheme is not an easy thing. Moreover, until now there is no way to show the strength of the RSA is equivalent to that of decomposing a large number. Currently, RSA based schemes use relatively long keys compared to the security they provide. In this aspect, a scheme based on elliptic curves provides much shorter keys. As the requirement of practice, it is necessary to design other KFR storage scheme related to different intractable problems.
In this study, we first present a FKR storage scheme based on discrete logarithm and discuss its security. Subsequently, we present an improved FKR storage scheme from pairings on elliptic curves. Compared to the mechanism presented by Kallahalla et al. (2003) the improved scheme provides relatively short keys to perform the same function. Moreover, the user can verify the validity of the regenerated keys via bilinear pairings.
KALLAHALLA et al.’ FORWARD KEY ROTATION SCHEME
Kallahalla et al. (2003) proposed a Forward Key Rotation scheme used
in PLUTUS system in 2003. In this section, we will briefly review their FKR
scheme. Suppose that there exists a secure RSA encrypt scheme as defined in
Rivest et al. (1978). Let U_{0} be a user who will establish
a FKR scheme, e_{0} be the public key of U_{0} and d_{0}
be the matching private key.
• 
User U_{0} chooses k_{0}εZ^{*}_{q}
uniformly at random and computes 
• 
When user U_{i≠o} wants to access the FKR scheme,
the user U_{0} gives U_{i≠o} the latest key .
Hence, U_{i≠o} has ability to compute and
get any k_{z≤l}. 
The security of the scheme is based on RSA. Kallahalla et al. (2003) simplify the key management of PLUTUS using this FKR scheme.
PRELIMINARIES
Complexity assumptions: We assume that a prime p is chosen at random
such that p1 has a large prime factor q. Let g be an element of order q. Define
the following problems.
• 
Computation diffiehellman (CDH): Given g^{a},
g^{b} for unknowns a, b εZ^{*}_{q}, compute
g^{ab}εZ^{*}_{q}. 
• 
Decision diffiehellman (DDH): Given g^{a}, g^{b},
g^{c} for unknowns a, b, c εZ^{*}_{q}, decide
whether g^{ab} = g^{c}. 
• 
Kexponent assumption (kE): Given for
unknown x, compute (Zhang
et al., 2004). 
Bilinear maps: Let G_{1} be a cyclic multiplicative group generated
by g, whose order is a prime q and G_{2} be a cyclic multiplicative
group of the same order q. Assume that the discrete logarithm in both G_{1}
and G_{2} is intractable. A bilinear pairing is a map: G_{1}xG_{1}→G_{2}
and satisfies the following properties:
• 
Bilinear: e(g^{a}, p^{b}) = e(g, p)^{ab}.
For all g, p ε G_{1} and a, b ε Z_{q}, the equation
holds. 
• 
Nondegenerate: There exists p ε G_{1}, if e(g, p)
= 1, then g = 0. 
• 
Computable: For g, p ε G_{1}, there is an efficient
algorithm to compute e(g, p). 
Typically, the map e will be derived either from the modified Weil pairing (Boneh et al., 2001; Boneh and Franklin, 2003) or the tate pairing (Paulo et al., 2002) on an elliptic curve over a finite field. Pairings and other parameters should be selected in proactive for efficiency and security. In group G_{1}, the CDH and KE assumptions defined are intractable. However, the DDH assumption is tractable.
General scheme: A FKR storage scheme consists of four algorithms.
• 
Initialize: Given the security parameter l, the algorithm
outputs the system parameters. 
• 
Key generation (i): Input the number i, output ith secret key
K_{i} used to encrypt ith files. 
• 
Encrypt (K_{i+1}, K_{i}, File_{i}): Input
two secret keys (K_{i+1}, K_{i}) and a file File_{i}.
The algorithm encrypts File_{i} using (K_{i+1}, K_{i})
and outputs the corresponding ciphertext EF_{i}. 
• 
Decrypt (K_{i+1}, K_{i}, K_{i}): Input
the ciphertext EF_{i} and the secret keys (K_{i+1}, K_{i}).
The algorithm decrypts the ciphertext using the secret key (K_{i+1},
K_{i}) and outputs the corresponding plaintext File_{i}.

Security notions: We define adaptively chosen ciphertext security of
a FKR storage scheme. Security is defined using the following game between an
Attacker and Challenger.
• 
Setup: The Challenger initializes the system. The Challenger
gives the Attacker the resulting system parameters. 
• 
Query phase 1: The Attacker adaptively issues encrypt queries q_{1},
q_{2}, ..., q_{m} and decryption queries q_{1},
q_{2}, ..., q_{m}, respectively. The Challenger simulates
Encrypt and Decrypt, respectively and responds with matching answers. 
• 
Challenge:Once the Attacker decides that Query phase 1 is over
it outputs two equal length files (File_{0}, File_{1}) to
the Challenger. The Challenger picks a random bit λε{0, 1} and
encrypts the message File_{λ}. It gives ciphertext C to the
Attacker. 
• 
Query phase 2: The Attacker continues to adaptively issue encryption
and decryption queries. The Challenger responds as in the phase 1. These
queries may be asked adaptively as in Query phase 1. Note that the decrypt
query q_{j} = C is not permitted, where 0≤j≤n. 
• 
Guess: Finally, the Attacker outputs a guess λ'ε{0, 1}
for λ and wins the game if λ' = λ. 
The storage scheme is secure against chosen ciphertext attack, if the Attacker has a negligible advantage ε = Pr(λ = λ')1/2 to win the game.
FORWARD KEY ROTATION STORAGE SCHEME
In this part of study, we will design a FKR storage scheme related to discrete
logarithm. We suppose that Server who has a series of files {File_{1},
File_{2}, ..., File_{n}} will establish the FKR storage scheme
and a user Alice asks to access it. Let p be a large prime and 〈g〉
be a cyclic multiplicative group generated by g, whose order is a prime q such
that q(p1). There exists a pair of security algorithms (E, D), where the algorithm
E is a secure encryption algorithm based on discrete logarithm and D is the
matching decryption algorithm.
Step 1: Server chooses a random number r ∈ Z^{*}_{q}
and computes as
a secret key.
Step 2: Server generates the encrypted files ,
where a  b denotes the concatenate of a and b. Thereafter, server publishes
all encrypted files.
When Alice asks to access to the FKR storage scheme at the point j, Server sends the secret key K_{j+1} to Alice. Since Alice can obtain any encrypted files, she can compute
and get K_{j} and File_{j}. Similarly, Alice can obtain K_{j1} and File_{j1} via K_{j} and EF_{j1}.
However, by the KE assumption defined already, Alice can’t produce the secret key K_{j+2} using K_{j} and K_{j+1}. In other words, Alice doesn’t have ability to decrypt EF_{j+1} even though she has secret key K_{i≤j+1}.
SECURITY
The security of the scheme is partly based on the algorithms (E, D). Thereby,
we assume that these two algorithms are secure. Given ,
one can’t deduce by
the KE assumption mentioned already. It means that if Server gives an access
point at j, one can’t access to the files File_{k}, where k>j.
Then we will give the following theorem to show the security of the proposed storage scheme.
Theorem: We assume that an attacker Eve who can, with success probability ε, break the FKR storage scheme within a time τ by asking Encrypt and Decrypt oracles at most q_{E} and q_{D} queries respectively, then there exists a challenger Alice who running in a time τ' can solve the DDH problem with success probability ε', where
where, t_{ED} is the time for performing an encryption or decryption algorithm.
Proof: We assume that Eve is an attacker who has the ability to break
the storage scheme. Then there exists a challenger Alice who can solve the DDH
problem by running Eve as a subroutine. The system chooses a random bit bε{0,
1} and a random number rεZ^{*}_{q}. The challenger Alice
is given .
If b = 1, the system sets ,
otherwise, chooses a random number TεZ^{*}_{p}.
The attacker Eve is allowed to issue Encrypt, Decrypt and Challenge queries. The challenger Alice will simulate the corresponding oracles to output the answers.
Query phase 1: The attacker Eve is allowed to issue following queries.
Encrypt queries: Eve chooses a random number jε[l, k] and takes
the file File_{j} and then issues query on (j, File_{j}).
• 
If j ≠ i, Alice computes and
outputs EF_{j} as the answer, where and
. 
• 
If j = i, Alice outputs error messages and halts. 
Decrypt queries: Eve chooses a random number jε[l, k] and takes
the ciphertext EF_{j} and then issues query on (j, EF_{j}).
• 
If j ≠ i, Alice computes and
outputs K_{j} and File_{j} as the answer, where and
. 
• 
If j = i, Alice outputs error message and halts. 
Since above simulation is perfect, the attacker Eve can’t distinguish the simulated result from the actual results. The above queries can be asked several times. When Eve decides this phase is over, he issues challenge query.
Challenge query: Eve outputs two equal length files File_{0} and File_{1} to Alice. Upon receiving the two files, Alice chooses a random bit λε{0, 1} and computes
where, Thereafter,
Alice sends EF_{j} to Eve as the answer.
Note that the Challenge query is allowed only once.
Query phase 2: The attacker Eve continues to adaptively issue encryption and decryption queries. The challenger Alice will respond as in the phase 1. However, decryption query q_{j} = EF_{i} is not permitted. We assume that Eve issues at most q_{E} encrypt queries and q_{D} decrypt queries.
Guess: After receiving the answer from Alice, Eve outputs his guess λ'. If λ' = λ, Alice decides b = 1, otherwise b = 0.
Since Eve has ability to break the scheme with nonnegligible probability ε, i.e., outputs λ' = λ with probability ε, then the challenger Alice can solve DDH with the same probability.
IMPROVED SCALABLE FKR STORAGE SCHEME
In practice some devices only have limited capability, so we should design a scheme which can provide shorter keys. Thereby, an improved FKR storage scheme from pairing on elliptic curve is presented part of research. In this scheme the regenerated keys can be verified via bilinear pairings. Thus also provide a measure for a user to verify the validity of the plaintext.
Let G_{1} and G_{2} be two groups that support a bilinear map. There exists a pair of security algorithms (E, D), where the algorithm E is a secure encryption algorithm based on elliptic curves and D is the matching decryption algorithm.
Step 1: Server chooses a random number rεZ^{*}_{q}
and computes .
Step 2: Server generates the encrypted files .
Thereafter, server publishes all encrypted files.
When Alice asks to access to the FKR storage scheme at the point j, server sends the secret key K_{j+1} to Alice. Since Alice can obtain any encrypted files, she can compute
and get K_{j} and File_{j}. Similarly, Alice can obtain K_{j1} and File_{j1} via K_{j} and EF_{j1}.
Step 3: After computing K_{j} and K_{j1}, Alice performs the following step to verify the validity of the regenerated keys.
If above equation is true, the regenerated keys are valid. Otherwise, Alice outputs error messages.
CONCLUSIONS
Secure storage is a crucial problem in the Internet. Motivated by Kallahalla’ forward key rotation and the requirement of the short key schemes, we present two FKR storage scheme. One is based on discrete logarithm and another is from bilinear pairing on elliptic curve. The latter storage scheme is suitable for implementation in many scenarios, especially those where the storage capability of the users is limited.