Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Journal of Cryptology
Published in: Journal of Cryptology 3/2013

01-07-2013

Compact Proofs of Retrievability

Published in: Journal of Cryptology | Issue 3/2013

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In a proof-of-retrievability system, a data storage center must prove to a verifier that he is actually storing all of a client’s data. The central challenge is to build systems that are both efficient and provably secure—that is, it should be possible to extract the client’s data from any prover that passes a verification check. In this paper, we give the first proof-of-retrievability schemes with full proofs of security against arbitrary adversaries in the strongest model, that of Juels and Kaliski.
Our first scheme, built from BLS signatures and secure in the random oracle model, features a proof-of-retrievability protocol in which the client’s query and server’s response are both extremely short. This scheme allows public verifiability: anyone can act as a verifier, not just the file owner. Our second scheme, which builds on pseudorandom functions (PRFs) and is secure in the standard model, allows only private verification. It features a proof-of-retrievability protocol with an even shorter server’s response than our first scheme, but the client’s query is long. Both schemes rely on homomorphic properties to aggregate a proof into one small authenticator value.
previous article Polynomial Runtime and Composability
next article Enhancements of Trapdoor Permutations

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Appendix
Available only for authorised users
Footnotes
1
We note that the sentinel-based scheme of Juels and Kaliski [22], the scheme of Ateniese, Di Pietro, Mancini, and Tsudik [4], and the scheme of Shah, Swaminathan and Baker [31] lack both unbounded use and statelessness. We do not consider these schemes further in this paper.
 
2
Naor and Rothblum show that one-bit MACs suffice for proving security in their less stringent model, for an overall response length of λ⋅(s+1) bits. The Naor–Rothblum scheme is not secure in the Juels–Kaliski model.
 
3
Or, more generally, from a subset B of ℤ p of appropriate size; see Sect. 1.1.
 
4
It would be possible to shorten the response further using knowledge-of-exponent assumptions, as Ateniese et al. do, but such assumptions are strong and nonstandard; more importantly, their use means that the extractor can never be implemented in the real world.
 
5
For example, choose keys k′ and k″ for PRFs with respective ranges [1,n] and B. The query indices are the first l distinct values amongst \(f'_{k'}(1), f'_{k'}(2), \ldots\); the query coefficients are the l values \(f''_{k''}(1),\ldots, f''_{k''}(l)\), not necessarily all distinct.
 
6
In an additional minor difference, we do not specify the extraction algorithm as part of a scheme, because we do not expect that the extract algorithm will be deployed in outsourced storage applications. Nevertheless, the extract algorithm used in our proofs (cf. Sect. 4.2) is quite simple: undertake many random \(\mathcal {V}\) interactions with the cheating prover; keep track of those queries for which \(\mathcal {V}\) accepts the cheating prover’s reply as valid; and continue until enough information has been gathered to recover file blocks by means of linear algebra. The adversary \(\mathcal {A}\) could implement this algorithm by means of its proof-of-retrievability protocol access.
 
7
We are using subscripts to denote vector elements (for q) and to choose a particular vector from a set (for u); but no confusion should arise.
 
8
In fact, the domain need only be ⌈lgN⌉-bit strings, where N is a bound on the number of blocks in a file.
 
9
For notational simplicity, we present our scheme using a symmetric bilinear map, but efficient implementations will use an asymmetric map e:G 1×G 2→G T . Translating our scheme to this setting is simple. User public keys v will live in G 2; file generators u j  will live in G 1, as will the output of H; and security will be reduced to co-CDH [9].
 
10
Hidden because they are used to compute only the values {u j } in the adversary’s view, and these are Pedersen commitments and so information-theoretically hiding.
 
11
The claim gives a condition for a single I satisfying the condition \(I \nsubseteq \operatorname {free} \mathbb {D}\); the inequality here is over all such I; but if the probability never exceeds 1/#B for any specific I then it does not exceed 1/#B over a random choice of I, either.
 
12
More specifically, O(tn) time if A is a t×n matrix; but of course t≤n.
 
13
See Bellare, Goldreich, and Mityagin [8] for why the MAC security definition incorporates verification queries.
 
14
The hash H can be instantiated using a hash onto all of ℤ N ; a value not in \(\mathbb {Z}_{N}^{*}\) would disclose the factorization of N and thus will never appear in practice.
 
15
Hidden because they are used to compute only the values {u j } in the adversary’s view, and thus are hidden by the \(\{g_{j}^{e}\}\) multipliers.
 
16
The l element summation computed by the prover in the first scheme requires work comparable to a multiplication when l≈lgp.
 
17
If l is odd, the adversary can set \(m'_{i} \gets m_{i} + (l^{-1} \bmod p)(m_{ {i^{*}}})\), which allows him to respond to that l/n fraction of queries where i ∗∈I.
 
Literature
[1]
M. Aigner, G. Ziegler, Proofs from the Book, 3rd edn. (Springer, Berlin, 2004) CrossRef
[2]
N. Alon, M. Luby, A linear time erasure-resilient code with nearly optimal recovery. IEEE Trans. Inf. Theory 42(6), 1732–1736 (1996) MathSciNetMATHCrossRef
[3]
G. Ateniese, R. Burns, R. Curtmola, J. Herring, O. Khan, L. Kissner, Z. Peterson, D. Song, Remote data checking using provable data possession. ACM Trans. Inf. Syst. Security 14(1) (2011)
[4]
G. Ateniese, R. Di Pietro, L. Mancini, G. Tsudik, Scalable and efficient provable data possession, in Proceedings of SecureComm 2008, ICST, ed. by P. Liu, R. Molva (2008), pp. 1–10
[5]
G. Ateniese, S. Kamara, J. Katz, Proofs of storage from homomorphic identification protocols, in Proceedings of Asiacrypt 2009, ed. by M. Matsui. LNCS, vol. 5912 (Springer, Berlin, 2009), pp. 319–333 CrossRef
[6]
P. Barreto, M. Naehrig, Pairing-friendly elliptic curves of prime order, in Proceedings of SAC 2005, ed. by B. Preneel, S. Tavares. LNCS, vol. 3897 (Springer, Berlin, 2006), pp. 319–331
[7]
M. Bellare, A. Desai, E. Jokipii, P. Rogaway, A concrete security treatment of symmetric encryption, in Proceedings of FOCS 2007, ed. by A.R. Karlin (IEEE Computer Society, Los Alamitos, 1997), pp. 394–403
[8]
M. Bellare, O. Goldreich, A. Mityagin, The power of verification queries in message authentication and authenticated encryption. Cryptology ePrint Archive, Report 2004/309, 2004. http://​eprint.​iacr.​org/​
[9]
[10]
K.D. Bowers, A. Juels, A. Oprea, Proofs of retrievability: theory and implementation, in Proceedings of CCSW 2009, ed. by R. Sion, D. Song (ACM Press, New York, 2009), pp. 43–54
[11]
H. Cohen, A Course in Computational Algebraic Number Theory. Graduate Texts in Mathematics, vol. 138 (Springer, Berlin, 1993) MATHCrossRef
[12]
R. Cramer, V. Shoup, Signature schemes based on the strong RSA assumption. ACM Trans. Inf. Syst. Secur. 3(3), 161–185 (2000) CrossRef
[13]
R. Cramer, V. Shoup, Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack. SIAM J. Comput. 33(1), 167–226 (2003) MathSciNetMATHCrossRef
[14]
Y. Deswarte, J.-J. Quisquater, A. Saïdane, Remote integrity checking, in Proceedings of IICIS 2003, ed. by S. Jajodia, L. Strous. IFIP, vol. 140 (Kluwer Academic, Dordrecht, 2004), pp. 1–11
[15]
Y. Dodis, S. Vadhan, D. Wichs, Proofs of retrievability via hardness amplification, in Proceedings of TCC 2009, ed. by O. Reingold. LNCS, vol. 5444 (Springer, Berlin, 2009), pp. 109–127
[16]
[17]
[18]
O. Goldreich, A sample of samplers: A computational perspective on sampling, in Studies in Complexity and Cryptography: Miscellanea on the Interplay Between Randomness and Computation. LNCS, vol. 6650 (Springer, Berlin, 2011), pp. 302–332 CrossRef
[19]
L. Guillou, J.-J. Quisquater, A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory, in Proceedings of Eurocrypt 1988, ed. by C. Günther. LNCS, vol. 330 (Springer, Berlin, 1988), pp. 123–128
[20]
V.T. Hoang, B. Morris, P. Rogaway, An enciphering scheme based on a card shuffle, in Proceedings of Crypto 2012, ed. by R. Safavi-Naini. LNCS, vol. 7417 (Springer, Berlin, 2012), pp. 1–13 CrossRef
[21]
C. Huang, H. Simitci, Y. Xu, A. Ogus, B. Calder, P. Gopalan, J. Li, S. Yekhanin, Erasure coding in Windows Azure storage, in Proceedings of USENIX ATC 2012, USENIX, ed. by G. Heiser, W. Hsieh (2012)
[22]
[23]
M. Lillibridge, S. Elnikety, A. Birrell, M. Burrows, M. Isard, A cooperative Internet backup scheme, in Proceedings of USENIX Technical 2003, USENIX, ed. by B. Noble (2003), pp. 29–41.
[24]
[25]
M. Mitzenmacher, Digital fountains: A survey and look forward, in Proceedings of ITW 2004, ed. by R. Calderbank, A. Orlitsky (IEEE Information Theory Society, New York, 2004), pp. 271–276.
[26]
M. Naor, G. Rothblum, The complexity of online memory checking. J. ACM 56(1) (2009)
[27]
M. Rabin, Efficient dispersal of information for security, load balancing, and fault tolerance. J. ACM 36(2), 335–348 (1989) MathSciNetMATH
[28]
L. Rizzo, Effective erasure codes for reliable computer communication protocols. ACM SIGCOMM Comput. Commun. Rev. 27(2), 24–36 (1997) CrossRef
[29]
T. Schwarz, E. Miller, Store, forget, and check: Using algebraic signatures to check remotely administered storage, in Proceedings of ICDCS 2006, ed. by M. Ahamad, L. Rodrigues (IEEE Computer Society, New York, 2006)
[30]
M. Shah, M. Baker, J. Mogul, R. Swaminathan, Auditing to keep online storage services honest, in Proceedings of HotOS 2007, USENIX, ed. by G. Hunt (2007)
[31]
Metadata
Title
Compact Proofs of Retrievability
Publication date
01-07-2013
Published in
Journal of Cryptology / Issue 3/2013
Print ISSN: 0933-2790
Electronic ISSN: 1432-1378
DOI
https://doi.org/10.1007/s00145-012-9129-2

Premium Partner

    Image Credits