Securing Cloud Data - Cloud Computing with e-Science Applications - page 62

useful for instances such as batch auditing or certificate chains. The signer i i
has secret key x i and public key yg

i x = and wants to sign message m i ;
we assume that all messages are distinct.

= () ,

x

Sign ( m 1 , …, m n ): First, each signer computes its signature: σ i Hm

i

i

n

∏ i
i

1 ≤ i ≤ n . The aggregate signature σ = σ .

n = 1

∏ 1

( ) =

( )

()

Ve r if y ( m , σ): Accept if eg , σ ey Hm

i

, .

i

i =

3.4.5 Data Auditing Using Aggregate Signatures

We present the basic algorithms used in the data-auditing protocol.

KeyGen (1 k ) → ( pk , sk ): This probabilistic algorithm is run by the client.
It takes a security parameter 1 k and returns public key pk and secret
key sk .
SigGen ( sk , F ) → (Φ, sig sk ( H ( f ( S )))): This algorithm is run by the client.
It takes as input private key sk and ile F , which is an ordered collec-
tion of blocks m i , and outputs a signature set Φ = {σ i } i = 1,2,…, n . It also
outputs metadata: the signature sig sk ( H ( f ( S ))) of the start node S of a
rank-based authenticated skip list. In our construction, the level zero
nodes of the rank-based authenticated skip list contain hashes H ( m i ).
SSig ssk (·): It is a signing function that uses signing key ssk to sign a string.
GenProof ( F , Φ, Ψ) → ( P ): This algorithm is run by the server. It takes
as input a file F , its signatures Φ, and a challenge Ψ (discussed fur-
ther in the chapter). It outputs a data integrity proof P for the blocks
specified by the challenge Ψ.
VerifyProof ( pk , Ψ, P ) → { TRUE , FA LSE }: This algorithm can be run by a
verifier on the receipt of P . It takes as input public key pk , the chal-
lenge Ψ, and proof P returned by the server and outputs TRUE if the
integrity of the file is verified as correct and FA LSE otherwise.
ExecUpdate ( F , Φ, update ) → ( F ′, Φ′, P update ): This algorithm is run by the
server. It takes as input a file F , its signatures Φ, and a data operation
request “update” from the client. It outputs updated file F ′, updated
signatures Φ′, and a proof P update for the operation.
VerifyUpdate ( pk , sig sk ( H ( f ( S ))), update , P update ) → {( TRUE , FA LSE , sig sk ( H ( S ′)))}:
This algorithm is run by the client. It takes as input public key pk ,
the signature sig sk ( H ( f ( S ))), operation request “update,” and the proof
P update from the server. If verification succeeds, it outputs a signature
sig sk ( H ( S ′)) for the new start node S ′ or FA LSE otherwise.