Error-Free Perfect Secrecy Systems

doi:10.1017/9781316450840.003

2 - Error-Free Perfect Secrecy Systems

from Part I - Theoretical Foundations

Published online by Cambridge University Press: 28 June 2017

S.-W. Ho ,

T. Chan ,

A. Grant and

Edited by

Ashish Khisti and

S.-W. Ho: Affiliation:
Institute for Telecommunications Research, University of South Australia
T. Chan: Affiliation:
Institute for Telecommunications Research, University of South Australia
A. Grant: Affiliation:
Myriota, Adelaide, Australia
C. Uduwerelle: Affiliation:
Institute for Telecommunications Research, University of South Australia
Rafael F. Schaefer: Affiliation:
Technische Universität Berlin
Holger Boche: Affiliation:
Technische Universität München
Ashish Khisti: Affiliation:
University of Toronto
H. Vincent Poor: Affiliation:
Princeton University, New Jersey

Book contents

Get access

Summary

Shannon's fundamental bound for perfect secrecy says that the source entropy cannot be larger than the entropy of the secret key initially shared by the sender and the legitimate receiver. Massey gave an information theoretic proof of this result, and his proof does not require independence of the key and the source message. By further assuming independence, some stronger results, which govern the probability distributions of the key and the ciphertext, can be shown. These results illustrate that the key entropy is not less than the logarithm of the message sample size in any cipher achieving perfect secrecy, even if the source distribution is fixed. The same bound also applies to the entropy of the ciphertext. These results still hold if the source message has been compressed before encryption.

The above observation leads to different research problems studied in this chapter. When the source distribution is non-uniform, the entropy of the key is required to be strictly greater than the source entropy, and hence some randomness in the key is wasted. To deal with this problem, this chapter investigates cipher systems that contain residual secret randomness after they are used. A collection of such systems can be used to generate a new secret key. The aforementioned entropy bound only gives the minimum size of the pre-shared secret key. A new measure for key consumption, i.e., the entropy difference between the pre-shared secret key and the newly generated key, is proposed and justified in this chapter. Key consumption is shown to be bounded below by the source entropy, and the lower bound can be achieved by the codes proposed in this chapter. Furthermore, the existence of a fundamental tradeoff between the expected key consumption and the number of channel uses for conveying a ciphertext is shown.

Introduction

Cipher systems with perfect secrecy were studied by Shannon in his seminal paper [1] (see also [2]). With reference to Fig. 2.1, a cipher system is defined by three components: a source message U, a ciphertext X, and a key R. Here, R is the collection of secret randomness shared only by the sender and the legitimate receiver.

Type: Chapter
Information: Information Theoretic Security and Privacy of Information Systems , pp. 21 - 50

DOI: https://doi.org/10.1017/9781316450840.003 [Opens in a new window]

Publisher: Cambridge University Press

Print publication year: 2017

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Book purchase

Temporarily unavailable

References

[1] C. E., Shannon, “Communication theory of secrecy systems,” Bell Syst. Tech. J., vol. 28, no. 4, pp. 656–715, Oct. 1949.Google Scholar

[2] J. L., Massey, “An introduction to contemporary cryptology,” Proc. IEEE, vol. 76, no. 5, pp. 533–549, May 1988.Google Scholar

[3] S.-W., Ho, “On the interplay between Shannon's information measures and reliability criteria,” in Proc. IEEE Int. Symp. Inf. Theory, Seoul, Korea, Jun. 2009, pp. 154–158.

[4] T. M., Cover and J. A., Thomas, Elements of Information Theory, 2nd edn. Chichester:Wiley & Sons, 2006.

[5] B., Chor and E., Kushilevitz, “Secret sharing over infinite domains,” J. of Cryptology, vol. 6, no. 2, pp. 87–96, Jun. 1993.Google Scholar

[6] L., Csirmaz, “Probabilistic infinite secret sharing,” 2012. [Online]. Available: https://eprint.iacr.org/2012/412.pdf

[7] S.-W., Ho, T., Chan, and A., Grant, “Non-entropic inequalities from information constraints,” in Proc. IEEE Int. Symp. Inf. Theory, Cambridge, MA, USA, Jul. 2012, pp. 1256–1260.

[8] C., Blundo, A. D., Santis, and U., Vaccaro, “On secret sharing schemes,” Inf. Process. Letters, vol. 65, no. 1, pp. 25–32, Jan. 1998.Google Scholar

[9] C., Blundo, A. D., Santis, and A. G., Gaggia, “Probability of shares in secret sharing schemes,” Inf. Process. Letters, vol. 72, no. 5–6, pp. 169–175, Dec. 1999.Google Scholar

[10] G., Vernam, “Cipher printing telegraph systems for secret wire and radio telegraphic communications,” J. American Inst. Elec. Eng., vol. 45, no. 2, pp. 295–301, Feb. 1926.Google Scholar

[11] G. V., Assche, Quantum Cryptography and Secret-Key Distillation. Cambridge: Cambridge University Press, 2006.

[12] C., Ye and P., Narayan, “Secret key and private key constructions for simple multiterminal source models,” IEEE Trans. Inf. Theory, vol. 58, no. 2, pp. 639–651, Feb. 2012.Google Scholar

[13] I., Csiszár and P., Narayan, “Secrecy capacities for multiple terminals,” IEEE Trans. Inf. Theory, vol. 50, no. 12, pp. 3047–3061, Dec. 2004.Google Scholar

[14] S.-W., Ho, J., Duan, and C. S., Chen, “Location-based information transmission systems using visible light communications,” Trans. Emerging Tel. Tech., vol. 28, no. 1, 2017.Google Scholar

[15] T. H., Chan and S.-W., Ho, “2-dimensional interval algorithm,” in Proc. IEEE Inf. Theory Workshop, Paraty, Brazil, Oct. 2011, pp. 633–637.

[16] J. L., Massey, “On probabilistic encipherment,” in Proc. IEEE Inf. Theory Workshop, Bellagio, Italy, 1987.

[17] H. N., Jendal, Y. J. B., Kuhn, and J. L., Massey, “An information-theoretic treatment of homophonic substitution,” Lecture Notes in Computer Science, vol. 434, pp. 382–394, 1990.Google Scholar

[18] B., Ryabko and A., Fionov, “Efficient homophonic coding,” IEEE Trans. Inf. Theory, vol. 45, no. 6, pp. 2083–2091, Sep. 1999.Google Scholar

[19] C. G., Günther and A. B., Boveri, “A universal algorithm for homophonic coding,” Lecture Notes in Computer Science, vol. 330, pp. 405–414, 1988.Google Scholar

[20] M., Hoshi and T. S., Han, “Interval algorithm for homophonic coding,” IEEE Trans. Inf. Theory, vol. 47, no. 3, pp. 1021–1031, Mar. 2001.Google Scholar

[21] S.-W., Ho and S., Verdú, “On the interplay between conditional entropy and error probability,” IEEE Trans. Inf. Theory, vol. 56, no. 12, pp. 5930–5942, Dec. 2010.Google Scholar

[22] C., Uduwerelle, S.-W., Ho, and T., Chan, “Design of error-free perfect secrecy system by prefix codes and partition codes,” in Proc. IEEE Int. Symp. Inf. Theory, Cambridge, MA, USA, Jul. 2012, pp. 1593–1597.Google Scholar