Visual Cryptography
Frederik Vercauteren University of Bristol, Merchant Venturers Building, Woodland Road, Bristol BS8 1UB frederik@[Link]
Frederik Vercauteren
University of Bristol 2001
November 30 2001
Overview
Introduction Basic 2 out of 2 scheme Modelling visual cryptography schemes Parameters of visual cryptography schemes Solution for k out of k scheme Extensions
Frederik Vercauteren
University of Bristol 2001
November 30 2001
Introduction
Eurocrypt 94: Naor and Shamir - Visual Cryptography Image split into 2 shares Decoding = stacking transparencies Perfectly secure, 1 share contains no information about image Extended to k out of n sharing problem Image split into n shares Any k stacked together reveal image Perfectly secure, any k , 1 shares contain no information
Frederik Vercauteren
University of Bristol 2001
November 30 2001
Basic Scheme: 2 out of 2
Black and white image: each pixel divided in 2 sub-pixels
Pixel Share 1 Share 2 Result
p=1 2 p=1 2 p=1 2 p=1 2
+ + + +
= = = =
Frederik Vercauteren
University of Bristol 2001
November 30 2001
Basic Scheme: Example
100 50 0
50
100
150
0 20 40 60 80 100
100 200
100
50 250 0 300 50 50 100 150 200 250 300 350 400 450 500 550 100
120 140 160 180 200 50 100 150 200 250
100 50
150
200 0 250 50 300 50 100 150 200 250 300 350 400 450 500 550
150
200
250
300 50 100 150 200 250 300 350 400 450 500 550
Frederik Vercauteren
University of Bristol 2001
November 30 2001
Basic Scheme - No Distortion
Black and white image: each pixel divided in 4 sub-pixels White pixel: shared into two identical sub-pixel layouts Black pixel: shared into two complementary sub-pixel layouts
Perfect security:
Layout was randomly chosen Each pixel has 2 black and 2 white sub-pixels
Vertical shares
Horizontal shares
Diagonal shares
Frederik Vercauteren
University of Bristol 2001
November 30 2001
Basic Scheme - No Distortion: Example
0 50 100
150
200
250
0 20 40 60
400 300
50 350 100
80 100
0
50
100
150
200
250
300
350
400
450
500
550
150
200
120 140 160 180
150 50
250
300 100 350
200 50 100 150 200 250
200
400 50 100 150 200 250 300 350 400 450 500 550
250
300
350
400 50 100 150 200 250 300 350 400 450 500 550
Frederik Vercauteren
University of Bristol 2001
November 30 2001
Visual Cryptography Schemes: Model
Each pixel (black or white): appears in n shares divided into m sub-pixels
1 pixel represented by n m Boolean matrix S = [si j]
si j = 1 iff jth sub-pixel in the ith transparency is black Example: 2 out of 2 scheme with 2 sub-pixels
01 10 White pixel: or 0 1 1 0 01 10 Black pixel: or 10 01
Frederik Vercauteren
University of Bristol 2001
November 30 2001
Visual Cryptography Schemes: Model
Combining shares i1; : : : ; ir gives Boolean or V of rows i1; : : : ; ir of S Grey level proportional to Hamming weight H(V ) Interpreted as black if H(V ) d for threshold d Interpreted as white if H(V ) d , m for relative difference 0
Example: 2 out of 2 scheme with 4 sub-pixels gives d = 4 and = 1=2 Resemblance of construction: linear codes based on groups VCS based on semi-groups, black sub-pixel cannot be undone
Frederik Vercauteren
University of Bristol 2001
November 30 2001
Visual Sharing Scheme: k out of n Solution consists of 2 collections of n m Boolean matrices C0 and C1
Share white pixel: randomly choose one matrix in C0 Share black pixel: randomly choose one matrix in C1 Solution is valid iff 3 conditions are met: 2. For any S 2 C1, the or of any k rows V satises H(V ) d 1. For any S 2 C0, the or of any k rows V satises H(V ) d , m
3. For any subset fi1; : : : ; iqg of f1; : : : ; ng with q k, the two collections Dt for t 2 f0; 1g obtained by restricting each matrix in Ct to rows fi1; : : : ; iqg are indistinguishable.
Frederik Vercauteren
10
University of Bristol 2001
November 30 2001
Visual Sharing Scheme: Parameters
Number of pixels m in share: Loss in resolution m as small as possible Relative difference : Loss in contrast as large as possible Size r of collections C0 and C1: log r is number of random bits needed to generate share Does not affect quality of the picture
Frederik Vercauteren
11
University of Bristol 2001
November 30 2001
General k out of k Scheme
Theorem: For all k there exists a general k out of k scheme with m=2
k ,1
2k,1
r = 2k,1!
Construct k 2k,1 matrices S0 (white pixels) and S1 (black pixels) as: S0 contains the 2k,1 vectors with even number of 1s S1 contains the 2k,1 vectors with odd number of 1s C0 and C1 consist of all permutations of columns in S0 and S1 Naor and Shamir: any k out of k scheme 2k1 1 and m 2k,1 ,
Frederik Vercauteren
12
University of Bristol 2001
November 30 2001
General k out of k Scheme: Examples
k = 3, therefore m = 4, = 1=4 and r = 24
3 0011 S0 = 40 1 0 15 0110
2 3 0011 S1 = 40 1 0 15 1001
k = 4, therefore m = 8, = 1=8 and r = 40320 0 6 0 60 S =4 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 17 7 15 1
0 6 1 60 S =4 0 1
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 17 7 15 0
Frederik Vercauteren
13
University of Bristol 2001
November 30 2001
General k out of k Scheme: Example
Share 1
0 0
Share 2
0
Share 3
50
50
50
100
100
100
150
150
150
200
200
200
250
250
250
300
300
300
350
350
350
400 50 100 150 200 250 300 350 400 450 500 550
400 50 100 150 200 250 300 350 400 450 500 550
400 50 100 150 200 250 300 350 400 450 500 550
50
50
50
100
100
100
150
150
150
200
200
200
250
250
250
300
300
300
350
350
350
400 50 100 150 200 250 300 350 400 450 500 550
400 50 100 150 200 250 300 350 400 450 500 550
400 50 100 150 200 250 300 350 400 450 500 550
Share 1 + 2
Share 1 + 3
Share 2 + 3
Frederik Vercauteren
14
University of Bristol 2001
November 30 2001
General k out of k Scheme: Example
0
50
100
150
200
250
300
350
400 50 100 150 200 250 300 350 400 450 500 550
Frederik Vercauteren
15
University of Bristol 2001
November 30 2001
Extensions of VCS
Visual cryptography for general access structures Set of participants P = f1; : : : ; ng Qualied set GQual 2P , forbidden set GForb 2P / If GQual GForb = 0 then (GQual; GForb) is general access structure Example: P = f1; 2; 3; 4g and GQual generated by ff1; 4g; f1; 2; 3gg then 0 6 0 60 S =4 0 0
0 1 1 0
1 0 1 1
3 1 17 7 05 1
2 0 6 1 60 S =4 1 1
0 1 0 1
1 0 0 0
3 1 17 7 15 0
Frederik Vercauteren
16
University of Bristol 2001
November 30 2001
Extensions of VCS: Example
0 0 0 0 50 50 50 50 100 100 100 100 150 150 150 150
200
200
200
200
250
250
250
250
300
300
300
300
350
350
350
350
400 50 100 150 200 250 300 350 400 450 500 550
400 50 100 150 200 250 300 350 400 450 500 550
400 50 100 150 200 250 300 350 400 450 500 550
400 50 100 150 200 250 300 350 400 450 500 550
Share 1
Share 2
Share 3
Share 4
50
50
50
50
100
100
100
100
150
150
150
150
200
200
200
200
250
250
250
250
300
300
300
300
350
350
350
350
400 50 100 150 200 250 300 350 400 450 500 550
400 50 100 150 200 250 300 350 400 450 500 550
400 50 100 150 200 250 300 350 400 450 500 550
400 50 100 150 200 250 300 350 400 450 500 550
Share 1 + 4
Share 1 + 2 + 3
Share 1 + 2
Share 2 + 3 + 4
Frederik Vercauteren
17
University of Bristol 2001
November 30 2001
Extensions of VCS
Grey scale images: pixels range from 0 (white) to 256 (black) Encoding using rotated half-circles: Angle of rst half-circle is random Angle of second half-circle is chosen grey level
Share 1
Share 2
Result
Frederik Vercauteren
18
University of Bristol 2001
November 30 2001
Extensions of VCS
Different schemes for colour images Schemes for visual authentication and identication Concealment of existence of secret message: Each share contains innocent looking image Stacking shares reveals secret image No sign of innocent images remains
Frederik Vercauteren
19
University of Bristol 2001
November 30 2001