Top

Designs, Codes and Cryptography

Published in:

12-03-2021

(In)security of concrete instantiation of Lin17’s functional encryption scheme from noisy multilinear maps

Authors: Wonhee Cho, Jiseung Kim, Changmin Lee

Published in: Designs, Codes and Cryptography | Issue 5/2021

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

search-config

AI-assisted search

Off

Abstract

Functional encryption (FE) is a novel cryptographic paradigm. In comparison to conventional encryption schemes, FE allows producing secret keys \(sk_f\) corresponding to a function f that decrypt encryptions of \(x_0\) to \(f(x_0)\). Recently, Lin proposed FE for arbitrary degree polynomials from the SXDH assumption to an exact multilinear map (CRYPTO’17). However, there is no concrete instantiation of the scheme in the absence of an exact multilinear map. Although Lin’s FE can be instantiated by noisy multilinear maps such as the GGH13, CLT13, and GGH15 schemes, the security of FE instantiated by noisy multilinear maps is unclear. In this paper, we point out the weakness of the Lin’s FE when it is instantiated by well-known candidates of noisy multilinear maps. In other words, we present a polynomial time attack of the FE on each noisy multilinear map. In the proposed method, our attack captures Lin’s FE for arbitrary degree polynomials instantiated by GGH13 and CLT13 and is also applicable to FE for polynomials of degree \(O(\log _2 \lambda )\) when instantiated by GGH15 under the current parameters where \(\lambda \) is the security parameter.

previous article Near-MDS codes from elliptic curves

next article Robustly reusable fuzzy extractor with imperfect randomness

Available only for authorised users

Given an ideal \(\langle {\mathbf{g}}\rangle \), recovering a short generator \({\mathbf{g}}\) is hard.

Here the size of components in a matrix is small.

\(\rho \) is a parameter used in the CLT13 multilinear map. For the parameter choice, please refer to reference [19]

As another option, we can encode an i-th component message vector into an i-th diagonal entry. Our analysis still works with this encoding method. Since this method comprising the encoding method and its analysis requires many calculations, and these calculations are placed in Appendix C.

One can easily consider the size of the samples to distinguish two distributions, but it is hard to formally show completeness. Please see this reference [13] for a detailed discussion.

The GGH15 multilinear map does not support homomorphic scalar multiplications; for simplicity we proceed as if scalar multiplication in GGH15 holds. Actually, our attack only uses \(c_{i,j,k} = 1\) or zero for all i, j, k.

In this case, there is no product of \( D \)’s. So the variance of \(X_{{\mathbf{x}}_b}^{i,3,l}\) is an exact value.

\( D _{i,l,{\mathbf{x}}_b}^3\) is a random vector so that these are random vectors.

\({\mathbf{u}}_{i,l,b}^{(3)}\) is a 3rd element of a random vector \({\mathbf{u}}_{i,l,b}\).

Abdalla M., Bourse F., De Caro A., Pointcheval D.: Simple functional encryption schemes for inner products. In: IACR International Workshop on Public Key Cryptography, pp. 733–751. Springer (2015).

Abdalla M., Gong J., Wee H.: Functional encryption for attribute-weighted sums from k-lin. In: Annual International Cryptology Conference, pp. 685–716. Springer (2020).

Agrawal S., Boyen X., Vaikuntanathan V., Voulgaris P., Wee H.: Functional encryption for threshold functions (or fuzzy ibe) from lattices. In: Fischlin M., Buchmann J., Manulis M. (eds.) Public Key Cryptography - PKC 2012, pp. 280–297. Springer, Berlin Heidelberg, Berlin, Heidelberg (2012).

Ananth P., Jain A.: Indistinguishability obfuscation from compact functional encryption. In: Annual Cryptology Conference, pp. 308–326. Springer (2015).

Apon D., Döttling N., Garg S., Mukherjee P.: Cryptanalysis of indistinguishability obfuscations of circuits over ggh13. In: LIPIcs-Leibniz International Proceedings in Informatics, vol. 80. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2017).

Baltico C.E.Z., Catalano D., Fiore D., Gay R.: Practical functional encryption for quadratic functions with applications to predicate encryption. In: Annual International Cryptology Conference, pp. 67–98. Springer (2017).

Bitansky N., Nishimaki R., Passelegue A., Wichs D.: From cryptomania to obfustopia through secret-key functional encryption. J. Cryptol. 33(2), 357–405 (2020).MathSciNetCrossRef

Bitansky N., Vaikuntanathan V.: Indistinguishability obfuscation from functional encryption. J. ACM (JACM) 65(6), 1–37 (2018).MathSciNetCrossRef

Boneh D., Sahai A., Waters B.: Functional encryption: Definitions and challenges. In: Theory of Cryptography Conference, pp. 253–273. Springer (2011).

10.

Chen Y., Gentry C., Halevi S.: Cryptanalyses of candidate branching program obfuscators. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 278–307. Springer (2017).

11.

Chen Y., Vaikuntanathan V., Wee H.: Ggh15 beyond permutation branching programs: Proofs, attacks, and candidates. In: Annual International Cryptology Conference, pp. 577–607. Springer (2018).

12.

Cheon J.H., Cho W., Hhan M., Kang M., Kim J., Lee C.: Algorithms for crt-variant of approximate greatest common divisor problem. Number-Theoretic Methods in Cryptology (NutMiC) 2019, 195 (2019).

13.

Cheon J.H., Cho W., Hhan M., Kim J., Lee C.: Statistical zeroizing attack: Cryptanalysis of candidates of bp obfuscation over ggh15 multilinear map. In: Annual International Cryptology Conference, pp. 253–283. Springer (2019).

14.

Cheon J.H., Han K., Lee C., Ryu H., Stehlé D.: Cryptanalysis of the multilinear map over the integers. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 3–12. Springer (2015).

15.

Cheon J.H., Hhan M., Kim J., Lee C.: Cryptanalyses of branching program obfuscations over GGH13 multilinear map from the NTRU problem. In: Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19–23, 2018, Proceedings, Part III, pp. 184–210 (2018).

16.

Coron J.S., Gentry C., Halevi S., Lepoint T., Maji H.K., Miles E., Raykova M., Sahai A., Tibouchi M.: Zeroizing without low-level zeroes: New mmap attacks and their limitations. In: Advances in Cryptology–CRYPTO 2015, pp. 247–266. Springer (2015).

17.

Coron J.S., Lee M.S., Lepoint T., Tibouchi M.: Cryptanalysis of ggh15 multilinear maps. In: Annual Cryptology Conference, pp. 607–628. Springer (2016).

18.

Coron J.S., Lee M.S., Lepoint T., Tibouchi M.: Zeroizing attacks on indistinguishability obfuscation over clt13. In: IACR International Workshop on Public Key Cryptography, pp. 41–58. Springer (2017).

19.

Coron J.S., Lepoint T., Tibouchi M.: Practical multilinear maps over the integers. In: Advances in Cryptology–CRYPTO 2013, pp. 476–493. Springer (2013).

20.

Garg S., Gentry C., Halevi S.: Candidate multilinear maps from ideal lattices. In: Eurocrypt, vol. 7881, pp. 1–17. Springer (2013).

21.

Garg S., Gentry C., Halevi S., Raykova M., Sahai A., Waters B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pp. 40–49. IEEE Computer Society (2013).

22.

Garg S., Gentry C., Halevi S., Zhandry M.: Functional encryption without obfuscation. In: Theory of Cryptography Conference, pp. 480–511. Springer (2016).

23.

Gay R.: Functional encryption for quadratic functions, and applications to predicate encryption. IACR Cryptol. 2016, 1106 (2016).

24.

Gay R.: A new paradigm for public-key functional encryption for degree-2 polynomials. In: IACR International Conference on Public-Key Cryptography, pp. 95–120. Springer (2020).

25.

Gentry C., Gorbunov S., Halevi S.: Graph-induced multilinear maps from lattices. In: Theory of Cryptography, pp. 498–527. Springer (2015).

26.

Gentry C., Peikert C., Vaikuntanathan V.: Trapdoors for hard lattices and new cryptographic constructions. In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, pp. 197–206. ACM (2008).

27.

Gong J., Qian H.: Simple and efficient fe for quadratic functions. Tech. rep., Cryptology ePrint Archive, Report 2020/1026 (2020).

28.

Goyal V., Pandey O., Sahai A., Waters B.: Attribute-based encryption for fine-grained access control of encrypted data. In: Proceedings of the 13th ACM Conference on Computer and Communications Security, pp. 89–98 (2006).

29.

Hu Y., Jia H.: Cryptanalysis of ggh map. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 537–565. Springer (2016).

30.

Kitagawa F., Nishimaki R., Tanaka K., Yamakawa T.: Adaptively secure and succinct functional encryption: improving security and efficiency, simultaneously. In: Annual International Cryptology Conference, pp. 521–551. Springer (2019).

31.

Komargodski I., Segev G.: From minicrypt to obfustopia via private-key functional encryption. J. Cryptol. 33(2), 406–458 (2020).MathSciNetCrossRef

32.

Lin H.: Indistinguishability obfuscation from sxdh on 5-linear maps and locality-5 prgs. In: Annual International Cryptology Conference, pp. 599–629. Springer (2017).

33.

Lin H., Vaikuntanathan V.: Indistinguishability obfuscation from ddh-like assumptions on constant-degree graded encodings. In: Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, pp. 11–20. IEEE (2016).

34.

Micciancio D., Peikert C.: Trapdoors for lattices: simpler, tighter, faster, smaller. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 700–718. Springer (2012).

35.

Miles E., Sahai A., Zhandry M.: Annihilation attacks for multilinear maps: cryptanalysis of indistinguishability obfuscation over ggh13. In: Annual Cryptology Conference, pp. 629–658. Springer (2016).

36.

O’Neill A.: Definitional issues in functional encryption. IACR Cryptol. ePrint Arch. 2010, 556 (2010). http://eprint.iacr.org/2010/556.

37.

Pellet-Mary A.: Quantum attacks against indistinguishablility obfuscators proved secure in the weak multilinear map model. In: Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19–23, 2018, Proceedings, Part III, pp. 153–183 (2018).

38.

Ryffel T., Pointcheval D., Bach F., Dufour-Sans E., Gay R.: Partially encrypted deep learning using functional encryption. Adv. Neural Inf. Process. Syst. 32, 4517–4528 (2019).

39.

Sahai A., Waters B.: Fuzzy identity-based encryption. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 457–473. Springer (2005).

40.

Shamir A.: Identity-based cryptosystems and signature schemes. In: Workshop on the Theory and Application of Cryptographic Techniques, pp. 47–53. Springer (1984).

41.

Wee H.: Functional encryption for quadratic functions from k-lin, revisited. In: Theory of Cryptography Conference, pp. 210–228. Springer (2020).

Title: (In)security of concrete instantiation of Lin17’s functional encryption scheme from noisy multilinear maps
Authors: Wonhee Cho
Jiseung Kim
Changmin Lee
Publication date: 12-03-2021
Publisher: Springer US
Published in: Designs, Codes and Cryptography / Issue 5/2021
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-021-00854-y

Springer Professional

(In)security of concrete instantiation of Lin17’s functional encryption scheme from noisy multilinear maps

Abstract

Premium Partner

Springer Professional

Abstract

Please log in to get access to your license.

Other articles of this Issue 5/2021

A scalable post-quantum hash-based group signature

Some constructions of quantum MDS codes

New families of self-dual codes

A note on Assmus–Mattson type theorems

Asymmetric entanglement-assisted quantum codes: bound and constructions

On the Resilience of Even-Mansour to Invariant Permutations

Premium Partner