In this work, we propose a systematic approach for obtaining leftover hash lemmas (LHLs) over cyclotomic rings. Such LHLs build a fundamental tool in lattice-based cryptography, both in theoretical reductions as well as in the design of cryptographic primitives. The scattered set of prior works makes it difficult to navigate the landscape and requires a substantial effort to understand the mathematical constraints under which the LHL holds over cyclotomic rings. This is especially painful if one’s given setting does not fit exactly into prior studies. We argue that all prior approaches boil down to two main theorems. From there on, we recover all previous flavours of seemingly independent LHLs as corollaries. More importantly, we further showcase the power of our interpretation by providing new useful LHL statements. Our work further proves LHLs in the presence of leakage for both approaches and provides novel bounds for wide families of leakage functions. We believe that our work will facilitate future uses of the LHL over cyclotomic rings, especially in the case of new algebraic and leakage settings.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Leftover Hash Lemma(s) Over Cyclotomic Rings

  • Katharina Boudgoust,
  • Oleksandra Lapiha

摘要

In this work, we propose a systematic approach for obtaining leftover hash lemmas (LHLs) over cyclotomic rings. Such LHLs build a fundamental tool in lattice-based cryptography, both in theoretical reductions as well as in the design of cryptographic primitives. The scattered set of prior works makes it difficult to navigate the landscape and requires a substantial effort to understand the mathematical constraints under which the LHL holds over cyclotomic rings. This is especially painful if one’s given setting does not fit exactly into prior studies. We argue that all prior approaches boil down to two main theorems. From there on, we recover all previous flavours of seemingly independent LHLs as corollaries. More importantly, we further showcase the power of our interpretation by providing new useful LHL statements. Our work further proves LHLs in the presence of leakage for both approaches and provides novel bounds for wide families of leakage functions. We believe that our work will facilitate future uses of the LHL over cyclotomic rings, especially in the case of new algebraic and leakage settings.