Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Designs, Codes and Cryptography

12.03.2021

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

verfasst von: Wonhee Cho, Jiseung Kim, Changmin Lee

Erschienen in: Designs, Codes and Cryptography | Ausgabe 5/2021

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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.
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
Given an ideal \(\langle {\mathbf{g}}\rangle \), recovering a short generator \({\mathbf{g}}\) is hard.
 
2
Here the size of components in a matrix is small.
 
3
\(\rho \) is a parameter used in the CLT13 multilinear map. For the parameter choice, please refer to reference  [19]
 
4
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.
 
5
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.
 
6
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.
 
7
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.
 
8
\( D _{i,l,{\mathbf{x}}_b}^3\) is a random vector so that these are random vectors.
 
9
\({\mathbf{u}}_{i,l,b}^{(3)}\) is a 3rd element of a random vector \({\mathbf{u}}_{i,l,b}\).
 
Literatur
1.
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).
2.
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).
3.
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).
4.
Ananth P., Jain A.: Indistinguishability obfuscation from compact functional encryption. In: Annual Cryptology Conference, pp. 308–326. Springer (2015).
5.
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).
6.
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).
7.
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
8.
Bitansky N., Vaikuntanathan V.: Indistinguishability obfuscation from functional encryption. J. ACM (JACM) 65(6), 1–37 (2018).MathSciNetCrossRef
9.
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.
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).
Metadaten
Titel
(In)security of concrete instantiation of Lin17’s functional encryption scheme from noisy multilinear maps
verfasst von
Wonhee Cho
Jiseung Kim
Changmin Lee
Publikationsdatum
12.03.2021
Verlag
Springer US
Erschienen in
Designs, Codes and Cryptography / Ausgabe 5/2021
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-021-00854-y