##
This **preview** shows page *1-2-3*
out of 10 **pages**.

*View Full Document*

End of preview. Want to read all 10 pages?

Upload your study docs or become a GradeBuddy member to access this document.

View Full Document**Unformatted text preview:**

Introduction to Cryptography 15-503/15-589PJanuary 23, 2006Manuel BlumScribe: Michelle GoodsteinScribe Notes1 OverviewToday’s class will go over three topics:Reminders: Hamilton Cycle and Zero-Knowledge ProtocolsVisual Cryptography (closely related to one-time pad)Zero-knowledge subset sum This is a variant of subset sum, that is used in cryptography, requiringn integers of size n bits.The normal subset sum problem takes as input a tuple of numbers a = (a1, a2, ..., an) and an integerbound A. It either outputs a bit vector x = x1x2· · · xnsuch that xi∈ {0, 1}, andPni=1xiai= Aif one exists, or returns “none”.The variant we will discuss further requires that n is even,Pni=1xi= n/2 and that each of the aiis represented as an n-bit integer.Sources handed out in class:Visual Cryptography: http://www.cacr.math.uwaterloo.ca/˜dstinson/visual.html(Also, http://citeseer.ist.psu.edu/naor95visual.html is a good paper on Visual Cryptography, thoughit was not distributed in class).One time pad: http://en.wikipedia.org/wiki/One-timepad2 Review and thoughts about last lecture2.1 Hamilton Path/CycleLast time, we went over a zero-knowledge proof of Hamilton cycle. For yourself, construct a zero-knowledge proof of Hamilton path. There is some overlap between the proofs, and some key differences.2.2 Algorithms versus ProtocolsAn algorithm is a set of instructions that are followed faithfully (presumably by a computer)A protocol is a set of instructions that may or may not be followed faithfully. Protocols are usuallydesigned for multiple agents, and the agents can attempt to cheat. Promises are made only to those whofollow the protocol. If the protocol is not followed, no promises are made–an agent may win, or lose.2.3 Grey Paint ClarificationInformally, let us think of “grey paint” as the equivalent of the grey paint on lottery scratch tickets,where what is underneath the paint is obscur ed until the paint is scratched off. In the proof of HamiltonCycle, we used a concept of “grey paint” as something that could obscure private data from the Verifier,but could be “scratched off” selectively to reveal only pieces at a time. Grey paint will be replaced by a“bit commitment” s cheme later on in the course. Search for “bit commitment” to learn more.3 Visual Cryptography3.1 TerminologyThe purpose of visual cryptography is to provide a simple way to securely encrypt graphical im-ages. The end result does not require intensive mathematical computations; instead, it can be donevisually, using two transparencies that are overlaid. Since the goal is to encrypt a graphical im-age that can be visually decrypted, it makes sense to use images in the encryption themselves (see1Introduction to Cryptography 15-503/15-589PJanuary 23, 2006Manuel BlumScribe: Michelle Goodsteinhttp://citeseer.ist.psu.edu/naor95visual.html for more information). For the purpose of this discussion,lets assume that we are encrypting black and white images, so that each pixel can be represented asbeing either black or white.We are going to talk about “ying/yang” graphical bits, which we will call yits. Yits will be used as ourbuilding blocks for visual encryption, in a similar way that we normally use bits in binary computations.Any two images where each image occupies half the area and their overlay fills the area can be calledyits. (See table below for examples, using a circle instead of a square area).ying yang filled cell open cell8 : aKey to visual cryptography symbolsLet us call8the “ying” yit and:the “yang” yit. One important property of these yits is how theybehave when they are overlapped. Drawing a ying on top of a ying looks like a ying. Similarly, drawinga yang on top of a yang is simply a yang. However, if a ying is laid down on a yang, the result is a filledcircle. See table below for graphical illustration.ying + ying8+8=8yang + yang:+:=:ying + yang8+:=ayang + ying:+8=aAddition of yits3.2 Problem StatementWe will now consider the problem of encrypting a message M. M could be thought of as a rectangularpicture with m × n pixels, where each pixel is either solid black or solid white. Equivalently, M can bethought of as a matrix of size m × n where each cell is either 0 or 1.Alice has access to M and wants to graphically encrypt it before sending to Bob. Suppose, in addition,Alice has access to a random matrix Rm×n, which was constructed as follows.1. For each cell in the array R, Alice tosses a fair coin, equally likely heads or tails.2. If it lands heads, the cell is filled in with a ying. If it lands tails, it is filled in with a yang.3. The fair coin is tossed mn times, once for each cell in R, and each coin flip is independent. R hasabsolutely no information about M, and is created independently from M.After constructing R, Alice transmits R to Bob using a secur e private channel, so that both Aliceand Bob have access to R. Now, Alice can follow a protocol to generate a new visual message S, withthe property that S combined with R allows you to see M. Furthermore, S can be transmitted along apublic channel, without an adversary being able to discern M.This concept is similar to a one-time pad. Think of R as a page on the one-time pad, and M as themessage being encrypted. Then S represents the encrypted plaintext, and R the decryption key. Theprotocol presented is b oth simple and secure as long as a private channel for communication is available.However, the protocol presented has the property that for every message yit in M, Alice will have totransmit two to Bob (one in R, and another in S). The protocol follows.1. Alice constructs an array Sm×n:(a) For each cell in M,(b) If M[i,j] is empty, use R[i,j]’s yit (S[i,j] = R[i,j]).(c) If M[i,j] is filled in (a), flip R[i,j]’s yit2Introduction to Cryptography 15-503/15-589PJanuary 23, 2006Manuel BlumScribe: Michelle GoodsteinThis is shown graphically b elow:M[i,j] R[i,j] S[i,j]8 8: :a 8 :a : 8Relationship of M[i,j], R[i,j] and S[i,j]2. Alice sends S to Bob.3. To reconstruct the message M, Bob simply needs to overlay S and R. Whenever a 0 or open space isencoded, R[i,j] + S[i,j] = R[i,j] = S[i,j]. On the other hand, whenever a 1 or filled space is encoded,R[i,j] + S[i,j] will b e a filled space.A graphical table showing this is below, based loosely on the one located inhttp://www.cacr.math.uwaterloo.ca/~dstinson/visual.htmlM[i,j] R[i,j] S[i,j] R[i,j] + S[i,j]8 8 8: : :a 8 : aa : 8 aResults of R[i,j]