Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) iacr.org. You can also get this service via
To receive your credentials via mail again, please click here.
You can also access the full news archive.
Starting with the work of Juels and Kaliski (CCS \'07), all prior solutions to this problem crucially assume that the client data is static and do not allow it to be efficiently updated. Indeed, they all store a redundant encoding of the data on the server, so that the server must delete a large fraction of its storage to `lose\' any actual content. Unfortunately, this means that even a single bit modification to the original data will need to modify a large fraction of the server storage, which makes updates highly inefficient.
Overcoming this limitation was left as the main open problem by all prior works.
In this work, we give the first solution providing proofs of retrievability for dynamic storage, where the client can perform arbitrary reads/writes on any location within her data by running an efficient protocol with the server. At any point in time, the client can execute an efficient audit protocol to ensure that the server maintains the latest version of the client data. The computation and communication complexity of the server and client in our protocols is only polylogarithmic in the size of the client\'s data. The starting point of our solution is to split up the data into small blocks and redundantly encode each block of data individually, so that an update inside any data block only affects a few codeword symbols. The main difficulty is to prevent the server from identifying and deleting too many codeword symbols belonging to any single data block. We do so by hiding where the various codeword symbols for any individual data lock are stored on the server and when they are being accessed by the client, using the algorithmic techniques of oblivious RAM.
The algorithm performance information provided by this and the preceding paper is aimed at making practical comparisons possible. Comparisons that take both the cost of pre-computation and the efficiency of the online phase into account, at parameters that achieve a common success rate, can now be carried out with ease. Comparisons can be based on the expected execution complexities rather than the worst case complexities, and details such as the effects of false alarms and various storage optimization techniques need no longer be ignored.
A large portion of this paper is allocated to accurately analyzing the execution behavior of the perfect table distinguished point method. In particular, we obtain a closed-form formula for the average length of chains associated with a perfect distinguished point table.
evaluate a function of their joint inputs without revealing their inputs
to each other.
SFE has been the focus of active research and recent work suggests that it can
be made practical. Unfortunately, current protocols and implementations have
inherent limitations that are hard to overcome using standard and practical
techniques. Among them are: (1) requiring participants to do work linear in
the size of the circuit representation of the function; (2) requiring all
parties to do the same amount of work; and (3) not being able to provide
A promising approach for overcoming these limitations is to augment the SFE
setting with a small set of untrusted servers that have no input to the
computation and that receive no output, but that make their computational
resources available to the parties. In this model, referred to as
server-aided SFE, the goal is to tradeoff the parties\' work at the
expense of the servers. Motivated by the emergence of public cloud services
such as Amazon EC2 and Microsoft Azure, recent work has explored the extent to
which server-aided SFE can be achieved with a single server.
In this work, we revisit the sever-aided setting from a practical perspective
and design single-server-aided SFE protocols that are considerably more
efficient than all previously-known protocols. We achieve this in part by
introducing several new techniques for garbled-circuit-based protocols,
including a new and efficient input-checking mechanism for cut-and-choose and a
new pipelining technique that works in the presence of malicious adversaries.
Furthermore, we extend the server-aided model to guarantee fairness which is an
important property to achieve in practice.
Finally, we implement and evaluate our constructions experimentally and show
that our protocols (regardless of the number of parties involved) yield implementations that are 4 and 6 times
faster than the most optimized two-party SFE implementation when the server is
assumed to be malicious and covert, respectively.