Cryptography Receives Indian Scrutiny

By Rob Knies, Managing Editor, Microsoft Research

You employ cryptographic techniques on a daily basis … don’t you?

Sure you do. Every time you type a password into a computer, you are practicing cryptography, using secret information to verify your identity. The same principle is invoked when you make a bid on eBay, purchase a book online, or push an ATM card into a cash machine.

A decade into the 21st century, cryptographic techniques have become an integral part of our day-to-day lives, and nobody knows that better than Satya Lokam of Microsoft Research India. He heads the Cryptography, Security, and Applied Mathematics (CSAM) group, founded in May 2006 by Ramarathnam (Venkie) Venkatesan, who remains an active member.

Lokam’s group focuses on theoretical and practical aspects of cryptography and security, as well as on related areas of theoretical computer science and mathematics, such as complexity theory and number theory. Such fields hold tremendous potential for Microsoft.

Underscoring the importance of such research, Lokam recently has hired a pair of young, yet already adept, researchers, Neeraj Kayal and Vipul Goyal.

“The main goal of our work,” Lokam says, “is to establish ourselves as top-notch researchers in the areas we work in.

“We leverage this strength of research to impact Microsoft technologies and to acquire intellectual capabilities for potential future directions the company might take, as well as to influence such future directions.”

Such results require expertise in some of the most fundamental areas of computer-science research.

“A substantial part of our research,” Lokam says, “is invested into foundational questions in theoretical computer science and mathematics that will have long-term impact on our understanding of computational complexity, cryptography, and security—and their mutual connections.

“Our choice of problems in cryptography and security is driven by the challenges faced by the research community and the needs of emerging technologies. Our fundamental research pushes the frontiers of computational complexity and the mathematical foundations of modern cryptography.”

And, he notes, that while technology transfer is a priority, it can only occur if you have strong research. For that reason, from the outset, Lokam made finding top-notch researchers a priority.

“We invested a great deal of effort,” he says, “into hiring strong researchers in the areas of cryptography, security, and complexity theory to build a world-class group.”

Members, in addition to Lokam and Venkatesan, include Prasad Naldurg, Raghav Bhaskar, Srivatsan Laxman, Vijay Patankar, and, since September 2008, Kayal—with Goyal to join them in a couple of months.

“We are proud,” Lokam says, “of having young, brilliant researchers such as Neeraj and Vipul on our team.”

A Big Splash

Kayal made a sudden name for himself when he, along with Manindra Agrawal and Nitin Saxena of the Department of Computer Science & Engineering at the Indian Institute of Technology Kanpur, electrified the mathematics community seven years ago with the paper Primes Is in P. The paper offered a solution to a problem that had confounded mathematicians for decades: how quickly a computer can identify if a given number is prime.

The identification of prime numbers is critical to many cryptographic procedures because it is generally believed to be a computationally complex problem.

Kayal, Agrawal, and Saxena devised a fast, definitive technique to determine this, a task previous algorithms could approach but could not perfect.

Acclaim came swiftly when their paper circulated among leading mathematicians. A story in The New York Times shortly thereafter stated that their algorithm, called the AKS Primality Test, “simply and elegantly solves a problem that has challenged many of the best minds in the field for decades.”

In 2006, Primes Is in P went on to win the Gödel Prize, a prestigious award presented to the authors of outstanding papers in theoretical computer science. All the attention was an unexpected delight for Kayal and his co-authors

“We three were all surprised by the amount of attention that work attracted, especially among non-scientists,” he recalls. “It was very satisfying to have our work recognized and awarded. On the other hand, the attention has also led to increased expectations and sometimes a gnawing fear that the work on primality testing might be a flash in the pan. I counter that by trying to maintain a playful and exploratory attitude while allowing myself to make lots of mistakes in the process.”

At Microsoft Research India, he finds that he has that ability.

“Like any university,” Kayal says, “I really have the freedom to work on topics that excite me. I can always find great colleagues willing to listen to half-baked ideas and to talk about research in general.”

Much of his current research revolves around the significant speed improvements that algorithms sometimes obtain by exploiting the power of subtraction, or cancellation. At intermediate stages of their operation, such algorithms generate many more terms (monomials) than are present in the target function. As the computation reaches its climax, these extraneous terms are canceled out, leaving precisely those terms that are present in the target function.

“For many computational problems, we know of algorithms that perform significantly better than those we’re taught in elementary school,” Kayal says, “and typically, these faster algorithms exploit the power of subtraction or cancellation in some beautiful and nontrivial way.”

He cites three fundamental questions as the focus of today’s research into computer science, including his own:

• Can randomness enhance computation?
• Can parallelism enhance computation?
• Can non-determinism—the ability to guess and check—enhance computation?

“Perhaps,” Kayal says, “progress on some of these questions, as well as the development of fast new algorithms, will depend on our ability to better understand and exploit the power of cancellations.”

That focus on algebraic complexity complements CSAM’s efforts.

“Neeraj is an outstanding researcher in complexity theory,” Lokam notes, “with stellar results and numerous awards to his credit. A deep understanding of the complexity of various algebraic problems will have an impact on many areas of computer science and mathematics, including cryptography.”

Love for the Labs

For Goyal, already well known in the cryptographic community for his solutions to challenging problems and his work in developing practical cryptographic schemes, working for Microsoft Research has become a passion in itself.

“I was interning at Microsoft Research Redmond in the summer of 2007 when my mentor, Venkie, told me about [Microsoft Research India]. I had a great experience working as an intern in Microsoft Research Redmond—I went back in summer 2008!—so I decided to visit Microsoft Research India in December 2007 and instantly fell in love with it: so many great researchers, exciting visitors—and free lunch! If felt like a family, and I could see myself being a happy part of it. I decided to apply for a position, and fortunately, I was offered one.”

Goyal, whose interests focus on cryptography and information security, is in the process of completing work on his UCLA thesis. This summer, he enjoyed his latest internship, in a novel yet familiar setting.

“I am working on designing powerful and general cryptographic protocols for the Internet,” he says. “I interned this summer at Microsoft Research Silicon Valley, and I have visited four of the six global Microsoft Research labs. My plan is to work on my thesis, defend, and then join the [India] lab.”

Why such affection for Microsoft Research?

“A major benefit of being at Microsoft Research,” Goyal says, “is that you get the best of both worlds: the kind of freedom to explore your ideas that you get in an academic setting, as well as the resources of a company as big as Microsoft to turn these ideas into reality.

“I expect to work on problems ranging from very fundamental—those that shed light on the kind of cryptographic protocols that can exist for the Internet—to the ones that can have real-world impact right away, like more effective solutions to prevent phishing attacks.”

“Vipul already has a reputation of being a prolific researcher,” Lokam says, “and is unique in the broad spectrum of topics he works on, ranging from abstract theoretical to very practical. Together with one of his advisors, Amit Sahai at UCLA, he recently resolved a fundamental conjecture—called the Simultaneous Resettability in Zero-Knowledge Proofs—that baffled several eminent researchers. This is an intricate proof involving several novel techniques that will likely find other applications.”

Practical Impact

Goyal also has researched attribute-based encryption, which happens to be one of CSAM’s research focuses, along with symmetric searchable encryption and order-preserving encryption. All fall under the umbrella of cryptography for the cloud and are part of work driven by Roy DSouza, a partner architect for Microsoft’s Cloud DB team, and Rahul Auradkar, director of the Storage Solutions group. Those teams, based in Redmond, are collaborating with CSAM to build a cryptographic infrastructure for cloud computing.

“This is somewhat of an unusual project,” Lokam explains, “in that much of the architectural design and scenario analysis work has been done by Roy and Rahul and their teams. We together identify research problems in cryptography that arise in this framework and either work on new solutions or identify and modify existing ones.”

That work, which is ongoing, also features contributions from other Microsoft Research labs and from academic institutes.

“Our work was inspired by a project on searchable encryption in collaboration with the Data Protection Manager team at the India Development Center, based in Hyderabad,” Lokam explains. “A few months into this project, Roy visited us and helped us define a much broader scope for the cryptographic problems we have been working on.”

That broader context includes secure database services, Exchange hosted services, and cloud computing.

“When we started to explore cryptographic techniques for the cloud,” DSouza says, “we learned about the IDC work that Satya describes. But we discovered that this was not practical for complex business scenarios, and most of the research in this area is challenging to implement at scale in the cloud.

“However, our interaction with the Microsoft Research India team has taken a fruitful direction, because our product teams zero in on the precise cloud problem, and then our embedded cryptographers collaborate with Satya’s team to leverage its strength and critical mass, channeled in a manner that focuses on practical implementations and time to market.”

It’s a prime example of productive, customer-focused interaction between researchers and product teams.

“Enterprises use data and storage services, whether offered as cloud services or as on-premise applications, in a variety of scenarios that span a swath of applications,” Auradkar says. “Staying focused on scenarios and applications that benefit from newer techniques and offer value to customers is an imperative. The primary focus for our interaction with the CSAM team is to understand what is possible and, subsequently, develop and deploy data and storage services.”

The collaboration was aided by Microsoft Research India’s Advanced Development and Prototyping (ADP) team.

“We collaborate extensively with the ADP team,” Lokam says. “They have been of tremendous help in interfacing between our research and various product teams.”

Efficient Vulnerability Handling

The team also has worked with the Redmond-based Microsoft Security Engineering Center Security Science group on a project called Pattern Mining for Security, designed to help strengthen software security. The project uses research on data mining to analyze and prioritize attack scenarios, and it has enabled the Redmond team to classify and handle security vulnerabilities much more efficiently.

“Security audit teams in Microsoft routinely collect auditing information and store them in large databases,” says Naldurg, who was joined in the effort by colleagues Laxman and Venkatesan. “Only a fraction of these reports are interesting to security analysts, in the sense that they correspond to new vulnerabilities, say in configuration files or in dynamically executed scripts that can be exploited by malware. Evidence of attempted malicious behavior, including failed attack attempts, is available in these databases but require super-human effort to find.

“With our pattern-based classification algorithm, we are able to automate the task of classifying these reports as malicious or benign and bring to attention only reports that are of high value to the analyst. We have a novel scoring technique for prioritization that works by finding patterns of interesting features that occur together in both malicious and benign and assigning weights to these features. Only a small number of hand-labeled samples are required to bootstrap our algorithm.”

The CSAM techniques, Naldurg adds, have been applied successfully to detect and prioritize access-control configuration vulnerabilities in Windows XP, and the researchers are extending their work to detect malicious JavaScript files without requiring expensive static analysis.

Approaching Success

CSAM researchers have a track record of publishing papers in top conferences and journals and have established close interactions with the Indian academic community. Group members collaborate with Ph.D. students and faculty, teach at institutes, serve on editorial boards and program committees, deliver talks, and review papers and grant proposals. Lokam just completed writing a book, Complexity Lower Bounds Using Linear Algebra, part of a series called Foundations and Trends in Theoretical Computer Science, edited by Madhu Sudan, a principal researcher at Microsoft Research New England.

All this activity confirms for Lokam that he made the right decision back in May 2006 to join Microsoft Research India.

“My family and I had been thinking of returning to India for several years, but we kept struggling with various options and constraints to implement that wish,” he says. “While visiting Microsoft Research Redmond, I learned about Microsoft Research India and that Venkie was helping to start a Crypto group here. After talking to Venkie, P. Anandan [managing director of the India lab], and other researchers here, I felt that this would be a great place to pursue my research in theoretical computer science and cryptography and would provide a perfect opportunity to move my family to India.”

So, is he ready to declare his team’s mission a success? Not quite, but clearly progress is being made in that direction.

“We will consider our mission a success,” Lokam concludes, “when we are recognized as the best in the world in the research domains we work in, both as individual researchers and collectively as a group—and when our work finds its way into Microsoft technologies.”

（在新选项卡中打开）