CS276 Lecture 12 (draft)


Today we prove the Goldreich-Levin theorem. Continue reading


Neutronic Encryption

Via Boing Boing and Bruce Schneier, I bring you the web site of singularics corporation.

I cannot do justice to it, because every sentence on every page is very special, but here is about one of their products:

One very important result from our advances in mathematics is a new patent-pending encryption algorithm called Neutronic Encryption™. Unlike strong encryption algorithms widely used today, Neutronic Encryption is not based directly on fixed prime points, but rather on the Neutronic forces that govern the distribution of the primes themselves. The resulting encryption is theoretically impossible to break.

And, in more detail,

Singularics has advanced the state of the art in cryptography by developing a new theoretically unbreakable public-key algorithm called Neutronic Encryption™.

Our advances in Prime Number Theory have led to a new branch of mathematics called Neutronics. Neutronic functions make possible for the first time the ability to analyze regions of mathematics commonly thought to be undefined, such as the point where one is divided by zero. In short, we have developed a new way to analyze the undefined point at the singularity which appears throughout higher mathematics.

This new analytic technique has given us profound insight into the way that prime numbers are distributed throughout the integers. According to RSA’s website, the RSA public key encryption algorithm has an installed based of nearly one billion. Each of these instances of the prime number based RSA algorithm can now be deciphered using Neutronic analysis . Unlike RSA, Neutronic Encryption is not based on two large prime numbers but rather on the Neutronic forces that govern the distribution of the primes themselves. The encryption that results from Singularics’ Neutronic public-key algorithm is theoretically impossible to break.

And you know what else you can do with this newly discovered netronic forces of the primes, besides breaking RSA and realizing impossible-to-break encryption? Continue reading

CS276 Lecture 11 (draft)


Today we begin a tour of the theory of one-way functions and pseudorandomness.

The highlight of the theory is a proof that if one-way functions exist (with good asymptotic security) then pseudorandom permutations exist (with good asymptotic security). We have seen that pseudorandom permutations suffice to do encryption and authentication with extravagantly high levels of security (respectively, CCA security and existential unforgeability under chosen message attack), and it is easy to see that if one-way functions do not exist, then every encryption and authentication scheme suffers from a total break.

Thus the conclusion is a strong “dichotomy” result, saying that either cryptography is fundamentally impossible, or extravagantly high security is possible.

Unfortunately the proof of this result involves a rather inefficient reduction, so the concrete parameters for which the dichotomy holds are rather unrealistic. (One would probably end up with a system requiring gigabyte-long keys and days of processing time for each encryption, with the guarantee that if it is not CCA secure then every 128-bit key scheme suffers a total break.) Nonetheless it is one of the great unifying achievements of the asymptotic theory, and it remains possible that a more effective proof will be found.

In this lecture and the next few ones we shall prove the weaker statement that if one-way permutations exist then pseudorandom permutations exist. This will be done in a series of four steps each involving reasonable concrete bounds. A number of combinatorial and number-theoretic problems which are believed to be intractable give us highly plausible candidate one-way permutations. Overall, we can show that if any of those well-defined and well-understood problems are hard, then we can get secure encryption and authentication with schemes that are slow but not entirely impractical. If, for example, solving discrete log with a modulus of the order of {2^{1,000}} is hard, then there is a CCA-secure encryption scheme requiring a {4,000}-bit key and fast enough to carry email, instant messages and probably voice communication. (Though probably too slow to encrypt disk access or video playback.)

Continue reading

Converting LaTeX to WordPress

Last month, I have written a program that converts a LaTeX document into a format that is ready to be copied and pasted into the WordPress editor.

I have been using it to post the notes of my cryptography class here, as well as some other posts.

Terry Tao has tested it on a couple of posts. Thanks to his feedback, the current version, while surely bug-filled and very limited, is stable enough to be used by other people. It is now available to anybody who might be interested.

What is the point of this program?
Continue reading

FOCS 2009

The call for papers of FOCS 2009 is out, and the deadline is April 2. Perhaps the committee will look with suspicion at papers sent exactly one day before the deadline.

There have been complaints about the requirement, in recent conferences, of submitting an abstract a week before the paper is due. This time, a “short description” is due one week after the paper submission deadline.

CS276 Lecture 10 (draft)


Cryptographic hash functions, as defined last time, have various applications. Their use for message authentication is common, but, unless it is carefully designed, it can lead to insecure systems.

We conclude the lecture with an overview of how the current standard pseudorandom permutation (AES) works. Next time we begin a study of how to construct pseudorandom permutations (and hence secure MACs and CCA-secure encryption) starting from well-understood assumptions such as the hardness of factoring or discrete log.

Continue reading

CS276 Lecture 8: CCA-Secure Encryption

Scribed by James Cook


Last time we described a secure MAC (message authentication code) based on pseudorandom functions. Its disadvantage was the length of the tag, which grew with the length of the message.

Today we describe the CBC-MAC, also based on pseudorandom functions, which has the advantage of short tags. We skip its security analysis.

Next, we show that combining a CPA-secure encryption with a secure MAC gives a CCA-secure encryption scheme.

Continue reading

CS276 Lecture 9 (draft)


Last time, we showed that combining a CPA-secure encryption with a secure MAC gives a CCA-secure encryption scheme. Today we shall see that such a combination has to be done carefully, or the security guarantee on the combined encryption scheme will not hold.

We then begin to talk about cryptographic hash functions, and their construction via the Merkle-Damgård transform.

Continue reading

Oded Goldreich’s Choices

Oded Goldreich has started a site in which he is going to collect selected recent papers in theoretical computer science.

He introduces this project with very interesting reflections on the matter of scientific exchange and communication:

My impression is that FOCS and STOC do not function any more as forums devoted to the presentation and exchange of ideas (but rather function as “weight-lifting competitions”). The question is what can be done to serve the need for the lost forums. One answer is provided by various personal blogs in which various researchers present their own choices of (relatively) recent works that have drawn their attention.

My problem with many of these blogs is that they cover the obvious (i.e., they all focus more or less on the same “hot results” that draw everybody’s attention). I would like to contribute to the project of regaining forums devoted to the presentation of ideas in a different way; specifically, by calling attention to works that have fascinated me although they were not necessarily labeled as “hot”.

CS276 Lecture 7: Message Authentication

Scribed by Mark Landry


Today we start to talk about message authentication codes (MACs). The goal of a MAC is to guarantee to the recipient the integrity of a message and the identity of the sender. We provide a very strong definition of security (existential unforgeability under adaptive chosen message attack) and show how to achieve it using pseudorandom functions.

Our solution will be secure, but inefficient in terms of length of the required authentication information.

Next time we shall see a more space-efficient authentication scheme, and we shall prove that given a CPA-secure encryption scheme and a secure MAC, one can get a CCA-secure encryption scheme. (That is, an encryption scheme secure against an adaptive chosen ciphertext and plaintext attack.)

Continue reading