### Improved Security Evaluation Techniques for Imperfect Randomness from Arbitrary Distributions

Takahiro Matsuda, Kenta Takahashi, Takao Murakami, and Goichiro Hanaoka

##### Abstract

Dodis and Yu (TCC 2013) studied how the security of cryptographic primitives that are secure in the "ideal" model in which the distribution of a randomness is the uniform distribution, is degraded when the ideal distribution of a randomness is switched to a "real-world" (possibly biased) distribution that has some lowerbound on its min-entropy or collision-entropy. However, in many constructions, their security is guaranteed only when a randomness is sampled from some non-uniform distribution (such as Gaussian in lattice-based cryptography), in which case we cannot directly apply the results by Dodis and Yu. In this paper, we generalize the results by Dodis and Yu using the Rényi divergence, and show how the security of a cryptographic primitive whose security is guaranteed when the ideal distribution of a randomness is a general (possibly non-uniform) distribution $Q$, is degraded when the distribution is switched to another (real-world) distribution $R$. More specifically, we derive two general inequalities regarding the Rényi divergence of $R$ from $Q$ and an adversary's advantage against the security of a cryptographic primitive. As applications of our results, we show (1) an improved reduction for switching the distributions of distinguishing problems with public samplability, which is simpler and much tighter than the reduction by Bai et al. (ASIACRYPT 2015), and (2) how the differential privacy of a mechanism is degraded when its randomness comes from not an ideal distribution $Q$ but a real-world distribution $R$. Finally, we show methods for approximate-sampling from an arbitrary distribution $Q$ with some guaranteed upperbound on the Rényi divergence (of the distribution $R$ of our sampling methods from $Q$).

Available format(s)
Publication info
Keywords
security evaluationRenyi divergencesquare-friendlyinversion sampling
Contact author(s)
t-matsuda @ aist go jp
tmatsuda310 @ gmail com
History
Short URL
https://ia.cr/2019/050

CC BY

BibTeX

@misc{cryptoeprint:2019/050,
author = {Takahiro Matsuda and Kenta Takahashi and Takao Murakami and Goichiro Hanaoka},
title = {Improved Security Evaluation Techniques for Imperfect Randomness from Arbitrary Distributions},
howpublished = {Cryptology ePrint Archive, Paper 2019/050},
year = {2019},
note = {\url{https://eprint.iacr.org/2019/050}},
url = {https://eprint.iacr.org/2019/050}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.