[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Constructions and bounds for visual cryptography

  • Session 10: Algorithms I
  • Conference paper
  • First Online:
Automata, Languages and Programming (ICALP 1996)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1099))

Included in the following conference series:

Abstract

A visual cryptography scheme for a set P of n participants is a method to encode a secret image SI into n images in such a way that any participant in P receives one image and only qualified subsets of participants can “visually” recover the secret image, but non-qualified sets of participants have no information, in an information theoretical sense, on SI. A “visual” recover for a set X \(\subseteq \) P consists of stacking together the images associated to participants in X. The participants in a qualified set X will be able to see the secret image without any knowledge of cryptography and without performing any cryptographic computation.

In this paper we propose two techniques to construct visual cryptography schemes for any access structure. We analyze the structure of visual cryptography schemes and we prove bounds on the size of the image distributed to the participants in the scheme. We provide a novel technique to realize k out of n visual cryptography schemes. Finally, we consider graph-based access structures, that is access structures in which any qualified set of participants contains at least an edge of a given graph whose vertices represent the participants of the scheme. Our constructions for 2 out of n visual cryptography schemes are the best possible with respect to pixel expansion and relative difference.

Research of C. Blundo and A. De Santis is partially supported by Italian Ministry of University and Research (M.U.R.S.T.) and by National Council for Research (C.N.R.). Research of D. R. Stinson is supported by NSF grant CCR-9402141.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. G. Ateniese, C. Blundo, A. De Santis, and D. R. Stinson, Visual Cryptography for General Access Structures. Available from ECCC, Electronic Colloquium on Computational Complexity (TR96-012), via WWW using http://www.eccc.uni-trier.de/eccc/.

    Google Scholar 

  2. G. Ateniese, C. Blundo, A. De Santis, and D. R. Stinson, Extended Schemes for Visual Cryptography, preprint, 1995.

    Google Scholar 

  3. M. Atici, S. S. Magliveras, D. R. Stinson, and W.-D. Wei, Some Recursive Constructions for Perfect Hash Families, Technical Report UNL, Univ. of NebraskaLincoln, June 1995.

    Google Scholar 

  4. C. Blundo, A. De Santis, D. R. Stinson, and U. Vaccaro, Graph Decomposition and Secret Sharing Schemes, Journal of Cryptology, Vol. 8, (1995), pp. 39–64.

    Article  Google Scholar 

  5. M. L. Fredman and J. Komlós, On the Size of Separating System and Families of Perfect Hash Functions, SIAM J. Alg. Disc. Meth., Vol 5, No 1, March 1984.

    Google Scholar 

  6. J. H. van Lint and R. M. Wilson, A Course in Combinatorics, Cambridge University Press, (1992).

    Google Scholar 

  7. K. Melhorn, On the Program Size of Perfect and Universal Hash Functions, in Proc. of 23rd Annual IEEE Symposium on Foundation of Computer Science, pp. 170–175, 1982.

    Google Scholar 

  8. M. Naor and A. Shamir, Visual Cryptography, in “Advances in Cryptology — Eurocrypt '94”, A. De Santis Ed., Vol. 950 of Lecture Notes in Computer Science, Springer-Verlag, Berlin, pp. 1–12, 1995.

    Google Scholar 

  9. P. Elias, Zero Error Capacity Under List Decoding, IEEE Trans. Inform. Theory, Vol. 34, 1988.

    Google Scholar 

  10. G. J. Simmons, W. Jackson, and K. Martin, The Geometry of Shared Secret Schemes, Bulletin of the ICA, 1:71–88, 1991.

    Google Scholar 

  11. D. R. Stinson, Decomposition Constructions for Secret Sharing Schemes, IEEE Trans. Inform. Theory, Vol. 40, pp. 118–125, 1994.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dipartimento di Informatica ed Applicazioni, Università di Salerno, 84081, Baronissi, SA, Italy

    Giuseppe Ateniese, Carlo Blundo & Alfrede De Santis

  2. Department of Computer Science and Engineering and Center for Communication and Information Science, University of Nebraska-Lincoln, 68588, Lincoln, NE, USA

    Douglas R. Stinson

Authors
  1. Giuseppe Ateniese
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Carlo Blundo
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Alfrede De Santis
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Douglas R. Stinson
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Friedhelm Meyer Burkhard Monien

Rights and permissions

Reprints and permissions

Copyright information

© 1996 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Ateniese, G., Blundo, C., De Santis, A., Stinson, D.R. (1996). Constructions and bounds for visual cryptography. In: Meyer, F., Monien, B. (eds) Automata, Languages and Programming. ICALP 1996. Lecture Notes in Computer Science, vol 1099. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-61440-0_147

Download citation

  • DOI: https://doi.org/10.1007/3-540-61440-0_147

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-61440-1

  • Online ISBN: 978-3-540-68580-7

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation