{"id":306446,"date":"2009-09-24T10:00:59","date_gmt":"2009-09-24T17:00:59","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/?p=306446"},"modified":"2016-10-17T11:20:30","modified_gmt":"2016-10-17T18:20:30","slug":"cryptography-receives-indian-scrutiny","status":"publish","type":"post","link":"https:\/\/www.microsoft.com\/en-us\/research\/blog\/cryptography-receives-indian-scrutiny\/","title":{"rendered":"Cryptography Receives Indian Scrutiny"},"content":{"rendered":"

By Rob Knies, Managing Editor, Microsoft Research<\/em><\/p>\n

You employ cryptographic techniques on a daily basis \u2026 don\u2019t you?<\/p>\n

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.<\/p>\n

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<\/a> of Microsoft Research India<\/a>. He heads the Cryptography, Security, and Applied Mathematics<\/a> (CSAM) group, founded in May 2006 by Ramarathnam (Venkie) Venkatesan<\/a>, who remains an active member.<\/p>\n

\"Satya

Satya Lokam<\/p><\/div>\n

Lokam\u2019s 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.<\/p>\n

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

\u201cThe main goal of our work,\u201d Lokam says, \u201cis to establish ourselves as top-notch researchers in the areas we work in.<\/p>\n

\u201cWe 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.\u201d<\/p>\n

Such results require expertise in some of the most fundamental areas of computer-science research.<\/p>\n

\u201cA substantial part of our research,\u201d Lokam says, \u201cis 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\u2014and their mutual connections.<\/p>\n

\u201cOur 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.\u201d<\/p>\n

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.<\/p>\n

\u201cWe invested a great deal of effort,\u201d he says, \u201cinto hiring strong researchers in the areas of cryptography, security, and complexity theory to build a world-class group.\u201d<\/p>\n

Members, in addition to Lokam and Venkatesan, include Prasad Naldurg, Raghav Bhaskar, Srivatsan Laxman, Vijay Patankar, and, since September 2008, Kayal\u2014with Goyal to join them in a couple of months.<\/p>\n

\u201cWe are proud,\u201d Lokam says, \u201cof having young, brilliant researchers such as Neeraj and Vipul on our team.\u201d<\/p>\n

A Big Splash<\/h2>\n

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<\/em> (opens in new tab)<\/span><\/a>. 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.<\/p>\n

\"Neeraj

Neeraj Kayal<\/p><\/div>\n

The identification of prime numbers is critical to many cryptographic procedures because it is generally believed to be a computationally complex problem.<\/p>\n

Kayal, Agrawal, and Saxena devised a fast, definitive technique to determine this, a task previous algorithms could approach but could not perfect.<\/p>\n

Acclaim came swiftly when their paper circulated among leading mathematicians. A story (opens in new tab)<\/span><\/a> in The New York Times<\/em> shortly thereafter stated that their algorithm, called the AKS Primality Test, \u201csimply and elegantly solves a problem that has challenged many of the best minds in the field for decades.\u201d<\/p>\n

In 2006, Primes Is in P<\/em> went on to win the G\u00f6del 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<\/p>\n

\u201cWe three were all surprised by the amount of attention that work attracted, especially among non-scientists,\u201d he recalls. \u201cIt 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.\u201d<\/p>\n

At Microsoft Research India, he finds that he has that ability.<\/p>\n

\u201cLike any university,\u201d Kayal says, \u201cI 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.\u201d<\/p>\n

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\u00a0terms (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.<\/p>\n

\u201cFor many computational problems, we know of algorithms that perform significantly better than those we\u2019re taught in elementary school,\u201d Kayal says, \u201cand typically, these faster algorithms exploit the power of subtraction or cancellation in some beautiful and nontrivial way.\u201d<\/p>\n

He cites three fundamental questions as the focus of today\u2019s research into computer science, including his own:<\/p>\n