cryptography(MSRColloqDec2009)

The Hitchhiker’s Guide to Public Key Cryptography : 

The Hitchhiker’s Guide to Public Key Cryptography Joseph Silverman Brown University & Microsoft Research MSR Colloquium December 2, 2009

The Hitchhiker’s Guide … : 

The Hitchhiker’s Guide … Far out in the uncharted backwaters of the unfashionable end of the Eastern Coast of Massachusetts lies a small research group whose ape-descended life forms are so amazingly primitive that they still think that public key cryptography is a pretty neat idea. This talk is about that idea. It will include + Some history (much of it true) + Some mathematics (most of it accurate) + Some miscellaneous observations

Public Key Cryptography:What It Is and From Whence It Came : 

Public Key Cryptography:What It Is and From Whence It Came

Cryptography the Old Fashioned Way : 

Cryptography the Old Fashioned Way Bob and Alice need to exchange confidential information. The first thing that they do is share a secret key. KEY EVE – the eavesdropper

So What’s the Problem? : 

So What’s the Problem? The difficulty is that Bob and Alice need to share the secret key before they even can get started. And since repeated use of a secret key is dangerous, they should change their secret key frequently Is there any way for Bob and Alice to exchange confidential information without first sharing a secret key? The obvious answer is NO – if Eve sees every message that Bob and Alice send to one another, how can they possibly exchange secret information. Enter Whitfield Diffie and Martin Hellman – stage left – with a brilliant idea!

Diffie and Hellman’s Brilliant Idea Public Key Cryptography : 

Diffie and Hellman’s Brilliant Idea Public Key Cryptography Suppose that Alice could create a cryptosystem that uses two different keys: Alice uses Key2 to decrypt the message. Since Eve does not know Key2 , she cannot decrypt Bob’s message. Standard Convention: Green quantities are public knowledge, red quantities are kept secret. Crucial Property: It is vitally important that knowing Key1 does not help Eve to determine Key2 . Key1 and Key2

A Brilliant Idea, But… : 

A Brilliant Idea, But… The concept of a two key cipher, now known as a public key cipher or an asymmetric cipher, is one of the truly brilliant ideas in Diffie and Hellman’s revolutionary 1976 paper New Directions in Cryptography.

The Birth of Public Key Cryptography : 

The Birth of Public Key Cryptography Within two years of the Diffie-Hellman paper, there were a small handful of suggested constructions of public key cryptosystems. The two most practical were the RSA Cryptosystem invented by Rivest, Shamir, and Adelman. Knapsack Cryptosystem invented by Merkle and Hellman. Of these two, only RSA has survived, but other systems have arisen to challenge RSA’s original dominance.

The Public Face of Public (and Private) Key Cryptography : 

The Public Face of Public (and Private) Key Cryptography In 1976 Diffie and Hellman initiate the age of public key cryptography … and in 1978 Rivest, Shamir, and Adelman invent the first practical public key cryptosystem that has withstood the test of time. Jumping ahead four centuries

The Public Uproar over Public Key Cryptography : 

The Public Uproar over Public Key Cryptography Diffie and Hellman begin their paper with a call to arms: We stand today on the brink of a revolution in cryptography. The government’s initial reaction was strong: They tried to suppress distribution of the RSA paper, but were stymied since Shamir is not a US citizen. The NSA instituted a “voluntary” prepublication review process for papers on cryptography. Mathematicians were told to exclude foreign nationals from cryptographic related seminars and conferences.

Putting the Genie Back into the Bottle? : 

Putting the Genie Back into the Bottle? The justification for the government’s actions was a law saying that cryptographic materials are munitions! This law dates back to the days when cryptographic materials meant cipher machines and code books whose internal workings were justifiably top secret. After a few years, the government realized the futility of trying to prevent academic discourse about cryptography, so they came up with a “compromise”: It was okay to do crypto research and to publish algorithms in journals and to give talks at conferences, but… foreign distribution of machine readable or executable crypto programs was forbidden without an export license.

Putting the Genie Back into the Bottle? : 

Putting the Genie Back into the Bottle? There were some huge problems with the government’s export policy: First, at some level, optical scanners make the “machine-readable” criterion obsolete. This led to the manufacture of… As an example of this policy in action, you may recall that early internet browsers were required to come in two flavors: A domestic version with high level crypto security. An exportable version with low level (40 bit) security, which presumably the NSA could break with ease.

Machine Readable Crypto Algorithms : 

Machine Readable Crypto Algorithms The non-exportableTee Shirt as Munition and the non-exportableSoda Can as Munition

An Unsustainable Public Policy : 

An Unsustainable Public Policy Public key algorithms are simple. The United States does not have a monopoly on top-notch scientists, engineers, and programmers. These amusing protests, and other more serious legal challenges, had some effect in changing government policy. But ultimately the policy was rendered moot by two simple facts: Thus restricting export of “strong crypto products” simply allowed other countries to create their own cryptographic and computer security industries.

The Claimants for the Public Key Cryptography Throne : 

The Claimants for the Public Key Cryptography Throne

Practical and Secure Public Key Crypto : 

Practical and Secure Public Key Crypto A first observation is that in the world of PKC, “practicality” and “security” are bitter foes. Public key cryptosystems are based on underlying hard mathematical problems. For example, RSA is based on the difficulty of factoring large numbers. Three problems in particular have been used to construct practical and secure PKCs. Integer Factorization Discrete Logarithm Problem Lattice Closest Vector Problem

A Man, A Plan, … : 

A Man, A Plan, … The plan for the rest of this talk: [1] Give you an idea of what these hard problems are and how difficult they are to solve. [2] Compare and contrast the operating characteristics of the associated public key cryptosystems. [3] Explain how some of these problems come equipped with special gadgets that allow them to be used in novel ways for public key crypto.

Hard Problem #1: Integer Factorization : 

Hard Problem #1: Integer Factorization Alice’s secret key is two “large” primes p and q. Alice’s public key is their product N = pq. Hard Problem: Given k and b, solve the congruence Xk ≡ b (mod N). Alice’s Trapdoor: It is easy to solve the congruence if you know p and q. The fastest known algorithm to factor N is called the Number Field Sieve. It takes about exp(c(log N)1/3) steps. That’s faster than Nε for every ε, but slower than (log N)d for every d.

HP #2: The Discrete Logarithm Problem : 

HP #2: The Discrete Logarithm Problem Alice’s secret key is a number e. Alice’s public key consists of a prime p, a number g, and its power h ≡ ge (mod p). Hard Problem: Given p, g, ga (mod p), and gb (mod p), compute the value of gab(mod p). Discrete Log Problem: Given p, g, and h, solve the congruence gx ≡ h (mod p). The fastest known algorithm to solve the DLP is called the Index Calculus. It takes about exp(c(log p)1/3) steps, so similar to integer factorization.

Security versus Efficiency : 

Modern methods can factor N and solve the DLP mod p for values up to around 2500, so… current standards require that N or p be at least 21000. More generally, typical security levels are set usingk-bit numbers with k = 1000 or 2000 or 4000 or 8000. Security versus Efficiency RSA depends on the difficulty of factoring integers.Elgamal depends on the difficulty of the DLP. Just how long does it take to do an exponentiation using k-bit numbers? With paper and pencil when, say, k = 1000? Left as an exercise for the audience!!

Security versus Efficiency : 

Security versus Efficiency There are two obvious ways to try to increase efficiency without sacrificing security. Find a problem that’s harder to solve, so we can reduce the bit size of the numbers. Find a problem where the computation is faster, say k2 bit operations.

Elliptic Curve Cryptography : 

Elliptic Curve Cryptography

What is an Elliptic Curve? : 

What is an Elliptic Curve? An elliptic curve is an object with a dual nature: On the one hand, it is a curve, a geometric object. On the other hand, we can “add” points on the curve as if they were numbers, so it is an algebraic object. The addition law on an elliptic curve can be described: Geometrically using intersections of curves Algebraically using polynomial equations Analytically using functions with complex variables Elliptic curves appear in diverse areas of mathematics, ranging from number theory to complex analysis, and from cryptography to mathematical physics.

What is an Elliptic Curve? : 

What is an Elliptic Curve?

Adding Points on an Elliptic Curve : 

Adding Points on an Elliptic Curve

The Addition Law on an Elliptic Curve : 

The Addition Law on an Elliptic Curve P + O = O + P = P for all P  E. P + (–P) = O for all P  E. (P + Q) + R = P + (Q + R) for all P,Q,R  E. P + Q = Q + P for all P,Q  E. In mathematical terminology, the addition law + makes the points of E into a commutative group. All of the group properties are easy to check except for the associative law (c). Ignoring various complications (tangent lines, vertical lines, …), the addition law has the following properties:

Elliptic Curves Mod p : 

Elliptic Curves Mod p Messy? Yes! But easily programmed and evaluated on a computer.

Elliptic Curves Mod p : 

Elliptic Curves Mod p Example:The curve E : Y2 = X3 – 5X + 8 modulo 37contains the points P = (6,3) and Q = (8,31). Using the addition formulas, we can compute in E(F37): 2P = (35,11) 3P = (34,25) 4P = (8,6) 5P = (16,19) … P + Q = (34,12) 3P + 4Q = (35,11) … Question: How many times do I have to add P to itself in order to get Q? This is an example of the Elliptic Curve Discrete Logarithm Problem. [The answer is Q = 11P.]

The Elliptic Curve Discrete Logarithm Problem : 

For example, here’s an (in)famous 1997 assessment from a prominent (not-to-be-named) cryptographer: … for now trying to get an evaluation of the security of an elliptic-curve cryptosystem is a bit like trying to get an evaluation of some recently discovered Chaldean poetry. The Elliptic Curve Discrete Logarithm Problem Suppose that you are given two points P and Q in E(Fp). If the prime p is large, it is extremely difficult to find m. Neal Koblitz and Victor Miller independently invented Elliptic Curve Cryptography in 1985 when they suggested building a cryptosystem around the ECDLP. For a long time, there was much scepticism about the security of elliptic curve cryptosystems:

HP #2': The Elliptic Curve Discrete Logarithm Problem as a Hard Problem : 

HP #2': The Elliptic Curve Discrete Logarithm Problem as a Hard Problem Alice’s secret key is again a number e. Alice’s public key consists of a prime p, an elliptic curve E, a point P on E mod p, and its multiple Q ≡ eP (mod p). Hard Problem: Given E, P, aP (mod p), and bP (mod p), compute the value of abP (mod p). Elliptic Curve Discrete Log Problem: Given E, P, and Q, solve the congruence xP ≡ Q (mod p). The fastest known algorithms to solve the ECDLP are Collision Algorithms. They take about p1/2 steps, so are much slower than solving DLP or factoring integers.

Elliptic Curves versus RSA : 

Elliptic Curves versus RSA Since the ECDLP is so much harder than the IFP (Integer Factorization Problem), cryptographic constructions using elliptic curves can get away with using much smaller numbers. # of bits in keys and ciphertexts Important Caveat: Security depends on your definition of the word “is”. “is” = “as far as we presently know”

Elliptic Curves versus RSA : 

Elliptic Curves versus RSA Elliptic curve cryptosystems have smaller keys, smaller ciphertexts, and smaller digital signatures than RSA. However, the “addition” formula on elliptic curves is quite complicated, so ECC and RSA take about the same amount of time to encrypt and decrypt, and to sign and verify. How about if RSA key and message sizes are okay, but we want faster encryption and decryption? To achieve this goal, people have devised cryptosystems based on hard lattice problems.

Lattice-Based Cryptography : 

Lattice-Based Cryptography

What is a Lattice? : 

What is a Lattice? A lattice is a regular array of points in space. We can connect the dots to form parallelograms. The lattice may be described by giving basis vectors that span a parallelogram.

What is the Closest Vector Problem? : 

What is the Closest Vector Problem? Suppose that someone gives you a point P. Suppose that you know a basis for the lattice L. This is the Closet Vector Problem. Challenge: Find the lattice point Q that is closest to P. P Q

Why Is That A Hard Problem? : 

Why Is That A Hard Problem? I can sense everyone thinking – “What’s so hard about the Closest Vector Problem? Just draw the picture and pick out the closest point!” For lattices in the plane, you’re right, it’s very easy. It’s not even very hard in dimension 3 However, the Closest Vector Problem is very hard in high dimension, say in dimension 500. Here is a picture of a lattice of dimension 500 , or 4 , or 5. Just kidding. It’s impossible to draw or visualize a 500 dimensional lattice. But it’s easy working with one on a computer. It is just a 500 by 500 array of numbers

Why Use Lattices for Cryptography? : 

Why Use Lattices for Cryptography? Let n be the number of bits in the underlying problem: n = # of bits in an RSA modulus pq n = # of bits in a prime p for ECC in E(Fp) n = (dimension of a lattice L) x (# of bits in a coordinate) Lattice problems offer the possibility of faster encryption and decryption algorithms.

Some History of Lattice-Based Crypto : 

Some History of Lattice-Based Crypto Ajtai and Dwork (1995) described a lattice-based public key cryptosystem having average case-worst case equivalence. This was a theoretical cryptographic milestone, but the AD cryptosystem is not practical. Inspired by the work of Ajtai and Dwork, Goldreich, Goldwasser, and Halevi (1996) proposed a more practical lattice-based cryptosystem. The GGH cryptosystem is fast, but it requires megabyte-size public keys to be secure. At the same time, working independently, Hoffstein (with Pipher and JS) developed a ring-based cryptosystem called NTRU that only requires RSA-sized keys. It was later discovered that NTRU could be described in terms of a special class of lattices and is closely related to the GGH system.

Key Sizes of Lattice-Based Cryptosystems : 

Key Sizes of Lattice-Based Cryptosystems In a lattice-based cryptosystem: The private key is a “good” (quasi-orthogonal) basis Bpri The public key is a “bad” (randomized) basis Bpub The GGH construction uses general bases: V1 = (a11,a12,…,a1n) V2 = (a21,a22,…,a2n) … Vn = (an1,an2,…,ann) NTRU solves this problem by using cyclical bases: V1 = (a1,a2,…,an) V2 = (a2,a3,…,a1) … Vn = (an,a1,…,an-1) So a GGH basis is a list of n2 numbers, where typically n is between 500 and 2000. This means that an NTRU basis can be described using only n numbers.

No Cost Added Features : 

No Cost Added Features

No-Cost Added Features : 

No-Cost Added Features Elliptic curve and lattice-based cryptosystems have some additional attractive features, beyond their respective smaller keys and faster encryption. Elliptic curve groups have a sort of multiplication called a bilinear pairing (due to Weil and Tate). The “product” P*Q of two points is a number mod p. Pairing-Based Cryptography This allows many interesting constructions, including for example Identity Based Encryption (Shamir, Boneh, Franklin) in which Alice can use her email address as her public key.

No Cost Added Features : 

No Cost Added Features Many cryptosystems have the property that (Encryption of M1) + (Encryption of M2) = (Encryption of M1+M2) or (Encryption of M1) * (Encryption of M2) = (Encryption of M1* M2) but it was a long-standing problem to find a cryptosystem with both properties. Fully Homomorphic Cryptography Such a cryptosystem allows a non-secure computer to run a program on encrypted input and produce encrypted output without knowledge of the unencrypted input or output. Last year Craig Gentry constructed the first fully homomorphic cryptosystem using ring-based lattices (and many clever ideas). Although not yet practical, it is a huge theoretical advance.

No Cost Added Features : 

No Cost Added Features Quantum-Resistant Cryptography A quantum computer is a computer in which the usual 0-1 bits of a digital computer are replaced by quantum states that take values between 0 and 1 according to some probability distribution. Lattice-based cryptosystems are said to be “quantum resistant” because the best known quantum algorithms for the closest vector problem are still exponential. In 1994 Peter Shor showed that a quantum computer could factor numbers in polynomial time, and later researchers showed the same for the classical and elliptic discrete logarithm problems.

The Hitchhiker’s Guide to Public Key Cryptography : 

The Hitchhiker’s Guide to Public Key Cryptography Joseph Silverman Brown University & Microsoft Research MSR Colloquium December 2, 2009