Threshold visual secret sharing by random grids with improved contrast

https://doi.org/10.1016/j.jss.2013.03.062Get rights and content

Highlights

  • We improve the contrast of Chen and Tsao's (k, n) threshold scheme published in The Journal of Systems and Software 84 (2011) 1197–1208.

  • For (k, n) access structures satisfying k > n/2, the proposed scheme works the same way as Chen and Tsao's scheme.

  • For (k, n) access structures satisfying k  n/2, the contrast of the proposed scheme is strictly larger than that of Chen and Tsao's scheme.

  • Computer simulations for (2, 4) access structure show that our scheme outperforms Chen and Tsao's scheme significantly in visual quality.

Abstract

A (k, n) visual cryptographic scheme (VCS) is a secret sharing method, which encodes a secret image S into n share images in such a way that the stacking of any more than or equal to k share images will reveal S, while any less than k share images provide no information about S. Kafri and Keren (1987) firstly implements (2,2)-VCS by random grids (RG-based VCS). Compared to conventional solutions of VCS, RG-based VCSs need neither extra pixel expansion nor complex codebook design. However, for a long period, RG-based VCSs are confined to (2,2) access structure. Until recently, Chen and Tsao (2011) proposed the first (k, n) RG-based VCS. In this paper, we improve the contrast of Chen and Tsao (2011)'s threshold scheme. The experimental results show that the proposed scheme outperforms Chen and Tsao (2011)'s scheme significantly in visual quality.

Introduction

A (k, n) visual cryptographic scheme (VCS), first formally defined by Naor and Shamir (1995), is a secret sharing method, which encodes a secret image into n share images in such a way that the stacking of any more than or equal to k share images can reveal the secret image, while any less than k share images provide no information about the secret image. The main advantage of VCS is that the decoding process is directly done by human visual system, where no computation is needed.

Conventional solutions of VCS generally involve the design of a codebook. Random grids (RG), proposed by Kafri and Keren (1987), is another way to implement VCSs. Compared to conventional solutions of VCS, RG-based VCS has the following advantages:

  • 1.

    Need no extra pixel expansion

    Conventional solutions of VCS significantly increase the size of shares. For example, the best pixel expansion of (n, n)-VCS is 2n−1.

  • 2.

    Need no codebook design

    Conventional solutions of VCS need a codebook to support encoding, which is generally very difficult to realize. For example, the pixel expansion optimal (2, n)-VCS is equivalent to Sperner families having n sets and with minimal ground set size, referring to Ateniese et al. (1996).

Despite of all the above advantages, Kafri and Keren (1987) only gave the construction of (2,2) RG-based VCS. For a long period, there is no significant development of RG-based VCS. Until recently, Shyu (2009) and Chen and Tsao (2009) independently proposed the first (n, n) RG-based VCS. Soon after, Chen and Tsao (2011) firstly gave the construction of (k, n) RG-based VCS. Our work aims to improve the contrast of Chen and Tsao (2011)'s scheme, which is presented as Algorithm 4 in this paper. For (k, n) access structures satisfying k > n/2, the proposed scheme works the same way as Chen and Tsao (2011)'s scheme. For (k, n) access structures satisfying k  n/2, the proposed scheme strictly improves the contrast of Chen and Tsao (2011)'s scheme. For (2,4) access structure, the contrast of the stacking result of any two (resp. three, four) share images generated by Chen and Tsao (2011)'s scheme is 2/29 (resp. 2/17, 1/8), while the contrast of the stacking result of any two (resp. three, four) share images generated by the proposed scheme is 1/7 (resp. 1/4, 1/4). However, we cannot characterize the contrast of the proposed scheme by a general formula of k and n. Thus in general, the exact gap between contrasts of the proposed scheme and Chen and Tsao (2011)'s scheme cannot be given by this paper. At last, the computer simulations for (2,4) access structure are given for a binary image, a color image and a natural dithered image, which show that the proposed scheme outperforms Chen and Tsao (2011)'s scheme significantly in visual quality.

Since the proposed (k, n) RG-based VCS realizes the concept of secret sharing, it can be applied to scenarios where secret sharing works as an important tool. For example, the proposed scheme can be combined with techniques from Sklavos and Zhang (2007) to deal with the key management problem in distributed systems. If the share images are printed on transparencies, the proposed scheme can work well without the assistance of computer systems or electric power. Therefore, the proposed scheme is more reliable and is especially suitable for harsh environment, e.g. war and catastrophe. Besides, since the computer systems are vulnerable to viruses and trojan, it is conceivable that the proposed scheme can provide a higher level of security than computer based cryptography systems.

This paper is organized as follows. In Section 2, we give a brief review of VCSs and RG-based VCSs. In Section 3, we propose a new (k, n) RG-based VCS. In Section 4, we formally prove the correctness of the proposed scheme. In Section 5, we compare the experimental results of Chen and Tsao (2011)'s scheme and the proposed scheme. The paper is concluded in Section 6.

Section snippets

Codebook based VCS

In this section, we will firstly take a (2, 4)-VCS for example to give an intuitive idea of codebook based VCS. The following two basis matrices M0 and M1 define a (2, 4)-VCS, where “0” denotes a transparent pixel and “1” denotes an opaque pixel.

M0=1000100010001000,M1=1000010000100001.

Physically, only the stacking of two transparent pixels will result in a transparent pixel. Thus the stacking of two pixels can be seen as the OR operation of two bits from {0, 1}. To encode a transparent pixel in

Improve the contrast of (k, n) RG-based VCS

In this section, two (k, n) RG-based VCSs for binary images and color images respectively are presented.

Performance analysis

This section first reviews some useful tools and previous results. Then we analyze Algorithm 5 with the help of those tools. The contrast of Algorithm 5 is compared with that of Algorithm 4. At last, we try to compare the contrasts of Algorithm 5 and Wu and Sun (2012)'s scheme.

Experimental results

This section presents the experimental results for Algorithm 4, Algorithm 5 of (2,4) access structure, for binary, color and natural dithered images.

Conclusions

We proposed a new (k, n) RG-based VCS, which needs neither extra pixel expansion nor codebook design. Besides, the proposed scheme improves the contrast of Chen and Tsao (2011)'s threshold scheme, leading to significantly better visual quality of decoded images. However, the contrast of the proposed scheme is not given directly by k and n, and the exact gap between contrasts of the proposed scheme and Chen and Tsao (2011)'s scheme is still unknown, which is left as an open problem for further

Acknowledgements

This work was supported by NSFC grant no. 60903210, the “Strategic Priority Research Program” of the Chinese Academy of Sciences no. XDA06010701 and the IIE Cryptography Research Projects no. Y2Z0011102 and no. Y3Z001B102. Besides, many thanks to the anonymous reviewers for their valuable comments.

Teng Guo received the bachelor degree in information security from Harbin Institute of Technology, in 2009. He is currently a Ph.D. Candidate in the Institute of Information Engineering, Chinese Academy of Sciences. His research interests include visual cryptography, secret sharing, secure computation, game theory and financial cryptography. He served as reviewers for many celebrated international academic journals and conferences.

References (25)

  • M. Bose et al.

    Optimal (k, n) visual cryptographic schemes for general k

    Designs, Codes and Cryptography

    (2010)
  • Y. Chen et al.

    Comment on ``cheating prevention in visual cryptography''

    IEEE Transactions on Image Processing

    (2012)
  • Cited by (89)

    • XOR-based visual cryptography scheme with essential shadows

      2022, Journal of Visual Communication and Image Representation
      Citation Excerpt :

      In addition, as the values of k and n increase, the contrast and pixel expansion will decrease and increase exponentially, respectively. A growing number of researchers proposed a variety of schemes aimed at improving the performance of VCS in terms of parameters [8–10]. Literature [11] proposed a new progressive visual cryptography scheme, in which the constructed basis matrix could generate meaningful shadow images without size expansion.

    • Improved Henon Chaotic Map-based Progressive Block-based visual cryptography strategy for securing sensitive data in a cloud EHR system

      2022, International Journal of Intelligent Networks
      Citation Excerpt :

      A random grid and void-cluster-oriented post-processing-based VSS scheme were proved to ensure competitive visual quality by contextually eliminating the issue of visual quality and pixel expansion during decryption. Then, a visual cryptographic approach using a (k,n) approach was proposed for encoding the ‘k' secret key into ‘n' share images [12]. This (k,n)-based visual cryptographic approach also confirmed predominant visual quality by stacking several shares more outstanding than ‘k’ in a specific context.

    View all citing articles on Scopus

    Teng Guo received the bachelor degree in information security from Harbin Institute of Technology, in 2009. He is currently a Ph.D. Candidate in the Institute of Information Engineering, Chinese Academy of Sciences. His research interests include visual cryptography, secret sharing, secure computation, game theory and financial cryptography. He served as reviewers for many celebrated international academic journals and conferences.

    Feng Liu received the bachelor degree in computer science from Shandong University in 2003, and the Ph.D. degree in information security from the Institute of Software (IOS), Chinese Academy of Sciences (CAS), in 2009. He then joined the State Key Laboratory of Information Security (SKLOIS) Chinese Academy of Sciences after graduation, and was promoted as associate professor in 2011. In 2012, he became an associate professor of the Institute of Information Engineering (IIE), Chinese Academy of Sciences. Currently, he serves as the director of the Executive Office of SKLOIS. His research interests include visual cryptography, security protocols and security system. He served as the general chair of the SKLOIS Conference for Young Researchers for 2010 and 2013. He was invited to be a guest editor for a number of special journal issues and to be the PC member of some international academic conferences.

    ChuanKun Wu received the B.Sc. degree in 1985 from Qufu Teacher's College, China, the M.Sc. degree in 1988 from Northwest Telecommunications Engineering Institute, China, and the Ph.D. degree in engineering in 1994 from Xidian University, China. Since January 1988, he has been teaching at Xidian University, China. He was promoted by Xidian University to a Lecturer in 1990, an Associate Professor in 1992, and a Full Professor in 1995. In September 1995, he became a postdoctoral fellow at Queensland University of Technology, then from 1997 a research fellow at the University of Western Sydney, and from 2000 a Lecturer in the Department of Computer Science, Australian National University. In 2003, he joined the Institute of Software, Chinese Academy of Sciences, as a research professor in the State Key Laboratory of Information Security. In 2012, he joined the Institute of Information Engineering, Chinese Academy of Sciences. As a cofounder, he served as a program chair for the 2001, 2002, and 2003 International Workshop on Cryptology and Network Security (CANS) which has become a regular annual conference since 2005. He has served as an Associate Editor of IEEE COMMUNICATIONS LETTERS since 2001. He is a member of the editorial board of the International Journal of Network Security, and was invited to be a guest editor for a number of special journal issues, including the 2008 and 2009 issues of IEICE-Special Section on Information and Communication System Security. His current research interests include Boolean functions, wireless network security, and group-oriented cryptography.

    View full text