CryptoDB
A Tight Computational Indistinguishability Bound of Product Distributions
| Authors: |
|
|---|---|
| Download: | |
| Presentation: | Slides |
| Conference: | TCC 2022 |
| Award: | Best Young Researcher Award |
| Abstract: | Assume that distributions X_0,X_1 (respectively Y_0,Y_1) are d_X (respectively d_Y) indistinguishable for circuits of a given size. It is well known that the product distributions X_0Y_0,X_1Y_1 are d_X+d_Y indistinguishable for slightly smaller circuits. However, in probability theory where unbounded adversaries are considered through statistical distance, it is folklore knowledge that in fact X_0Y_0 and X_1Y_1 are d_x+d_y-d_x*d_y indistinguishable, and also that this bound is tight. We formulate and prove the computational analog of this tight bound. Our proof is entirely different from the proof in the statistical case, which is non-constructive. As a corollary, we show that if X and Y are d indistinguishable, then k independent copies of X and k independent copies of Y are almost 1-(1-d)^k indistinguishable for smaller circuits, as against d*k using the looser bound. Our bounds are useful in settings where only weak (i.e. non-negligible) indistinguishability is guaranteed. We demonstrate this in the context of cryptography, showing that our bounds yield simple analysis for amplification of weak oblivious transfer protocols. |
BibTeX
@inproceedings{tcc-2022-32670,
title={A Tight Computational Indistinguishability Bound of Product Distributions},
publisher={Springer-Verlag},
author={Nathan Geier},
year=2022
}