The Existence of Error-Correcting Codes Implies Privacy Lower Bounds

Excited to share this recent IEEE BITS article in the Special Issue on Error-Correcting Codes [1].

Abstract

We discuss how the lens of error-correcting codes yields lower bounds on the privacy-utility tradeoff in differential privacy (DP). Reconstruction attacks, packing and covering arguments, and fingerprinting codes can all be interpreted as coding-theoretic tools: they allow for analysis of families of datasets whose query-answer patterns form (possibly randomized) codewords with large pairwise distance. Any DP mechanism answering these queries too accurately reveals enough structure to enable “decoding”; that is, identifying a user or reconstructing large parts of the dataset. By presenting each lower-bound technique through an explicit coding viewpoint, this survey unifies classical results on counting queries with recent advances in statistical estimation and high-dimensional learning, including Gaussian covariance estimation. We conclude with open problems at the intersection of coding theory and differential privacy.

[1] https://ieeexplore.ieee.org/document/11481645

(Scalable) Multiterminal Key Agreement

In cryptography, secret key agreement is usually framed as a two-party story: Alice and Bob want to agree on a shared secret while Eve listens. But many real systems are not two-party systems. They involve teams of devices, servers, users, or sensors that need to establish the same secret key, often in the presence of public discussion and potentially powerful adversaries. A recent paper of mine, with Benjamin Kim (lead student author) and Lav Varshney, asks a simple question:

Can ideas from coding theory and secret sharing give us a clean, scalable way to do multiterminal secret key agreement?

Our answer is yes! The paper develops a simple multiterminal key agreement scheme built from maximum distance separable (MDS) codes (specifically Reed-Solomon codes) and then analyzes its secrecy and rate through the lens of secret key capacity and multivariate mutual information (MMI). The key point is that the same threshold structure that makes Reed-Solomon codes powerful for secret sharing also makes them surprisingly natural for multiterminal key agreement.

The Big Picture

The paper sits at the intersection of three ideas.

First, there is secret sharing. In a threshold secret sharing scheme, a secret is split into $n$ shares so that any $k$ shares can reconstruct the secret, but any fewer than $k$ reveal nothing about it. Shamir Secret Sharing schemes (via use of Reed-Solomon codes) are a well-studied class of techniques to realize this threshold property.

Second, there is secret key agreement (SKA). In the multiterminal SKA setting, multiple parties start with correlated private observations, publicly discuss information over an authenticated public channel, and aim to end with the same shared key while leaking essentially nothing useful to an eavesdropper. The information-theoretic performance limit is measured by the secret key capacity.

Third, there is coding theory. Error-correcting codes already encode redundancy in a structured way. MDS codes are optimal in a precise sense: they achieve the maximum possible distance for their block length and dimension. That is, they give the strongest threshold-reconstruction behavior for a given amount of redundancy.

What our paper does is connect these three threads in a particularly direct way: use an MDS codeword as the object being partially distributed across terminals, then exploit the threshold property to guarantee recoverability for the legitimate users and secrecy against the wiretapper.

Why this Connection is Interesting

At a high level, secret sharing and multiterminal key agreement share many goals/targets/techniques.

In secret sharing, you start with a secret and want to distribute it safely across many users.

In multiterminal key agreement, you start with distributed private information and want users to end up with a shared secret key.

These are not identical tasks, but they share the same core geometry: some subsets of information should be enough to reconstruct, and smaller subsets should reveal nothing. The paper’s main conceptual contribution is to push this analogy far enough to get an explicit multiterminal SKA protocol out of it. (The abstract states this clearly: the work explores the connection between secret sharing and secret key agreement, yielding “a simple and scalable multiterminal key agreement protocol” based on Reed-Solomon codes with threshold reconstruction.)

The threshold semantics of MDS codes are exactly the right structure for a scalable multiterminal key agreement design.

The Model

The paper works in the standard multiterminal communication setup. There is a set of terminals $V$ , a subset $A\subseteq V$ active users who must recover the final key, and possibly helpers in $V\setminus A$ . Each user has access to a private correlated source $Z_i$ , and everyone can participate in public discussion, which an eavesdropper also sees. The key must satisfy two conditions:

Secrecy: the public discussion should reveal essentially no information about the key.
Recoverability: every active user should be able to reconstruct the key from their private source and the public discussion.

The paper also recalls the standard definition of secret key capacity, the maximum achievable key rate over all allowed protocols in this model.

The Coding Idea

Now for the protocol idea.

Suppose we take a secret and pad it with additional uniform randomness, forming a vector $K=(s, u_1, \ldots, u_{k-1})$ ,

where $s$ is the actual secret and the $u_i$ ‘s are random pads. Then we encode $K$ using an $(n, k)$ Reed-Solomon code with generator matrix $G$ , obtaining a codeword $Z=KG$ . Each terminal receives one symbol $z_i$ of this codeword, and then the protocol publicly reveals exactly $k-1$ additional symbols. Since any $k$ symbols of an $(n,k)$ MDS code suffice to reconstruct the message, each legitimate terminal can combine its private symbol with the $k-1$ public symbols and recover the full encoded message $K$ .

This is the reconstruction side.

On the secrecy side, the protocol masks the privately delivered shares using independent random values $r_i$ . In the “secret-sharing-inspired” version of the scheme, terminal $Z_1$ has a distinct random shared value $r_i$ with each terminal $Z_i$ , and broadcasts $e_i = z_i + r_i$ .. Each intended recipient can subtract its own mask $r_i$ and recover the corresponding code symbol, but the eavesdropper only sees the masked version.

So the core protocol can be summarized as follows:

Encode the secret-plus-padding with an MDS code,
Privately give each user one share (masked),
Publicly reveal exactly $k$ additional shares,
Let each legitimate user reconstruct,
Rely on the threshold property to ensure that the eavesdropper still stays below the reconstruction threshold.

The Main Security Statements

In the paper, we show that the eavesdropper learns nothing about the secret from the entire visible transcript.

The first main theorem captures the information-theoretic secrecy of this setup. There is also a computational variant. If one uses an IND-CPA-secure public-key encryption scheme to distribute the shares to terminals, then the protocol becomes computationally secure against PPT adversaries rather than information-theoretically secure against unbounded ones. That computational extension is practically important because it shows the scheme is not tied to idealized pre-shared masks. If you are willing to step down from unconditional secrecy to computational secrecy, you can distribute shares using standard encrypted channels.

If I had to summarize the paper in one sentence, I would say this:

It shows that MDS codes are not just a convenient implementation tool for multiterminal key agreement; they are a structural bridge between secret sharing, error correction, and SKA capacity.

For further details, take a look at the paper. Feedback/comments are welcome!

The Talking Drum as a Communication Channel

We just wrapped up Week 1 of my UIUC course, ECE598DA: Topics in Information-Theoretic Cryptography. The class introduces students to how tools from information theory can be used to design and analyze both privacy applications and foundational cryptographic protocols. Like many courses in privacy and security, we began with the classic one-time pad as our entry point into the fascinating world of secure communication.

We also explored another ‘tool’ for communication: the talking drum. This musical tradition offers a striking example of how information can be encoded, transmitted, and understood only by those familiar with the underlying code. In class, I played a video of a master drummer to bring this idea to life.

What Are Talking Drums?

Talking drums, especially those like the Yoruba dùndún, are traditional African hourglass‑shaped percussion instruments prized for their ability to mimic speech. Skilled drummers can vary pitch and rhythm to convey tonal patterns, effectively transmitting messages over short distances.

Speech surrogacy: The drum replicates the microstructure of tonal languages by adjusting pitch and rhythm, embodying what researchers call a “speech surrogate” .
Cultural ingenuity: Historically, these drums served as everyday communication tools, not merely for music or rituals but for sharing proverbs, announcements, secure messages, and more.

Here’s one of the exercises I gave students in Week 1:

Exercise: Talking drums. Chapter 1 of Gleick’s The Information highlights the talking drum as an early information technology: a medium that compresses, encodes, and transmits messages across distance. Through a communications theory lens, can you describe the talking drum as a medium that achieves a form of secure communication?

And here’s a possible solution:

African talking drums (e.g., Yoruba “dùndún”) reproduce the pitch contours and tonal patterns of speech. Since many West African languages are tonal, the drum reproduces structure without literal words.

Encoding: A spoken sentence is mapped into rhythmic and tonal patterns.
Compression: The drum strips away vowels and consonants, leaving tonal “skeletons.”
Security implication: To an outsider unfamiliar with the tonal code or local idioms, the message is incomprehensible. In effect, the drum acts as an encryption device where the key is cultural and linguistic context.

There are a few entities to model:

Source: Message in natural language (tonal West African language, e.g., Yoruba).
Encoder: Drummer maps source to a drummed signal using tonal contours and rhythmic patterns.
Channel: Physical propagation of drum beats across distance, subject to noise (wind, echo, competing sounds).
Legitimate receiver: Villager fluent in both the spoken language and cultural conventions.
Adversary: Outsider (colonial administrator, rival tribe, foreign merchant) who hears the same signal but lacks full knowledge of mapping or redundancy rules.

Let $X$ denote a message in a tonal language (e.g., Yoruba). A drummer acts as an encoder $E$ mapping $X$ to a drummed signal $S = E(X,K)$ , where $K$ denotes shared cultural/linguistic knowledge (idioms, proverbs, discourse templates) known to legitimate receivers but not to outsiders. The signal $S$ traverses a physical channel $C$ and is received as $Y_R$ by insiders and as $Y_A$ by an adversary (outsider). Decoders $D_R$ and $D_A$ attempt to reconstruct $X$ :