Towards a Ring Analogue of the Leftover Hash Lemma

Journal of mathematical cryptology

article

Dana Dachman-Soled¹  Huijing Gong²  Mukul Kulkarni¹  Aria Shahverdi¹ 

[1] Department of Electrical and Computer Engineering and UMIACS, University of Maryland, 8125 Paint Branch Dr., College Park, United States of America;Department of Computer Science and UMIACS, University of Maryland, 8125 Paint Branch Dr., College Park, United States of America

关键词: Lattice-based cryptography;    leakage resilience;    Ring-LWE;    regularity lemma;   

DOI  :  10.1515/jmc-2020-0076

学科分类：社会科学、人文和艺术（综合）

来源: De Gruyter

【 摘 要 】

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.

【 授权许可】

CC BY|CC BY-NC-ND