# CS276 Lecture 18: Public Key Encryption

Scribed by Steve Hanna

Summary

Today we discuss the three ways in which definitions of security given in class differ from the way they are given in the Katz-Lindell textbook,.

Then we study the security of hybrid encryption schemes, in which a public-key scheme is used to encode the key for a private-key scheme, and the private-key scheme is used to encode the plaintext.

We also define RSA and note that in order to turn RSA into an encryption scheme we need a mechanism to introduce randomness.

# CS276 Lecture 26 (draft)

Summary

After showing that last week’s protocol for quadratic residuosity is indeed zero-knowledge, we move on to the formal definition of proof of knowledge, and we show that the quadratic residuosity protocol is also a proof of knowledge.

# CS276 Lecture 25 (draft)

Summary

Today we show that the graph isomorphism protocol we defined last time is indeed a zero-knowledge protocol. Then we discuss the quadratic residuosity problem modulo a composite, and define a protocol for proving quadratic residuosity. (We shall prove that the protocol is zero knowledge next time.)

# CS276 Lecture 24 (draft)

Summary

Today we introduce the notion of zero knowledge proof and design a zero knowledge protocol for the graph isomorphism problem.

# CS276 Lecture 23 (draft)

Summary

Today we show how to construct an efficient CCA-secure public-key encryption scheme in the random oracle model using RSA.

As we discussed in the previous lecture, a cryptographic scheme defined in the random oracle model is allowed to use a random function ${H: \{ 0,1 \}^n \rightarrow \{ 0,1 \}^m}$ which is known to all the parties. In an implementation, usually a cryptographic hash function replaces the random oracle. In general, the fact that a scheme is proved secure in the random oracle model does not imply that it is secure when the random oracle is replaced by a hash function; the proof of security in the random oracle model gives, however, at least some heuristic confidence in the soundness of the design.

# CS276 Lecture 22 (draft)

Summary

In the last lecture we described a very complex signature scheme based on one-time signatures and pseudorandom functions. Unfortunately there is no known simple and efficient signature scheme which is existentially unforgeable under a chosen message attack under general assumptions.

Today we shall see a very simple scheme based on RSA which is secure in the random oracle model. In this model, all parties have oracle access to a random function ${H : \{ 0,1 \}^n \rightarrow \{ 0,1 \}^m}$. In implementations, this random function is replaced by a cryptographic hash function. Unfortunately, the proof of security we shall see today breaks down when the random oracle is replaced by hash function, but at least the security in the random oracle model gives some heuristic confidence in the design soundness of the construction.

# Sigact News Draft

I would be grateful for any comments of my current draft of a survey paper I am writing for Sigact News on additive combinatorics and computer science. The paper was due a week ago, which was a strict deadline, so I probably will have to send it off quite soon.

# 100 More Years!

Today Rita Levi-Montalcini turns 100. One of six living Italian Nobel Laureates, Levi-Montalcini was born in 1909 and she was a young researcher in medicine when the 1938 “racial laws” promulgated by Mussolini forced all Italian Jews out of University positions. After the end of the war she moved to the US, to St. Louis, where she remained for thirty years and where she made her most important discovery: the “nerve growth factor.” She received the 1986 Nobel Prize in Medicine for her discovery.

Italy has a lovely tradition whereby the President can nominate distinguished citizens to become senators for life (all former Presidents are also senators for life). Levi-Montalcini has been senator-for-life since 2001. May her tenure last much longer!

p.s. the other living Italian Nobel Laureates are virologist Renato Dulbecco, playwright, writer and actor Dario Fo (winner of the Literature Prize), experimental high-energy physicist Carlo Rubbia, genetist Mario Capecchi (who has lived in the US since he was 9) and astrophysicist Riccardo Giacconi. Of the six, Dario Fo is the only one who is not a scientist, and the only one who did his prize-winning work in Italy. The sample space is small, but one can say that more than 83% of living Italian Nobel Laureates are scientists (yay for Italian scientists!) and that 100% of them had to go abroad to do their work (boo for Italy’s support of research!).

# Earliest Connections of Additive Combinatorics and Computer Science

I am writing a short survey on connections between additive combinatorics and computer science for SIGACT News and I have been wondering about the “history” of the connections. (I will be writing as little as possible about history in the SIGACT article, because I don’t have the time to research it carefully, but if readers help me out, I would write about it in a longer article that I plan to write sometime next year.)

Now, of course, there is always that Russian paper from the 1950s . . .

Then there is the Coppersmith-Winograd matrix multiplication algorithm, which uses Behrend’s construction of large sets of integers with no length-3 arithmetic progressions. (They don’t need the full strength of Behrend’s construction, and the weaker construction of Salem and Spencer suffices.) As far as I know, this was an isolated application.

My understanding (which is quite possibly mistaken) is that there are three main threads to the current interactions: one concerning the Szemeredi Regularity Lemma and the “triangle removal lemma” of Ruzsa and Szemeredi; one concerning “sum-product theorems” and the Kakeya problem; and one concerning the Gowers uniformity norms. The earliest connection is the first one, and, depending how one is counting, started in 1992 or 2001, and is due, respectively, to Alon et al. or just to Alon.