Review of a course in cryptography – Part 1/2

Due to two cancellations of my flight, I was trapped in the USA with a lonely X’mas. To cheer me up, I self-learned the lecture notes of 6.875 in MIT, taught by Prof Silvio Micali in 2010. I’m not a crypto person, but it’s never a bad idea to spend a beautiful X’mas with some knowledge I’m not good at.

Lecture 1-5: Intro

Lectures 1-2 are just some basic number theory. Lectures 3-5 start with two average-case hardness assumptions, the Discrete Logarithm Assumption (DLA) and the Integer Factorization Assumption (IFA). The constraint of “average-case” has been emphasized and will be later compared to the worst-case assumption in lattice. Next comes the details of the RSA trapdoor permutation and the critisisms upon its unsecurity: e.g. RSA might be easier than IFA.

Lecture 5-8: Goldwasser-Micali Cryptosystem based on QRA

Starting from the end of Lecture 5, the notes start to focus on the Goldwasser-Micali cryptosystem based on the Quadratic Residuosity (QR) Assumption. Lecture 6 proves that solving the QR with a probability of 1/2+e (in average-case) is equivalent to solving it nearly perfectly. The explicit public-key 1-bit cryptosystem adopts a composite n=pq, and the encryption is simply a random residue (or non-residue) according to the message bit. Breaking this cryptosystem will violate the QRA assumption for such n=pq. The multi-bit counterpart is simply the trivial concatenation of 1-bit systems using the same public/private key. If there are two messages to be distinguished by a poly-size circuit family, then it can also break the security of 1-bit system, using hybrid argument analysis.

Notice that the security of multi-bit cryptosystems has been defined in many ways. The polynomial-security assumes that for two messages \{m_0,m_1\}, the encryption distribution \{E(m_0)\} and \{E(m_1)\} are polynomial-time indistinguishable; the GM-security states that if some message is randomly chosen from \{m_0,m_1\}, then any polynomial adversary cannot tell which message it is w.p. better than 1/2; the semantic-security says that for all function over the message f(m), and a message m randomly drawn from the distribution, no poly-time circuit family guesses the value of f(m) with probability better than p_k, where p_k is the probability of the most frequent message in the distribution. Interestingly, these three definitions are equivalent and GM-security is the one that is often adopted for its simplicity.

Lecture 9-14: Pseudorandomness

Starting from Lecture 9 the notes have been discussing the pseudorandom generator (PRG). We want the generator to be unpredicted: giving the first i bits, the i+1-th cannot be predicted w.p. better than 1/2. Next, lecture 9 proves that if friendship-pairs (f,B) exist, then PRG exist. Here f is a one-way permutation and B is the hard-core predicate for f: B(x) is hard to compute given f(x), but easy given x. This PRG is simply the sequence of b_1=B(f^{k^d}(x)) \rightarrow \ldots \rightarrow b_{k^d}=B(f^1(x)).

A candidate of the friendship-pair is to let f(x)=g^x \pmod{p} and B(x)=0\textrm{\ if\ }x<=(p-1)/2,\textrm{\ and\ }1\textrm{\ if\ }x>(p-1)/2. Indeed, it is based on the discrete log assumption DLA. The proof is that under DLA, f is a one-way permutation. furthermore, if B is not a hard-core predicate, then one can use that subroutine to calculate the principal square root, and then even the discrete log directly. The major difficulty of the proof is to amplify the average success rate of the routine.

In Lecture 11, the notes prove the Yao’s Theorem saying that the next-bit-unpredictability is equivalent to passing all statistical tests: no poly-time algorithm can distinguish between the generated distribution and the uniform distribution. This is again using some hybrid argument. In particular, the reverse-order generation of the random sequence is not necessary; one can directly output B(f(x)), B(f^2(x)), \ldots.

In Lecture 12, the pseudorandom function family is defined. We are only interested in the PRF \mathcal{S}=\{\mathcal{S}_k\}_{k\in \mathbb{N}} as follows:

  • \mathcal{S}_k=\{f_i|i\in\{0,1\}^k\} can be indexed easily;
  • f_s(x) can be calculated efficiently, for all s,x\in\{0,1\}^k;
  • \mathcal{S}_k looks like truly random functions (no poly-time algorithm can distinguish them).

The construction of PRF from PRG is easy. Given a PRG G with expansion factor l(k)=2k, and define G_0(s),G_1(s) to be the first/second half of G(s), then f_s(x) := G_{x_n}(G_{x_{n-1}}(\ldots G_{x_1}(s) \ldots )). This construction is a PRF because of a tree-style hybrid argument, which is ignored here.

Some history and applications of PRF/PRG are mentioned in Lecture 13 and 14, including the fact that if one-way function exists, then PRG exists (and also PRF). Also, with the help of PRG, one can build an (communication) efficient public-key cryptosystem based on the existence of trapdoor permutation (but not a specific number-theory assumption), using the Goldreich-Levin theorem. The PRG gets rid of the random vectors that will be sent in the traditional Goldreich-Levin theorem.

However, this cryptosystem is not computational efficient enough. The Blum-Goldwassar public-key encryption scheme has been studied at the very ending of Lecture 14. Consider the trapdoor function (under IFA) f_n(x)=x^2 \pmod{n} where n=pq and p,q are primes congruent to 3 module 4. The least-significant bit of f_n(x) is unpredictable as the hard-core predicate. This enables us to get rid of the Goldreich-Levin theorem and obtain better computational complexity. Details are ignored here.

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

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