Aria Shahverdi
Research Subjects
Aria Shahverdi has a total of 15 co-authors. Here are the top co-authors by number of shared publications:
- Dana Dachman-Soled
University of Maryland
6 shared publications - Huijing Gong
University of Maryland
3 shared publications Dana Dachman-Soled
University of Maryland
2 shared publicationsMukul Kulkarni
University of Massachusetts
2 shared publications- Mukul Kulkarni
Department of Electrical and Computer Engineering and UMIACS, University of Maryland , 8125 Paint Branch Dr., College Park, MD 20742 , Maryland United States of America
2 shared publications Huijing Gong
Intel Labs
1 shared publication
Latest Publications
- 4 November 2021
- Published by Springer Nature
- p. 658-688
BKW Meets Fourier New Algorithms for LPN with Sparse Parities
- 4 November 2021
- Published by Springer Nature
- p. 658-688
BKW Meets Fourier New Algorithms for LPN with Sparse Parities
- Open Access
Database Reconstruction from Noisy Volumes: A Cache Side-Channel Attack on SQLite
We demonstrate the feasibility of database reconstruction under a cache side-channel attack on SQLite. Specifically, we present a Flush+Reload attack on SQLite that obtains approximate (or "noisy") volumes of range queries made to a private database. We then present several algorithms that, taken together, reconstruct nearly the exact database in varied experimental conditions, given these approximate volumes. Our reconstruction algorithms employ novel techniques for the approximate/noisy setting, including a noise-tolerant clique-finding algorithm, a "Match & Extend" algorithm for extrapolating volumes that are omitted from the clique, and a "Noise Reduction Step" that makes use of a closest vector problem (CVP) solver to improve the overall accuracy of the reconstructed database. The time complexity of our attacks grows quickly with the size of the range of the queried attribute, but scales well to large databases. Experimental results show that we can reconstruct databases of size 100,000 and ranges of size 12 with error percentage of 0.11 % in under 12 hours on a personal laptop.
Open AccessDatabase Reconstruction from Noisy Volumes: A Cache Side-Channel Attack on SQLite
We demonstrate the feasibility of database reconstruction under a cache side-channel attack on SQLite. Specifically, we present a Flush+Reload attack on SQLite that obtains approximate (or "noisy") volumes of range queries made to a private database. We then present several algorithms that, taken together, reconstruct nearly the exact database in varied experimental conditions, given these approximate volumes. Our reconstruction algorithms employ novel techniques for the approximate/noisy setting, including a noise-tolerant clique-finding algorithm, a "Match & Extend" algorithm for extrapolating volumes that are omitted from the clique, and a "Noise Reduction Step" that makes use of a closest vector problem (CVP) solver to improve the overall accuracy of the reconstructed database. The time complexity of our attacks grows quickly with the size of the range of the queried attribute, but scales well to large databases. Experimental results show that we can reconstruct databases of size 100,000 and ranges of size 12 with error percentage of 0.11 % in under 12 hours on a personal laptop.
- 4 December 2020
- Published by Springer Nature
- p. 93-125
Security of NewHope Under Partial Key Exposure
- Open Access
- 17 November 2020
- Published by Walter de Gruyter GmbH in Journal of Mathematical Cryptology
- Vol. 15 (1) , 87-110
Towards a Ring Analogue of the Leftover Hash Lemma
The leftover hash lemma (LHL) is used in the analysis of various lattice-based cryptosystems, such as the Regev and Dual-Regev encryption schemes as well as their leakage-resilient counterparts. The LHL does not hold in the ring setting, when the ring is far from a field, which is typical for efficient cryptosystems. Lyubashevsky et al . (Eurocrypt ’13) proved a “regularity lemma,” which can be used instead of the LHL, but applies only for Gaussian inputs. This is in contrast to the LHL, which applies when the input is drawn from any high min-entropy distribution. Our work presents an approach for generalizing the “regularity lemma” of Lyubashevsky et al . to certain conditional distributions. We assume the input was sampled from a discrete Gaussian distribution and consider the induced distribution, given side-channel leakage on the input. We present three instantiations of our approach, proving that the regularity lemma holds for three natural conditional distributions.
- 17 November 2020
- Published by Walter de Gruyter GmbH in Journal of Mathematical Cryptology
- Vol. 15 (1) , 87-110
Open AccessTowards a Ring Analogue of the Leftover Hash Lemma
The leftover hash lemma (LHL) is used in the analysis of various lattice-based cryptosystems, such as the Regev and Dual-Regev encryption schemes as well as their leakage-resilient counterparts. The LHL does not hold in the ring setting, when the ring is far from a field, which is typical for efficient cryptosystems. Lyubashevsky et al . (Eurocrypt ’13) proved a “regularity lemma,” which can be used instead of the LHL, but applies only for Gaussian inputs. This is in contrast to the LHL, which applies when the input is drawn from any high min-entropy distribution. Our work presents an approach for generalizing the “regularity lemma” of Lyubashevsky et al . to certain conditional distributions. We assume the input was sampled from a discrete Gaussian distribution and consider the induced distribution, given side-channel leakage on the input. We present three instantiations of our approach, proving that the regularity lemma holds for three natural conditional distributions.
- Open Access
- 17 November 2020
- Published by Walter de Gruyter GmbH in Journal of Mathematical Cryptology
- Vol. 15 (1) , 72-86
(In)Security of Ring-LWE Under Partial Key Exposure
We initiate the study of partial key exposure in Ring-LWE (RLWE)-based cryptosystems. Specifically, we (1) Introduce the search and decision Leaky R-LWE assumptions (Leaky R-SLWE, Leaky R-DLWE), to formalize the hardness of search/decision RLWE under leakage of some fraction of coordinates of the NTT transform of the RLWE secret. (2) Present and implement an efficient key exposure attack that, given certain 1/4-fraction of the coordinates of the NTT transform of the RLWE secret, along with samples from the RLWE distribution, recovers the full RLWE secret for standard parameter settings. (3) Present a search-to-decision reduction for Leaky R-LWE for certain types of key exposure. (4) Propose applications to the security analysis of RLWE-based cryptosystems under partial key exposure.
- 17 November 2020
- Published by Walter de Gruyter GmbH in Journal of Mathematical Cryptology
- Vol. 15 (1) , 72-86
Open Access(In)Security of Ring-LWE Under Partial Key Exposure
We initiate the study of partial key exposure in Ring-LWE (RLWE)-based cryptosystems. Specifically, we (1) Introduce the search and decision Leaky R-LWE assumptions (Leaky R-SLWE, Leaky R-DLWE), to formalize the hardness of search/decision RLWE under leakage of some fraction of coordinates of the NTT transform of the RLWE secret. (2) Present and implement an efficient key exposure attack that, given certain 1/4-fraction of the coordinates of the NTT transform of the RLWE secret, along with samples from the RLWE distribution, recovers the full RLWE secret for standard parameter settings. (3) Present a search-to-decision reduction for Leaky R-LWE for certain types of key exposure. (4) Propose applications to the security analysis of RLWE-based cryptosystems under partial key exposure.
- 1 October 2019
- Published by Elsevier in Information and Computation
- Vol. 268, 104428
Tight upper and lower bounds for leakage-resilient, locally decodable and updatable non-malleable codes
- 1 October 2019
- Published by Elsevier in Information and Computation
- Vol. 268, 104428
Tight upper and lower bounds for leakage-resilient, locally decodable and updatable non-malleable codes
- 1 March 2018
- Published by Springer Nature
- p. 281-311
Local Non-malleable Codes in the Bounded Retrieval Model
- 1 March 2018
- Published by Springer Nature
- p. 281-311
Local Non-malleable Codes in the Bounded Retrieval Model