Review of a course in cryptography – Part 2/2

Continued from the previous post. This second part reviews the commitment scheme, the zero-knowledge, the digital signatures and the lattices.

Lecture 15-16: Commitment Schemes

A commitment scheme between the sender and the receiver satisfies two security properties: hiding and biding. The former says that the commitment looks random to the receiver before the decommitment, and the later says that the sender cannot generate two different but valid de-commitments. A trusted party in charge of generating e.g. public random bits might be necessary, however, it would be more desirable to design commitment schemes without such party.

A first example is based on OWP f (without trusted party). It can be associated with a hard-core predicate B (e.g. using Goldreich-Levin). For some randomly picked x, the commitment would be c=(f(x),B(x)+b) where b is the message bit. To de-commit the sender only needs to send x. The perfect binding follows from the oneway permutation, and the computational hiding follows from the hard-core predicate. Though a trusted party is not necessary here, one needs to make sure that f is verifiable to be a one-way permutation.

The second example is based on DLP (with trusted party). For some prime p, let some random generator g and y\leftarrow \mathbb{Z}_p^* be the common knowledge. Then the commitment would be c=g^r y^b \pmod{p} for some random r, and the de-commitment be r itself. The perfect hiding follows from the randomly chosen r, and the computational binding follows from the DLA.

The third example is based on OWF (with interactive scheme, without a trusted party). Because of the existence of OWF, we have PRG G. First let the receiver send a random 3k-bit string r to the sender, and then the sender draws a k-bit seed s, and sends G(s)\oplus r as a commitment for 1, and G(s) as a commitment for 0. This is computational hiding because of the pseudorandomness of G, and statistically binding because to find a conflict of G(s_1)=G(s_2)\oplus r for some random r is w.p. 2^{-k}.

The fourth example is based on hardness of factoring. Let \textsf{QR}(n) be the set of quadratic residue module n=pq, where p=3 \pmod{8}, q=7\pmod{8}. Now both f_0(x)=x^2 \pmod{n} and f_1(x)=4x^2 \pmod{n} are permutations over \textsf{QR}(n), but they are claw-free: i.e. it is hard to find f_0(x)=f_1(y).

Now, the commitment would be (after some prefix-free encoding) to take some random x\in \textsf{QR}(n) and output f_{m_0}(f_{m_1}(\ldots(x)\ldots)). It is perfectly hiding because a random input after some permutation is still random; it is computational binding following from the claw-free property.

Lecture 17-18: Zero-Knowledge

Zero knowledge IP system is defined as an IP such that for all PPT verifier \tilde{V}, there exists some PPT S that can generate the “view” of the verifier as if he has interacted with the prover. Two things are important here: first, it needs to hold for all verifier \tilde{V} because even dishonest verifier should not be able to extract knowledge; second, the “view” is defined as not only the communication history but also the randomness known to the verifier himself.

Besides the definition, the examples of ISO and 3COLOR are given. The zero-knowledge proof for ISO is to let the prover send a random graph isomorphic to the two graphs, and then ask the verifier to randomly pick one of the graph and then send the mapping. The zero-knowledge proof for 3COLOR is to randomly permute the coloring and send the commitments of the colors to the receiver. The receiver can only ask one pair of nodes and check their colors.

Lecture 19-20: Digital Signature

Lecture 19 is missing from the folder, and therefore I referred to lecture 15-18 in 2009 of this same course.

Signature is something in which the verifier sends some message and oracle signs it. The signature must be unforgeable according to:

  • (single-message) knowing the public key and with one adaptive message to the oracle, the adversary cannot forge the signature for any (unqueried) message;
  • (multi-message) knowing the public key and with i adaptive messages to the oracle, the adversary cannot forge the signature for any (unqueried) message.

As expected, the RSA signature and the Rabin signature are not secure. One successful single-message secure signature adopts the claw-free permutation as mentioned in Lecture 15-16.
Assume we have two pairs of claw-free permutations: f_0,f_1,g_0,g_1, then let x,f_0,f_1,g_0,g_1 be the public key, and f_0^{-1},f_1^{-1},g_0^{-1},g_1^{-1} be the secret key. Given message m, the signature is a pair (R,z), where R is following from x by applying f_0^{-1},f_1^{-1} to some random y, and z is following from y by applying g_0^{-1},g_1^{-1} to (the prefix-encoding of) the message. To verify a signature, one needs to apply z the message using g and obtain y, and then apply R the y using f and check if it is x. It can be proved that, with the introduction of some random R, this signature scheme is robust against one single adaptive query from the adversary.

To obtain a multi-message signature, one needs to concatenate each message with some key to the next message. This makes the signature sig(m_i)=(R_i,z_i,y_{i-1},\ldots,y_1). To verify a message, the verifier starts with z_i and applies g according m_i to obtain y_i'. It then starts from R_i, apply f according to y_i', continue to apply y_{i-1}' and so on. It should eventually reach x if valid. This is unforgeable because of the claw-free property again.

Another easy single-message secure (one-time) signature is mentioned in the early Lecture 17 (2009) based on OWF f. The public key is (f(x_1),f(x_2)),\ldots,(f(x_{2k-1},x_{2k})), and the signature sig(m)=x_{1+m_1}x_{3+m_2}\ldots x_{2k-1+m_k}. To verify the signature one simply calculates the function f and check if it coincides the public key.

In Lecture 20 (2010), another way of constructing multiple-message scheme using one-time signature is given, with better efficiency than the simply concatenation mentioned two paragraphs earlier. The major difference is that instead of using a sequence of messages, one can use a Merkle Tree so that the signature will only be of logarithmic length. To ensure that we do not need to store the whole tree, the PRF can again be adopted. Details ignored here.

Lecture 21-26: Lattices (taught by Yael Tauman Kalai)

Some basic algebraic knowledge about lattices are defined in lecture 21, and then the hardness of finding the shortest vector or some vector closest to a given vector is addressed in lecture 22. The LLL Algorithm that uses the Gram-Schmidt orthogonalization to solve the shortest vector with an exponential approximation factor is given in lecture 22 and 23. The main difficulty is to find some LLL-reduced basis with small Schmidt coefficient \mu_{i,j} = \langle b_i,\tilde{b_j}\rangle / \|\tilde{b_j}\|^2 < 1/2. This is done by performing rounded version of Gram-Schmidt orthogonalization, and swapping i,i+1 whenever \|\tilde{b}_{i+1}\|<\frac{1}{3}\|\tilde{b}_i\|. This algorithm terminates in poly-time.

Though there are many important applications of lattices, the notes only manage to mention one of them in details. That is to base on the worst-case lattice assumption, one can construct a collision-resilient hash function, which is as simple as f_A(x)=Ax \pmod{q}. One can reduce any poly-time collision-finding algorithm to a solver for any GapSVP for any lattice (i.e. in the worst case).

The first step of the reduction is to consider a problem GDD, that is given some target vector t, find some vector x in the lattice such that \|t-x\| is no more than \gamma fraction of the “covering radius” – a global largest distance of any point to the lattice. A solution of GDD_{\gamma} implies GapSVP_{\gamma \cdot n^{3/2}}. Notice that this is the major tool for us to relate an average-case problem to some worst-case assumption.

The second step is the smoother. Starting from an arbitrary point, as long as the deviation is large enough (still poly), the Gaussian distribution module P(B), the fundamental parallelepiped, is close enough to the uniform distribution. The last step is the algorithm which is stated in the end of lecture 25. Complicated so ignored here.

In sum, if there exists some collision-finder, then the GDD_{n^3} can be solved in the worst-case (for an arbitrary t).

The last lecture slightly mention the learning with error (LWE) assumption and its relationship with te lattice assumption. A public-key encryption is also mentioned under such assumption.

This entry was posted in Cryptogaphy, Readings. Bookmark the permalink.

2 Responses to Review of a course in cryptography – Part 2/2

  1. vassmann says:

    It’s a wonderful thing to advertise theory and explain interesting concepts that are more difficult to grasp, but with these posts you aren’t doing anything but brag that you’ve read some lecture notes.

    As a suggestion, if you were really intending to write something new/useful, you could try to prove a theorem that seemed exciting to you. Or you could show the general idea behind some research topic. At least put some links to relevant materials.

  2. Thanks for your suggestion. The contain of this blog contains my liteature review and (in the future) new ideas. Since my current research topic is still underground, I could only write something in the former.

    I chose to write “reviews” because 2 months ago, I realized that whenever I am trying to summarize things, I get to understand them much much better. This is especially true for lecture notes because they are written down by different people and (in most of the time) not well-organized. On the other hand, it is not always easy to write a concrete proof for some theorem I am interested in. Instead, I prefer write down the general ideas behind the proof. This provides me a reference to look back whenever I need something here in the future.

    I apologize if this lecture review fails to include a reference (unlike my previous learning theory reviews), since the lecture notes are not published anywhere, but well-spreaded in the us.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s