Efficient laconic cryptography from learning with errors. (English) Zbl 1528.94046
Hazay, Carmit (ed.) et al., Advances in cryptology – EUROCRYPT 2023. 42nd annual international conference on the theory and applications of cryptographic techniques, Lyon, France, April 23–27, 2023. Proceedings. Part III. Cham: Springer. Lect. Notes Comput. Sci. 14006, 417-446 (2023).
Summary: Laconic cryptography is an emerging paradigm that enables cryptographic primitives with sublinear communication complexity in just two messages. In particular, a two-message protocol between Alice and Bob is called laconic if its communication and computation complexity are essentially independent of the size of Alice’s input. This can be thought of as a dual notion of fully-homomorphic encryption, as it enables “Bob-optimized” protocols. This paradigm has led to tremendous progress in recent years. However, all existing constructions of laconic primitives are considered only of theoretical interest: They all rely on non-black-box cryptographic techniques, which are highly impractical.
This work shows that non-black-box techniques are not necessary for basic laconic cryptography primitives. We propose a completely algebraic construction of laconic encryption, a notion that we introduce in this work, which serves as the cornerstone of our framework. We prove that the scheme is secure under the standard Learning With Errors assumption (with polynomial modulus-to-noise ratio). We provide proof-of-concept implementations for the first time for laconic primitives, demonstrating the construction is indeed practical: For a database size of \(2^{50}\), encryption and decryption are in the order of single digit milliseconds.
Laconic encryption can be used as a black box to construct other laconic primitives. Specifically, we show how to construct:
For the entire collection see [Zbl 1525.94003].
This work shows that non-black-box techniques are not necessary for basic laconic cryptography primitives. We propose a completely algebraic construction of laconic encryption, a notion that we introduce in this work, which serves as the cornerstone of our framework. We prove that the scheme is secure under the standard Learning With Errors assumption (with polynomial modulus-to-noise ratio). We provide proof-of-concept implementations for the first time for laconic primitives, demonstrating the construction is indeed practical: For a database size of \(2^{50}\), encryption and decryption are in the order of single digit milliseconds.
Laconic encryption can be used as a black box to construct other laconic primitives. Specifically, we show how to construct:
- ●
- Laconic oblivious transfer
- ●
- Registration-based encryption scheme
- ●
- Laconic private-set intersection protocol.
For the entire collection see [Zbl 1525.94003].
MSC:
| 94A60 | Cryptography |
| 68P25 | Data encryption (aspects in computer science) |
| 68T05 | Learning and adaptive systems in artificial intelligence |
References:
| [1] | Agrawal, S.; Boneh, D.; Boyen, X.; Rabin, T., Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE, Advances in Cryptology - CRYPTO 2010, 98-115 (2010), Heidelberg: Springer, Heidelberg · Zbl 1280.94035 · doi:10.1007/978-3-642-14623-7_6 |
| [2] | Ajtai, M.: Generating hard instances of lattice problems (extended abstract). In: 28th ACM STOC, pp. 99-108. ACM Press (1996). doi:10.1145/237814.237838 · Zbl 0921.11071 |
| [3] | Alamati, N.; Branco, P.; Döttling, N.; Garg, S.; Hajiabadi, M.; Pu, S.; Nissim, K.; Waters, B., Laconic private set intersection and applications, Theory of Cryptography, 94-125 (2021), Cham: Springer, Cham · Zbl 1511.94040 · doi:10.1007/978-3-030-90456-2_4 |
| [4] | Albrecht, MR; Lai, RWF; Malkin, T.; Peikert, C., Subtractive sets over cyclotomic rings, Advances in Cryptology - CRYPTO 2021, 519-548 (2021), Cham: Springer, Cham · Zbl 1486.94076 · doi:10.1007/978-3-030-84245-1_18 |
| [5] | Alekhnovich, M.: More on average case vs approximation complexity. In: 44th FOCS, pp. 298-307. IEEE Computer Society Press (2003). doi:10.1109/SFCS.2003.1238204 |
| [6] | Alperin-Sheriff, J.; Peikert, C.; Fischlin, M.; Buchmann, J.; Manulis, M., Circular and KDM security for identity-based encryption, Public Key Cryptography - PKC 2012, 334-352 (2012), Heidelberg: Springer, Heidelberg · Zbl 1294.94030 · doi:10.1007/978-3-642-30057-8_20 |
| [7] | Aranha, D., Lin, C., Orlandi, C., Simkin, M.: Laconic private set-intersection from pairings. Cryptology ePrint Archive, Report 2022/529 (2022). https://eprint.iacr.org/2022/529 |
| [8] | Benhamouda, F.; Lin, H.; Nielsen, JB; Rijmen, V., k-round multiparty computation from k-round oblivious transfer via garbled interactive circuits, Advances in Cryptology - EUROCRYPT 2018, 500-532 (2018), Cham: Springer, Cham · Zbl 1428.94060 · doi:10.1007/978-3-319-78375-8_17 |
| [9] | Boneh, D.; Franklin, M.; Kilian, J., Identity-based encryption from the Weil pairing, Advances in Cryptology — CRYPTO 2001, 213-229 (2001), Heidelberg: Springer, Heidelberg · Zbl 1002.94023 · doi:10.1007/3-540-44647-8_13 |
| [10] | Bos, J., et al.: CRYSTALS - kyber: a CCA-secure module-lattice-based KEM. Cryptology ePrint Archive, Paper 2017/634 (2017). doi:10.1109/EuroSP.2018.00032, https://eprint.iacr.org/2017/634 |
| [11] | Boudgoust, K.; Jeudy, C.; Roux-Langlois, A.; Wen, W.; Moriai, S.; Wang, H., Towards classical hardness of module-LWE: the linear rank case, Advances in Cryptology - ASIACRYPT 2020, 289-317 (2020), Cham: Springer, Cham · Zbl 07666666 · doi:10.1007/978-3-030-64834-3_10 |
| [12] | Bourse, F.; Del Pino, R.; Minelli, M.; Wee, H.; Robshaw, M.; Katz, J., FHE circuit privacy almost for free, Advances in Cryptology - CRYPTO 2016, 62-89 (2016), Heidelberg: Springer, Heidelberg · Zbl 1391.94733 · doi:10.1007/978-3-662-53008-5_3 |
| [13] | Boyen, X.; Li, Q.; Cheon, JH; Takagi, T., Towards tightly secure lattice short signature and id-based encryption, Advances in Cryptology - ASIACRYPT 2016, 404-434 (2016), Heidelberg: Springer, Heidelberg · Zbl 1407.94091 · doi:10.1007/978-3-662-53890-6_14 |
| [14] | Brakerski, Z.; Döttling, N.; Pass, R.; Pietrzak, K., Lossiness and entropic hardness for ring-LWE, Theory of Cryptography, 1-27 (2020), Cham: Springer, Cham · Zbl 1492.94068 · doi:10.1007/978-3-030-64375-1_1 |
| [15] | Brakerski, Z.; Lombardi, A.; Segev, G.; Vaikuntanathan, V.; Nielsen, JB; Rijmen, V., Anonymous IBE, leakage resilience and circular security from new assumptions, Advances in Cryptology - EUROCRYPT 2018, 535-564 (2018), Cham: Springer, Cham · Zbl 1423.94056 · doi:10.1007/978-3-319-78381-9_20 |
| [16] | Cash, D.; Hofheinz, D.; Kiltz, E.; Peikert, C.; Gilbert, H., Bonsai trees, or how to delegate a lattice basis, Advances in Cryptology - EUROCRYPT 2010, 523-552 (2010), Heidelberg: Springer, Heidelberg · Zbl 1280.94043 · doi:10.1007/978-3-642-13190-5_27 |
| [17] | Cho, C.; Döttling, N.; Garg, S.; Gupta, D.; Miao, P.; Polychroniadou, A.; Katz, J.; Shacham, H., Laconic oblivious transfer and its applications, Advances in Cryptology - CRYPTO 2017, 33-65 (2017), Cham: Springer, Cham · Zbl 1409.94866 · doi:10.1007/978-3-319-63715-0_2 |
| [18] | Döttling, N.; Garg, S.; Kalai, Y.; Reyzin, L., From selective IBE to full IBE and selective HIBE, Theory of Cryptography, 372-408 (2017), Cham: Springer, Cham · Zbl 1385.94034 · doi:10.1007/978-3-319-70500-2_13 |
| [19] | Döttling, N.; Garg, S.; Katz, J.; Shacham, H., Identity-based encryption from the Diffie-Hellman assumption, Advances in Cryptology - CRYPTO 2017, 537-569 (2017), Cham: Springer, Cham · Zbl 1385.94033 · doi:10.1007/978-3-319-63688-7_18 |
| [20] | Döttling, N., Garg, S., Goyal, V., Malavolta, G.: Laconic conditional disclosure of secrets and applications. In: Zuckerman, D. (ed.) 60th FOCS, pp. 661-685. IEEE Computer Society Press (2019). doi:10.1109/FOCS.2019.00046 |
| [21] | Döttling, N.; Garg, S.; Hajiabadi, M.; Masny, D.; Abdalla, M.; Dahab, R., New constructions of identity-based and key-dependent message secure encryption schemes, Public-Key Cryptography - PKC 2018, 3-31 (2018), Cham: Springer, Cham · Zbl 1385.94035 · doi:10.1007/978-3-319-76578-5_1 |
| [22] | Döttling, N.; Garg, S.; Ishai, Y.; Malavolta, G.; Mour, T.; Ostrovsky, R.; Boldyreva, A.; Micciancio, D., Trapdoor hash functions and their applications, Advances in Cryptology - CRYPTO 2019, 3-32 (2019), Cham: Springer, Cham · Zbl 1436.94054 · doi:10.1007/978-3-030-26954-8_1 |
| [23] | Garg, S.; Hajiabadi, M.; Shacham, H.; Boldyreva, A., Trapdoor functions from the computational Diffie-Hellman assumption, Advances in Cryptology - CRYPTO 2018, 362-391 (2018), Cham: Springer, Cham · Zbl 1436.94067 · doi:10.1007/978-3-319-96881-0_13 |
| [24] | Garg, S.; Hajiabadi, M.; Mahmoody, M.; Rahimi, A.; Beimel, A.; Dziembowski, S., Registration-based encryption: removing private-key generator from IBE, Theory of Cryptography, 689-718 (2018), Cham: Springer, Cham · Zbl 1443.94057 · doi:10.1007/978-3-030-03807-6_25 |
| [25] | Garg, S.; Hajiabadi, M.; Mahmoody, M.; Rahimi, A.; Sekar, S.; Lin, D.; Sako, K., Registration-based encryption from standard assumptions, Public-Key Cryptography - PKC 2019, 63-93 (2019), Cham: Springer, Cham · Zbl 1453.94080 · doi:10.1007/978-3-030-17259-6_3 |
| [26] | Garg, S., Srinivasan, A.: Garbled protocols and two-round MPC from bilinear maps. In: Umans, C. (ed.) 58th FOCS, pp. 588-599. IEEE Computer Society Press (2017). doi:10.1109/FOCS.2017.60 |
| [27] | Garg, S.; Srinivasan, A.; Nielsen, JB; Rijmen, V., Adaptively secure garbling with near optimal online complexity, Advances in Cryptology - EUROCRYPT 2018, 535-565 (2018), Cham: Springer, Cham · Zbl 1428.94073 · doi:10.1007/978-3-319-78375-8_18 |
| [28] | Garg, S.; Srinivasan, A.; Nielsen, JB; Rijmen, V., Two-round multiparty secure computation from minimal assumptions, Advances in Cryptology - EUROCRYPT 2018, 468-499 (2018), Cham: Springer, Cham · Zbl 1428.94072 · doi:10.1007/978-3-319-78375-8_16 |
| [29] | Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Mitzenmacher, M. (ed.) 41st ACM STOC, pp. 169-178. ACM Press (2009). doi:10.1145/1536414.1536440 · Zbl 1304.94059 |
| [30] | 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). doi:10.1145/1374376.1374407 · Zbl 1231.68124 |
| [31] | Glaeser, N., Kolonelos, D., Malavolta, G., Rahimi, A.: Efficient registration-based encryption. Cryptology ePrint Archive, Paper 2022/1505 (2022). https://eprint.iacr.org/2022/1505 |
| [32] | Goldreich, O., Goldwasser, S., Halevi, S.: Collision-free hashing from lattice problems. Cryptology ePrint Archive, Report 1996/009 (1996). https://eprint.iacr.org/1996/009 · Zbl 1343.94055 |
| [33] | Goyal, R.; Vusirikala, S.; Micciancio, D.; Ristenpart, T., Verifiable registration-based encryption, Advances in Cryptology - CRYPTO 2020, 621-651 (2020), Cham: Springer, Cham · Zbl 1504.94142 · doi:10.1007/978-3-030-56784-2_21 |
| [34] | Håstad, J.; Impagliazzo, R.; Levin, LA; Luby, M., A pseudorandom generator from any one-way function, SIAM J. Comput., 28, 4, 1364-1396 (1999) · Zbl 0940.68048 · doi:10.1137/S0097539793244708 |
| [35] | Hohenberger, S., Lu, G., Waters, B., Wu, D.J.: Registered attribute-based encryption. Cryptology ePrint Archive, Paper 2022/1500 (2022). https://eprint.iacr.org/2022/1500 |
| [36] | Libert, B.; Ling, S.; Nguyen, K.; Wang, H.; Fischlin, M.; Coron, J-S, Zero-knowledge arguments for lattice-based accumulators: logarithmic-size ring signatures and group signatures without trapdoors, Advances in Cryptology - EUROCRYPT 2016, 1-31 (2016), Heidelberg: Springer, Heidelberg · Zbl 1369.94552 · doi:10.1007/978-3-662-49896-5_1 |
| [37] | Micciancio, D.; Peikert, C.; Pointcheval, D.; Johansson, T., Trapdoors for lattices: simpler, tighter, faster, smaller, Advances in Cryptology - EUROCRYPT 2012, 700-718 (2012), Heidelberg: Springer, Heidelberg · Zbl 1297.94090 · doi:10.1007/978-3-642-29011-4_41 |
| [38] | O’Neill, A.; Peikert, C.; Waters, B.; Rogaway, P., Bi-deniable public-key encryption, Advances in Cryptology - CRYPTO 2011, 525-542 (2011), Heidelberg: Springer, Heidelberg · Zbl 1290.94113 · doi:10.1007/978-3-642-22792-9_30 |
| [39] | Peikert, C.; Rabin, T., An efficient and parallel Gaussian sampler for lattices, Advances in Cryptology - CRYPTO 2010, 80-97 (2010), Heidelberg: Springer, Heidelberg · Zbl 1280.94091 · doi:10.1007/978-3-642-14623-7_5 |
| [40] | Quach, W., Wee, H., Wichs, D.: Laconic function evaluation and applications. In: Thorup, M. (ed.) 59th FOCS, pp. 859-870. IEEE Computer Society Press (2018). doi:10.1109/FOCS.2018.00086 |
| [41] | 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). doi:10.1145/1060590.1060603 · Zbl 1192.94106 |
| [42] | Yao, A.C.C.: How to generate and exchange secrets (extended abstract). In: 27th FOCS, pp. 162-167. IEEE Computer Society Press (1986). doi:10.1109/SFCS.1986.25 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
