Lattices, Codes, and Algebraic Cryptography

[ People | Project Description | Download | References ]


Antonio R. Nicolosi, Zakir Akram (doctoral student), Miaomiao Zhang (doctoral student).

Outside collaborators: Nelly Fazio (CCNY).

Former contributors: Carleton J. Bosley (postdoctoral associate, 2009–2011), Cyrus Peterpaul (CUNY-GC doctoral student), Linda Wong (B.Sc., CCNY, 2012).

Project Description

Cryptographic constructions are at the core of our modern information technology infrastructure, and it is thus crucial to understand their resilience to attacks. The resilience of a given construction is typically relative to the hardness of a handful of reference "intractable" computational problems like integer factorization. Because of the intrinsic strength of heterogeneity, diversifying the set of intractable problems available for the design of cryptosystems enhances the robustness of the overall cryptographic infrastructure to breakthroughs in the development of quantum computers and to other unforeseen cryptanalytic advances against any specific construction. This project responds to these challenges by building a foundation for cryptography from problems in combinatorial group theory, coding theory, and lattices, all fields in which quantum computing is not known to bring about substantial changes in the intractability landscape. Highlights include: (1) a framework for defining computational assumptions based on the hardness of learning homomorphisms between (non-commutative) groups in the presence of noise [BFN+11] (developed with collaborators at CUNY); (2) a specific instantiation of this framework and evidence to its hardness [FIN+15], [FNW13] (with collaborators at CUNY, Pepperdine University, and University of Paris VI); and (3) an algorithmic evaluation of the hardness of coding problems that have recently been suggested as the foundation for lightweight cryptography. Our approach adapts the collision-search method used in the crypto-analysis of code-based cryptography to work in tandem with algorithmic approximation tools like nearest neighbor search [BNZ12], [BHNZ13].



G. Baumslag, N. Fazio, A. Nicolosi, V. Shpilrain, and W.E. Skeith. Generalized learning problems and applications to non-commutative cryptography. In International Conference on Provable Security—ProvSec'11, pages 324–339. Springer, 2011. LNCS 6980.
C. Bosley, A. Nicolosi, and M. Zhang. Learning from Noisy Parities via Nearest-Neighbor Search. Joint AMS/SAMS International Congress, Port Elizabeth, South Africa, November–December 2011.
C. Bosley, K. Haralambiev, A. Nicolosi, and M. Zhang. HBNZ: An HB-like protocol secure against man-in-the-middle attacks. Manuscript. 2013
N. Fazio, A. Nicolosi and L. Wong. Manipulating Burnside Groups of Exponent Three. Manuscript. 2013
N. Fazio, K. Iga, A. Nicolosi, L. Perret, and W.E Skeith. Hardness of learning problems over Burnside groups of exponent three. Journal of Design, Codes, and Cryptography. 2015. 75(1):59–70.

(C) 2012–2015 Nelly Fazio, Antonio Nicolosi.
(C) 2012 Linda Wong.
Valid HTML 4.01! Valid CSS!