Shortcuts
What multimedia security do you mean?
As a broad research topic, multimedia security can be loosely split into digital watermarking, steganography and steganalysis, and multimedia encryption. This web page is mainly about multimedia encryption, although it also overlaps with digital watermarking.
For encryption of digital images and video sequences, several ideas have been widely used in the literature:

Total or selective encryption of blockwise DCT coefficients

Total or selective encryption of sign bits of blockwise DCT coefficients

Total or selective secret permutation of pixels or blocks or DCT coefficients inside a block

Total or selective encryption of other syntax elements in a compressed image or video sequence that can still maintain format compliance (i.e. encrypted images/video sequences can still be decoded by a standardcompliant decoder without knowledge of the decryption key)
The above ideas can be applied alone or combined (the latter is more common).
Why does discrete optimization matter?
Cryptanalysis of many multimedia encryption problems can be conducted by modelling the image/video recovery problem as a discrete optimization model and then solving it using standard discrete optimization tools or developing bespoke discrete optimization algorithms.
This is a less studied topic in multimedia encryption, and previous methods are often not based on discrete optimization or based on some local optimization approaches which can not find global optimum solutions.
Shujun Li has been working in this area since 2010 and produced two important milestone papers on cryptanalysis of selective encryption of blockwise DCT coefficients:

Sabine Cornelsen, Andreas Karrenbauer and Shujun Li, "Leveling the Grid," in Proceedings of the Meeting on Algorithm Engineering & Experiments, Kyoto, Japan, January 16, 2012 (ALENEX 2012), pp. 4554, 2012 (Acceptance rate: 15/48=31%) © SIAM

Shujun Li, Andreas Karrenbauer, Dietmar Saupe and C.C. Jay Kuo, "Recovering Missing Coefficients in DCTTransformed Images," in Proceedings of 2011 18th IEEE International Conference on Image Processing (ICIP 2011, Brussels, Belgium, September 1114, 2011), pp. 15371540, 2011 Companion Web Page (Media Coverage: Vision Systems Design) © IEEE

Shujun Li, Junaid Jameel Ahmad, Dietmar Saupe and C.C. Jay Kuo, "An Improved DC Recovery Method from AC Coefficients of DCTTransformed Images," in Proceedings of 2010 17th IEEE International Conference on Image Processing (ICIP 2010, Hong Kong, China, September 2629, 2010), pp. 20852088, 2010 Companion Web Page © IEEE
The basic idea behind the ICIP 2011 work is to represent the recovery problem as a linear programming (LP) model which can be solved in polynomial time. Shujun is currently generalizing the idea to other types of multimedia encryption methods. The above work outperforms the previous work and extends to recover not only DC coefficients:
A unique feature of the approach is that it provide a general framework of ciphertextonly attacks (COA) on multimedia encryption, which is the least studied area of cryptanalysis of multimedia encryption.
Other Related Topics
A highly related line of research is puzzle solving or image defragmenting such as the following work:

Hongsheng Li, Yuanjie Zheng, Shaoting Zhang and Jian Cheng, "Solving a Special Type of Jigsaw Puzzles: Banknote Reconstruction From a Large Number of Fragments," IEEE Transactions on Multimedia, vol. 16, no. 2, pp. 571578, IEEE, 2014

Dolev Pomeranz, Michal Shemesh and Ohad BenShahar, "A fully automated greedy square jigsaw puzzle solver," in Proceedings of 2011 IEEE conference on Computer Vision and Pattern Recognition (CVPR 2011), pp. 916, IEEE, 2011 (Companion Website)

Efthymia Tsamoura and Ioannis, "Automatic Color Based Reassembly of Fragmented Images and Paintings," IEEE Transactions on Image Processing, vol. 19, no. 3, pp. 680690, IEEE, 2010

Helena Cristina da Gama Leitao and Jorge Stolfi, "A Multiscale Method for the Reassembly of 2D Fragmented Objects," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 24, no. 9, pp. 12391251, IEEE, 2002
Extension to Digital Watermarking
The use of discrete optimization to cryptanalysis of multimedia encryption is effectively about image recovery where unknown information has a known special structure. This idea has also been applied to image authentication and selfrestoration watermarking by Shujun Li and his coauthors:
Are there other ways to cryptanalyze multimedia encryption schemes?
Yes, there are some other approaches some of which are briefed below.
ErrorConcealment Attacks (ECA)
A more straightforward and "naive" method is the socalled ErrorConcealment Attacks (ECA) which tries to replace encrypted elements by some values to reveal sufficient visual information that is concealed by encryption. A common practice is to replace all encrypted elements by a fixed value (the most likely values). Such methods can be also more intelligent in that the replacement can be driven by statistical rules (see one example in the following paper).
Sketch Attacks
This attack aims at a different goal: rather than trying to recover all pixels in the plaintext image, one can switch to recover as much as edge information to reveal the shapes of key objects in an encrypted image or video sequence.

Kazuki Minemura and KokSheik Wong, "Sketch Attacks: A Note on Designing Video Encryption Method in H.264/AVC," (@APSIPA) in Proceedings of 2014 Annual Summit and Conference of AsiaPacific Signal and Information Processing Association (APSIPA 2014), IEEE, 2014

Weihai Li and Yuan Yuan, "A leak and its remedy in JPEG image encryption," International Journal of Computer Mathematics, vol. 84, no. 9, pp. 13671378, John, Wiley & Sons, Inc., 2007
KnownPlaintext Attacks (KPA) and ChosenPlaintext Attacks (CPA)
Some multimedia encryption schemes are not secure when some plaintexts are known or can be chosen by the attacker. The most wellstudied multimedia encryption schemes in this context is permutationonly image ciphers which just shuffle positions of all pixels or blocks within a plaintext image. The idea can be generalized to video encryption easily. The following key papers have proved quantitative results of such attacks on digital images.

Chengqing Li and KwokTung Lo, "Optimal quantitative cryptanalysis of permutationonly multimedia ciphers against plaintext attacks," Signal Processing, vol. 91, no. 4, pp. 949–954, Elsevier, 2011

Shujun Li, Chengqing Li, Guanrong Chen, Nikolaos G. Bourbakis and KwokTung Lo, "A general quantitative cryptanalysis of permutationonly multimedia ciphers against plaintext attacks," Signal Processing: Image Communication, vol. 23, no. 3, pp. 212223, 2008 © Elsevier Science B. V.
You are interested?
Please contact Shujun Li for possible collaborations! There are plenty of ideas but short of hands! :)
Only one revision exists, which was created (or modified) by hooklee at Sunday, June 19, 2016 9:19:28 PM.
This page was locked and can only be edited by administrators.