Entropy Measures and Unconditional Security in Cryptography
Christian Cachin
One of the most important properties of a cryptographic system is a proof of its security. In the present work, information-theoretic methods are used for proving the security of unconditionally secure cryptosystems. The security of such systems does not depend on unproven intractability assumptions.
A survey of entropy measures and their applications in cryptography is presented. A new information measure, smooth entropy, is introduced to quantify the number of almost uniform random bits that can be extracted from a source by probabilistic algorithms. Smooth entropy unifies previous work on privacy amplification in cryptography and on entropy smoothing in theoretical computer science. It enables a systematic investigation of the spoiling knowledge proof technique to obtain lower bounds on smooth entropy.
The Renyi entropy of order at least 2 of a random variable is a lower bound for its smooth entropy, whereas an assumption about Renyi entropy of order 1, which is equivalent to the Shannon entropy, is too weak to guarantee any non-trivial amount of smooth entropy. The gap between Renyi entropy of order 1 and 2 is closed by proving that Renyi entropy of order $\alpha$ between 1 and 2 is a lower bound for smooth entropy, up to a small parameter depending on $\alpha$, the alphabet size, and the failure probability.
The operation of many unconditionally secure cryptosystems can be divided into the three phases advantage distillation, information reconciliation, and privacy amplification. The relation between privacy amplification and information reconciliation is investigated, in particular, the effect of side information, obtained by an adversary through an initial reconciliation step, on the size of the secret key that can be distilled safely by subsequent privacy amplification. It is shown that each bit of side information reduces the size of the key that can be generated by at most one bit, except with negligible probability.
A private-key cryptosystem and a protocol for key agreement by public discussion are proposed that are unconditionally secure based on the sole assumption that an adversary's memory capacity is limited. The systems make use of a random bit string of length slightly larger than the adversary's memory capacity that can be received by all parties.
BibTeX Citation
@phdthesis{Cachin97a,
author = {Christian Cachin},
title = {Entropy Measures and Unconditional Security in Cryptography},
year = {1997},
note = {Reprint as vol.~1 of {ETH Series in Information Security and Cryptography}, {ISBN} 3-89649-185-7, {H}artung-{G}orre {V}erlag, {K}onstanz, 1997},
school = {{ETH} Zurich},
}