Different security notions of secret sharing schemes have been proposed by different information measures. Entropies, such as Shannon entropy and min entropy, are frequently used in the setting security notions for secret sharing schemes. Different to the entropies, Kolmogorov complexity was also defined and used in study the security of individual instances for secret sharing schemes. This paper is concerned with these security notions for secret sharing schemes defined by the variational measures, including Shannon entropy, guessing probability, min entropy and Kolmogorov complexity.
Different security notions of secret sharing schemes have been proposed by different information measures. Entropies, such as Shannon entropy and min entropy, are frequently used in the setting security notions for secret sharing schemes. Different to the entropies, Kolmogorov complexity was also defined and used in study the security of individual instances for secret sharing schemes. This paper is concerned with these security notions for secret sharing schemes defined by the variational measures, including Shannon entropy, guessing probability, min entropy and Kolmogorov complexity.
Fundamental results on secret sharing schemes (SSSs) are discussed in the setting where security and share size are measured by (conditional) min-entropies. We first formalize a unified framework of SSSs based on (conditional) Rέnyi entropies, which includes SSSs based on Shannon and min entropies etc. as special cases. By deriving the lower bound of share sizes in terms of Rέnyi entropies based on the technique introduced by Iwamoto-Shikata, we obtain the lower bounds of share sizes measured by min entropies as well as by Shannon entropies in a unified manner. As the main contributions of this paper, we show two existential results of non-perfect SSSs based on min-entropies under several important settings. We first show that there exists a nonperfect SSS for arbitrary binary secret information and arbitrary monotone access structure. In addition, for every integers k and n (k ≤ n), we prove that the ideal non-perfect (k, n)-threshold scheme exists even if the distribution of the secret is not uniformly distributed.
The following standard relaxations of perfect security for secret sharing schemes (SSSs) exist in the literature:quasi-perfect,almost-perfect, andstatistical. Understanding the power of these relaxations on the efficiency of SSSs, measured via a parameter calledinformation ratio, is a long-standing open problem. In this article, we introduce and study an extremely relaxed security notion, calledpartial security, for which it is only required that any qualified set gains strictly more information about the secret than any unqualified one. To get a meaningful efficiency measure, we normalize the (standard) information ratio of such schemes by an appropriate parameter and refer to the new measure aspartial information ratio. We present three main results in this paper.First, we prove that partial and perfect information ratios coincide for the class of linear SSSs.Second, we prove that for the general (i.e., non-linear) class of SSSs, partial and statistical information ratios are equal.Third, we show that partial and almost-perfect information ratios do not coincide for the class of mixed-linear schemes (i.e., schemes constructed by combining linear schemes with different underlying finite fields). We also use the notion of partial secret sharing to strengthen and unify the previousdecompositiontheorems for constructing SSSs.
This book offers a mathematical foundation for modern cryptography. It is primarily intended as an introduction for graduate students. Readers should have basic knowledge of probability theory, but familiarity with computational complexity is not required. Starting from Shannon's classic result on secret key cryptography, fundamental topics of cryptography, such as secret key agreement, authentication, secret sharing, and secure computation, are covered. Particular attention is drawn to how correlated randomness can be used to construct cryptographic primitives. To evaluate the efficiency of such constructions, information-theoretic tools, such as smooth min/max entropies and information spectrum, are developed. The broad coverage means the book will also be useful to experts as well as students in cryptography as a reference for information-theoretic concepts and tools.
Quantitative theories of information flow are of growing interest, due to the fundamental importance of protecting confidential information from improper disclosure, together with the unavoidability of "small" leaks in practical systems. But while it is tempting to measure leakage using classic information-theoretic concepts like Shannon entropy and mutual information, these turn out not to provide very satisfactory security guarantees. As a result, several researchers have developed an alternative theory based on Renyi's min-entropy. In this theory, uncertainty is measured in terms of a random variable's vulnerability to being guessed in one try by an adversary, note that this is the complement of the Bayes Risk. In this paper, we survey the main theory of min-entropy leakage in deterministic and probabilistic systems, including comparisons with mutual information leakage, results on min-capacity, results on channels in cascade, and techniques for calculating min-entropy leakage in systems.
In a k-threshold secret sharing scheme, a dealer who holds a secret s distributes parts of this secret (the shares) to n players; If k or more of these players pool their shares, they are able to determine s, but if less than k of them pool their shares, they cannot infer any information on s. In 1979, Shamir introduced such a scheme, based on polynomial interpolation in a finite field. This scheme is widely used in other cryptographic protocols, because it is simple, elegant and above all information-theoretically secure. There are a few proofs of the scheme's security, but to our knowledge, none of them is entirely based on the information-theoretical entropy function introduced by Shannon in 1948. We propose such a demonstration.
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.