Top

Designs, Codes and Cryptography

Published in:

28-09-2022

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

Authors: Shuichi Katsumata, Toi Tomita, Shota Yamada

Published in: Designs, Codes and Cryptography | Issue 2/2023

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

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

previous article A design and flexible assignment of orthogonal binary sequence sets for (QS)-CDMA systems

next article Gold functions and switched cube functions are not 0-extendable in dimension n > 5

Available only for authorised users

The first \(\textsf {ABE}\) for \({\textbf {NC}}^1\) circuits based on \(\textsf {poly}\)-\(\textsf {LWE}\) was by Gorbunov, Vaikuntanathan, and Wee [34]. Their construction requires long-secret keys that grow with the size of the circuit.

The estimate is based on [10] and the Lecture Notes 8 and 9 of [54].

This may not fit conventional definition of branching programs. However, we believe this rough explanation suffices for the introduction. A more formal treatment is provided in Sect. 3.

Note that [16] needs to rely on \(\textsf {superpoly}\)-\(\textsf {LWE}\) for the security but the construction itself only requires a polynomial-sized modulus.

Agrawal S., Boneh D., Boyen X.: Efficient lattice (H)IBE in the standard model. In: Gilbert H. (ed.) EUROCRYPT 2010, LNCS, vol. 6110, pp. 553–572. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_28.

Agrawal S., Freeman D.M., Vaikuntanathan V.: Functional encryption for inner product predicates from learning with errors. In: Lee D.H., Wang X. (eds.) ASIACRYPT 2011, LNCS, vol. 7073, pp. 21–40. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25385-0_2.

Agrawal S., Boyen X., Vaikuntanathan V., et al.: Functional encryption for threshold functions (or fuzzy IBE) from lattices. In: Fischlin M., Buchmann J., Manulis M. (eds.) PKC 2012, LNCS, vol. 7293, pp. 280–297. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-30057-8_17.

Alperin-Sheriff J., Peikert C.: Practical bootstrapping in quasilinear time. In: Canetti R., Garay J.A. (eds.) CRYPTO 2013, Part I, LNCS, vol. 8042, pp. 1–20. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_1.

Alperin-Sheriff J., Peikert C.: Faster bootstrapping with polynomial error. In: Garay J.A., Gennaro R. (eds.) CRYPTO 2014, Part I, LNCS, vol. 8616, pp. 297–314. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44371-2_17.

Attrapadung N., Libert B.: Functional encryption for inner product: Achieving constant-size ciphertexts with adaptive security or support for negation. In: Nguyen P.Q., Pointcheval D. (eds.) PKC 2010, LNCS, vol. 6056, pp. 384–402. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13013-7_23.

Banerjee A., Peikert C.: New and improved key-homomorphic pseudorandom functions. In: Garay J.A., Gennaro R. (eds.) CRYPTO 2014, Part I, LNCS, vol. 8616, pp. 353–370. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44371-2_20.

Banerjee A., Peikert C., Rosen A.: Pseudorandom functions and lattices. In: Pointcheval D., Johansson T. (eds.) EUROCRYPT 2012, LNCS, vol. 7237, pp. 719–737. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_42.

Barrington D.A.: Bounded-width polynomial-size branching programs recognize exactly those languages in NC1. J. Comput. Syst. Sci. 38(1), 150–164 (1989).MathSciNetCrossRefMATH

10.

Beame P.W., Cook S.A., Hoover H.J.: Log depth circuits for division and related problems. SIAM J. Comput. 15(4), 994–1003 (1986).MathSciNetCrossRefMATH

11.

Blazy O., Kakvi S.A., Kiltz E., et al.: Tightly-secure signatures from chameleon hash functions. In: Katz J. (ed.) PKC 2015, LNCS, vol. 9020, pp. 256–279. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46447-2_12.

12.

Boneh D., Franklin M.K.: Identity-based encryption from the Weil pairing. In: Kilian J. (ed.) CRYPTO 2001, LNCS, vol. 2139, pp. 213–229. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44647-8_13.

13.

Boneh D., Waters B.: Conjunctive, subset, and range queries on encrypted data. In: Vadhan S.P. (ed.) TCC 2007, LNCS, vol. 4392, pp. 535–554. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-70936-7_29.

14.

Boneh D., Gentry C., Gorbunov S., et al.: Fully key-homomorphic encryption, arithmetic circuit ABE and compact garbled circuits. In: Nguyen P.Q., Oswald E. (eds.) EUROCRYPT 2014, LNCS, vol. 8441, pp. 533–556. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-55220-5_30.

15.

Boneh D., Ishai Y., Passelègue A., et al.: Exploring crypto dark matter: new simple PRF candidates and their applications. In: Beimel A., Dziembowski S. (eds.) TCC 2018, Part II, LNCS, vol. 11240, pp. 699–729. Springer, Heidelberg (2018). https://doi.org/10.1007/978-3-030-03810-6_25.

16.

Boyen X., Li Q.: Towards tightly secure lattice short signature and id-based encryption. In: Cheon J.H., Takagi T. (eds.) ASIACRYPT 2016, Part II, LNCS, vol. 10032, pp. 404–434. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53890-6_14.

17.

Boyen X., Li Q.: All-but-many lossy trapdoor functions from lattices and applications. In: Katz J, Shacham H. (eds.) CRYPTO 2017, Part III, LNCS, vol. 10403, pp. 298–331. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-319-63697-9_11.

18.

Brakerski Z., Vaikuntanathan V.: Efficient fully homomorphic encryption from (standard) LWE. In: Ostrovsky R. (ed.) 52nd FOCS. IEEE Computer Society Press, pp. 97–106 (2011). https://doi.org/10.1109/FOCS.2011.12.

19.

Brakerski Z., Vaikuntanathan V.: Lattice-based FHE as secure as PKE. In: Naor M. (ed.) ITCS 2014, pp. 1–12. ACM (2014). https://doi.org/10.1145/2554797.2554799.

20.

Brakerski Z., Vaikuntanathan V.: Circuit-ABE from LWE: unbounded attributes and semi-adaptive security. In: Robshaw M., Katz J. (eds.) CRYPTO 2016, Part III, LNCS, vol. 9816, pp. 363–384. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53015-3_13.

21.

Brakerski Z., Gentry C., Vaikuntanathan V.: (Leveled) fully homomorphic encryption without bootstrapping. In: Goldwasser S. (ed.) ITCS 2012, pp. 309–325. ACM (2012). https://doi.org/10.1145/2090236.2090262.

22.

Brakerski Z., Langlois A., Peikert C., et al.: Classical hardness of learning with errors. In: Boneh D., Roughgarden T., Feigenbaum J. (eds.) 45th ACM STOC, pp. 575–584. ACM Press (2013). https://doi.org/10.1145/2488608.2488680.

23.

Brakerski Z., Lombardi A., Segev G., et al.: Anonymous IBE, leakage resilience and circular security from new assumptions. In: Nielsen J.B., Rijmen V. (eds.) EUROCRYPT 2018, Part I, LNCS, vol. 10820, pp. 535–564. Springer, Heidelberg (2018) https://doi.org/10.1007/978-3-319-78381-9_20.

24.

Cash D., Hofheinz D., Kiltz E., et al.: Bonsai trees, or how to delegate a lattice basis. In: Gilbert H. (ed.) EUROCRYPT 2010, LNCS, vol. 6110, pp. 523–552. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_27.

25.

Cheon J.H., Cho W., Kim J.H., et al.: Adventures in crypto dark matter: attacks and fixes for weak pseudorandom functions. In: LNCS, pp 739–760. Springer, Heidelberg (2021). https://doi.org/10.1007/978-3-030-75248-4_26.

26.

Dodis Y., Reyzin L., Smith A.: Fuzzy extractors: how to generate strong keys from biometrics and other noisy data. In: Cachin C., Camenisch J. (eds.) EUROCRYPT 2004, LNCS, vol. 3027, pp. 523–540. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24676-3_31.

27.

Gentry C.: Fully homomorphic encryption using ideal lattices. In: Mitzenmacher M. (ed.) 41st ACM STOC, pp. 169–178. ACM Press (2009). https://doi.org/10.1145/1536414.1536440.

28.

Gentry C., Halevi S.: Fully homomorphic encryption without squashing using depth-3 arithmetic circuits. In: Ostrovsky R. (ed.) 52nd FOCS, pp. 107–109. IEEE Computer Society Press (2011). https://doi.org/10.1109/FOCS.2011.94.

29.

Gentry C., Peikert C., Vaikuntanathan V.: Trapdoors for hard lattices and new cryptographic constructions. In: Ladner R.E., Dwork C. (eds.) 40th ACM STOC, pp. 197–206. ACM Press (2008). https://doi.org/10.1145/1374376.1374407.

30.

Gentry C., Halevi S., Smart N.P.: Better bootstrapping in fully homomorphic encryption. In: Fischlin M., Buchmann J., Manulis M. (eds.) PKC 2012, LNCS, vol. 7293, pp. 1–16. Springer, Heidelberg (2012a).https://doi.org/10.1007/978-3-642-30057-8_1.

31.

Gentry C., Halevi S., Smart N.P.: Fully homomorphic encryption with polylog overhead. In: Pointcheval D., Johansson T. (eds.) EUROCRYPT 2012, LNCS, vol. 7237, pp 465–482. Springer, Heidelberg (2012b). https://doi.org/10.1007/978-3-642-29011-4_28.

32.

Gentry C., Sahai A., Waters B.: Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based. In: Canetti R., Garay J.A. (eds.) CRYPTO 2013, Part I, LNCS, vol. 8042, pp. 75–92. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_5.

33.

Gorbunov S., Vinayagamurthy D.: Riding on asymmetry: efficient ABE for branching programs. In: Iwata T., Cheon J.H. (eds.) ASIACRYPT 2015, Part I, LNCS, vol. 9452, pp. 550–574. Springer, Heidelberg (2015).https://doi.org/10.1007/978-3-662-48797-6_23.

34.

Gorbunov S., Vaikuntanathan V., Wee H.: Attribute-based encryption for circuits. In: Boneh D., Roughgarden T., Feigenbaum J. (eds.) 45th ACM STOC, pp. 545–554. ACM Press (2013). https://doi.org/10.1145/2488608.2488677.

35.

Gorbunov S., Vaikuntanathan V., Wee H.: Predicate encryption for circuits from LWE. In: Gennaro R., Robshaw M.J.B. (eds.) CRYPTO 2015, Part II, LNCS, vol. 9216, pp. 503–523. Springer, Heidelberg (2015a). https://doi.org/10.1007/978-3-662-48000-7_25.

36.

Gorbunov S., Vaikuntanathan V., Wichs D.: Leveled fully homomorphic signatures from standard lattices. In: Servedio R.A., Rubinfeld R. (eds.) 47th ACM STOC, pp. 469–477. ACM Press (2015b). https://doi.org/10.1145/2746539.2746576.

37.

Katsumata S., Yamada S.: Partitioning via non-linear polynomial functions: more compact IBEs from ideal lattices and bilinear maps. In: Cheon J.H., Takagi T. (eds.) ASIACRYPT 2016, Part II, LNCS, vol. 10032, pp. 682–712. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53890-6_23.

38.

Katsumata S., Yamada S.: Group signatures without NIZK: from lattices in the standard model. In: Ishai Y., Rijmen V. (eds.) EUROCRYPT 2019, Part III, LNCS, vol. 11478, pp. 312–344. Springer, Heidelberg (2019a). https://doi.org/10.1007/978-3-030-17659-4_11.

39.

Katsumata S., Yamada S.: Non-zero inner product encryption schemes from various assumptions: LWE, DDH and DCR. In: Lin D., Sako K. (eds.) PKC 2019, Part II, LNCS, vol. 11443, pp. 158–188. Springer, Heidelberg (2019b). https://doi.org/10.1007/978-3-030-17259-6_6.

40.

Katz J., Wang N.: Efficiency improvements for signature schemes with tight security reductions. In: Jajodia S., Atluri V., Jaeger T. (eds.) ACM CCS 2003, pp. 155–164. ACM Press (2003). https://doi.org/10.1145/948109.948132.

41.

Katz J., Sahai A., Waters B.: Predicate encryption supporting disjunctions, polynomial equations, and inner products. In: Smart N.P. (ed.) EUROCRYPT 2008, LNCS, vol. 4965, pp. 146–162. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78967-3_9.

42.

Kim S., Wu D.J.: Multi-theorem preprocessing NIZKs from lattices. In: Shacham H., Boldyreva A. (eds.) CRYPTO 2018, Part II, LNCS, vol. 10992, pp 733–765. Springer, Heidelberg (2018). https://doi.org/10.1007/978-3-319-96881-0_25.

43.

Lai Q., Liu F.H., Wang Z.: Almost tight security in lattices with polynomial moduli—PRF, IBE, all-but-many LTF, and more. In: PKC 2020, Part I, LNCS, pp. 652–681. Springer, Heidelberg (2020). https://doi.org/10.1007/978-3-030-45374-9_22.

44.

Libert B., Sakzad A., Stehlé, D., et al.: All-but-many lossy trapdoor functions and selective opening chosen-ciphertext security from LWE. In: Katz J., Shacham H. (eds.) CRYPTO 2017, Part III, LNCS, vol. 10403, pp. 332–364. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-319-63697-9_12.

45.

Libert B., Stehlé D., Titiu R.: Adaptively secure distributed PRFs from \({\sf LWE}\). In: Beimel A., Dziembowski S. (eds.) TCC 2018, Part II, LNCS, vol. 11240, pp. 391–421. Springer, Heidelberg (2018). https://doi.org/10.1007/978-3-030-03810-6_15.

46.

Litvak A.E., Pajor A., Rudelson M., et al.: Smallest singular value of random matrices and geometry of random polytopes. Adv. Math. 195(2), 491–523 (2005).MathSciNetCrossRefMATH

47.

Micciancio D., Peikert C.: Trapdoors for lattices: simpler, tighter, faster, smaller. In: Pointcheval D., Johansson T. (eds.) EUROCRYPT 2012, LNCS, vol. 7237, pp. 700–718. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_41.

48.

Micciancio D., Peikert C.: Hardness of SIS and LWE with small parameters. In: Canetti R., Garay J.A. (eds.) CRYPTO 2013, Part I, LNCS, vol. 8042, pp. 21–39. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_2.

49.

Peikert C.: Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. In: Mitzenmacher M. (ed.) 41st ACM STOC, pp. 333–342. ACM Press (2009). https://doi.org/10.1145/1536414.1536461.

50.

Peikert C., Vaikuntanathan V., Waters B.: A framework for efficient and composable oblivious transfer. In: Wagner D. (ed.) CRYPTO 2008, LNCS, vol. 5157, pp. 554–571. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85174-5_31.

51.

Regev O.: On lattices, learning with errors, random linear codes, and cryptography. In: Gabow H.N., Fagin R. (eds.) 37th ACM STOC, pp. 84–93. ACM Press (2005). https://doi.org/10.1145/1060590.1060603.

52.

Sahai A., Waters B.R.: Fuzzy identity-based encryption. In: Cramer R. (ed.) EUROCRYPT 2005, LNCS, vol. 3494, pp. 457–473. Springer, Heidelberg (2005). https://doi.org/10.1007/11426639_27.

53.

Tsabary R.: Fully secure attribute-based encryption for t-CNF from LWE. In: Boldyreva A., Micciancio D. (eds.) CRYPTO 2019, Part I, LNCS, vol. 11692, pp. 62–85. Springer, Heidelberg (2019). https://doi.org/10.1007/978-3-030-26948-7_3.

54.

Viola E.: Gems of theoretical computer science. In: Lecture Notes (2009). http://www.ccs.neu.edu/home/viola/classes/gems-08/index.html.

55.

Waters B.R.: Efficient identity-based encryption without random oracles. In: Cramer R. (ed.) EUROCRYPT 2005, LNCS, vol. 3494, pp. 114–127. Springer, Heidelberg (2005). https://doi.org/10.1007/11426639_7.

56.

Yamada S.: Adaptively secure identity-based encryption from lattices with asymptotically shorter public parameters. In: Fischlin M., Coron J.S. (eds.) EUROCRYPT 2016, Part II, LNCS, vol. 9666, pp. 32–62. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49896-5_2.

57.

Yamada S.: Asymptotically compact adaptively secure lattice IBEs and verifiable random functions via generalized partitioning techniques. In: Katz J., Shacham H. (eds.) CRYPTO 2017, Part III, LNCS, vol. 10403, pp. 161–193. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-319-63697-9_6.

Title: Direct computation of branching programs and its applications to more efficient lattice-based cryptography
Authors: Shuichi Katsumata
Toi Tomita
Shota Yamada
Publication date: 28-09-2022
Publisher: Springer US
Published in: Designs, Codes and Cryptography / Issue 2/2023
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-022-01104-5

Springer Professional

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

Abstract

Premium Partner

Springer Professional

Abstract

Please log in to get access to your license.

Other articles of this Issue 2/2023

Self-orthogonal codes over a non-unital ring and combinatorial matrices

-linear codes: rank and kernel

Gold functions and switched cube functions are not 0-extendable in dimension n > 5

On strongly walk regular graphs, triple sum sets and their codes

Improved generalized block inserting construction of constant dimension codes

The irreducible vectors of a lattice:

Premium Partner