Towards a Ring Analogue of the Leftover Hash Lemma
Dana Dachman-Soleda b, Huijing Gongc d✉, Mukul Kulkarnia b, Aria Shahverdia b
- aDepartment of Electrical and Computer Engineering and UMIACS, University of Maryland , 8125 Paint Branch Dr., College Park , , Maryland , United States of America
- bDepartment of Electrical and Computer Engineering and UMIACS, University of Maryland, 8125 Paint Branch Dr., College Park, MD 20742, Maryland, United States of America
- cDepartment of Computer Science and UMIACS, University of Maryland , 8125 Paint Branch Dr., College Park , , Maryland , United States of America
- dDepartment of Computer Science and UMIACS, University of Maryland, 8125 Paint Branch Dr., College Park, MD 20742, Maryland, United States of America
- ✉Corresponding author
Papers open inside SciRah from the original publisher or repository; SciRah never hosts them.
Abstract
Abstract 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.