Abstract
We initiate the study of steganography (BS), an extension of steganography to the multi-recipient setting. BS enables a sender to communicate covertly with a dynamically designated set of receivers, so that the recipients recover the original content, while unauthorized users and outsiders remain unaware of the covert communication. One of our main technical contributions is the introduction of a new variant of anonymous broadcast encryption that we term outsider-anonymous broadcast encryption with pseudorandom ciphertexts((oABE$). Our oABE$ construction achieves sublinear ciphertext size and is secure in the standard model. Besides being of interest in its own right, oABE$ enables an efficient construction of BS secure in the standard model against adaptive adversaries with sublinear communication complexity.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abdalla, M., Bellare, M., Catalano, D., Kiltz, E., Kohno, T., Lange, T., Malone-Lee, J., Neven, G., Paillier, P., Shi, H.: Searchable encryption revisited: Consistency properties, relation to Anonymous IBE, and extensions. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 205–222. Springer, Heidelberg (2005)
Agrawal, S., Boyen, X.: Identity-based encryption from lattices in the standard model (2009) (manuscript), http://www.cs.stanford.edu/~xb/ab09/
von Ahn, L., Hopper, N.J.: Public-key steganography. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 323–341. Springer, Heidelberg (2004)
von Ahn, L., Hopper, N.J., Langford, J.: Covert two-party computation. In: ACM Symposium on Theory of Computing, STOC, pp. 513–522 (2005)
Anderson, R., Petitcolas, F.: On the limits of steganography. IEEE Journal on Selected Areas in Communications 16(4), 474–481 (1998)
Backes, M., Cachin, C.: Public-key steganography with active attacks. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 210–226. Springer, Heidelberg (2005)
Barth, A., Boneh, D., Waters, B.: Privacy in encrypted content distribution using private broadcast encryption. In: Di Crescenzo, G., Rubin, A. (eds.) FC 2006. LNCS, vol. 4107, pp. 52–64. Springer, Heidelberg (2006)
Berkovits, S.: How to broadcast a secret. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 535–541. Springer, Heidelberg (1991)
Boneh, D., Gentry, C., Waters, B.: Collusion resistant broadcast encryption with short ciphertexts and private keys. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 258–275. Springer, Heidelberg (2005)
Boneh, D., Katz, J.: Improved efficiency for CCA-secure cryptosystems built using identity-based encryption. In: Menezes, A. (ed.) CT-RSA 2005. LNCS, vol. 3376, pp. 87–103. Springer, Heidelberg (2005)
Boyen, X., Waters, B.: Anonymous hierarchical identity-based encryption (without random oracles). In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 290–307. Springer, Heidelberg (2006)
Cachin, C.: An information-theoretic model for steganography. Information and Computation 192(1), 41–56 (2004)
Cash, D.M., Kiltz, E., Shoup, V.: The twin Diffie-Hellman problem and applications. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 127–145. Springer, Heidelberg (2008)
Chandran, N., Goyal, V., Ostrovsky, R., Sahai, A.: Covert multi-party computation. In: IEEE Symposium on Foundations of Computer Science, FOCS, pp. 238–248 (2007)
Dedic, N., Itkis, G., Reyzin, L., Russell, S.: Upper and Lower Bounds on Black-Box Steganography. Journal of Cryptology 22(3), 365–394 (2009)
Dodis, Y., Fazio, N.: Public key broadcast encryption for stateless receivers. In: Feigenbaum, J. (ed.) DRM 2002. LNCS, vol. 2696, pp. 61–80. Springer, Heidelberg (2003)
Dodis, Y., Fazio, N.: Public-key trace and revoke scheme secure against adaptive chosen ciphertext attack. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 100–115. Springer, Heidelberg (2002)
Dodis, Y., Fazio, N., Kiayias, A., Yung, M.: Scalable public-key tracing and revoking. In: ACM Symposium on Principles of Distributed Computing, pp. 190–199 (2003); invited to the Special Issue of Journal of Distributed Computing, PODC 2003 (2003)
Dodis, Y., Fazio, N., Lysyanskaya, A., Yao, D.: ID-based encryption for complex hierarchies with applications to forward security and broadcast encryption. In: ACM Conference on Computer and Communications Security, pp. 354–363 (2004)
Dodis, Y., Katz, J.: Chosen-ciphertext security of multiple encryption. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 188–209. Springer, Heidelberg (2005)
Fazio, N.: On Cryptographic Techniques for Digital Rights Management. Ph.D. thesis, New York University (2006)
Fazio, N., Nicolosi, A.R., Perera, I.M.: Broadcast steganography. Cryptology ePrint Archive, Report 2013/078 (2013)
Fazio, N., Perera, I.M.: Outsider-anonymous broadcast encryption with sublinear ciphertexts. In: Fischlin, M., Buchmann, J., Manulis, M. (eds.) PKC 2012. LNCS, vol. 7293, pp. 225–242. Springer, Heidelberg (2012)
Fazio, N., Perera, I.M.: Outsider-anonymous broadcast encryption with sublinear ciphertexts. Cryptology ePrint Archive, Report 2012/129 (2012), full Version of [23]
Fiat, A., Naor, M.: Broadcast encryption. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 480–491. Springer, Heidelberg (1994)
Garay, J.A., Staddon, J., Wool, A.: Long-lived broadcast encryption. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 333–352. Springer, Heidelberg (2000)
Gentry, C.: Practical identity-based encryption without random oracles. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 445–464. Springer, Heidelberg (2006)
Gentry, C., Waters, B.: Adaptive security in broadcast encryption systems (with short ciphertexts). In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 171–188. Springer, Heidelberg (2009)
Halevy, D., Shamir, A.: The LSD broadcast encryption scheme. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 47–60. Springer, Heidelberg (2002)
Hopper, N.J.: Toward a Theory of Steganography. Ph.D. thesis, Carnegie Mellon University (2004)
Hopper, N.J.: On steganographic chosen covertext security. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 311–323. Springer, Heidelberg (2005)
Hopper, N.J., Langford, J., von Ahn, L.: Provably Secure Steganography. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 77–92. Springer, Heidelberg (2002)
Impagliazzo, R., Zuckerman, D.: How to recycle random bits. In: IEEE Symposium on Foundations of Computer Science—FOCS, pp. 248–253 (1989)
Katzenbeisser, S., Petitcolas, F.A.: Defining security in steganographic systems. In: Security and Watermarking of Multimedia Contents IV, pp. 50–56 (2002)
Kiayias, A., Raekow, Y., Russell, A.: Efficient steganography with provable security guarantees. In: Barni, M., Herrera-Joancomartí, J., Katzenbeisser, S., Pérez-González, F. (eds.) IH 2005. LNCS, vol. 3727, pp. 118–130. Springer, Heidelberg (2005)
Kiayias, A., Russell, A., Shashidhar, N.: Key-efficient steganography with provable security guarantees. In: Information Hiding—IH, pp. 118–130 (2012)
Kiayias, A., Samari, K.: Lower bounds for private broadcast encryption. In: Kirchner, M., Ghosal, D. (eds.) IH 2012. LNCS, vol. 7692, pp. 176–190. Springer, Heidelberg (2013)
Le, T., Kurosawa, K.: Efficient Public Key Steganography Secure Against Adaptive Chosen Stegotext Attacks. Cryptology ePrint Archive, Report 2003/244 (2003)
Libert, B., Paterson, K.G., Quaglia, E.A.: Anonymous broadcast encryption. In: Fischlin, M., Buchmann, J., Manulis, M. (eds.) PKC 2012. LNCS, vol. 7293, pp. 206–224. Springer, Heidelberg (2012)
Lysyanskaya, A., Meyerovich, M.: Provably Secure Steganography with Imperfect Sampling. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds.) PKC 2006. LNCS, vol. 3958, pp. 123–139. Springer, Heidelberg (2006)
Mazurczyk, W., Karas, M., Szczypiorski, K.: Skyde: A skype-based steganographic method (2013), http://arxiv.org/abs/1301.3632
Naor, D., Naor, M., Lotspiech, J.: Revocation and tracing schemes for stateless receivers. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 41–62. Springer, Heidelberg (2001)
Pedersen, T.P.: Non-interactive and information-theoretic secure verifiable secret sharing. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 129–140. Springer, Heidelberg (1992)
Simmons, G.: The Prisoners’ Problem and the Subliminal Channel. In: Advances in Cryptology—CRYPTO, pp. 51–67 (1983)
The Economist: Speaking with silence (February 2013)
Zuckerman, D.: General weak random sources. In: IEEE Symposium on Foundations of Computer Science—FOCS, pp. 534–543 (1990)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Fazio, N., Nicolosi, A.R., Perera, I.M. (2014). Broadcast Steganography. In: Benaloh, J. (eds) Topics in Cryptology – CT-RSA 2014. CT-RSA 2014. Lecture Notes in Computer Science, vol 8366. Springer, Cham. https://doi.org/10.1007/978-3-319-04852-9_4
Download citation
DOI: https://doi.org/10.1007/978-3-319-04852-9_4
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-04851-2
Online ISBN: 978-3-319-04852-9
eBook Packages: Computer ScienceComputer Science (R0)