We study the security of a variety of cryptographic tasks including traditional privacy (e.g., seeded extractors, encryptions, commitments, and secret sharing schemes) and differential privacy from the perspective of α-mutual information. As far as we know, encryption scheme, commitment, and differential privacy have been studied via mutual information based on the Shannon entropy. Though Bellare et al. in CRYPTO 2012 have got some results about encryption schemes, the upper bound of mutual information is not the tightest. Though Cuff and Yu in CCS 2016 mentioned the direction of the Rényi entropy generalization, only a few results about differential privacy were obtained, and even for Shannon entropy, the proof in that paper has some limitations. In this paper, we propose a modular and unified framework to study the relations between statistical security and mutual information security for a series of privacy schemes other than prior work that focused on a special scheme. In addition, we introduce α-mutual information security via the Rényi entropy for a series of privacy schemes and aim to bridge the gap between statistical security and α-mutual information security. By resorting to an improved upper bound on the difference between the Shannon entropy of two distributions, the convexity of a function, useful equality about statistical distance, and the absolutely homogeneous property of α-norm, we obtain rigorous proofs of their essential equivalence. An extra fruit is that the relations between mutual information security and statistical security of encryption and commitment schemes are improved. Hence, two fundamentally different ways of defining privacy security are connected.
A Generalized Constraint of Privacy: α -Mutual Information Security
We study the security of a variety of cryptographic tasks including traditional privacy (e.g., seeded extractors, encryptions, commitments, and secret sharing schemes) and differential privacy from the perspective of α-mutual information. As far as we know, encryption scheme, commitment, and differential privacy have been studied via mutual information based on the Shannon entropy. Though Bellare et al. in CRYPTO 2012 have got some results about encryption schemes, the upper bound of mutual information is not the tightest. Though Cuff and Yu in CCS 2016 mentioned the direction of the Rényi entropy generalization, only a few results about differential privacy were obtained, and even for Shannon entropy, the proof in that paper has some limitations. In this paper, we propose a modular and unified framework to study the relations between statistical security and mutual information security for a series of privacy schemes other than prior work that focused on a special scheme. In addition, we introduce α-mutual information security via the Rényi entropy for a series of privacy schemes and aim to bridge the gap between statistical security and α-mutual information security. By resorting to an improved upper bound on the difference between the Shannon entropy of two distributions, the convexity of a function, useful equality about statistical distance, and the absolutely homogeneous property of α-norm, we obtain rigorous proofs of their essential equivalence. An extra fruit is that the relations between mutual information security and statistical security of encryption and commitment schemes are improved. Hence, two fundamentally different ways of defining privacy security are connected.
Abstract. In this paper, information theoretic cryptography is discussed based on conditional Rényi entropies. Our discussion focuses not only on cryptography but also on the definitions of conditional Rényi entropies and the related information theoretic inequalities. First, we revisit conditional Rényi entropies, and clarify what kind of properties are required and actually satisfied. Then, we propose security criteria based on Rényi entropies, which suggests us deep relations between (conditional) Rényi entropies and error probabilities by using several guessing strategies. Based on these results, unified proof of impossibility, namely, the lower bounds of key sizes is derived based on conditional Rényi entropies. Our model and lower bounds include the Shannon’s perfect secrecy, and the minentropy based encryption presented by Dodis, and Alimomeni and Safavi-Naini. Finally, new optimal symmetric key cryptography and almost optimal secret sharing schemes are proposed which achieve our lower bounds.
We revisit the impossibility of a variety of cryptographic tasks including privacy and differential privacy with imperfect randomness. For traditional notions of privacy, such as security of encryption, commitment or secret sharing schemes, dramatic impossibility results are known [MP90,DOPS04] for several concrete sources R, including a (seemingly) very “nice and friendly” Santha-Vazirani (SV) source. Moreover, Bosley and Dodis [BD07] gave strong evidence that many traditional privacy tasks (e.g., encryption) inherently require an “extractable” source of randomness. The common interpretation of these negative results is that privacy is impossible even with “very structured” imperfect sources. Somewhat surprisingly, Dodis et al. [DLMV12] put a slight dent in this belief, by showing that non-trivial differential privacy is possible with the SV sources. This suggested a qualitative gap between traditional and differential privacy, and left open the question if differential privacy is possible with more realistic (i.e., less structured) sources than the SV sources. Motivated by solving this question, we introduce a new, modular framework for showing strong impossibility results for (either traditional or differential) privacy under a general imperfect source R. In particular, we introduce natural and easy-to-understand concepts of expressiveness and separability of a given imperfect source R, and show the following results: – Low levels of expressiveness generically imply strong impossibility results for both traditional and differential privacy. – Separability implies expressiveness; NON-separability is equivalent to “weak bit extraction”. – While the separability of some concrete (e.g., SV) sources R was implicitly known, we show new separability results for several important sources, including general “block sources”. As direct corollaries of these general results, we get the following corollaries: – Existing, but quantitatively improved, impossibility results for traditional privacy, but under a wider variety of sources R. – First impossibility results for differential privacy. Although, unsurprisingly, these results (barely) miss the highly structured SV sources, they come back extremely quickly once the source becomes slightly more realistic (e.g., a realistic “block source”). – Any imperfect source allowing (either traditional or differential) privacy admits a certain type of deterministic bit extraction. (This result is incomparable to the result of [BD07].) Overall, we believe our results provide an intuitive, modular and unified picture elucidating the (im)possibility of privacy with general imperfect sources.
An encryption scheme is said to be entropically secure if an adversary whose min-entropy on the message is upper bounded cannot guess any function of the message. Similarly, an encryption scheme is entropically indistinguishable if the encrypted version of a message whose min-entropy is high enough is statistically indistinguishable from a fixed distribution. We present full generalizations of these two concepts to the encryption of quantum states in which the quantum conditional min-entropy, as introduced by Renner, is used to bound the adversary's prior information on the message. A proof of the equivalence between quantum entropic security and quantum entropic indistinguishability is presented. We also provide proofs of security for two different ciphers in this model and a proof for a lower bound on the key length required by any such cipher. These ciphers generalize existing schemes for approximate quantum encryption to the entropic security model.
We present and compare definitions of the notion of "statistically hiding" protocols, and we propose a novel statistically hiding commitment scheme. Informally, a protocol statistically hides a secret if a computationally unlimited adversary who conducts the protocol with the owner of the secret learns almost nothing about it. One definition is based on the L1-norm distance between probability distributions, the other on information theory. We prove that the two definitions are essentially equivalent. For completeness, we also show that statistical counterparts of definitions of computational secrecy are essentially equivalent to our main definitions. Commitment schemes are an important cryptologic primitive. Their purpose is to commit one party to a certain value, while hiding this value from the other party until some later time. We present a statistically hiding commitment scheme allowing commitment to many bits. The commitment and reveal protocols of this scheme are constant round, and the size of a commitment is independent of the number of bits committed to. This also holds for the total communication complexity, except of course for the bits needed to send the secret when it is revealed. The proof of the hiding property exploits the equivalence of the two definitions. Index terms -- Cryptology, Shannon theory, unconditional security, statistically hiding, multi-bit commitment, similarity of ensembles of distributions, zero-knowledge, protocols.
There are no universally accepted definitions of Rényi conditional entropy and Rényi mutual information, although motivated by different applications, several definitions have been proposed in the literature. In this paper, we consider a family of two-parameter Rényi conditional entropy and a family of two-parameter Rényi mutual information. By performing a change of variables for the parameters, the two-parameter Rényi conditional entropy we study coincides precisely with the definition introduced by Hayashi and Tan [IEEE Trans. Inf. Theory, 2016], and it also emerges naturally as the classical specialization of the three-parameter quantum Rényi conditional entropy recently put forward by Rubboli, Goodarzi, and Tomamichel [arXiv:2410.21976 (2024)]. We establish several fundamental properties of the two-parameter Rényi conditional entropy, including monotonicity with respect to the parameters and variational expression. The associated two-parameter Rényi mutual information considered in this paper is new and it unifies three commonly used variants of Rényi mutual information. For this quantity, we prove several important properties, including the non-negativity, additivity, data processing inequality, monotonicity with respect to the parameters, variational expression, as well as convexity and concavity. Finally, we demonstrate that these two-parameter Rényi information quantities can be used to characterize the strong converse exponents in privacy amplification and soft covering problems under Rényi divergence of order α∈(0,∞).
Differential privacy has been an exceptionally successful concept when it comes to providing provable security guarantees for classical computations. More recently, the concept was generalized to quantum computations. While classical computations are essentially noiseless and differential privacy is often achieved by artificially adding noise, near-term quantum computers are inherently noisy and it was observed that this leads to natural differential privacy as a feature. In this work we discuss quantum differential privacy in an information theoretic framework by casting it as a quantum divergence. A main advantage of this approach is that differential privacy becomes a property solely based on the output states of the computation, without the need to check it for every measurement. This leads to simpler proofs and generalized statements of its properties as well as several new bounds for both, general and specific, noise models. In particular, these include common representations of quantum circuits and quantum machine learning concepts. Here, we focus on the difference in the amount of noise required to achieve certain levels of differential privacy versus the amount that would make any computation useless. Finally, we also generalize the classical concepts of local differential privacy, Rényi differential privacy and the hypothesis testing interpretation to the quantum setting, providing several new properties and insights.