Direct computation of branching programs and its applications to more efficient lattice-based cryptography

• Published in: Designs, codes, and cryptography codes, and cryptography, 2023-02, Vol.91 (2), p.391-431
• Main Authors: Katsumata, Shuichi, Tomita, Toi, Yamada, Shota
• Format: Article
• Language: English
• Subjects: Applications programs; Circuits; Coding and Information Theory; Computer Science; Cryptography; Cryptology; Discrete Mathematics in Computer Science; Efficiency; Lattices; Polynomials; Pseudorandom; Security; Theorems
• ISSN: 0925-1022; 1573-7586
• DOI: 10.1007/s10623-022-01104-5

In this paper, we develop and formalize a set of tools to efficiently compute inner-products homomorphically over the ring Z p for small modulus  p . 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 ( ABE ) schemes with improved efficiency for several useful predicates in NC 1 . 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 ( IBE ) 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 ( PRF ) by Boneh et al. (TCC 535–554, Springer, Heidelberg, 2018, 10.1007/978-3-540-70936-7_29).