Image Encryption and Compression

Image Encryption and Compression
based on Shamir’s Scheme
Powered by Matlab

INTRODUCTION
 Data sharing is one of the main aspect in todays e-world. And
image is one of the most commonly used component over the
network. But every boon comes with a bane. Data over the
network are vulnerable to eavesdroppers.
 Thus image encryption comes into play as a shield to us.
Image Encryption is the process which uses a finite set of
instructions to convert original image into an encrypted form
that is unreadable by any intruder.
 For image encryption we use Shamir’s k-out-of-n Threshold
Secret Sharing Scheme. This algorithm encrypts each
information or pixels of the image into ‘n’ components,
thereby increasing the size of the encoded data to ‘n’ times
the original information.
 This in turn is followed by vector quantization which is carried
out to compress the encoded data.

SHAMIR’S (K, N) THRESHOLD SCHEME
Shamir’s Threshold Scheme refers to a Secret Sharing
Algorithm.
 In cryptography, secret sharing refers to a method for
distributing a secret among a group of participants, each of
which is allocated a share of the secret.
 The secret can only be reconstructed when the shares are
combined together ; individual shares are of no use on their
own.
 In Shamir’s Secret Sharing Scheme, a secret value ‘S’ is
divided into ‘n’ parts and minimum of ‘k’ number of
components are required to reconstruct the secret, where
k<=n.

MATHEMATICAL DEFINITION
The goal is to divide secret S into n pieces of data S1,S2… Sn
in such a way that:
 Knowledge of any k or more Si pieces makes S easily
computable.
 Knowledge of any k-1 or fewer Si pieces leaves S
completely undetermined.
This scheme is called (k, n) threshold scheme, where n is the
total number of parts in which the secret is broken into and k is
the threshold value, i.e., the least number of shares that are
required to reconstruct the secret value.
 If k = n then all participants are required to reconstruct the
secret.

MATHEMATICAL DEFINITION CONT.
 It takes k number of shares to define a polynomial of
degree k-1, where 0 < k <= n < p and S<p where p is a
prime number.
 Choose at random k-1 positive integers a1, a2, … ak-1 with
1<ai<p, and let a0 = S.
 Build the polynomial, f(x)=a0+a1x+a2x2 +a3x3 +…+ak-1xk-1.
 Let us construct any n points out of it, for instance set
i = 1, …, n to retrieve (i,f(i)).
 Given any subset of k of these pairs, we can find the
coefficients of the polynomial using Lagrange interpolation.
 The secret is the constant term a0.

Example
 Shares Construction Phase
 Input: n =6; k =3 and S = 206
 Step 1: Arbitrarily choose two random numbers
a1=166, a2=94 and a prime number p=257. Then,
construct a polynomial function :
f(x) = (S+a1.x+a2.x2) mod p
 Therefore f(x) = (206 + 166𝑥 + 94𝑥2
) mod 257
 Step 2: Compute six shares : {(i, f(i))} =
{(1,209),(2,143),(3,8),(4,61),(5,45),(6,217)} where i is 1
to 6.

Example Cont.
 Revealing Phase:
 Consider three shares chosen randomly: (2,143),
(4,61) ,(5,45)
 Step 1: Compute Lagrange basis polynomials
 L1 =
𝑥−𝑥2
𝑥1−𝑥2
x
𝑥−𝑥3
𝑥1−𝑥3
=
𝑥−4
2−4
x
𝑥−5
2−5
= (-2)-1 (𝑥 -4)(-3)-1(𝑥 -5)
 L2 =
𝑥−𝑥1
𝑥2−𝑥1
x
𝑥−𝑥3
𝑥2−𝑥3
=
𝑥−2
4−2
x
𝑥−5
4−5
= (2)-1 (𝑥 -2) (-1)-1(𝑥 -5)
 L3 =
𝑥−𝑥1
𝑥3−𝑥1
x
𝑥−𝑥2
𝑥3−𝑥2
=
𝑥−2
5−2
x
𝑥−4
5−4
= (3)-1 (𝑥 -2) (1)-1(𝑥 -4)

Example Cont.
Therefore
f(x) = (143 x ((-2)-1 x ( 𝑥 -4) x (-3)-1 x ( 𝑥 -5)) +
61 x ((2)-1 x ( 𝑥 -1) x (-1)-1 x ( 𝑥 -5)) +
45 x ((3)-1 x ( 𝑥 -2) x (1)-1 x ( 𝑥-4))) mod 257
= (143 x (128 x ( 𝑥 -4) x 171 x ( 𝑥 -5)) +
61 x (129 x ( 𝑥 -1) x 256 x ( 𝑥 -5)) +
45 x (86 x ( 𝑥 -2) x ( 𝑥 -4))) mod 257
= (51483 𝑥2 – 42294324 𝑥 + 82775280) mod 257
= 94 𝑥 2 + 166 𝑥 + 206
 Step 3: Obtain the secret data S = f(0) = 206

VECTOR QUANTIZATION
 Vector Quantization (VQ) is a lossy data compression method
 In 1980, Linde, Buzo, and Gray proposed a VQ design algorithm based
on a training sequence
 Vector quantization, also called "block quantization" or "pattern
matching quantization“ works by encoding values from a
multidimensional vector space into a finite set of values from a discrete
subspace of lower dimension.
 Divide the range of values that the source generates into a number of
intervals.
 Usually, the midpoint of the interval that is taken into account for
forming vectors and providing indices to each group of vectors.
 Set of values is mapped to an index corresponding to the closest
vectors to form a codebook
 Vector quantization technique is efficiently used in various areas of
biometric modalities like finger print pattern recognition, face
recognition by generating codebooks of desired size.

INVERSE QUANTIZATION
 Index in codebook is mapped to the computed vectors
closely representing the original values.
 In estimating the value, the dequantizer might generate
some errors.

BLOCK DIAGRAM
Input Image Shamir’s Encoding
Scheme
Vector QuantizationDe Quantization
Lagrange’s Basis
Polynomial
Encoded
Values
Codebook
Closest
Values
Output Image

RESULTS
Image
Name
Original Image
Size of
Input
Image
Size of
nX6
matrix
Size of
Codebook
Increase in size
from original
image to nX6
matrix (%)
Decrease in
size from nX6
matrix to
Codebook (%)
Change in size
from original
image to
Codebook (%)
Resultant Image Correlation Value
Lena
8.85
KB
67.7
KB
7.25
KB
664.97 % 82.57 %
18.08 %
decrease
0.9870
Mandrill
8.91
KB
53.8
KB
12.0
KB
503.82 % 77.70 %
34.68 %
increase
0.9839

FUTURE SCOPE
 We will optimize the whole process to
produce better and perfect image with least
approximation error possible.
 We will work upon rgb images also.

CONCLUSION
 Shamir’s secret sharing is one of the secured
sharing scheme where atleast k shares is
required to reconstruct the secret.
 Co-operation of all the shares is not required
to reconstruct the secret.
 It can be extended by adding on deleting
shares.
 After Encryption, Vector Quantization comes
as an assistance to highly compress the image
for efficient sharing of it over the Internet.

THANK YOU
Presented By :
Sayantan Sur
Riyanka Dhar
MCA 5th Semester

Image Encryption and Compression

Recommended

More Related Content

What's hot (20)

Similar to Image Encryption and Compression (20)

More from Sayantan Sur (12)

Recently uploaded (20)

Image Encryption and Compression