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 standard-compliant 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. 45-54, 2012 (Acceptance rate: 15/48=31%) © SIAM
• Shujun Li, Andreas Karrenbauer, Dietmar Saupe and C.-C. Jay Kuo, "Recovering Missing Coefficients in DCT-Transformed Images," in Proceedings of 2011 18th IEEE International Conference on Image Processing (ICIP 2011, Brussels, Belgium, September 11-14, 2011), pp. 1537-1540, 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 DCT-Transformed Images," in Proceedings of 2010 17th IEEE International Conference on Image Processing (ICIP 2010, Hong Kong, China, September 26-29, 2010), pp. 2085-2088, 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:

• Takeyuki Uehara, Reihaneh Safavi-Naini and Philip Ogunbona, "Recovering DC coefficients in block-based DCT," IEEE Transactions on Image Processing, vol. 15, no. 11, pp. 3592-3596, IEEE, 2006

A unique feature of the approach is that it provide a general framework of ciphertext-only 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. 571-578, IEEE, 2014
• Dolev Pomeranz, Michal Shemesh and Ohad Ben-Shahar, "A fully automated greedy square jigsaw puzzle solver," in Proceedings of 2011 IEEE conference on Computer Vision and Pattern Recognition (CVPR 2011), pp. 9-16, 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. 680-690, IEEE, 2010
• Helena Cristina da Gama Leitao and Jorge Stolfi, "A Multiscale Method for the Reassembly of 2-D Fragmented Objects," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 24, no. 9, pp. 1239-1251, 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 self-restoration watermarking by Shujun Li and his co-authors:

• Hui Wang, Anthony TS Ho and Shujun Li, "A Novel Image Restoration Scheme Based on Structured Side Information and Its Application to Image Watermarking," Signal Processing: Image Communication, vol. 29, no. 7, pp. 773-787, 2014 © Elsevier Science B. V.

Are there other ways to cryptanalyze multimedia encryption schemes?

Yes, there are some other approaches some of which are briefed below.

Error-Concealment Attacks (ECA)

A more straightforward and "naive" method is the so-called Error-Concealment 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).

• Shujun Li, Chengqing Li, Kwok-Tung Lo and Guanrong Chen, "Cryptanalyzing an Encryption Scheme Based on Blind Source Separation," IEEE Transactions on Circuits and Systems-I: Regular Papers, vol. 55, no. 4, pp. 1055-1063, April 2008 © IEEE

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 Asia-Pacific 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. 1367-1378, John, Wiley & Sons, Inc., 2007

Known-Plaintext Attacks (KPA) and Chosen-Plaintext Attacks (CPA)

Some multimedia encryption schemes are not secure when some plaintexts are known or can be chosen by the attacker. The most well-studied multimedia encryption schemes in this context is permutation-only 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 Kwok-Tung 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 Kwok-Tung Lo, "A general quantitative cryptanalysis of permutation-only multimedia ciphers against plaintext attacks," Signal Processing: Image Communication, vol. 23, no. 3, pp. 212-223, 2008 © Elsevier Science B. V.

You are interested?

Please contact Shujun Li for possible collaborations! There are plenty of ideas but short of hands! :-)