Proof of retrievability for archived files

A proof of retrievability (POR) mechanism is applicable to a file for providing assurances of file possession to a requesting client by transmitting only a portion of the entire file. The client compares or examines validation values returned from predetermined validation segments of the file with previously computed validation attributes for assessing the existence of the file. Since the archive server does not have access to the validation function prior to the request, or challenge, from the client, the archive server cannot anticipate the validation values expected from the validation function. Further, since the validation segments from which the validation attributes, and hence the validation values were derived, are also unknown to the server, the server cannot anticipate which portions of the file will be employed for validation.

BACKGROUND

In a managed information environment, such as a networked computer infrastructure, cryptographic techniques have been employed for transforming data in a manner indiscernible to an unauthorized interceptor, but efficiently renderable to an intended recipient. Such techniques typically rely on a so-called one-way function, for which computation in the forward direction is relatively, straightforward, but reverse computation based on applying an inverse function are computationally infeasible. One-way functions are typically facilitated by the use of a key that is known to the authorized parties to the message, without which the corresponding inverse function requires substantial computational resources to compute. Early cryptographic techniques, due to the computationally intensive operations required, were typically reserved for encryption and authentication of highly sensitive communications, but modern advances in computational abilities coupled with increased awareness of a need to protect electronically transmitted information have made such cryptographic techniques commonplace.

These and other trends are opening up computing systems to new forms of outsourcing, that is, delegation of computing services to outside entities. Improving network bandwidth and reliability are reducing user reliance on local resources. Energy and labor costs as well as computing system complexity are militating toward the centralized administration of hardware. Increasingly, users employ software and data that resides thousands of miles away on machines and that they themselves do not own. Grid computing, the harnessing of disparate machines into a unified computing platform, has played a role in scientific computing for some years. Similarly, software as a service (SaaS)—loosely a throwback to terminal/mainframe computing architectures—is now a pillar in the Internet-technology strategies of major companies.

Storage is no exception to the outsourcing trend. Online data-backup services abound for consumers and enterprises alike. Amazon® Simple Storage Service, for example, offers an abstracted online-storage interface, allowing programmers to access data objects through web service calls, with fees metered in gigabyte-months and data transfer amounts. Researchers have investigated alternative service models, such as peer-to-peer data archiving, as an emerging trend.

SUMMARY

As archived storage for electronic data evolves, such storage tends to become more like a commodity. Contractual obligations to provide archive services become delegated according to a supply chain. As the actual archivers of sensitive data become more attenuated from the clients for whom the archived data belongs, and since it is quite likely that archives may never be invoked, a breakdown in the archive chain may not be realized until the data is called upon, at which point irrecoverable losses may have occurred. Service contracts covering archive services may specify a duration or resilience in the archive process, but with an ever increasing volume of electronic data generated by modern business practices, it can be problematic to inventory or assess the resiliency of archived data.

Conventional archive and recovery mechanisms store a file and either recall an entire file to verify existence or simply assume the file is intact. Accordingly, conventional archive and recovery systems suffer from the shortcoming that corruption or other inability to accurately retrieve the file may not be detectable until the failed recovery attempt. Periodic conventional validation of file existence requires retrieval of the entire file. As the number and size of archived files increases, it becomes inefficient, if not infeasible, to recall each entire archived file to verify the existence thereof. It would be beneficial for an archiving entity to be able to provide assurances of file possession, and hence recoverability, without having to present the entire file, and further that the requestor of the archived file can validate the assurances in a manner that cannot be falsely generated by the archiver.

A more recent application of the cryptographic techniques mentioned above involves so-called “proof of retrievability” for archived electronic media, typically file backups, or archives. Traditional backups of computer generated information entailed nothing more than an individual user copying files onto a floppy disk, or a system operations manager systematically downloading magtapes of company files stored on disk drives in a machine room, and storing the magtapes in an adjacent closet or safe. Modern proliferation of electronically generated and transported data, however, along with services associated with such information, have defined a business niche of archive services for providing backup storage, typically in a transparent manner via remote connections, rather than the conventional collection of magtapes.

As users and enterprises come to rely on diverse sets of data repositories, with variability in service guarantees and underlying hardware integrity, they will require new forms of assurance of the integrity and accessibility of their data. Simple replication offers one avenue to higher-assurance data archiving, but at often unnecessarily and unsustainably high expense. (Indeed, a recent IDC report suggests that data generation is outpacing storage availability) Protocols such as a so-called data-dispersion scheme (Rabin) are more efficient: They share data across multiple repositories with minimum redundancy, and ensure the availability of the data given the integrity of a quorum (k-out-of-n) of repositories. Such protocols, however, do not provide assurances about the state of individual repositories—a shortcoming that limits the assurance the protocols can provide to relying parties.

Configurations disclosed below present a cryptographic building block known as a proof of retrievability (POR). A POR enables a user (verifier) to determine that an archive (prover) “possesses” a file or data object F. More precisely, a successfully executed POR assures a verifier that the prover presents a protocol interface through which the verifier can retrieve F in its entirety. Of course, a prover can refuse to release F even after successfully participating in a POR. A POR, however, provides strong assurances of file retrievability barring changes in prover behavior.

Accordingly, configurations herein substantially overcome the shortcomings of conventional archive and recovery mechanisms by a proof of retrievability (POR) applicable to a file for providing assurances of file possession to a requesting client by transmitting only a portion of the entire file. A function interface to an archive server allows the archive server to perform a validation function, provided by the client, on predetermined portions of the archived file. The client compares or examines validation values returned from predetermined validation segments of the file with previously computed validation attributes for assessing the existence (i.e. recoverability) of the file on the archive server. Since the archive server does not have access to the validation function prior to the request, or challenge, from the client, the archive server cannot anticipate the validation values expected from the validation function. Further, since the validation segments from which the validation attributes, and hence the validation values were derived, are also unknown to the server, the server cannot anticipate which portions of the file will be employed for validation. The validation function is typically enabled from the client in the form of a key provided to the archive server by the client, minimizing the extent of the transaction required to invoke the function interface at the archive server (server, or prover).

A POR scheme as disclosed herein enables an archive or back-up service (prover) to produce a concise proof that a user (verifier) can retrieve a target file F, that is, that the archive retains and reliably transmits file data sufficient for the user to recover F in its entirety. A proof of retrievability (POR) therefore provides assurances that an archiving entity to whom a file is entrusted will be able to produce the archived file if called upon to do so. A POR may be viewed as a kind of cryptographic proof of knowledge (POK), but one specially designed to handle a large file (or bitstring) F. Configurations herein define POR protocols in which the communication costs, number of memory accesses for the prover, and storage requirements of the user (verifier) are small parameters essentially independent of the length of F. In a POR, unlike a POK, neither the prover nor the verifier need actually have knowledge of F. PORs therefore, give rise to a beneficial security definition.

PORs are an important tool for semi-trusted online archives. Existing cryptographic techniques help users ensure the privacy and integrity of files they retrieve. It is also natural, however, for users to want to verify that archivers do not delete or modify files prior to retrieval. The goal of a POR is to accomplish these checks without users having to download the files themselves. A POR can also provide quality-of-service guarantees, i.e., show that a file is retrievable within a certain time bound.

In the event of file corruption, or other indication of an inability to retrieve the file resulting from the POR, error correcting code (ECC) techniques are employed to recover a file. The method generates error correction codes for withstanding at least a degree of file corruption beyond which corruption is assured to be detectable from the POR operation. In other words, the state of a file is verifiable to be either uncorrupted within a range for which the undetectable corruption is recoverable by the ECC codes, or else such unrecoverable corruption detected, such that the true state of the file is ascertainable, enabling mitigating action rather than leaving unrecoverable corruption undetected. For example, if a POR is applied that detects greater than 10% corruption, and an ECC is employed which covers up to 10% corruption, then either the POR may be guaranteed to assure file recoverability because any undetected corruption (less than 10%) will be accommodated by the ECC.

The ECC processing also avoids false assurances of file recoverability by encrypting and permuting the error correction portions of the file. Identification of portions of a file over which the ECCs are computed allows spoofing by a file adversary that can compromise the ECC recovery. Encrypting the file causes ECC portions and non ECC portions to be indistinguishable. Permutation applies an ordering or interleaving to a file which cannot be easily interpreted, thus preventing an association between ECC codes and the corresponding file portions. In contrast, conventional archive storage suffers from the shortcoming that it is difficult to verify the existence or recoverability of stored files, and failure of the recovery may not be determined until a failed recovery attempt, at which time irrecoverable loss may have occurred.

The further disclosed application of the ECC framework complements the assurances of the POR. The PORs employed as examples herein operate generally as follows: The client applies an error-correcting code ECCout to the target file F to obtain an encoded (expanded) file˜F, which it stores with the server. The code ECCout has the effect of rendering F recoverable even if up to some ε-fraction of˜F is corrupted, where ε is a parameter dependent on the choice of ECCout.

To rule out high file-corruption rates and thus ensure that F is retrievable, the client randomly samples˜F. It does so by challenging the server. The client specifies a subset s of blocks in˜F plus a nonce u (whose purpose is discussed below). The server applies a function respond to s and returns the result respond (s, u). With sufficient challenge rounds, the client obtains the following two-sided guarantee:

1. If the server corrupts more than an ε-fraction of˜F, and F is therefore unretrievable, the client will detect this condition with high probability;

2. If the server corrupts less than (or exactly) an ε-fraction of˜F, the client is able to retrieve F in its entirety via decoding under ECCout. By analogy with zero-knowledge proofs, the same interface used for challenge-response interactions between the client and server is also available for extraction. The client first attempts to download F as normal (checking the integrity of the file against a MAC or digital signature). If this usual process fails, then the client resorts to a POR-based extraction. The client in this case submits challenges to the server and reconstructs F from the (partially corrupted) values yielded by server via respond.

To illustrate the basic idea and operation of a POR, it is worth considering a straightforward design involving a keyed hash function h(k(F)). In this scheme, prior to archiving a file F, the verifier computes and stores a hash value r=h(k(F)) along with secret, random key k. To check that the prover possesses F, the verifier releases k and asks the prover to compute and return r. Provided that h is resistant to second-preimage attacks, this simple protocol provides a strong proof that the prover knows F. By storing multiple hash values over different keys, the verifier can initiate multiple, independent checks. This keyed-hash approach, however, may impose high resource costs. The keyed-hash protocol operates on the notion that the verifier store a number of hash values linear in the number of checks it is to perform. This characteristic conflicts with the aim of enabling the verifier to offload its storage burden. More significantly, each protocol invocation requires that the prover process the entire file F. For large F, even a computationally lightweight operation like hashing can be highly burdensome. Furthermore, it requires that the prover read the entire file for every proof—a significant overhead for an archive whose intended load is only an occasional read per file, were every file to be tested frequently.

In conventional POR constructions, the function respond returns a single file block or an XOR of file blocks. However, configurations here substantially overcome above described shortcomings of file corruption detection in that the respond may itself apply an arbitrary error correcting code. In particular, configurations below consider schemes in which respond computes a codeword on the blocks in s and returns the uth symbol. Configurations employ such an arrangement as the inner code as ECCin and to the code ECCout as the outer code.

Alternate configurations of the invention include a multiprogramming or multiprocessing computerized device such as a workstation, handheld or laptop computer or dedicated computing device or the like configured with software and/or circuitry (e.g., a processor as summarized above) to process any or all of the method operations disclosed herein as embodiments of the invention. Still other embodiments of the invention include software programs such as a Java Virtual Machine and/or an operating system that can operate alone or in conjunction with each other with a multiprocessing computerized device to perform the method embodiment steps and operations summarized above and disclosed in detail below. One such embodiment comprises a computer program product that has a computer-readable storage medium including computer program logic encoded thereon that, when performed in a multiprocessing computerized device having a coupling of a memory and a processor, programs the processor to perform the operations disclosed herein as embodiments of the invention to carry out data access requests. Such arrangements of the invention are typically provided as software, code and/or other data (e.g., data structures) arranged or encoded on a computer readable medium such as an optical medium (e.g., CD-ROM), floppy or hard disk or other medium such as firmware or microcode in one or more ROM, RAM or PROM chips, field programmable gate arrays (FPGAs) or as an Application Specific Integrated Circuit (ASIC). The software or firmware or other such configurations can be installed onto the computerized device (e.g., during operating system execution or during environment installation) to cause the computerized device to perform the techniques explained herein as embodiments of the invention.

DETAILED DESCRIPTION

The example configuration below discloses a POR protocol in which the verifier need store only one or more cryptographic keys—irrespective of the size and number of the files whose retrievability it seeks to verify—as well as a small amount of dynamic state (some tens of bits) for each file. More strikingly, and somewhat counterintuitively, the disclosed scheme requires that the prover access only a small portion of a (large) file F in the course of a POR. In fact, the portion of F “touched” by the prover is essentially independent of the length of F and would, in a typical parameterization, include just hundreds or thousands of data blocks.

Briefly, the disclosed POR protocol encrypts F and randomly embeds a set of randomly-valued check blocks called sentinels. The use of encryption here renders the sentinels indistinguishable from other file blocks. Alternatively, portions of the file itself may be encrypted to generate the check blocks (values), discussed below. The verifier challenges the prover by specifying the positions of a collection of sentinels and asking the prover to return the associated sentinel values. If the prover has modified or deleted a substantial portion of F, then with high probability it will also have suppressed a number of sentinels. It is therefore unlikely to respond correctly to the verifier. To protect against corruption by the prover of a small portion of F, the disclosed recovery approach also employs error-correcting codes.

Alternatively, schemes based on the use of message-authentication codes (MACs) applied to (selected) file blocks may be employed for generating the validation segments. The principle is much the same as in the sentinel based scheme. The verifier performs spot-checks on elements of˜F. Error-coding ensures that if a sizeable fraction of˜F is uncorrupted and available, as demonstrated by spot-checks, then the verifier can recover F with high probability.

FIG. 1shows a context diagram of an archive storage environment suitable for use with configurations disclosed herein. Referring toFIG. 1, an archive storage environment100includes a plurality of users110-1. . .110-4(110generally) invoking a set of archive servers120-1. . .120-N (120generally). Each of the archive servers120is operable for mass storage of data from the users110, usually via a contractual or service arrangement. A network130interconnects the users110, also known as clients, and archive servers (servers) for providing remote storage invocation to transport the archived data between the users110and the servers120. A typical exchange includes an archive request140, in which a user110sends a data item such as a file122to the archive server120for storage. At a subsequent time, the user issues a request142for the file, to which the server120responds with the recovered file144.

In an environment as inFIG. 1, the general exchange for proof of recoverability is as follows: an authenticator transforms a raw file F into an encoded file˜F122to be stored with the prover/archive120. A key generation algorithm produces a key k in stored by the verifier and used in encoding (The key k may be independent of F). The verifier performs a challenge-response protocol with the prover to check that the verifier can retrieve F. In a typical environment100, there are many users110each sending a multitude of files122to the servers120. In the configurations discussed below, at some time prior to an archive request142, a user110may desire to verify existence of the file on the server120, for the reasons discussed above. Accordingly, the user issues a challenge146for the file122including a file identifier122′ to the server120, to which the server120responds with a validation value148as a response149to the challenge146. The user110compares the validation value148with a recoverability attribute124corresponding to the file122which was sent to the archive server120. The recoverability attribute124, discussed further below, is a value or set of values based on the data in the file122and which is computationally infeasible to produce accurately without actual possession of the file122. Therefore, the user120performs a check, such as a comparison, match, or other functional or equivalence comparison, between the returned validation value148and the previously computed recoverability attributes124to confirm possession of the file122by the server120and hence, the ability to reproduce or recover the file upon a later request142

FIG. 2shows a block diagram of information flow for a proof of retrievability exchange in the environment ofFIG. 1. Referring toFIGS. 1-2, the archive server120receives and stores an archived file152representing the client file122. Since the purpose of proving retrievability demands that the archive server120not be able to guess or determine the validation value or values148expected as a response, the client110invokes a pseudorandom function154to generate block indices156-1. . .156-3(156generally) pointing to a particular subset of file segments157as validation segments158-1. . .158-3(158generally). The pseudorandom function (PRF)154also generates a MAC key160for generating the recoverability attributes124from the selected validation segments158. Further, the client110employs a file key164for the PRF154employed for the block indices156and the MAC key160for each file122. Both the client110and the server120have access to the PRF154for generating the indices156and recoverability attributes124, but the client110retains the file key164until it issues a challenge146, allowing the server120to compute but not anticipate the expected validation values148for comparison with the recoverability attributes124from which they were derived.

In the example ofFIG. 2, the client110generates a MAC value as a validation attribute148-1. . .148-3for each validation segment158of the archived file152. The client110stores the validation attributes124in a table162or other suitable mechanism, for subsequent challenge146/response149exchanges, discussed further below. Also, in alternate arrangements, multiple recoverability segments158-1. . .158-N may be included in computing a single validation attribute124(i.e. MAC). To accommodate successive challenge/response inquiries, the client110generates a plurality of recoverability attributes124′,124″, each from a different PRF154. Therefore, the server120cannot anticipate the file segments157selected as validation segments158for successive challenges146. The file key162therefore provides a functional interface for which the server120can deterministically compute the indices156and corresponding validation values148, but cannot anticipate because the file key164is employed for the validation function.

The client110stores the recoverability attributes124and, upon successive challenges146, issues the file key162corresponding to a particular set of validation values124. The server120computes the block indices156to obtain the validation segments158based on the file key162, and then computes the validation values148(i.e. MACs) based on the MAC key160. If the server120has all the recoverability segments158for producing validation values148corresponding to the recoverability attributes124from which they were produced. The coverage of recoverability segments158deemed sufficient to assure file possession is based upon a threshold ε indicative of a maximum corruptible portion of the file that could evade detection, and encompasses iterative application of recoverability segment158selection, also discussed further below.

FIG. 3shows a flowchart of proof of retrievability processing according toFIG. 2. Referring toFIGS. 1-3, in a particular example configuration discussed herein, the method of storing a file for subsequent proof of recoverability includes, at step200sending a file122to an archive server120, in which the file122has a plurality of file segments157. A selection of file segments157is included in the validation segments158for which the recoverability attributes124are generated, and this selection may be further subdivided into subsets, or groups, of validation segments158, also discussed further below. The client110identifies a set of validation segments158-1. . .158-N, in which the set of validation segments158is for verifying recoverability of the file122on the archive server120, as depicted at step201. The client110determines, for each of a subset of the validation segments158, recoverability attributes124applicable to each of the segments of the set of validation segments158, as shown at step202. The recoverability attributes124are typically generated by applying a one way function, such as the validation function186(FIG. 4) discussed below, however other approaches may be employed, such as generating sentinel values.

The client defines the validation function186, such that the validation function186is responsive to a challenge146for computing the validation values148, as depicted at step203. The validation values148are for comparison with the corresponding recoverability attributes124based on a particular subset of the set of validation segments158from which the recoverability attributes124were derived. Typically, the validation function186is such that substantial computational resources are required to determine the validation values148corresponding to a particular subset, or group of recoverability segments158without knowledge of one or more of the validation segments158in the particular subset. A key or other mathematical operation is employed to compute both the location of the recoverability segments158and the corresponding validation values148. Further, the validation function186may be the same that was used to compute the recoverability attributes124at the client110, as when a symmetric key is used, or may be a different function, as when a public key scheme or sentinel values are employed.

The server120stores the set of validation segments158with the file152on the archive server120, as shown at step204, such that the recoverability segments158may be indexed or otherwise recovered from the archived file152. The server120then stores the client110provided recoverability attributes124in an association with corresponding validation segments158of the file, such that the recoverability attributes124are operable for subsequent comparison, matching, or other operation with the corresponding validation values148, as depicted at step205. The recoverability attributes124may be stored on either the client110or the server120, as long as the file key164and associated MAC keys160and segmentation keys175(used to compute indices156from the file key164) remain unavailable to the server120until the client110issues a challenge146.

FIG. 4shows a diagram of archive storage and retrievability in the environment ofFIG. 1. Referring toFIGS. 1,2and4, an alternate configuration is shown including error correction codes (ECC) for recovering files determined to be corrupted at the archive server120. The combination of POR with ECC ensures that either corruption beyond the recoverability threshold ε is identified by the POR, or that corrupting within the recoverability threshold is recoverable via the ECCs. Further, conventional ECCs are typically focused on covering accidental erasure. They tend not to hold up well against an intentional adversary. Accordingly, configurations herein employ permutation and encryption on an ECC protected file, deterring a would-be intentional adversary from identifying ECC contents and corresponding non-ECC contents such that it is not apparent which portions (ECC contents) would foil subsequent ECC efforts.

The use of PORs complemented by ECCs is illustrated in the following examples: Suppose that the prover, on receiving an encoded file˜F, corrupts three randomly selected bits, B1, B2 and B3. These bits are unlikely to reside in either sentinels or validation segments, which constitute a small fraction of˜F. Thus, the verifier will probably not detect the corruption through POR execution. Thanks to the error-correction present in˜F, however, the verifier can recover the original file F completely intact.

Example 2. Suppose conversely that the prover corrupts many blocks in˜F, e.g., 20% of the file. In this case (absent very heavy error-coding), the verifier is unlikely to be able to recover the original file F. On the other hand, every sentinel that the verifier requests in a POR will detect the corruption with probability about ⅕. By requesting hundreds of sentinels, the verifier can detect the corruption with overwhelming probability.

InFIG. 4, an example configuration of an archiving client110and an archive server120are shown depicting a particular implementation of the features discussed above. A client120archives a file122with an archive server120employing POR and ECC protection as defined herein. A seed generator170generates a file key172for segmenting the file122and for generating recoverability attributes124-11. A segmenter174employs the file key172to generate or map to a run key175for computing the indices156indicative of validation segments158-11. . .158-13. A retrievability processor180receives the indices156for identifying the validation segments158in the segmented file122′. An authenticator182employs the file key172to generate or lookup a MAC key160and computes recoverability attributes124using a validation function186. Alternatively, the sentinel generator184is invoked to generate sentinel values as recoverability attributes124. The sentinel values are inserted or overwritten in the archived file152as the recoverability segments158′. Sentinel values avoid the need for a validation function186, as the sentinel generator184produces the actual values expected to be returned upon a successive validation. In either case, the archived file152includes recoverability segments158′ that return values corresponding to the recoverability attributes124-11.

The validation function186, responsive to the MAC key160, is also provided to a validation generator190at the archive server120as function186′; in the case of a sentinel value the validation generator190simply returns the actual sentinel values158′.

The recoverability attributes124-11include a value common to a group158-11-158-13of recoverability segments. A common recoverability attribute124value may be computed (i.e. MACed) for all recoverability segments158or otherwise grouped in a suitable manner. Further, the recoverability attributes124-11may be stored at the client110or appended/stored as recoverability attributes124-12at the server120. Multiple recoverability attributes124′ may also be computed to allow successive PORs, such as quarterly or yearly, to be performed on the file122.

In conjunction with the POR operations, an ECC encoder520generates ECC values500for subsequent recovery. The segmenter174identifies segments510-1. . .510-4(510generally) for which to computer ECC values. The ECC encoder520generates ECC values502-1. . .502-4(502generally) corresponding to the segments510, but in an interleaved, or striping manner discussed further below. A permuter530receives a permutation key532from the seed generator170such that interleaving is defined by the permutation key532. The permutation of the ECC values avoids correlation of ECC values502with the segments510in the file122″ to which they correspond without possession of the permutation key532. As with the recoverability attributes124, the ECC values500may also be stored at the server120as ECC values500′. Further, the ECC encoder520may also encrypt either the ECC values alone or the entire file to prevent an identification of ECC and non-ECC information in the archived file152′. In a particular arrangement, the archive stored ECC values500′ involves two permutations, one the reorders the file122′ implicitly to determine segments510and a second that reorders ECC values that are appended to the file. Alternatively, permutation may be applied to the whole file. It should be further noted that the ECC segmented file152′ and POR segmented file152are not stored twice at the server120, being merely illustrated with the appropriate segmentation performed for POR operations and ECC operations.

Upon a POR request, the client110sends a challenge146including the run key175and the MAC key160. An indexer192employs the run key175to compute the indices156indicative of the validation segments158. The validation generator190employs the computed indices156to identify the validation segments158, and invokes the MAC key160on the archived validation segments158′ to compute the validation values148. A validator188at the client110receives the validation values148, and compares and/or analyzes the values148against the recoverability attributes124computed when the file122was archived. Depending on the nature of the validation values148, i.e. sentinel, MAC key, or other, various comparisons and/or matching may be involved in assessing the validity of the archived file152. If the validator188determines that the archived file152is not intact, then the ECC verifier194retrieves the ECC codes500and attempts to recreate the file.

FIGS. 5-9show a flowchart of archive storage and retrievability in the system ofFIG. 4. Referring toFIGS. 4-9, a user/client110stores a file for subsequent proof of recoverability as disclosed herein by sending a file120to an archive server120, such that the file122is arrangeable into file segments157, as depicted at step300. From the sent file152(either a local copy or just prior to sending the file), the client110identifies a set of validation segments158, in which the set of validation segments158are those file segments157selected for verifying recoverability of the file152on the archive server120, as shown at step301. In the example arrangement, coupling POR processing with ECC mechanisms, identifying the set of validation segments158further includes determining a corruption threshold ε, such that the corruption threshold is indicative of a minimum detectable corruption of the file122, as depicted at step302. The segmenter174identifies, based on the corruption threshold, a size of the set of validation segments158, as depicted at step303, such that corruption below the threshold is correctable via the ECC verifier194.

The retrievability processor180determines, for each of a subset of the validation segments158-N, recoverability attributes124applicable to each of the segments158of the set of validation segments158-1. . .158-N, as depicted at step304. As indicated above, individual recoverability attributes124may encompass multiple recoverability segments158, such that each attribute value124-N covers a group of segments158, or even the entire archived file152. The retrievability processor180computes the recoverability attributes124by computing the validation segments158according to the corruption threshold ε, such that the corruption threshold is indicative of a number of file validation segments158for verifying existence of the file on the archive server120, as disclosed at step305. An increasing portion of file coverage by the validation segments158increases the likelihood of detecting even small quantums of corruption. For some files, even a single bit of corruption is substantially detrimental; however smaller deviations are more readily correctable via ECC operations, discussed further below. The corruption threshold therefore encompasses a ratio of coverage of the validation segments158and a number of iterations.

In the example arrangement which prevents false assurances of retrievability, computing the validation segments158of the file122further includes computing a run key175corresponding to a particular subset of segments in the file, such that the run key175is for computing an index156to the validation segments158of the file152, as depicted at step306. The retrievability processor180defines a validation function186, such that the validation function186is responsive to a challenge146for computing the validation values148, as shown at step307. The server120computes the validation values148for comparison with the corresponding recoverability attributes124based on a particular subset of the set of validation segments158from which the recoverability attributes124were derived, in which the validation function186is such that substantial computational resources are required to determine the validation values148corresponding to a particular subset without knowledge of one or more of the validation segments158in the particular subset. In other words, it is computationally infeasible for the server120to falsely generate the expected recoverability attributes124because the server120cannot identify the recoverability function186or the file segments157for which to apply it to without the corresponding keys.

A check is performed, at step308, to determine whether sentinel values are employed for the recoverability attributes124. Sentinel values are external to the file, rather than computed from the file, and therefore can be simply compared upon retrieval rather than recomputed from the archived file. If sentinel values are employed, then the sentinel generator184generates the validation segments158for the archived file152as sentinel values and the validation function186′ for generating validation values148simply returns the previously computed sentinel value, as shown at step309. In the case of sentinel values, the sentinel values are stored as validation segments158by either insertion or overwriting in the file152, as depicted at step310. Although an overwriting approach has the effect of obliterating some of the data in the file158, the overwritten data is less than the corruption threshold such that it may be subsequently recreated via the ECC verifier194.

Alternatively, at step311, the authenticator182determines a validation key160, such that the validation function186is responsive to the key160for computing the recoverability attribute124corresponding to a subset of the set of validation segments158. In the example configuration, the validation key186is a message authentication code (MAC) key160, in which the authenticator182selects a MAC key160known to the client and initially unknown to the archive server120, as depicted at step312. The validation key is a symmetric key, such that the validation key provides a message authentication code (MAC), known to the client and requiring substantial computational resources to determine by the archive server without the validation key, as shown at step313. Alternatively, a variety of authentication and key generation schemes may be employed, such as a public/private key pair and/or other authentication mechanism such as MD4, MD5, and SHA, as is known in the art.

The authenticator182then generates the recoverability attributes124for later comparison, as disclosed at step314, which includes generating, using the validation function186and the MAC key160, the recoverability attribute124of the subset of the set of validation segments158determined from the run key156, as shown at step315.

The retrievability processor180associates the recoverability attributes124of the subset of validation segments158with the particular MAC key160under which it was generated, as depicted at step316, so that subsequent validation (i.e. challenges) may be performed. This includes, at step317, storing the set of validation segments124-12with the file152on the archive server120. Alternatively, the validation segments124-11may be retained by the client, however since the validation segments124are unintelligible without the MAC key160and the validation function186, the client110need only maintain the MAC key160in secrecy.

The retrievability processor180sends, or otherwise makes available, the validation function to the archive server120separate from the generated MAC key160, as shown at step318, thus enabling a functional interface to the server120invokable on demand via the MAC key160. Similarly, the retrievability processor180provides, to the archive server120, a segment function156′ operable to identify, using the run key175, the particular subset of validation segments158, as depicted at step319. The run key175, as with the MAC key160, is retained until a challenge so that the particular file segments157sought as validation segments158cannot be anticipated by the archive server120. The retrievability processor180then ensures storage of the recoverability attributes124in an association with corresponding validation segments158of the file122, thus preserving the recoverability attributes124for subsequent comparison with the corresponding validation values148upon computation by the archive server120, as disclosed at step320.

As indicated above, the POR validation is coupled with an ECC mechanism to recover from smaller deviations in file integrity that may not be caught by the POR approach, thus enabling complete coverage of the true state of the archived file152, i.e. that it is either recoverable or identified as irretrievably corrupted so that remedial measures may be pursued. Accordingly, the ECC encoder520at the client110establishes a re-creation mechanism, such that the recreation mechanism is operable to tolerate a corruption based on the corruption threshold, as depicted at step321. The ECC encoder positions a file122for recovery by identifying an error correction function operable to generate error correction code values500on segments510of a file122″, such that the error correction code (ECC) values are operable to recreate the file122, as disclosed at step322. The ECC encoder520invokes the segmenter174to identify a segmentation function for segmenting the file122″, such that the segmenter generates a set of the segments510-1. . .510-4responsive to the ECC values500, in which the generated segments510are based on a maximum corruptible portion of the file sufficient for recovery, as depicted at step323. In the example shown, the segmentation function is a permutation function, such that the permutation function identifies a sequence of the set of segments510responsive to the ECC values, in which the permutation function is initially unknown to the archiver120of the file152′, as disclosed at step324. The permutation function applies an interleaving, or striping order to the ECC values500′ such that the ordering of the segments510from which they were derived is not ascertainable from the ECC values502.

The ECC encoder520applies the error correction function to the file122″ to generate the ECC values500, as depicted at step325, and stores the values500either at the client110or at the server120as augmented attributes500′. Upon storage at the server120, a permuter530augments the file such that an association of error correction values502to corresponding segments510in the generated set of segments responsive to the ECC values is not apparent from the location534of the ECC values502in the file152′, as shown at step326. In the example arrangement, this includes arranging the ECC values502such that the segments510upon which the ECC values are based are not apparent from the location of the ECC values in the file152′, depicted at step327. Arrangement includes, as shown at step328, defining, according to a permutation key, a sequence534of the ECC values510, derived from the segments510, interleaved in the file152′, the interleaving defining an ordering of the ECC values502, such that the set of segments510is selected in response to the maximum corruptible portion, and in which the interleaving is recreatable from the permutation key532.

Depending on the types of data in the file, the nature or appearance of the ECC data may suggest it's identity as parity data, i.e. a text file will appear with unintelligible portions for the ECC values500. Accordingly, augmenting the file includes augmenting such that error correction values are indiscernible from non-error correction values in the file, as shown at step329. Thus, in the example arrangement, augmenting further comprises encrypting the file such that insertion of ECC values500′ avoids establishing an identifiable inconsistency in the file indicative of error correction control data, as depicted at step330.

An archive service such as provided by server120may then endure indefinitely pending a retrieval request142, and may in fact never be called upon to produce the file122. In contrast, in the configurations herein, the client110may request a POR146at any time, and the approach outlined herein may be employed to pursue quarterly or yearly PORs as part of archive maintenance, for example. At a particular point in time, therefore, the server120receives a challenge146indicative of a request to validate recoverability of the file152from the archive server120, as disclosed at step331. At some time, presumably immediately prior to generating the POR for validation of the file, the retrievability processor180sends to the archive sever120information sufficient to compute the MAC key160for computing the validation values148on the subset of segments158using the validation function186, as depicted at step332. This includes identifying, at the archive server120, the validation function186′, and receiving an indication of the subset of validation segments158′ of the server file152, in which the indication (i.e. indices) was previously unknown to the archive server120, as shown at step334In the example arrangement, these correspond to the MAC key160, in conjunction with the authentication function186′, and the run key156for identifying the segments158′. The retrievability processor180sends the run key156to the archive server120as an indication of the subset of validation segments158, in which the run key is previously unknown to the server, as shown at step335, and the indexer192executes the segment function with the sent run key156to identify the subset of the validation segments158, depicted at step336.

Using the indexer to identify the recoverability segments158, the validation generator190employs the MAC key160to compute the validation values148for comparison with the corresponding recoverability attribute124for validation of segments158indicated by the run key156, as shown at step337. This includes applying the validation function186to each of the validation segments158in the indicated subset to compute the validation value148, as depicted at step338. The validator188compares the validation value148to the corresponding recoverability attribute124to assess recoverability of the file, as disclosed at step339, and determine if proof of recoverability has been satisfied, or if corruption was detected. If the corruption was below the threshold ε, then even if it was undetected, the file is recoverable via the ECC verifier194, as depicted at step340. If corruption above the threshold was detected, then it is known that other mechanisms, such as parallel archives, should be pursued. In either case, the true state of the file is detected within an interval of periodic POR checks, such as quarterly or yearly.

The specific operations surrounding the example POR approach disclosed above may be considered as follows. A POR system PORSYS comprises the six functions defined below. The function respond is the only one executed by the prover P. All others are executed by the verifier V. For a given verifier invocation in a POR system, it is intended that the set of verifier-executed functions share and implicitly modify some persistent state. In other words, ‘a’ represents the state of a given invocation of V; we assume a is initially null. We let ‘p’ denote the full collection of system parameters. The only parameter we explicitly require for our system and security definitions is a security parameter j. (In practice, as will be seen in our main scheme in section 3, it is convenient for p also to include parameters specifying the length, formatting, and encoding of files, as well as challenge/response sizes.) On any failure, e.g., an invalid input or processing failure, we assume that a function outputs the special symbol |.

Keygen[p]−>k: The function keygen generates a secret key ‘k’. (In a generalization of our protocol to a public-key setting, ‘k’ may be a public/private key pair. Additionally, for purposes of provability and privilege separation, we may choose to decompose k into multiple keys.)
Encode(F; k, a)−>Fn, N: The function encode generates a file handle n that is unique to a given verifier invocation. The function also transforms F into an (enlarged) file Fn and outputs the pair (Fn, n). Where appropriate, for a given invocation of verifier V, we let Fn denote the (unique) file whose input to encode has yielded handle n. Where this value is not well defined, i.e., where no call by verifier V to encode has yielded handle n, we let Fn def=|.
Extract(n, k, a)[p]−>F: The function extract is an interactive one that governs the extraction by verifier V of a file from a prover P. In particular, extract determines a sequence of challenges that V sends to P, and processes the resulting responses. If successful, the function recovers and outputs F□.
Challenge(n, k, a)[p]−>c. The function challenge takes secret key k and a handle and accompanying state as input, along with system parameters. The function outputs a challenge value c for the file n.
Respond(c, n)−>r. The function respond is used by the prover P to generate a response to a challenge c. Note that in a POR system, a challenge c may originate either with challenge or extract.
Verify((r, n); k, a)−>b: {0, 1}. The function verify determines whether r represents a valid response to challenge c. The challenge c does not constitute explicit input in our model; it is implied by n and the verifier state. The function outputs a ‘1’ bit if verification succeeds, and ‘0’ otherwise.

The adversary A consists of two parts, A(“setup”) and A(“respond”). The component A(“setup”) may interact arbitrarily with the verifier; it may create files and cause the verifier to encode and extract them; it may also obtain challenges from the verifier. The purpose of A(“setup”) is to create an archive on a special file Fn*. This archive is embodied as the second component, A(“respond”). It is with A(“respond”) that the verifier executes the POR and attempts to retrieve Fn*.

In the example model, an archive—whether honest or adversarial—performs only one function. It receives a challenge c and returns a response r. An honest archive returns the correct response for file˜Fn; an adversary may or may not do so. This challenge/response mechanism serves both as the foundation for proving retrievability in a POR and as the interface by which the function extract recovers a file Fn. In the normal course of operation, extract submits a sequence of challenges c1, c2, c3 . . . to an archive, reconstructs˜Fn from the corresponding responses, and then decodes˜Fn to obtain the original file Fn.

In the security definition exemplified above, we regard A(“respond”) as a stateless entity. (That is, its state does not change after responding to a challenge, it has no “memory.”) On any given challenge c, A(“respond”) returns the correct response with some probability; otherwise, it returns an incorrect response according to some fixed probability distribution. These probabilities may be different from challenge to challenge, but because of our assumption that A(“respond”) is stateless, the probabilities remain fixed for any given challenge value. Put another way, A(“respond”) may be viewed as set of probability distributions over challenge values c.

The ECC configuration thus complements the POR as in the following example: The ECC encoder520uses a striped “scrambled” code in which the file is divided into stripes, each stripe is encoded with a standard (n, k, d) Reed-Solomon code and a pseudorandom permutation is applied to the resulting symbols, followed by encryption of permuted file blocks. The permutation and encryption secret keys are known only to the client110. Alternative configurations employ a systematic adversarial error-correcting code, i.e., one in which the message blocks of F remain unchanged by error-correcting. A systematic code of this kind has considerable practical benefit. In the ordinary case when the server is honest and extraction is unnecessary, i.e., the vast majority of the time, the client110need not perform any permutation or decryption on the recovered file122. To build a systematic adversarial error-correcting code, we apply code “scrambling” exclusively to parity blocks. Scrambling alone does not ensure a random adversarial channel, as a plaintext file reveals stripe boundary information to an adversary. To hide stripe boundaries from an adversary, i.e., to scramble F122, we partition the file122into stripes by implicit application of a pseudorandom permutation. (We need not explicitly permute the file.) Our outer code outputs the file F untouched, followed by the “scrambled” parity blocks. To hide stripe boundaries, the parity blocks are then encrypted. More formally, our adversarial error-correcting code SA-ECC takes as input secret keys k1, k2 and k3, and a message M of size m blocks. It encodes via the following operations:

1. Permute M using PRP[m] with key k1, divide the permuted message into [m/k] stripes of consecutive k blocks each, and compute error-correcting information for each stripe using code ECCout.

2. The output codeword is M followed by permuted and encrypted error-correcting information. (The permutation of parity blocks is accomplished by PRP[m/k(n−k)] with secret key k2; encryption takes place under key k3.) To decode, SA-ECC reverses the order of the above operations.

Those skilled in the art should readily appreciate that the programs and methods for providing proof of retrievability as defined herein are deliverable to a processing device in many forms, including but not limited to a) information permanently stored on non-writeable storage media such as ROM devices, b) information alterably stored on writeable storage media such as floppy disks, magnetic tapes, CDs, RAM devices, and other magnetic and optical media, or c) information conveyed to a computer through communication media, for example as in an electronic network such as the Internet or telephone modem lines. Such delivery may be in the form of a computer program product having a computer readable storage medium operable to store computer program logic embodied in computer program code encoded thereon, for example. The operations and methods may be implemented in a software executable object or as a set of instructions embedded in an addressable memory element. Alternatively, the operations and methods disclosed herein may be embodied in whole or in part using hardware components, such as Application Specific Integrated Circuits (ASICs), Field Programmable Gate Arrays (FPGAs), state machines, controllers or other hardware components or devices, or a combination of hardware, software, and firmware components.

While the system and method for providing proof of retrievability has been particularly shown and described with references to embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the scope of the invention encompassed by the appended claims.