28-07-2012, 03:12 PM
A SHORT SURVEY ON VISUAL CRYPTOGRAPHY SCHEMES
SHORT SURVEY.pdf (Size: 283.01 KB / Downloads: 49)
Abstract
Visual Cryptography Scheme (VCS) is an encryption method that uses
combinatorial techniques to encode secret written materials. The idea is to convert
the written material into an image and encode this image into n shadow images.
The decoding only requires only selecting some subset of these n images, making
transparencies of them, and stacking them on top of each other. In this survey paper,
we will provide the readers an overview of the basic VCS constructions, as well as
several extended work in the area. In addition, we also review several state-of-art
applications that take full advantage of such simple yet secure scheme.
Introduction
Suppose 4 intelligent thieves have deposited their loot in a Swiss bank account 1. These
thieves obviously do not trust each other. In particular, they do not want a single member
of themselves to withdraw the money and °ed. However, they assume that withdrawing
money by two members of the group is not considered a conspiracy, rather it is considered
to have received "authorizations". Therefore, they decided to encode the bank code (with
a trusted computer) into 4 partitions so that any two or more partitions can be used to
reconstruct the code. Since the thieves's representatives will not have a computer with
them to decode the bank code when they come to withdraw the money, they want to
be able to decode visually: each thief gets a transparency. The transparency should
yield no information about the bank code (even implicitly). However, by taking any two
transparencies, stacking them together and aligning them, the secret number should "pop
out". How can this be done?
Optimizations.
The optimality of VCS is determined mostly by its pixel expansion
m and the relative contrast ®. Pixel expansion m represents the loss in resolution from
the original image to the decoded one. Therefore m needs to be as small as possible. In
addition, m also needs to be in the form of n2 where n 2 N in order to preserve the
aspect ratio of the original image. On the other hand, the relative contrast ® needs to be
as large as possible to ensure visibility[1]. In the scope of this paper, we will only explore
works related to contrast optimization. Works related to deriving lower bound of pixel
expansion m can be found in [7], [8] etc.
The research on contrast optimization was motivated by the problem of extra greying
e®ect introduced to decoded image. This occurs because the decoded image is not an
exact reproduction of the original image, but an expansion of the original, with extra
black pixels. The black pixels in the original image will remain black if d=m. However,
the white pixels will become grey, due to the blackness introduced by the black sub-pixels,
which resulted in loss of contrast to the entire image.
Applications
Visual Cryptography Schemes can decode concealed images based purely on human
visual systems, without any aid from cryptographic computation. This nice property
gives birth to a wide range of encryption applications. In this section, we will discuss how
VCS is used in applications such as E-Voting system, ¯nancial documents and copyright
protections.
Electronic-Balloting System.
Nowadays, most of the voting are managed with
computer systems. These voting machines expected voters to trust them, without giving
proof that they recorded each vote correctly. One way to solve this problem is to issue
receipts to voters to ensure them their votes are counted. However, this could improperly
in°uence the voters, which produces coercion or vote selling problems. To solve this
dilemma, Chaum [6] proposed a secret-Ballot Receipts system that is based on (2,2)-
threshold binary VCS. It generates an encrypted receipt to every voter which allows her to
verify the election outcome - even if all election computers and records were compromised.
At the polling station, you will receive a double-layer receipt that prints your voting
decision. You will be asked to give one of the layer to the poll worker who will destroy it
immediately with a paper shredder. The remaining one layer will now become unreadable.
To make sure that your vote is not altered or deleted, you could querying the serial
number on your receipt on the election Web site.
conclusion
In this paper, we brie°y review the literature of visual cryptography schemes as special
instances of secret sharing methods among participants. We also described di®erent
constructions that generalize and optimize VCS. Among various advantages of VCS, we
emphasize the property that VCS decoding relies purely on human visual system, which
leads to a lot of interesting applications in private and public sectors of our society.