Paper Info
Title
Extended capabilities for visual cryptography
Abstract
An extended visual cryptography scheme (EVCS), for an access structure (Γ Qual ,Γ Forb ) on a set of n participants, is a technique to encode n images in such a way that when we stack together the transparencies associated to participants in any set X ∈ Γ Qual we get the secret message with no trace of the original images, but any X ∈ Γ Forb has no information on the shared image. Moreover, after the original images are encoded they are still meaningful, that is, any user will recognize the image on his transparency. The main contributions of this paper are the following: • A trade-off between the contrast of the reconstructed image and the contrast of the image on each transparency for ( k , k )-threshold EVCS (in a ( k , k )-threshold EVCS the image is visible if and only if k transparencies are stacked together). This yields a necessary and sufficient condition for the existence of ( k , k )-threshold EVCS for the values of such contrasts. In case a scheme exists we explicitly construct it. • A general technique to implement EVCS, which uses hypergraph colourings. This technique yields ( k , k )-threshold EVCS which are optimal with respect to the pixel expansion. Finally, we discuss some applications of this technique to various interesting classes of access structures by using relevant results from the theory of hypergraph colourings. Keywords Visual cryptography Secret sharing schemes References [1] G. Ateniese C. Blundo A. De Santis D.R. Stinson Visual cryptography for general access structures Inform. Comput. 129 1996 86 106 [2] G. Ateniese, C. Blundo, A. De Santis, D.R. Stinson, Constructions and bounds for visual cryptography, in 23rd Int. Colloq. on Automata, Languages and Programming (ICALP ’96), Lecture Notes in Computer Science, vol. 1099, Springer, Berlin, 1996, pp. 416–428. [3] C. Blundo, P. D'Arco, A. De Santis, D.R. Stinson, Contrast optimal threshold visual cryptography schemes, 1998, submitted for publication. [4] C. Blundo, A. De Bonis and A. De Santis, Improved schemes for visual cryptography, 1998, submitted for publication. [5] C. Blundo, A. De Santis, Visual cryptography schemes with perfect reconstruction of black pixels, J. Comput. Graphics (special issue) Data security in image communications and networking 22-4 (1998) 449–455. [6] C. Blundo, A. De Santis, D.R. Stinson, On the contrast in visual cryptography schemes, J. Cryptol, to appear. [7] M. Bellare, O. Goldreich, M. Sudan, Free bits, PCPs and non-approximability — towards tight results, Proc. 36th IEEE Symp. on Foundations of Computer Science, 1995, pp. 422–431. [8] C. Berge Graphs and Hypergraphs 2nd Edition 1976 North-Holland Austerdam [9] S. Droste New results on visual cryptography Advances in Cryptology — CRYPTO ’96, Lecture Notes in Computer Science vol. 1109 1996 Springer Berlin 401 415 [10] M. Fürer, Improving hardness results for approximating the chromatic number, Proc. 36th IEEE Symp. on Foundations of Computer Science, 1995, pp. 414–421. [11] T. Hofmeister, M. Krause, H.U. Simon, Contrast-optimal k out of n secret sharing schemes in visual cryptography, COCOON ’97, Lecture Notes in Computer Science, vol. 1276, Springer, Berlin, 1997, pp. 176–185. [12] D. Naccache, Colorful Cryptography — a purely physical secret-sharing scheme based on chromatic filters, Coding and Information Integrity, French-Israeli Workshop, December 1994. [13] M. Naor, A. Shamir, Visual cryptography, in: Advances in Cryptology — Eurocrypt ’94, Lecture Notes in Computer Science, vol. 950, Springer, Berlin, 1995, pp. 1–12. [14] M. Naor, A. Shamir, Visual cryptography II: improving the contrast via the cover base, Theory of Cryptography Library, n. 96-07, 1996, Available at http://theory.lcs.mit.edu/ ∼ tcryptol /1996.html . [15] V. Rijmen, B. Preneel, Efficient colour visual encryption or shared colors of benetton, presented at EUROCRYPT ’96 Rump Session, available as http://www.iacr.org/conferences/ec96/rump /preneel.ps. [16] E.R. Verheul, H.C.A. van Tilborg, Constructions and properties of k out of n visual secret sharing schemes, Des. Codes Cryptogr. 11-2 (1997) 179–196.
Year
DOI
Venue
2001
10.1016/S0304-3975(99)00127-9
Theor. Comput. Sci.
Keywords
DocType
Volume
extended capability,visual cryptography
Journal
250
Issue
ISSN
Citations 
1-2
Theoretical Computer Science
56
PageRank 
References 
Authors
5.95
5
4
Name
Order
Citations
PageRank
Giuseppe Ateniese14380254.66
Carlo Blundo21901229.50
Alfredo De Santis34049501.27
Douglas R. Stinson42387274.83