Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

The role of Mrs. Gerber's lemma for evaluating the information leakage of masked computations

Olivier Rioul

Published Feb 12, 2023• 0 citations
OpenAlex

Abstract

In the context of secret sharing computation in some finite Abelian group, given noisy observations of each share, how can one measure the information leakage of the secret? We show that in various instances of this problem, it boils down to establishing some variation of a ”Mrs. Gerber’s lemma”. That is, find a lower bound on some randomness measure of a sum of discrete random variables in the Abelian group in terms of the product of individual randomnesses of each discrete random variable. It is an open problem to generalize these approaches in a suitable framework.

Related papers

Privacy, Secrecy, and Storage with Noisy Identifiers.

Onur Günlü, Gerhard G. Kramer

The key-leakage-storage capacity regions for a hidden identifier's noisy measurements at two terminals of a secrecy system are derived. The capacity regions of binary sources with multiple measurements are obtained by applying Mrs. Gerber's lemma twice in different directions to a Markov chain to show gains in privacy-leakage as compared to assuming a noise-free identifier at the encoder.

•Jan 25, 2016•4 citations

On the number of random bits in totally private computation

Carlo Blundo, Alfredo De Santis, Giuseppe Persiano +1 more

Lecture notes in computer science•Jan 1, 1995•15 citations

Lower and Upper Bounds on the Randomness Complexity of Private Computations of AND

Eyal Kushilevitz, Rafail Ostrovsky, Emmanuel Prouff +3 more

Lecture notes in computer science•Jan 1, 2019•6 citations

Bounds on Information Combining with Quantum Side Information

Christoph Hirche, David Reeb

“Bounds on information combining” are entropic inequalities that determine how the information (entropy) of a set of random variables can change when these are combined in certain ways. Such bounds play an important role in classical information theory, particularly in coding and Shannon theory. The arguably most elementary kind of information combining is the addition of two binary random variables (a CNOT gate), and the resulting quantities play an important role in Belief propagation and Polar coding. We investigate this problem in the setting where quantum side information is available. Our main technical result is a non-trivial, and close to optimal, lower bound on the combined entropy, which can be seen as an almost optimal “quantum Mrs. Gerber's Lemma”. Our proof uses three main ingredients: (1) a new bound on the concavity of von Neumann entropy; (2) the quantitative improvement of strong subadditivity due to Fawzi-Renner; (3) recent duality results due to Renes et al. We furthermore present conjectures on the optimal bounds under quantum side information, supported by analytical observations and strong numerical evidence. We finally apply our bounds to Polar coding for classical-quantum channels, and show that even non-stationary channels polarize, the blocklength required to approach the symmetric capacity scales at most sub-exponentially in the gap to capacity and under the lower bound conjecture a blocklength polynomial in the gap suffices.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2018•1 citation

Privacy and secrecy with multiple measurements of physical and biometric identifiers

Onur Günlü, Gerhard G. Kramer, Maciej Skórski

Multiple measurements of a physical or biometric identifier are used at the decoder of a secrecy system to improve the secret-key vs. privacy-leakage capacity region of the single-measurement case. The capacity regions of doubly symmetric binary sources with multiple measurements are derived by applying Mrs. Gerber's lemma to mixtures of binary channels.

IEEE Conference on Communications and Network Security•Sep 1, 2015•8 citations

Optimal Black-Box Secret Sharing over Arbitrary Abelian Groups

Ronald Cramer, Serge Fehr

Lecture notes in computer science•Jan 1, 2002•67 citations
In the context of secret sharing computation in some finite Abelian group, given noisy observations of each share, how can one measure the information leakage of the secret? We show that in various instances of this problem, it boils down to establishing some variation of a ”Mrs. Gerber’s lemma”. That is, find a lower bound on some randomness measure of a sum of discrete random variables in the Abelian group in terms of the product of individual randomnesses of each discrete random variable. It is an open problem to generalize these approaches in a suitable framework.
“Bounds on information combining” are entropic inequalities that determine how the information (entropy) of a set of random variables can change when these are combined in certain ways. Such bounds play an important role in classical information theory, particularly in coding and Shannon theory. The arguably most elementary kind of information combining is the addition of two binary random variables (a CNOT gate), and the resulting quantities play an important role in Belief propagation and Polar coding. We investigate this problem in the setting where quantum side information is available. Our main technical result is a non-trivial, and close to optimal, lower bound on the combined entropy, which can be seen as an almost optimal “quantum Mrs. Gerber's Lemma”. Our proof uses three main ingredients: (1) a new bound on the concavity of von Neumann entropy; (2) the quantitative improvement of strong subadditivity due to Fawzi-Renner; (3) recent duality results due to Renes et al. We furthermore present conjectures on the optimal bounds under quantum side information, supported by analytical observations and strong numerical evidence. We finally apply our bounds to Polar coding for classical-quantum channels, and show that even non-stationary channels polarize, the blocklength required to approach the symmetric capacity scales at most sub-exponentially in the gap to capacity and under the lower bound conjecture a blocklength polynomial in the gap suffices.