Nicolas Gama

Nicolas Gama

Auto-generated profile, based on publicly available information

Nicolas Gama

SandboxAQ

Research Focus & Metrics

Academic Career Length

4Years (2023-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
16 April 2023
Verified
Book Chapter
Closed access
PDF file
CACarlos Aguilar-Melchor
Carlos Aguilar-Melchor
NGNicolas Gama
Nicolas Gama
JHJames Howe
James Howe
AHAndreas Hülsing
Andreas Hülsing
DJDavid Joseph
David Joseph
DYDongze Yue
Dongze Yue

10 December 2024
Verified
Book Chapter
Closed access
PDF file
MBM. G. Belorgey
M. G. Belorgey
SCS. Carpov
S. Carpov
NGN. Gama
N. Gama
SGS. Guasch
S. Guasch
DJD. Jetchev
D. Jetchev


16 December 2024 in Physical Review Research
Verified
Journal Article
Open access
JBJúlia Barberà-Rodríguez
Júlia Barberà-Rodríguez
NGNicolas Gama
Nicolas Gama
ANAnand Kumar Narayanan
Anand Kumar Narayanan
DJDavid Joseph
David Joseph
Lattice-based cryptography has emerged as one of the most prominent candidates for postquantum cryptography, projected to be secure against the imminent threat of large-scale fault-tolerant quantum computers. The Shortest Vector Problem (SVP) is to find the shortest nonzero vector in a given lattice. It is fundamental to lattice-based cryptography and believed to be hard even for quantum computers. We study a natural generalization of the SVP known as the K -Densest Sublattice Problem ( K -DSP): to find the densest K -dimensional sublattice of a given lattice. We formulate K -DSP as finding the first excited state of a Z -basis Hamiltonian, making K -DSP amenable to investigation via an array of quantum algorithms, including Grover search, quantum Gibbs sampling, adiabatic, and variational quantum algorithms. The complexity of the algorithms depends on the basis through which the input lattice is presented. We present a classical polynomial-time algorithm that takes an arbitrary input basis and preprocesses it into inputs suited to quantum algorithms. With preprocessing, we prove that O ( K N 2 ) qubits suffice for solving K -DSP for N -dimensional input lattices. We empirically demonstrate the performance of a quantum approximate optimization algorithm K -DSP solver for low dimensions, highlighting the influence of a good preprocessed input basis. We then discuss the hardness of K -DSP in relation to the SVP, to see if there is a reason to build postquantum cryptography on K -DSP. We devise a quantum algorithm that solves K -DSP with runtime exponent ( 5 K N log 2 N ) / 2 . Therefore, for fixed K , K -DSP is no more than polynomially harder than the SVP. The central insight we use is similar in spirit to those underlying the best-known classical K -DSP algorithm due to Dadush and Micciancio. Whether the exponential dependence on K can be lowered remains an open question. Published by the American Physical Society 2024

4 April 2025
Verified
Book Chapter
Closed access
PDF file
MAMartin R. Albrecht
Martin R. Albrecht
NGNicolas Gama
Nicolas Gama
JHJames Howe
James Howe
ANAnand Kumar Narayanan
Anand Kumar Narayanan

26 November 2023
Verified
Conference Paper
Open access
MBMariya Georgieva Belorgey
Mariya Georgieva Belorgey
SDSofia Dandjee
Sofia Dandjee
NGNicolas Gama
Nicolas Gama
DJDimitar Jetchev
Dimitar Jetchev
DMDmitry Mikushin
Dmitry Mikushin
We propose a novel protocol, Falkor, for secure aggregation for Federated Learning in the multi-server scenario based on masking of local models via a stream cipher based on AES in counter mode and accelerated by GPUs running on the aggregating servers. The protocol is resilient to client dropout and has reduced clients/servers communication cost by a factor equal to the number of aggregating servers (compared to the naïve baseline method). It scales simultaneously in the two major complexity aspects: 1) large number of clients; 2) highly complex machine learning models such as CNNs, RNNs, Transformers, etc. The AES-CTR-based masking function in our aggregation protocol is built on the concept of counterbased cryptographically-secure pseudorandom number generators (csPRNGs) as described in [32] and subsequently used by Facebook for their torchcsprng csPRNG. We improve upon torchcsprng by careful use of shared memory on the GPU device, a recent idea of Cihangir Tezcan [38] and obtain 100x speedup in the masking function compared to a single CPU core. Finally, we demonstrate scalability of our protocol in two realworld Federated Learning scenarios: 1) efficient training of large logistic regression models with 50 features and 50M data points distributed across 1000 clients that can dropout and securely aggregated via three servers (running secure multi-party computation (SMPC)); 2) training a recurrent neural network (RNN) model for sentiment analysis of Twitter feeds coming from a large number of Twitter users (more than 250,000 users). In case 1), our secure aggregation algorithm runs in less than a minute compared to a pure MPC computation (on 3 parties) that takes 27 hours and uses 400GB RAM machines as well as 1 gigabit-per-second network. In case 2), the total training is around 10 minutes using our GPU powered secure aggregation versus 10 hours using a single CPU core.