Proposal Exam: Hunter Kippen

Wednesday, June 7, 2023
12:00 p.m.
Iribe 4107
Maria Hoo
301 405 3681

ANNOUNCEMENT: Ph.D. Research Proposal Exam


Name: Hunter Kippen



Prof. Dana Dachman-Soled (Chair)

Prof. Jonathan Katz

Prof. Ankur Srivastava

Date/time: Wednesday June 7, 2023 at 12 PM


Location: Iribe 4107


Title: Advances in Concrete Cryptanalysis of Lattice Problems and Blind Signatures


 Recent reports suggest that governments and private actors are harvesting troves of sensitive internet communications, hoping to decrypt them once a sufficiently powerful quantum computer is made available. To combat this threat, NIST and other standards agencies such as Germany's BSI, have selected new quantum resistant cryptosystems for standardization. Most of these schemes are based on the hardness of computational problems over lattices.
Lattice cryptography has emerged as the pre-eminent method for securing data against adversaries armed with a quantum computer due to their combination of well-studied security and algorithmic performance. As such, large technology companies are beginning to migrate their software to use these new encryption standards where applicable. However, there are many challenges involved with deploying lattice-based cryptosystems. The complexity of the algorithms leaves lattice schemes particularly vulnerable to side-channel attacks. These attacks exploit design flaws in the underlying software or hardware to obtain secret information without directly breaking the cryptosystem.

As such, determining the risk of any particular deployment involves analyzing the concrete security (the exact length of time it would take to break the encryption) of the encryption scheme as well as quantifying how concrete security can degrade due to any exploitable side-channels.
In this proposal, we seek to further quantify the concrete hardness of lattice problems. In two prior works, we examine the security degradation of lattice problems when an adversary is given access to side-channel information.

In the first work, we develop a novel side-channel attack on the FrodoKEM key exchange mechanism as submitted to the NIST Post Quantum Cryptography (PQC) standardization process.
Our attack involves \emph{poisoning} the FrodoKEM Key Generation (KeyGen) process using a security exploit in DRAM known as ``Rowhammer''. The Rowhammer side-channel allows an adversary to flip bits in DRAM by “hammering” rows of memory adjacent to some target-victim memory location by repeated memory accesses. Using Rowhammer, we induce the FrodoKEM software to output a higher-error Public Key (PK). Then, we perform a decryption failure attack, using a variety of publicly-accessible supercomputing resources running on the order of only 200,000 core-hours, allowing us to recover the private key material.
In the second work, we revisit the security of the lattice problem known as Learning with Errors (LWE) under side-channel attacks. Dachman-Soled et al. [Crypto ’20] presented a framework for integrating side-channel information in the form of “hints,” which enable (iteratively) tracking the conditional distribution of the private key material. They showed that this principled approach can lead to algorithms forside-channel attacks that perform better than ad-hoc algorithms used in prior works.
This work focuses on new methods for integrating hints. We view hints from a geometric perspective, as opposed to the distributional perspective from the prior work. Our approach provides the rigorous promise that, as hints are integrated, the correct solution is a (unique) lattice point contained in an ellipsoidsal search space. We instantiate our approach with two new types of hints (1) Inequality hints, and (2) Combined hints. The compatibility of “approximate,” “modular,” and “short vector” hints from the prior work is also examined.
Our current ongoing work directly follows from these two prior works.
Our proposed work involves lattice-based digital signatures. These signature schemes employ advanced rejection sampling procedures during key generation in order to ensure output signatures are independent of the messages being signed. We propose an alternative to rejection sampling that would allow for shorter signatures, albeit at the cost of limiting the number of signatures that can be generated by a fresh public key. We propose to quantify these limits using techniques from the LWE “hint” framework.

Audience: Faculty 

remind we with google calendar


June 2023

28 29 30 31 1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 1
Submit an Event