Stevens Graduate Student Wins Award for Cryptography Research

12/5/2011

The 7th Annual Graduate Student Research Day at New Jersey Institute of Technology (NJIT) showcased the talents and initiatives of New Jersey graduate students, including a group from Stevens, who are advancing knowledge on a wide range of frontiers as they work toward their degrees.

Out of 50 accepted poster presentations, Miaomiao Zhang of Stevens won the Outstanding Research Award for her cutting-edge cryptography research, which was conducted in collaboration with her advisor, Professor Antonio Nicolosi, and postdoctoral research fellow Carl Bosely. For winning the award, Zhang received two gift certificates for the award – one for her participation and the other for the best poster from Stevens.

Zhang’s research was based on a lattice-based cryptography – specifically, studying the computational complexity of the Learning Parity with Noise (LPN) problem. LPN is a well-known problem from computational learning theory that has recently found numerous applications in cryptography. It is closely related to NP-hard problems from coding theory, but its average-case complexity is not yet fully understood. This motivated Zhang’s team to look into its hardness, an active research area in the field.

The team devised a new approach to attack the LPN problem using tools from approximation algorithms, such as nearest-neighbor search.  Although not asymptotically faster than the best theoretical algorithm for their purpose, their algorithm required much less learning data than other approaches. This made it relevant for practical attacks. Among the proposals with this feature, the algorithms they presented perform reasonably well.

Zhang said that this is an ongoing work and they have yet to finalize the strict analysis of their new algorithm.

“In cryptography, we care about hard problems because sometimes we want to make things hard – for example, we want to make it hard for adversaries to steal our credit cards and impersonate us,” Zhang said. “I work on the field of lattice-based cryptography, which is believed to be secure against quantum computers while traditional cryptographic techniques are not.  Lattice-base cryptographic constructions enjoy very strong security proofs based on worst-case hardness, great simplicity and relatively efficient implementations. Therefore, lattice-based cryptography holds a great promise for the post-quantum cryptography.”

Zhang was interested in math at a very young age, and sought out the Stevens Computer Science program because it fit both her interests and intellectual strengths. She was initially exposed to cryptography as she researched network privacy and security during her master’s study, as cryptography is the foundation of network security.

"I was delighted when I first realized that mathematics and cryptography are so closely related,” she said. “It was exciting to know that my expertise in math would come in handy in solving cryptographic problems.”

Looking to the future, Zhang’s ideal job is to be able to conduct research in a field where she can leverage her strong mathematical sense and rigorous reasoning ability.