![](https://csdnimg.cn/release/download_crawler_static/10541928/bg7.jpg)
Remote Data Checking Using Provable Data Possession 12:7
CheckProof(pk, sk, chal , V) →{“success”, “ failure”} is run by the client in order to val-
idate a proof of possession. It takes as inputs a public key pk, a s ecret key sk, a
challenge chal, and a proof of possession V. It returns whether V is a correct proof of
possession for the blocks determined by chal.
We construct a PDP protocol from a PDP scheme in two phases, Setup and Challenge.
Setup. The client C is in possession of the file F and runs KeyGen(1
k
) → (pk, sk),
followed by TagBlock(pk, sk, b
i
) → T
b
i
, for all 1 ≤ i ≤ f . C stores the pair (sk, pk). C
then sends pk, F,and = (T
b
1
,...,T
b
f
)toS for storage and may delete F and .
Challenge. C generates a challenge chal that, among other things, indicates the specific
blocks for which C wants a proof of possession. C then sends chal to S. S runs
GenProof(pk, F, chal,) → V and sends to C the proof of possession V. Finally, C can
check the validity of the proof V by running CheckProof(pk, sk, chal, V).
In the Setup phase, C computes tags for each file block and stores them together with
the file at S.IntheChallenge phase, C requests proof of possession for a subset of
the blocks in F. This phase can be executed an unlimited number of times in order
to ascertain whether S still possesses the selected blocks. We note that GenProof and
CheckProof may receive different input values for chal, as these algorithms are run by
S and C, respectively.
We state the security for a PDP protocol using a game that captures the data posses-
sion property. Intuitively, the Data Possession Game captures that an adversary cannot
successfully construct a valid proof without possessing all the blocks corresponding to
a given challenge, unless it guesses all the missing blocks.
Data Possession Game
—Setup. The challenger runs KeyGen(1
k
) → (pk, sk), sends pk to the adversary and
keeps sk secret.
—Query. The adversary makes tagging queries adaptively: It selects a block b
1
and
sends it to the challenger. The challenger computes the verification metadata
TagBlock(pk, sk, b
1
) → T
b
1
and sends it back to the adversary. The adversary con-
tinues to query the challenger for the verification metadata T
b
2
,...,T
b
f
on the blocks
of its choice b
2
,...,b
f
. As a general rule, the challenger generates T
b
j
for some
1 ≤ j ≤ f , by computing TagBlock(pk, sk, b
j
) → T
b
j
. The adversary then stores all
the blocks as an ordered collection F = (b
1
,...,b
f
), together with the corresponding
verification metadata T
b
1
,...,T
b
f
.
—Challenge. The challenger generates a challenge chal and requests the adversary
to provide a proof of possession for the blocks b
i
1
,...,b
i
c
determined by chal, where
1 ≤ i
j
≤ f, 1 ≤ j ≤ c, 1 ≤ c ≤ f .
—Forge. The adversary computes a proof of possession V for the blocks indicated by
chal and returns V.
If CheckProof(pk, sk, chal, V) = “ success”, the adversary has won the Data Possession
Game.
Definition 3.2. A PDP protocol (Setup, Challenge) built on a PDP scheme (KeyGen,
TagBlock, GenProof, CheckProof) guarantees data possession if for any (probabilistic
polynomial-time) adversary A the probability that A wins the Data Possession Game
on a set of file blocks is negligibly close to the probability that the challenger can extract
those file blocks by means of a (probabilistic polynomial-time) knowledge extractor E.
In our security definition, the notion of a knowledge extractor is similar to the standard
one, introduced in the context of proofs of knowledge [Bellare and Goldreich 1992]. If
ACM Transactions on Information and System Security, Vol. 14, No. 1, Article 12, Publication date: May 2011.