Dr. Dobb's Journal - October 2007 - (Page 22)

Core Technology by Daniel Stoleru Visual Cryptography and Bit-Plane Complexity Segmentation Putting the power of secret sharing to work Steganography is defined as “the art and science of writing hidden messages such that no one Daniel is a senior programmer for the Aareal Bank in Germany, and a doctoral student in applied cryptography at the Military Technical Academy in Romania. He can be contacted at danielst@gmx.com. apart from the intended recipient knows of the existence of the message” (en.wikipedia .org/wiki/Steganography). In implementing steganography applications, you can embed information in both the image domain itself and in one of the image’s transformed domains— frequency, cosine, or wavelet. In this article, I describe a steganography technique based on BitPlane Complexity Segmentation (BPCS) and visual cryptography. To test its viability, I implemented the technique in Python. Bit-Plane Complexity Segmentation, a lossy imagecompression technique first proposed at the Kyushu Institute of Technology, lets you embed large amounts of data in images. But to do so, you need visual cryptography to decompose a message in two shares with a highly random character. Generally, visual cryptography is considered a visual form of secret sharing; see Doug Stinson’s article “Visual Cryptography and Threshold Schemes” (www.ddj.com/184410530) and my article “Extended Visual Cryptography Schemes” (www.ddj.com/dept/ architect/184406280). In its simplest form, a (2,2) visual cryptography scheme “splits” the original image into two “shadow images” called “shares.” Every pixel in the original image is expanded to a 2✕2 pixel matrix with a different version in any of the two shares. Any share contains uniformly distributed random black-andwhite pixels. By analyzing only a single share, you can’t obtain information about the original image, no matter how much computing power or analysis method is used. The whole point of visual cryptography is that in the decryption process, the original image has to be visually reconstructed. Each share is printed on a separate transparency and passed to a participant at the scheme. When the two participants come together, the secret can simply (and theoretically instantaneously) be reconstructed by stacking the two transparencies. To build the shares, the visual cryptography scheme my application uses only considers diagonal matrices—see Versions 1 and 2 in Table 1. Figure 1 is an example of the visual cryptography scheme implemented by the application. Bit-Plane Complexity Segmentation Bit-Plane Complexity Segmentation (BPCS) relies on the fact that the human visual system is sensitive to patterns, but unable to identify random white noise. Therefore, if you want to implement a BCPS algorithm, you divide the image into regions and calculate the complexity of these regions. Any region with complexity Table 1: A (2,2) visual cryptography scheme. 22 Dr. Dobb’s Journal l www.ddj.com l October 2007 http://en.wikipedia.org/wiki/Steganography http://en.wikipedia.org/wiki/Steganography http://www.ddj.com/184410530 http://www.ddj.com/dept/architect/184406280 http://www.ddj.com/dept/architect/184406280 http://www.ddj.com

Table of Contents Feed for the Digital Edition of Dr. Dobb's Journal - October 2007

Cover Contents Hmmmm Alia Vox Developer Diaries Developer’s Notebook AI: It’s OK Again! Conversations Visual Cryptography and Bit-Plane Complexity Segmentation Inside the Windows Vista Disk Encryption Algorithm Memory-Aware Components Software and the Core Description Process Logging In C++ Effective Concurrency The Agile Edge Swaine’s Flames

Dr. Dobb's Journal - October 2007

For optimal viewing of this digital publication, please enable JavaScript and then refresh the page. If you would like to try to load the digital publication without using Flash Player detection, please click here.