Direct computation of branching programs and its applications to more efficient lattice-based cryptography
Direct computation of branching programs and its applications to more efficient lattice-based cryptography
复制标题
DOI：
10.1007/s10623-022-01104-5
复制
发表时间：
2022-09
期刊：
影响因子：
--
通讯作者：
Shuichi Katsumata;Toi Tomita;Shota Yamada
中科院分区：
文献类型：
--
作者：
Shuichi Katsumata;Toi Tomita;Shota Yamada
在本文中，我们开发并形式化了一套有效地计算小模环上同态内积的工具。这允许我们在基于格的各种密码原语中使用更小的模大小，这从安全性和效率的角度来看都是可取的。我们的方法是将内积的计算直接表示为分支规划的一种特殊形式，然后对它们进行同态求值。这与先前的工作形成对比，这些工作首先调用巴林顿定理，将计算内积的电路间接转换为分支程序。与以前的方法相比，分支程序的直接计算大大提高了效率，因为调用巴林顿定理会导致显著的效率损失。由于我们的技术，我们获得了以下具体应用。(1)我们提出了新的基于属性的加密方案，提高了算法中几个有用谓词的加密效率。虽然以前的方法通常需要超多项式模量或调用巴林顿定理，但我们设法使模量大小多项式地小，而不依赖于任何这些。因此，我们得到了更有效和安全的方案。(2)提出了一种基于小多项式模格的紧安全身份加密方案。与Boyen和Li （Asiacrypt 404-434，施普林格，Heidelberg, 2016, 10.1007/978-3-662-53890-6_14）的构造相比，我们的方案实现了更好的效率，尽管假设Boneh等人（TCC 535-554，施普林格，Heidelberg, 2018, 10.1007/978-3-540-70936-7_29）的特殊类型的伪随机函数（）的安全性。
In this paper, we develop and formalize a set of tools to efficiently compute inner-products homomorphically over the ringfor small modulusp. This allows us to use smaller modulus size in various cryptographic primitives based on lattices, which is desirable both from a security and efficiency points of view. Our approach is to directly express the computation of inner-products as a special form of branching program and then homomorphically evaluate them. This is in contrast to previous works that first invoked the Barrington’s theorem to convert the circuit computing the inner-product indirectly into a branching program. The direct computation of branching programs substantially improves the efficiency compared to previous methods since the invocation of the Barrington’s theorem incurred a significant efficiency loss. We obtain the following concrete applications as a result of our technique. (1) We propose new attribute-based encryption () schemes with improved efficiency for several useful predicates in. While previous approaches typically require either a super-polynomial modulus or invocation of the Barrington’s theorem, we manage to make the modulus size polynomially small without relying on any of these. Consequently, we obtain more efficient and secure schemes. (2) We propose a new tightly secure identity-based encryption () scheme from lattices with small polynomial modulus. Compared with the construction by Boyen and Li (Asiacrypt 404–434, Springer, Heidelberg, 2016, 10.1007/978-3-662-53890-6_14), our scheme achieves much better efficiency, albeit assuming the security of a special type of pseudorandom function () by Boneh et al. (TCC 535–554, Springer, Heidelberg, 2018, 10.1007/978-3-540-70936-7_29).