Paper 2021/1274
Tight Computational Indistinguishability Bound of Product Distributions
Nathan Geier
Abstract
Assume that $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_Yd_X\cdot 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 nonconstructive. 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(1d)^k$ indistinguishable for smaller circuits, as against $d\cdot k$ using the looser bound. Our bounds are useful in settings where only weak (i.e. nonnegligible) 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.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint. Minor revision.
 Keywords
 computational indistinguishabilitydirect product
 Contact author(s)
 nathangeier @ mail tau ac il
 History
 20210924: received
 Short URL
 https://ia.cr/2021/1274
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/1274, author = {Nathan Geier}, title = {Tight Computational Indistinguishability Bound of Product Distributions}, howpublished = {Cryptology ePrint Archive, Paper 2021/1274}, year = {2021}, note = {\url{https://eprint.iacr.org/2021/1274}}, url = {https://eprint.iacr.org/2021/1274} }