Paper 2021/1274

A Tight Computational Indistinguishability Bound for Product Distributions

Nathan Geier, Tel Aviv University
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\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 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\cdot 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published by the IACR in TCC 2022
Keywords
computational indistinguishability direct product
Contact author(s)
nathangeier @ mail tau ac il
History
2022-10-04: last of 2 revisions
2021-09-24: received
See all versions
Short URL
https://ia.cr/2021/1274
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1274,
      author = {Nathan Geier},
      title = {A Tight Computational Indistinguishability Bound for Product Distributions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/1274},
      year = {2021},
      url = {https://eprint.iacr.org/2021/1274}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.