可進行檔案修改的可取回性認證系統

Abstract

我們提出了對於一巨大委外(outsource)儲存檔案其資料完整性的驗證方式。 使用了 Merkle Tree 為主體，我們提出的方法可對該檔案進行 Verification， Modification， Retrieval 以及 Partial Retrieval 之動作。 而於 Verification 時所使用之 Communication Cost 為$O(log(n))$， 且驗證客戶端 (Client/User) 所需儲存之資料量為$O(1)$。 同時三種最常使用之動作： Verification， Modification， Partial Retrieval 對於伺服器端 (Server) 為不可分辨的 (Indistinguishable)。

A POR(Proof Of Retrievability) system is a system designed for a client to verify a fairly large file $F$ on some untrusted storage service providers. The client may not access the whole file every time, but he has to ensure the retrievability of $F$. Once the client needs $F$, the file shall be retrievable from the storage service provider. For efficiency on both client and the storage service provider, an efficient POR system shall only process part of the file $F$.

There are some efficient POR systems for static file $F$. However, most of them can not accommodate modifications on $F$. The file modification ability is crucial on some practical applications such as periodically backuped archives. It is clearly inefficient to send whole file with minor differences every backup since it takes too much computational and communication resources. Therefore, file modification is a required attribute for practical POR system deployments on backup files.

There are also some efficient POR systems with file modification ability. However they have some drawbacks such as unwilling information leakage of the data or limited verification number. In this paper, we include a scheme based on \textit{Merkle Tree} to provide file modification ability while preventing possible information leakage induced by the modifications. The communication and computational costs of our schemes for each verification are bounded above by logarithm of the file size $l$. ($O(log(l))$, where $l$ is the file size.)