Distributed keyless security for correlated data with applications in visual sensor networks

ABSTRACT

This paper examines the problem in which several nodes sharing highly correlated data, such as visual data, wish to compress and encrypt their data to provide confidentiality. The nodes however perform these tasks separately, without communicating with one another and without the use of cryptographic keys. The base station (BS) receiving all such encrypted data, can reconstruct each of the nodes' data, whereas a passive eavesdropper who is only allowed a subset of the encrypted data gleans as little information as possible about the nodes' data.

We build on previous results with the goal of increasing secrecy (measured by Shannon equivocation) by: (1) relaxing the BS's perfect reconstruction criterion thus permitting non-zero distortion reconstruction; (2) permitting communication (feedback) from the BS to the nodes. We show that permitting non-zero distortion reconstruction does increase secrecy, however unconditional secrecy is still not achievable unless the distortion is maximal. We also prove that feedback from the BS usually (under most practical scenarios) does not improve secrecy, unless the BS has certain knowledge concerning the eavesdropper.

Finally this paper proposes ideas for applying the results to images by analyzing the ideal image model to demonstrate the practical difficulties in achieving provable security for images.

REFERENCES

• 1: R. Ahlswede and I. Csiszár. Common randomness in information theory and cryptography - part I: Secret sharing. IEEE Trans. on Information Theory, 39(4):1121--1132, July 1993.
• 2: J. Barros and S. D. Servetto. On the rate-distortion region for separate encoding of correlated sources. In IEEE International Symposium on Information Theory, page 171, Yokohama, Japan, June 29 - July 4 2003.
• 3: C. H. Bennett, G. Brassard, C. Crépeau, and U. M. Maurer. Generalized privacy amplification. IEEE Trans. on Information Theory, 41(6):1915--1923, November 1995.
• 4: T. Berger, Z. Zhang, and H. Viswanathan. The CEO problem. IEEE Trans. on Information Theory, 42(3):887--902, May 1996.
• 5: T. Berger, Z. Zhang, and H. Viswanathan. The CEO problem. IEEE Trans. on Information Theory, 42(3):887--902, May 1996.
• 6: I. Deslauriers. Distributed encryption and the Slepian-Wolf theorem. In Canadian Conference on Electrical and Computer Engineering, pages 93--97, Saskatoon, Sask., Canada, May 2005.
• 7: Borko Furht , Darko Kirovski, Multimedia Security Handbook, CRC Press, Inc., Boca Raton, FL, 2004
• 8: Oded Goldreich, Foundations of Cryptography: Basic Tools, Cambridge University Press, New York, NY, 2000
• 9: K. B. Housewright. Source Coding Studies for Multiterminal Systems. PhD thesis, University of California, Los Angeles, 1977.
• 10: R. M. Kahn. Privacy in Multi-user Information Theory. PhD thesis, Stanford University, 1979.
• 11: E. D. Karnin, J. W. Greene, and M. E. Hellman. On secret sharing systems. IEEE Trans. on Information Theory, 29(1):35--41, January 1983.
• 12: Oleksiy Koval , Svyatoslav Voloshynovskiy , Taras Holotyak , Thierry Pun, Information-theoretic analysis of steganalysis in real images, Proceedings of the 8th workshop on Multimedia and security, September 26-27, 2006, Geneva, Switzerland [doi>10.1145/1161366.1161370]
• 13: L. Lai, H. E. Gamal, and H. V. Poor. The wiretap channel with feedback: Encryption over the channel. IEEE Trans. on Information Theory, 2007. submitted.
• 14: S. K. Leung-Yan-Cheong. Multi-User and Wire-Tap Channels Including Feedback. PhD thesis, Stanford University, Stanford, CA, 1976.
• 15: S. P. Lloyd. Least squares quantization in PCM. IEEE Trans. on Information Theory, 28(2):129--137, March 1982.
• 16: W. Luh and D. Kundur. Distributed keyless secret sharing over noiseless channels. In IEEE Globecom, Washington, D. C., November 25-30 2007.
• 17: W. Luh and D. Kundur. Separate enciphering of correlated messages for confidentiality in distributed networks. In IEEE Globecom, Washington, D.C., November 25-30 2007.
• 18: U. M. Maurer. Secret key agreement by public discussion from common information. IEEE Trans. on Information Theory, 39(3):733--742, May 1993.
• 19: J. Max. Quantizing for minimum distortion. IRE Trans. on Information Theory, 6:7--12, March 1960.
• 20: M. Naor and A. Shamir. Visual cryptography. In Advances in Cryptology - EUROCRYPT '94. Workshop on the Theory and Application of Cryptographic Techniques. Proceedings, pages 1--12, 1995.
• 21: A. Nosratinia, G. Davis, Z. Xiong, and R. Rajagopalan. Wavelet, subband and block transforms in communications and multimedia, chapter Subband Image Compression, pages 1--49. Kluwer, 1999.
• 22: S. Sandeep Pradhan , Kannan Ramchandran, Distributed Source Coding: Symmetric Rates and Applications to Sensor Networks, Proceedings of the Conference on Data Compression, p.363, March 28-30, 2000
• 23: L. Qiao and K. Nahrstedt. A new algorithm for MPEG video encryption. In International Conference on Imaging Science, Systems and Technology, pages 21--29, 1997.
• 24: Adi Shamir, How to share a secret, Communications of the ACM, v.22 n.11, p.612-613, Nov. 1979 [doi>10.1145/359168.359176]
• 25: C. E. Shannon. Communication theory of secrecy systems. Bell System Technical Journal, 28(4):656--715, 1949.
• 26: Yun Q. Shi , Huifang Sun, Image and Video Compression for Multimedia Engineering, CRC Press, Inc., Boca Raton, FL, 1999
• 27: D. Slepian and J. K. Wolf. Noiseless coding of correlated information sources. IEEE Trans. Inform. Theory, 19(4):471--480, July 1973.
• 28: Douglas R. Stinson, Cryptography: Theory and Practice, CRC Press, Inc., Boca Raton, FL, 1995
• 29: S.-Y. Tung. Multiterminal Source Coding. PhD thesis, Cornell University, 1978.
• 30: A. D. Wyner. The wire-tap channel. The Bell System Technical Journal, 54(8):1355--1387, October 1975.
• 31: H Yamamoto, On secret sharing communication systems with two or three channels, IEEE Transactions on Information Theory, v.32 n.3, p.387-393, May 1986 [doi>10.1109/TIT.1986.1057177]
• 32: H. Yamamoto. Rate-distortion theory for the Shannon cipher system. IEEE Trans. on Information Theory, 43(3):827--835, May 1997.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.1 Systems and Information Theory
          Subjects: Information theory

Additional Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.2 Compression (Coding)

General Terms:
Security, Theory

Keywords:
distributed secrecy, multiterminal source coding, shannon equivocation