Small Memory Robust Simulation of Client-Server Interactive Protocols over Oblivious Noisy Channels

T.-h. Hubert Chan, Zhibin Liang, Antigoni Polychroniadou, Elaine Shi

TL;DR

This paper introduces a new method for running interactive communication protocols over noisy channels while using very little memory. By replacing full transcript histories with clever hashes of transcript prefixes, the authors provide a robust "client-server" simulation that maintains high communication efficiency and fixes correctness flaws found in previous low-memory attempts.

What Problem Does This Paper Address?

In standard error correction, we worry about sending a single message. In interactive coding, we worry about a conversation. If Alice sends a bit to Bob and it gets flipped by noise, Bob’s next response might be based on wrong information, causing the entire protocol to derail.

Previous solutions (like those by Haeupler in 2014) achieved excellent communication rates—meaning they didn't add too much "extra" data to fix errors—but they required every participant to remember the entire history of the conversation. For long protocols, this is a memory nightmare. A later attempt to fix this used a "computational DAG" to save only the current state, but the authors of this paper discovered a critical flaw: if you only save the state ID, you can't detect if you reached that state via a corrupted path.

This paper aims to provide a simulation that is:

  1. Robust: It survives noise that flips a fraction ($\epsilon$) of bits.
  2. Memory-Efficient: It doesn't require storing the whole transcript.
  3. Scalable: It works for a "client-server" model (one Alice, many Bobs).

Methods

The authors build upon the concept of Meeting Point Based Backtracking. Instead of starting over when an error is detected, parties periodically save "meeting points" and can roll back to a previous valid state.

The key innovations include:

  • Transcript Prefix Hashing: Instead of saving the whole transcript or just a state ID, they save a hash of the transcript prefix. This is the "secret sauce" that ensures correctness; if noise led the parties down different paths to the same state ID, the hashes won't match, and they'll know to backtrack.
  • Client-Server Coordination: They extend the two-party model to a leader (Alice) communicating with $m$ servers (Bobs). Alice must coordinate with all Bobs to ensure that if one channel is noisy, the entire system stays synchronized.
  • Low-Memory Randomness: To generate the hashes, the parties need shared randomness. Storing a massive random string would defeat the "low memory" goal, so the authors use a technique to "unpack" random bits from a tiny seed only when needed.
  • Potential Function Analysis: To prove the protocol eventually finishes, they use a complex mathematical "potential function" that tracks the progress of the simulation vs. the "damage" done by the adversary.

Datasets

Not discussed in the paper. As a theoretical work in computer science and information theory, the results are proven mathematically rather than tested on empirical datasets.

Key Insights and Ideas

  • The State-Only Trap: The biggest "aha" moment is the realization that saving just the "node" in a protocol's logic isn't enough. You need a fingerprint of the path taken to get there to guarantee you aren't hallucinating a successful conversation.
  • Graceful Degradation: The communication overhead is designed to be "graceful." As the error rate ($\epsilon$) goes to zero, the extra data added by the simulation also vanishes, approaching a perfect 1:1 communication rate.
  • PIR Application: The authors highlight Private Information Retrieval (PIR) as a primary use case. PIR allows a user to fetch data from servers without the servers knowing what was fetched. This paper provides the first framework to make PIR protocols work reliably over noisy real-world channels without sacrificing privacy or memory.

Key Results

  • Communication Rate: The protocol achieves a communication rate of $1 - O(m^{2.5} \sqrt{\epsilon \log m})$. Essentially, the "tax" paid for noise resistance is proportional to the square root of the error rate.
  • Memory Usage: For a protocol with $n$ rounds, the memory required is only $O(\log n)$—a massive improvement over the $O(n)$ required by previous robust simulations.
  • Theorem 1.1: This main result formally proves that any interactive protocol $\Pi$ can be transformed into a noise-robust version $\Pi'$ that correctly simulates the original with high probability, provided the number of servers $m$ isn't too large relative to the protocol length.

Limitations and Future Work

  • Oblivious Noise Only: The current technique only defends against "oblivious" corruptions (where the noise pattern is decided before the conversation starts). It cannot yet handle an "adaptive" adversary who changes their strategy based on what Alice and Bob are saying.
  • Dependence on $m$: The communication overhead has a somewhat high dependence on the number of servers ($m^{2.5}$). The authors suggest that future work could improve this through a more refined potential analysis.
  • Computational Complexity: While memory-efficient, the paper focuses on information-theoretic bounds. The actual computational time required to find and manage these meeting points in practice could be further optimized.

Summary updated

Abstract

We revisit the problem of low-memory robust simulation of interactive protocols over noisy channels. Haeupler [FOCS 2014] considered robust simulation of two-party interactive protocols over oblivious, as well as adaptive, noisy channels. Since the simulation does not need to have fixed communication pattern, the achieved communication rates can circumvent the lower bound proved by Kol and Raz [STOC 2013]. However, a drawback of this approach is that each party needs to remember the whole history of the simulated transcript. In a subsequent manuscript, Haeupler and Resch considered low-memory simulation. The idea was to view the original protocol as a computational DAG and only the identities of the nodes are saved (as opposed to the whole transcript history) for backtracking to reduce memory usage. In this paper, we consider low-memory robust simulation of more general client-server interactive protocols, in which a leader communicates with other members/servers, who do not communicate among themselves; this setting can be applied to information-theoretic multi-server Private Information Retrieval (PIR) schemes. We propose an information-theoretic technique that converts any correct PIR protocol that assumes reliable channels, into a protocol which is both correct and private in the presence of a noisy channel while keeping the space complexity to a minimum. Despite the huge attention that PIR protocols have received in the literature, the existing works assume that the parties communicate using noiseless channels. Moreover, we observe that the approach of Haeupler and Resch to just save the nodes in the aforementioned DAG without taking the transcript history into account will lead to a correctness issue even for oblivious corruptions. We resolve this issue by saving hashes of prefixes of past transcripts. Departing from the DAG representation also allows us to accommodate scenarios where a party can simulate its part of the protocol without any extra knowledge (such as the DAG representation of the whole protocol). In the the two-party setting, our simulation has the same dependence on the error rate as in the work of Haeupler, and in the client-server setting it also depends on the number of servers. Furthermore, since our approach does not remember the complete transcript history, our current technique can defend only against oblivious corruptions.
BibTeX
@inproceedings{chan2020small,
  author = {T.-H. Hubert Chan and Zhibin Liang and Antigoni Polychroniadou and Elaine Shi},
  title = {{Small Memory Robust Simulation of Client-Server Interactive Protocols over Oblivious Noisy Channels}},
  booktitle = {SODA},
  year = {2020},
  url = {https://openreview.net/forum?id=j9Zf9GoxD2p},
}

Loading related content...

Figure