Delegating RAM Computations with Adaptive Soundness and Privacy

Prabhanjan Ananth, Yu-Chi Chen, Kai-Min Chung, Huijia Lin, Wei-Kai Lin

Abstract

As cloud computing becomes ubiquitous, the need to delegate complex computations over persistent databases has grown. However, existing cryptographic solutions often struggle to provide both privacy and soundness in an "adaptive" setting—where a user's queries depend on previous results. This paper introduces the first cryptographic scheme for delegating RAM computations that achieves both adaptive soundness and adaptive privacy. The authors achieve this by developing a novel "security lifting technique" and a new primitive called "history-less accumulators," which allow for the transformation of selective security proofs into full adaptive security with minimal loss.

1. Introduction

In modern cloud architectures, users frequently outsource large, persistent databases to remote servers. To maintain efficiency, these computations are modeled as Random Access Machine (RAM) programs, which allow for sub-linear execution time by accessing only the necessary portions of a database rather than reading it in its entirety.

While delegation is efficient, it introduces significant security risks. A robust delegation scheme must satisfy two primary properties:

  1. Soundness: A malicious server cannot provide an incorrect result and trick the user into accepting it.
  2. Privacy: The server learns nothing about the underlying database or the specific programs being executed.

Crucially, these properties must hold in an adaptive environment. In practice, users do not pre-determine all future queries; instead, they choose their next computation based on the outputs of previous ones. Prior to this work, most schemes were either limited to "selective" security (where queries are fixed in advance) or failed to provide privacy alongside soundness.

2. The Challenge of Adaptive Security

The primary barrier to achieving adaptive security in RAM delegation is the "complexity leveraging" problem. Traditionally, proving adaptive security involves guessing the adversary's future choices. If an adversary has many options, the probability of a correct guess is infinitesimally small, leading to an exponential loss in the security strength of the proof. To overcome this, the authors focus on the structure of the security proof itself rather than just the construction of the scheme.

3. The Security Lifting Technique

The paper’s most significant theoretical contribution is a framework designed to "lift" selective security proofs into adaptive ones. This framework relies on a property the authors term "niceness."

A selective proof is considered "nice" if it consists of a series of hybrid steps where each step only depends on a small (logarithmic) amount of information regarding the adversary’s adaptive choices. By identifying these local dependencies, the authors apply a "small-loss" version of complexity leveraging. Instead of guessing the entire strategy of the adversary globally, the leveraging is applied locally within individual hybrid steps. This prevents the security loss from exploding, resulting in a polynomial rather than exponential loss.

4. History-less Accumulators

To make the delegation proof "nice" enough for the lifting technique, the authors had to rethink how memory consistency is verified. Standard schemes often use positional accumulators, such as Merkle trees. However, Merkle trees are inherently tied to the history of memory accesses; to "program" a specific value into a proof, one must account for every previous modification to that memory location.

To solve this, the authors introduced history-less accumulators. Built on the Decisional Diffie-Hellman (DDH) assumption, these accumulators allow a proof to bind a value to a specific memory location regardless of how many times that location was previously accessed or modified. By decoupling the current state from its access history, the authors simplified the proof structure, making it compatible with their security lifting framework.

5. Implementation and Efficiency

The proposed scheme utilizes Indistinguishability Obfuscation (iO) to protect the logic of the delegated programs. iO effectively "scrambles" the program, allowing the server to execute the logic without gaining insight into its internal operations.

Despite the complexity of the underlying primitives, the scheme maintains high efficiency for the client:

  • Setup: The client performs a one-time setup proportional to the size of the database.
  • Querying: For each subsequent query, the client's computational work is proportional only to the program's description and the output length, not the size of the database.
  • Server Work: The server’s workload scales linearly with the actual runtime of the RAM program.

Furthermore, the authors demonstrate that their techniques extend naturally to Parallel RAM (PRAM) models, enabling the secure delegation of parallelized computations over shared, persistent data structures.

6. Conclusion and Future Work

This work establishes a new feasibility result for secure cloud computing, proving that adaptive privacy and soundness are achievable for RAM delegation. While the reliance on Indistinguishability Obfuscation (iO) currently places this scheme in the realm of theoretical cryptography—as iO is not yet efficient enough for production use—the "security lifting" framework itself holds broad potential. Future research may apply this technique to other cryptographic primitives, potentially upgrading a wide range of selectively secure protocols to meet the demands of adaptive, real-world environments.

Summary updated

BibTeX
@inproceedings{ananth2016delegating,
  author = {Prabhanjan Ananth and Yu-Chi Chen and Kai-Min Chung and Huijia Lin and Wei-Kai Lin},
  title = {{Delegating RAM Computations with Adaptive Soundness and Privacy}},
  booktitle = {TCC (B2)},
  year = {2016},
  doi = {10.1007/978-3-662-53644-5\_1},
}
Figure