CS 647B Advanced Cryptography

Problem set #4

due on Monday April 10, 2000

 

 

  1. Code equivalence in ZK.

    2. We say that two linear codes C and C’ are equivalent if there exists a permutation matrix P (in each line and column, all elements are "0" except for one "1") and a base change matrix S (full rank) such that

    G’ = SGP

    where G, G’ are the generating matrices of C,C’ respectively. Give a perfect zero-knowledge interactive proof for the language

    Leqv = { (G,G’) | G is equivalent to G’ }.

     

  2. (N,J,K)-functions.

    3. Define f:{0,1}N-> {0,1}J to be an (N,J,K)-function (N>=K+J) if seeing any K bits of x in {0,1}N reveal absolutely nothing about f(x). For instance, f(x)=x1 XOR x2 XOR x3 is a (3,1,2)-function, since seeing any two bits of x reveal nothing about f(x). Moreover we say that such a function is an xor-(N,J,K)-function when each bit of the output is obtained by xoring input bits together.

    • Show that, there exists an xor-(N,J,K)-function if and only if there exists an [N,J,D] linear code, for D>=K+1.

    • How do these functions relate to question 3 of HW #3 ??

     

  3. Interactive parity tests.

 

Let X be Alice’s string of size n and X’ be Bob’s string. Suppose Eve knows nothing about X, but that she hears everything about their efforts to agree on a common string. We define a parity test for comparing X and X’ to be the following : Alice and Bob compute the XOR of the elements Xi, 1<=i<=n, that is

 

par(X) = XOR1≤i≤n Xi and par(X’) = XOR1≤i≤n Xi’.

 

• Show that par(X) = par(X’) if and only if dH(X,X’) is even.

 

Consider now, the following interactive error-correcting algorithm.

Suppose Alice and Bob know that the number of errors between X and X’ is roughly en. Suppose they randomize the errors by permuting the positions of the bits of their string at random. They then form 2en blocks X=B1..B2en of size 1/2e and for each of them compute the parity. If par(Bi) differs from par(Bi’) then these two blocks Bi,Bi’ are discarded. For each block not discarded, they discard one bits so to wipe out the information Eve may have obtained. Doing so, they keep Eve in perfect ignorance about their remaining string. The same method can be repeated several times until no errors remain.

 

• What is the probability that a block of size 1/2e contains more than one error ?

• What is the expected number of blocks of size 1/2e containing more than one error ?

 

As a function of e :

 

• How many errors are expected to remain after one step ?

• How many bits are expected not to be discarded after one step ?

• What is the expected resulting error rate e’ ?

• How many steps are expected to correct all errors ?

• How many bits are expected not to be discarded at the end of correcting all the errors, if they want to have at most probability 1/106 that some errors are still present ?