More Web Proxy on the site http://driver.im/

research-article

Provable Secure Universal Steganography of Optimal Rate: Provably Secure Steganography does not Necessarily Imply One-Way Functions

Authors:

Sebastian Berndt,

Maciej LiśkiewiczAuthors Info & Claims

IH&MMSec '16: Proceedings of the 4th ACM Workshop on Information Hiding and Multimedia Security

Pages 81 - 92

https://doi.org/10.1145/2909827.2930796

Published: 20 June 2016 Publication History

Abstract

We present the first complexity-theoretic secure steganographic protocol which, for any communication channel, is provably secure, reliable, and has nearly optimal bandwidth. Our system is unconditionally secure, i.e. our proof does not rely on any unproven complexity-theoretic assumption, like e.g. the existence of one-way functions. This disproves the claim that the existence of one-way functions and access to a communication channel oracle are both necessary and sufficient conditions for the existence of secure steganography, in the sense that secure and reliable steganography exists independently of the existence of one-way functions.

References

[1]

M. Backes and C. Cachin. Public-key steganography with active attacks. In Proc. TCC, volume 3378 of Lecture Notes in Computer Science, pages 210--226. Springer, 2005.

Digital Library

[2]

F. Balado and D. Haughton. Optimum perfect universal steganography of finite memoryless sources. CoRR, abs/1410.2659, 2014.

[3]

M. Bellare, A. Desai, E. Jokipii, and P. Rogaway. A concrete security treatment of symmetric encryption. In Proc. FOCS, pages 394--403. IEEE, 1997.

Digital Library

[4]

C. Cachin. An information-theoretic model for steganography. Information and Computation, 192(1):41--56, 2004.

Digital Library

[5]

P. Comesaña and F. Pérez-González. On the capacity of stegosystems. In Proc. MM&Sec, pages 15--24. ACM, 2007.

Digital Library

[6]

N. Dedić, G. Itkis, L. Reyzin, and S. Russell. Upper and lower bounds on black-box steganography. Journal of Cryptology, 22(3):365--394, 2009.

Digital Library

[7]

T. Filler and J. Fridrich. Fisher information determines capacity of $\varepsilon$-secure steganography. In Proc. IH, volume 5806 of Lecture Notes in Computer Science, pages 31--47. Springer, 2009.

Digital Library

[8]

T. Filler, A. D. Ker, and J. J. Fridrich. The square root law of steganographic capacity for markov covers. In Proc. EI, Media Forensics and Security, volume 7254, pages 801--811. SPIE, 2009.

[9]

J. Fridrich. Steganography in digital media: principles, algorithms, and applications. Cambridge University Press, 2009.

Digital Library

[10]

O. Goldreich. The Foundations of Cryptography -- Volume 2, Basic Applications. Cambridge University Press, 2004.

Digital Library

[11]

O. Goldreich, S. Goldwasser, and S. Micali. How to construct random functions. Journal of the ACM, 33(4):792--807, 1986.

Digital Library

[12]

O. Goldreich and H. Krawczykt. Sparse pseudorandom distributions. Random Structures and Algorithms, 3(2):163--174, 1992.

Digital Library

[13]

N. J. Hopper. Toward a theory of steganography. Technical report, Technical Report Carnegie Mellon University-CS-04-157, Carnegie Mellon Univ., 2004.

[14]

N. J. Hopper, J. Langford, and L. Ahn. Provably secure steganography. In Proc. CRYPTO, volume 2442 of Lecture Notes in Computer Science, pages 77--92. Springer, 2002.

Digital Library

[15]

N. J. Hopper, L. von Ahn, and J. Langford. Provably secure steganography. IEEE Transactions on Computers, 58(5):662--676, 2009.

Digital Library

[16]

S. Katzenbeisser and F. A. Petitcolas. Defining security in steganographic systems. In Proc. EI, volume 4675, pages 50--56. SPIE, 2002.

[17]

A. D. Ker. The square root law in stegosystems with imperfect information. In Proc. IH, volume 6387 of Lecture Notes in Computer Science, pages 145--160. Springer, 2010.

Digital Library

[18]

A. D. Ker, P. Bas, R. Böhme, R. Cogranne, S. Craver, T. Filler, J. Fridrich, and T. Pevnỳ. Moving steganography and steganalysis from the laboratory into the real world. In Proc. IH&MMSec, pages 45--58. ACM, 2013.

Digital Library

[19]

A. D. Ker, T. Pevnỳ, J. Kodovskỳ, and J. J. Fridrich. The square root law of steganographic capacity. In Proc. MM&Sec, pages 107--116. ACM, 2008.

Digital Library

[20]

A. Kiayias, Y. Raekow, A. Russell, and N. Shashidhar. A one-time stegosystem and applications to efficient covert communication. Journal of Cryptology, 27(1):23--44, 2014.

Digital Library

[21]

T. V. Le and K. Kurosawa. Bandwidth optimal steganography secure against adaptive chosen stegotext attacks. In Proc. IH, volume 4437 of Lecture Notes in Computer Science, pages 297--313. Springer, 2006.

Digital Library

[22]

M. Liśkiewicz, R. Reischuk, and U. Wölfel. Grey-box steganography. Theoretical Computer Science, 505:27--41, 2013.

Digital Library

[23]

B. Ryabko and D. Ryabko. Constructing perfect steganographic systems. Information and Computation, 209(9):1223--1230, 2011.

[24]

Y. Wang and P. Moulin. Perfectly secure steganography: Capacity, error exponents, and code constructions. IEEE Transactions on Information Theory, 54(6):2706--2722, 2008.

Digital Library

Cited By

Iv JGeorgiou MMalozemoff AShrimpton T(2022)Security Foundations for Application-Based Covert Communication Channels2022 IEEE Symposium on Security and Privacy (SP)10.1109/SP46214.2022.9833752(1971-1986)Online publication date: May-2022
https://doi.org/10.1109/SP46214.2022.9833752
Giron AMartina JCustódio R(2021)Steganographic Analysis of BlockchainsSensors10.3390/s2112407821:12(4078)Online publication date: 13-Jun-2021
https://doi.org/10.3390/s21124078
Nakajima TKer A(2020)The Syndrome-Trellis Sampler for Generative Steganography2020 IEEE International Workshop on Information Forensics and Security (WIFS)10.1109/WIFS49906.2020.9360885(1-6)Online publication date: 6-Dec-2020
https://doi.org/10.1109/WIFS49906.2020.9360885
Show More Cited By

Index Terms

Provable Secure Universal Steganography of Optimal Rate: Provably Secure Steganography does not Necessarily Imply One-Way Functions
1. Security and privacy
  1. Cryptography
    1. Symmetric cryptography and hash functions
  2. Formal methods and theory of security
    1. Formal security models
2. Theory of computation
  1. Computational complexity and cryptography
    1. Cryptographic primitives

Recommendations

Unconditionally Secure Steganography Against Active Attacks

In this paper, we study unconditionally secure stegosystems against active attacks over an insecure channel in which an adversary can read and write a message. More specifically, we propose an information-theoretic model for steganography in the ...
Provably Secure Steganography

Steganography is the problem of hiding secret messages in "innocent-looking” public communication so that the presence of the secret messages cannot be detected. This paper introduces a cryptographic formalization of steganographic security in terms of ...
Secure universal designated verifier signature without random oracles

In Asiacrypt 2003, the concept of universal designated verifier signature (UDVS) was introduced by Steinfeld, Bull, Wang and Pieprzyk. In the new paradigm, any signature holder (not necessarily the signer) can designate the publicly verifiable signature ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

IH&MMSec '16: Proceedings of the 4th ACM Workshop on Information Hiding and Multimedia Security

June 2016

200 pages

ISBN:9781450342902

DOI:10.1145/2909827

General Chairs:
Fernando Pérez-González
University of Vigo, Spain
,
Patrick Bas
CNRS, University of Lille, France
,
Program Chairs:
Tanya Ignatenko
Eindhoven University of Technology, The Netherlands
,
François Cayre
Grenoble INP, University of Grenoble Alpes, France

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGMM: ACM Special Interest Group on Multimedia

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 June 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Best Student Paper

Author Tags

Qualifiers

Research-article

Conference

IH&MMSec '16

Sponsor:

SIGMM

IH&MMSec '16: ACM Information Hiding and Multimedia Security Workshop

June 20 - 22, 2016

Galicia, Vigo, Spain

Acceptance Rates

IH&MMSec '16 Paper Acceptance Rate 21 of 61 submissions, 34%;

Overall Acceptance Rate 128 of 318 submissions, 40%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
205
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)0

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Iv JGeorgiou MMalozemoff AShrimpton T(2022)Security Foundations for Application-Based Covert Communication Channels2022 IEEE Symposium on Security and Privacy (SP)10.1109/SP46214.2022.9833752(1971-1986)Online publication date: May-2022
https://doi.org/10.1109/SP46214.2022.9833752
Giron AMartina JCustódio R(2021)Steganographic Analysis of BlockchainsSensors10.3390/s2112407821:12(4078)Online publication date: 13-Jun-2021
https://doi.org/10.3390/s21124078
Nakajima TKer A(2020)The Syndrome-Trellis Sampler for Generative Steganography2020 IEEE International Workshop on Information Forensics and Security (WIFS)10.1109/WIFS49906.2020.9360885(1-6)Online publication date: 6-Dec-2020
https://doi.org/10.1109/WIFS49906.2020.9360885
Berndt SLiśkiewicz M(2020)On the universal steganography of optimal rateInformation and Computation10.1016/j.ic.2020.104632(104632)Online publication date: Oct-2020
https://doi.org/10.1016/j.ic.2020.104632
Giron AMartina JCustódio R(2020)Bitcoin Blockchain Steganographic AnalysisApplied Cryptography and Network Security Workshops10.1007/978-3-030-61638-0_3(41-57)Online publication date: 14-Oct-2020
https://doi.org/10.1007/978-3-030-61638-0_3

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents