Second-order analysis improves randomness extraction with side information
Second-Order Expansion of Privacy Amplification Under f-Divergence Criteria
Information Theory
Summary
Extracting secure random numbers from sources that have some predictable patterns is important for privacy. This paper looks closely at the small variations (second-order effects) in how much randomness can be securely extracted when an adversary knows some related side information. The authors analyze this problem using a general family of privacy measures and show how uncertainty breaks down into different parts, leading to precise predictions about security. These results generalize known insights and provide a clearer understanding of randomness extraction under diverse security definitions.
What this means in practice
- •For cryptography engineers: Design randomness extraction protocols that optimize security guarantees under complex privacy measures when facing side information.
- •For security analysts: Better evaluate the tightness of privacy bounds in systems that rely on randomness and adversaries with partial knowledge.
A theory result. No direct application yet.
Authors
Mario Berta, Hao-Chung Cheng, Marco Tomamichel
Abstract
We derive the second-order asymptotics of randomness extraction from memoryless sources with side information under security criteria based on a broad class of Csiszàr f-divergences, treating both a fixed reference side-information marginal and optimization over that marginal. The conditional varentropy decomposes into fluctuations of the conditional entropy across different values of the side information and the average variance of the conditional surprisal for each value. Without marginal optimization, these contributions yield a Gaussian-mixture second-order profile. With marginal optimization, they combine into the total conditional varentropy, yielding a single Gaussian profile. As corollaries, we obtain second-order expansions for Rényi-entropy criteria of all orders $α\in (0,1)$ and recover the known expansion for total variation distance.