One-Time Padding Still Matters in Modern Cryptography

Table of Links

Abstract and I. Introduction

II. System Model

III. Secure and Private Source Coding Regions

IV. Gaussian Sources and Channels

V. Proof for Theorem 1

Acknowledgment and References

V. PROOF FOR THEOREM 1

A. Achievability Proof for Theorem 1

Proof Sketch: We leverage the output statistics of random binning (OSRB) method [16], [43], [44] for the achievability proof by following the steps described in [45, Section 1.6]

Communication Rate: (58) and (60) result in a communication (storage) rate

Privacy Leakage Rate: Since the private key K is uniformly distributed and is independent of source and channel random variables, we can consider the following virtual scenario to calculate the leakage. We first assume for the virtual scenario that there is no private key such that the encoder output for the virtual scenario i

We calculate the leakage for the virtual scenario. Then, given the mentioned properties of the private key and due to the one-time padding step in (52), we can subtract H(K) = nR0 from the leakage calculated for the virtual scenario to obtain the leakage for the original problem, which follows from the sum of (59) and (60) if ǫ → 0 when n → ∞. Thus, we have the privacy leaka

B. Converse Proof for Theorem 1

Privacy Leakage Rate: We obtain

n(Rℓ + δn)

Secrecy Leakage Rate: We have

Cardinality Bounds: We use the support lemma [48, Lemma 15.4] for the cardinality bound proofs, which is a standard step, so we omit the proof.

ACKNOWLEDGMENT

O. Gunlu and R. F. Schaefer were supported in part by the German Federal Ministry of Education and Research (BMBF) under the Grant 16KIS1004. H. Boche was supported in part by the BMBF within the national initiative on 6G Communication Systems through the research hub 6G-life under the Grant 16KISK002 and within the national initiative on Information Theory for Post Quantum Crypto “Quantum Token Theory and Applications - QTOK” under the Grant 16KISQ037K, which has received additional funding from the German Research Foundation (DFG) within Germany’s Excellence Strategy EXC-2092 CASA-390781972. H. V. Poor was supported in part by the U.S. National Science Foundation (NSF) under the Grant CCF-1908308.

REFERENCES

[1] D. Slepian and J. Wolf, “Noiseless coding of correlated information sources,” IEEE Trans. Inf. Theory, vol. 19, no. 4, pp. 471–480, July 1973.

[2] A. El Gamal and Y.-H. Kim, Network Information Theory. Cambridge, U.K.: Cambridge University Press, 2011.

[3] A. Orlitsky and J. R. Roche, “Coding for computing,” IEEE Trans. Inf. Theory, vol. 47, no. 3, pp. 903–917, Mar. 2001.

[4] O. Gunlu, “Function computation under privacy, secrecy, distortion, and communication constraints,” Entropy, vol. 24, no. 1, June 2022.

[5] V. Prabhakaran and K. Ramchandran, “On secure distributed source coding,” in Proc. IEEE Inf. Theory Workshop, Tahoe City, CA, Sep. 2007, pp. 442–447.

[6] D. Gunduz, E. Erkip, and H. V. Poor, “Secure lossless compression with side information,” in Proc. IEEE Inf. Theory Workshop, Porto, Portugal, May 2008, pp. 169–173.

[7] R. Tandon, S. Ulukus, and K. Ramchandran, “Secure source coding with a helper,” IEEE Trans. Inf. Theory, vol. 59, no. 4, pp. 2178–2187, Apr. 2013.

[8] D. Gunduz, E. Erkip, and H. V. Poor, “Lossless compression with security constraints,” in Proc. IEEE Int. Symp. Inf. Theory, Toronto, ON, Canada, July 2008, pp. 111–115.

[9] W. Luh and D. Kundur, “Distributed secret sharing for discrete memoryless networks,” IEEE Trans. Inf. Forensics Security, vol. 3, no. 3, pp. 1–7, Sep. 2008.

[10] K. Kittichokechai, Y.-K. Chia, T. J. Oechtering, M. Skoglund, and T. Weissman, “Secure source coding with a public helper,” IEEE Trans. Inf. Theory, vol. 62, no. 7, pp. 3930–3949, July 2016.

[11] S. Salimi, M. Salmasizadeh, and M. R. Aref, “Generalised secure distributed source coding with side information,” IET Commun., vol. 4, no. 18, pp. 2262–2272, Dec. 2010.

[12] F. Naghibi, S. Salimi, and M. Skoglund, “The CEO problem with secrecy constraints,” IEEE Trans. Inf. Forensics Security, vol. 10, no. 6, pp. 1234–1249, June 2015.

[13] H. Yamamoto, “Coding theorems for Shannon’s cipher system with correlated source outputs, and common information,” IEEE Trans. Inf. Theory, vol. 40, no. 1, pp. 85–95, Jan. 1994.

[14] H. Ghourchian, P. A. Stavrou, T. J. Oechtering, and M. Skoglund, “Secure source coding with side-information at decoder and shared key at encoder and decoder,” in Proc. IEEE Inf. Theory Workshop, Kanazawa, Japan, Oct. 2021, pp. 1–6.

[15] U. M. Maurer, “Secret key agreement by public discussion from common information,” IEEE Trans. Inf. Theory, vol. 39, no. 3, pp. 2733–2742, May 1993.

[16] R. Ahlswede and I. Csisz´ar, “Common randomness in information theory and cryptography - Part I: Secret sharing,” IEEE Trans. Inf. Theory, vol. 39, no. 4, pp. 1121–1132, July 1993. [

17] A. C. Yao, “Protocols for secure computations,” in Proc. IEEE Symp. Foundations Comp. Sci., Chicago, IL, Nov. 1982, pp. 160–164.

[18] ——, “How to generate and exchange secrets,” in Proc. IEEE Symp. Foundations Comp. Sci., Toronto, ON, Canada, Oct. 1986, pp. 162–167.

[19] M. Bloch et al., “An overview of information-theoretic security and privacy: Metrics, limits and applications,” IEEE J. Sel. Areas Inf. Theory, vol. 2, no. 1, pp. 5–22, Mar. 2021.

[20] O. Gunlu and G. Kramer, “Privacy, secrecy, and storage with multiple noisy measurements of identifiers,” IEEE Trans. Inf. Forensics Security, vol. 13, no. 11, pp. 2872–2883, Nov. 2018.

[21] O. Gunlu, M. Bloch, and R. F. Schaefer, “Secure multi-function computation with private remote sources,” Sep. 2021, [Online]. Available: arxiv.org/abs/2106.09485.

[22] T. Berger, Rate Distortion Theory: A Mathematical Basis for Data Compression. Englewood Cliffs, NJ: Prentice-Hall, 1971.

[23] H. Permuter and T. Weissman, “Source coding with a side information “Vending Machine”,” IEEE Trans. Inf. Theory, vol. 57, no. 7, pp. 4530– 4544, July 2011.

[24] T. Berger, Z. Zhang, and H. Viswanathan, “The CEO problem,” IEEE Trans. Inf. Theory, vol. 42, no. 3, pp. 887–902, May 1996. [25] O. Gunlu, “Key agreement with physical unclonable functions and biometric identifiers,” Ph.D. dissertation, TU Munich, Germany, Nov. 2018, published by Dr.-Hut Verlag in Feb. 2019.

[26] T. Ignatenko and F. M. J. Willems, “Biometric systems: Privacy and secrecy aspects,” IEEE Trans. Inf. Forensics Security, vol. 4, no. 4, pp. 956–973, Dec. 2009.

[27] L. Lai, S.-W. Ho, and H. V. Poor, “Privacy-security trade-offs in biometric security systems - Part I: Single use case,” IEEE Trans. Inf. Forensics Security, vol. 6, no. 1, pp. 122–139, Mar. 2011.

[28] L. Kusters, O. G ¨unl ¨u, and F. M. Willems, “Zero secrecy leakage for multiple enrollments of physical unclonable functions,” in Proc. Symp. Inf. Theory Sign. Process. Benelux, Twente, Netherlands, May-June 2018, pp. 119–127.

[29] L. Lai, S. W. Ho, and H. V. Poor, “Privacy-security trade-offs in biometric security systems - Part II: Multiple use case,” IEEE Trans. Inf. Forensics Security, vol. 6, no. 1, pp. 140–151, Mar. 2011.

[30] O. Gunlu, “Multi-entity and multi-enrollment key agreement with correlated noise,” IEEE Trans. Inf. Forensics Security, vol. 16, pp. 1190–1202, 2021.

[31] W. Tu and L. Lai, “On function computation with privacy and secrecy constraints,” IEEE Trans. Inf. Theory, vol. 65, no. 10, pp. 6716–6733, Oct. 2019.

[32] J. Villard and P. Piantanida, “Secure multiterminal source coding with side information at the eavesdropper,” IEEE Trans. Inf. Theory, vol. 59, no. 6, pp. 3668–3692, June 2013.

[33] S. I. Bross, “Secure cooperative source-coding with side information at the eavesdropper,” IEEE Trans. Inf. Theory, vol. 62, no. 8, pp. 4544– 4558, Aug. 2016.

[34] E. Ekrem and S. Ulukus, “Secure lossy source coding with side information,” in Proc. Allerton Conf. Commun., Control, Comput., Monticello, IL, Sep. 2011, pp. 1098–1105.

[35] J. Korner and K. Marton, “Comparison of two noisy channels,” Topics Inf. Theory, pp. 411–423, Aug. 1977.

[36] P. Bergmans, “A simple converse for broadcast channels with additive white Gaussian noise (Corresp.),” IEEE Trans. Inf. Theory, vol. 20, no. 2, pp. 279–280, Mar. 1974.

[37] O. Gunlu, R. F. Schaefer, and H. V. Poor, “Biometric and physical identifiers with correlated noise for controllable private authentication,” July 2020, [Online]. Available: arxiv.org/abs/2001.00847.

[38] A. D. Wyner and J. Ziv, “A theorem on the entropy of certain binary sequences and applications: Part I,” IEEE Trans. Inf. Theory, vol. 19, no. 6, pp. 769–772, Nov. 1973.

[39] S. Watanabe and Y. Oohama, “Secret key agreement from correlated Gaussian sources by rate limited public communication,” IEICE Trans. Fundam. Electron., Commun. Comp. Sci., vol. 93, no. 11, pp. 1976– 1983, Nov. 2010.

[40] F. M. Willems and T. Ignatenko, “Quantization effects in biometric systems,” in Proc. Inf. Theory Appl. Workshop, La Jolla, CA, Feb. 2009, pp. 372–379.

[41] V. Yachongka, H. Yagi, and Y. Oohama, “Secret key-based authentication with passive eavesdropper for scalar Gaussian sources,” Feb. 2022, [Online]. Available: arxiv.org/abs/2202.10018.

[42] T. M. Cover and J. A. Thomas, Elements of Information Theory, 2nd ed. Hoboken, NJ: John Wiley & Sons, 2012.

[43] M. H. Yassaee, M. R. Aref, and A. Gohari, “Achievability proof via output statistics of random binning,” IEEE Trans. Inf. Theory, vol. 60, no. 11, pp. 6760–6786, Nov. 2014.

[44] J. M. Renes and R. Renner, “Noisy channel coding via privacy amplification and information reconciliation,” IEEE Trans. Inf. Theory, vol. 57, no. 11, pp. 7377–7385, Nov. 2011.

[45] M. Bloch, Lecture Notes in Information-Theoretic Security. Atlanta, GA: Georgia Inst. Technol., July 2018.

[46] T. Holenstein and R. Renner, “On the randomness of independent experiments,” IEEE Trans. Inf. Theory, vol. 57, no. 4, pp. 1865–1871, Apr. 2011.

[47] M. Bloch and J. Barros, Physical-layer Security. Cambridge, U.K.: Cambridge University Press, 2011.

[48] I. Csisz´ar and J. K ¨orner, Information Theory: Coding Theorems for Discrete Memoryless Systems, 2nd ed. Cambridge, U.K.: Cambridge University Press, 2011.