Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
One-Round Strong Oblivious Signature-Based Envelope Read chapter Read first chapter

2016 | OriginalPaper | Chapter

Generalized Hardness Assumption for Self-bilinear Map with Auxiliary Information

Authors : Takashi Yamakawa, Goichiro Hanaoka, Noboru Kunihiro

Published in: Information Security and Privacy

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

A self-bilinear map (SBM) is a bilinear map where source and target groups are identical. An SBM naturally yields a multilinear map, which has numerous applications in cryptography. In spite of its usefulness, there is known a strong negative result on the existence of an ideal SBM. On the other hand, Yamakawa et al. (CRYPTO’14) introduced the notion of a self-bilinear map with auxiliary information (AI-SBM), which is a weaker variant of SBM and constructed it based on the factoring assumption and an indistinguishability obfuscation (\(i\mathcal {O}\)). In their work, they proved that their AI-SBM satisfies the Auxiliary Information Multilinear Computational Diffie-Hellman (AI-MCDH) assumption, which is a natural analogue of the Multilinear Computational Diffie-Hellman (MCDH) assumption w.r.t. multilinear maps. Then they show that they can replace multilinear maps with AI-SBMs in some multilinear-map-based primitives that is proven secure under the MCDH assumption.
In this work, we further investigate what hardness assumptions hold w.r.t. their AI-SBM. Specifically, we introduce a new hardness assumption called the Auxiliary Information Generalized Multilinear Diffie-Hellman (AI-GMDH) assumption. The AI-GMDH is parameterized by some parameters and thus can be seen as a family of hardness assumptions. We give a sufficient condition of parameters for which the AI-GMDH assumption holds under the same assumption as in the previous work. Based on this result, we can easily prove the AI-SBM satisfies certain hardness assumptions including not only the AI-GMDH assumption but also more complicated assumptions. This enable us to convert a multilinear-map-based primitive that is proven secure under a complicated hardness assumption to AI-SBP-based (and thus the factoring and \(i\mathcal {O}\)-based) one. As an example, we convert Catalano et al.’s multilinear-map-based homomorphic signatures (CRYPTO’14) to AI-SBP-based ones.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter A New Attack on Three Variants of the RSA Cryptosystem
next chapter Deterministic Encoding into Twisted Edwards Curves
Footnotes
1
Actually in [29], this assumption is called Multilinear Computational Diffie-Hellman with Auxiliary Information (MCDHAI) assumption. We rename the assumption for the consistency with other assumptions in this paper.
 
2
Actually, the AI-GMDH assumption is also parametrized by an additional natural number M. We omit it here for making the intuition simpler. For more details, see Definition 3 followed by Remark 2.
 
3
This holds for example, if we assume the existence of a constant \(\delta \) such that all prime factors of \((P-1)(Q-1)/4\) is no less than \(\delta \ell _N\)-bit as in [22, 29]. Especially, strong RSA moduli (e.g., \(N=PQ=(2p+1)(2q+1)\) such that P, Q, p and q are distinct primes) suffice.
 
4
Note that actually not all of these elements are needed to evaluate the map \(e_n\).
 
5
There is flexibility for the definition of the canonical circuit. However, any definition works if the size of \(\tilde{C}_{N,x}\) is polynomially bounded in \(\lambda \) and |x|.
 
6
The actual presentation is slightly modified due to the modification of the definition.
 
Literature
1.
Albrecht, M.R., Farshim, P., Hofheinz, D., Larraia, E., Paterson, K.G.: Multilinear maps from obfuscation. In: Kushilevitz, E., et al. (eds.) TCC 2016-A. LNCS, vol. 9562, pp. 446–473. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-49096-9_​19 CrossRef
2.
Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S.P., Yang, K.: On the (im)possibility of obfuscating programs. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 1–18. Springer, Heidelberg (2001)CrossRef
3.
Boneh, D., Boyen, X.: Efficient selective-ID secure identity-based encryption without random oracles. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 223–238. Springer, Heidelberg (2004)CrossRef
4.
Boneh, D., Franklin, M.: Identity-based encryption from the weil pairing. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 213–229. Springer, Heidelberg (2001)CrossRef
5.
Boneh, D., Freeman, D.M.: Homomorphic signatures for polynomial functions. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 149–168. Springer, Heidelberg (2011)CrossRef
6.
Boneh, D., Gentry, C., Gorbunov, S., Halevi, S., Nikolaenko, V., Segev, G., Vaikuntanathan, V., Vinayagamurthy, D.: 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)CrossRef
7.
8.
Boneh, D., Waters, B., Zhandry, M.: Low overhead broadcast encryption from multilinear maps. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part I. LNCS, vol. 8616, pp. 206–223. Springer, Heidelberg (2014)CrossRef
9.
Catalano, D., Fiore, D., Warinschi, B.: Homomorphic signatures with efficient verification for polynomial functions. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part I. LNCS, vol. 8616, pp. 371–389. Springer, Heidelberg (2014)CrossRef
10.
Cheon, J.H., Fouque, P.-A., Lee, C., Minaud, B., Ryu, H.: Cryptanalysis of the new CLT multilinear map over the integers. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 509–536. Springer, Heidelberg (2016). doi:10.​1007/​978-3-662-49890-3_​20 CrossRef
11.
Cheon, J.H., Han, K., Lee, C., Ryu, H., Stehlé, D.: Cryptanalysis of the multilinear map over the integers. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 3–12. Springer, Heidelberg (2015)
12.
13.
Coron, J.-S., Lepoint, T., Tibouchi, M.: Practical multilinear maps over the integers. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 476–493. Springer, Heidelberg (2013)CrossRef
14.
Coron, J.-S., Lepoint, T., Tibouchi, M.: New multilinear maps over the integers. CRYPTO 1, 267–286 (2015)MathSciNetMATH
15.
Garg, S., Gentry, C., Halevi, S.: Candidate multilinear maps from ideal lattices. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 1–17. Springer, Heidelberg (2013)CrossRef
16.
Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: FOCS, pp. 40–49 (2013)
17.
Garg, S., Gentry, C., Halevi, S., Sahai, A., Waters, B.: Attribute-based encryption for circuits from multilinear maps. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part II. LNCS, vol. 8043, pp. 479–499. Springer, Heidelberg (2013)CrossRef
18.
Gentry, C., Gorbunov, S., Halevi, S.: Graph-induced multilinear maps from lattices. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015, Part II. LNCS, vol. 9015, pp. 498–527. Springer, Heidelberg (2015)CrossRef
19.
Gorbunov, S., Vaikuntanathan, V., Wichs, D.: Leveled fully homomorphic signatures from standard lattices. In: STOC 2015, 469–477 (2015)
20.
Groth, J., Ostrovsky, R., Sahai, A.: Perfect non-interactive zero knowledge for NP. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 339–358. Springer, Heidelberg (2006)CrossRef
21.
Groth, J., Sahai, A.: Efficient non-interactive proof systems for bilinear groups. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 415–432. Springer, Heidelberg (2008)CrossRef
22.
Hofheinz, D., Kiltz, E.: The group of signed quadratic residues and applications. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 637–653. Springer, Heidelberg (2009)CrossRef
23.
24.
Lee, C., Cheon, J.H., Jeong, J.: An algorithm for ntru problems and cryptanalysis of the ggh multilinear map without an encoding of zero. Cryptology ePrint Archive, Report 2016/139 (2016). http://​eprint.​iacr.​org/​
25.
Miles, E., Sahai, A., Zhandry, M.: Annihilation attacks for multilinear maps: Cryptanalysis of indistinguishability obfuscation over ggh13. Cryptology ePrint Archive, Report 2016/147 (2016). http://​eprint.​iacr.​org/​
26.
27.
Sahai, A., Waters, B.: Fuzzy identity-based encryption. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 457–473. Springer, Heidelberg (2005)CrossRef
28.
29.
Yamakawa, T., Yamada, S., Hanaoka, G., Kunihiro, N.: Self-bilinear map on unknown order groups from indistinguishability obfuscation and its applications. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part II. LNCS, vol. 8617, pp. 90–107. Springer, Heidelberg (2014)CrossRef
Metadata
Title
Generalized Hardness Assumption for Self-bilinear Map with Auxiliary Information
Authors
Takashi Yamakawa
Goichiro Hanaoka
Noboru Kunihiro
Copyright Year
2016
Book
Information Security and Privacy

Print ISBN: 978-3-319-40366-3

Electronic ISBN: 978-3-319-40367-0

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-40367-0_17

Premium Partner

    Image Credits