article

Adriana López-Alt
AT&T Labs Fellowship Award Winner

by: Staff, August 3, 2010

 

Each year, AT&T Research through its AT&T Labs Fellowship Program (ALFP) offers three-year fellowships to outstanding under-represented minority and women students pursuing PhD studies in computing and communications-related fields. This year three students received fellowships. Adriana López-Alt is one.

201007_AdrianaAward01

 

 

At a high level, cryptography is the science of securing information so only those in possession of a secret can succeed in communicating this information. Long the domain of spies and the military, cryptography was once limited to encrypting messages with codes that were not mathematically proven to be secure and were therefore easily broken. They also required a secret possessed by both sides, which created the problem of exchanging secrets before communication was possible.

 

2201007_Adriana_basic-encryption

 Encryption methods of the past depended on both sides having the same secret code.

In the 70s, with computers providing new and faster ways to break codes, more secure cryptographic methods were clearly needed. New cryptographic types were also needed, such as digital signatures, to validate or authenticate parties in online transactions.

The solution was two-fold. First, security began to be mathematically proven, guaranteeing that adversaries had no chance in breaking the code. Second, public-key cryptography was developed, so that there was no longer a need to exchange a shared key prior to communication. An example of public-key encryption is RSA (for the three inventors’ initials). RSA security uses a two-key approach: one public to encrypt messages and one private to unscramble messages. The two keys are mathematically related but in a way that makes it very difficult to deduce the private key by knowing only the public key. The algorithms behind RSA take advantage of the difficulty in finding the two prime factors of a large number (see sidebar).

(Cryptography deals with numbers. Character-based messages are first translated into numbers using one of several methods.)

For today’s relatively slow computers, RSA was and is secure but may be vulnerable to the quantum computers that may be coming in the next few years. So the race is on to find harder math problems that can withstand the brute-force attacks by quantum computers.

Different strategies are being explored with harder math problems, and this search forms the summer project of Adriana López-Alt.

Mathematics is a subject Adriana enjoys thinking about, and her otherwise serene face lights up whenever she gets the chance to talk math. She’s considered herself a mathematician since high school, which for her was an all-girls high school in Bogotá. From there she went to MIT to major in mathematics and where she took classes from Shafi Goldwasser, one of the pioneers in modern cryptography and the person who piqued Adriana’s initial interest in the field.

Blending number theory, complexity theory, algorithmics, information theory, probability theory, abstract algebra, and formal analysis, cryptography is a mathematician’s dream.

After a short working stint at Oracle, where there was quite a bit of programming but precious little math, Adriana enrolled in NYU’s graduate school of computer science, joining the cryptography group where she is, by the way, the only female.

Under her mentor Juan Garay at AT&T Research, Adriana is exploring lattice-based cryptography, an area which came into being following the seminal work of Ajtai in 1996 connecting the average-case complexity of lattice problems to their complexity in the  worst case. While there are many hard problems associated with lattices, the area was further energized by the work of Regev in 2005 showing a problem known as Learning with Errors to be as hard to solve as worst-case lattice problems. Adriana is currently focusing on constructions based on such problems, an example of which is the closest vector problem: given a multi-dimensional lattice defined by a set of vectors (called a basis), is a randomly chosen point in space close to or far from a point on the lattice?

In an example construction of a public-key cryptosystem, the easily constructed basis would constitute the public key, together with a point that is close to the lattice, and the private information is knowing the lattice point that is close that point.

 

201007_Adriana_vector-lattice-encryption

 

 

 

 

 

 

 

 

In lattice-based cryptography, it’s almost impossible without secret information to know whether a random point in space is close to or far from a point on the lattice.

 
A picture is misleading since it’s immediately obvious whether a point is close to a vector or not, but a computer doesn’t see the picture (just a matrix).

Apart from offering harder problems to solve than other cryptographic methods, lattice-based cryptography has, besides its theoretical appeal, other advantages: it’s efficient and conceptually simple (usually requiring only linear operations on small integers), and it’s hard in the average case, not just worse case (in factoring, for example, some numbers are harder than others to factor; lattice problems are equally hard in all cases).

Adriana is working to design lattice-based constructions for different so-called “primitives” that form the building blocks of secure multi-party computation. Such primitives include oblivious transfer (where each party of the transaction reveals some information while keeping some private) and commitments, where each party commits to something without initially revealing exactly what and without the ability to change the terms (such as a sealed bid that isn’t opened until all other bids are received).

The project’s level of difficulty is high, involving problems in advanced linear geometry, and it’s somewhat surprising that this project should be given to a first-year graduate student (she starts her second year this fall). However, as her mentor pointed out, Adriana is already the co-author of two cryptography papers (Efficient Public-Key Cryptography in the Presence of Key Leakage and Cryptography Against Continuous Memory Attacks), unusual for someone just beginning graduate studies.

It’s even more impressive considering she’s had to work through the problems and equations herself; lattice-based cryptography, being relatively new, doesn’t yet have a large body of work, so while this means she has less background material to refer to, it provides an opportunity for her to some day make important contributions to the field.

Lattice-based cryptography is assumed to be computationally hard, and so far no one has been able to break it. Unfortunately for Internet security, lattice-based cryptography is still a long way off (though so too are quantum computers). Implementing any new security scheme will be comprehensive and expensive; most companies will delay until real threats develop.

So it’s unlikely that Adriana’s work will have real-world impact any time soon. But that doesn’t seem to bother Adriana. She likes the problems. Her long-term plan is to stay in academia and continue working on the cryptographic problems that stir her interest in mathematics.

 

 

201007_adriana-stats2

 

Private keys for encryption

Public keys encrypt messages, and private keys decrypt them.

Public keys can be widely distributed so anyone can encrypt a message, such as a bank customer requesting a balance.

The trick is for the public key to be divulged without revealing the private key. Fortunately there are math problems that are easy to solve in one direction but hard in the other. One such problem is factoring large prime numbers.

In the following, p and q are two large primes (of between 40 and 200 digits):

               p x q = N

If you know p and q, you know N. But knowing N doesn’t reveal p or q. So N becomes the public key and banks or anyone else can freely and safely distribute it.

Finding p and q, which form the private key, is hard since the only known method to find two prime factors of a large number is to check all possibilities one by one. Today’s computers are too slow to solve the problem.

Quantum computers may be able to do it. Hence the interest in harder math problems such as lattice-based cryptography.

 

Proust questionnaire
If not cryptography, what else?
Algorithms, complexity, maybe chemistry or who knows, perhaps literature.

Role models in life
Might sound cheesy but my mom and dad.

Heroes from history.
Euler, Borges

Academy or a job in the real world?
A mix... research lab.

What motivates you?
On a technical level, exploiting the structure of mathematics to create something practical... on a non-technical level, working hard to then fully enjoy my free time with a book in hand.

What single course helped decide your future study?
Shafi Goldwasser's "Introduction to Cryptography"  and Silvio Micali/Ran Canetti's seminar in Zero Knowledge.

Most fun course?
Mike Sipser's "Theory of Computation"

Course you most regretted not taking?
Coding Theory, Randomized Algorithms