Cryptanalysis of the Multilinear Map over the Integers
详细信息 查看全文
- 作者：Jung Hee Cheon (15)
Kyoohyung Han (15)
Changmin Lee (15)
Hansol Ryu (15)
Damien Stehl茅 (16)
15. Seoul National University (SNU) ; Seoul ; Republic of Korea
16. ENS de Lyon ; Laboratoire LIP (U. Lyon ; CNRS ; ENSL ; INRIA ; UCBL) ; Lyon ; France - 关键词：Multilinear maps ; Graded encoding schemes
- 刊名：Lecture Notes in Computer Science
- 出版年：2015
- 出版时间：2015
- 年：2015
- 卷：9056
- 期：1
- 页码：3-12
- 全文大小：231 KB
- 参考文献：1. Abdalla, M, Benhamouda, F, Pointcheval, D (2014) Disjunctions for hash proof systems: New constructions and applications. IACR Cryptology ePrint Archive 2014: pp. 483
2. Attrapadung, N (2014) Fully secure and succinct attribute based encryption for circuits from multi-linear maps. IACR Cryptology ePrint Archive 2014: pp. 772
3. Boneh, D, Boyen, X, Shacham, H Short group signatures. In: Franklin, M eds. (2004) Advances in Cryptology 鈥?CRYPTO 2004. Springer, Heidelberg, pp. 41-55 CrossRef
4. Boneh, D, Goh, E-J, Nissim, K Evaluating 2-DNF formulas on ciphertexts. In: Kilian, J eds. (2005) Theory of Cryptography. Springer, Heidelberg, pp. 325-341 CrossRef
5. Boneh, D, Lewi, K, Montgomery, H, Raghunathan, A Key homomorphic PRFs and their applications. In: Canetti, R, Garay, JA eds. (2013) Advances in Cryptology 鈥?CRYPTO 2013. Springer, Heidelberg, pp. 410-428 CrossRef
6. Benhamouda, F, Pointcheval, D (2013) Verifier-based password-authenticated key exchange: New models and constructions. IACR Cryptology ePrint Archive 2013: pp. 833
7. Brakerski, Z, Rothblum, GN Obfuscating conjunctions. In: Canetti, R, Garay, JA eds. (2013) Advances in Cryptology 鈥?CRYPTO 2013. Springer, Heidelberg, pp. 416-434 CrossRef
8. Boneh, D, Silverberg, A (2002) Applications of multilinear forms to cryptography. Contemporary Mathematics 324: pp. 71-90 CrossRef
9. Boneh, D, Wu, DJ, Zimmerman, J (2014) Immunizing multilinear maps against zeroizing attacks. IACR Cryptology ePrint Archive 2014: pp. 930
10. Coron, J-S, Lepoint, T, Tibouchi, M Practical multilinear maps over the integers. In: Canetti, R, Garay, JA eds. (2013) Advances in Cryptology 鈥?CRYPTO 2013. Springer, Heidelberg, pp. 476-493 CrossRef
11. Coron, J-S, Lepoint, T, Tibouchi, M (2014) Cryptanalysis of two candidate fixes of multilinear maps over the integers. IACR Cryptology ePrint Archive 2014: pp. 975
12. Coron, J.-S., Lepoint, T., Tibouchi, M.: Personal communication (2014)
13. Dijk, M, Gentry, C, Halevi, S, Vaikuntanathan, V Fully homomorphic encryption over the integers. In: Gilbert, H eds. (2010) Advances in Cryptology 鈥?EUROCRYPT 2010. Springer, Heidelberg, pp. 24-43 CrossRef
14. Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Proceedings of STOC, pp. 169鈥?78. ACM (2009)
15. Garg, S, Gentry, C, Halevi, S Candidate multilinear maps from ideal lattices. In: Johansson, T, Nguyen, PQ eds. (2013) Advances in Cryptology 鈥?EUROCRYPT 2013. Springer, Heidelberg, pp. 1-17 CrossRef
16. Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: Proceedings of FOCS, pp. 40鈥?9. IEEE Computer Society Press (2013)
17. Gentry, C, Gorbunov, S, Halevi, S (2014) Graded multilinear maps from lattices. IACR Cryptology ePrint Archive 2014: pp. 645
18. Garg, S., Gentry, C., Halevi, S., Zhandry, M.: Fully secure attribute based encryption from multilinear maps. Cryptology ePrint Archive, Report 2014/622 (2014)
19. Garg, S., Gentry, C., Halevi, S., Zhandry, M.: Fully secure functional encryption without obfuscation. Cryptology ePrint Archive, Report 2014/666 (2014)
20. Gentry, C, Halevi, S, Maji, HK, Sahai, A (2014) Zeroizing without zeroes: Cryptanalyzing multilinear maps without encodings of zero. IACR Cryptology ePrint Archive 2014: pp. 929
21. Gentry, C, Lewko, AB, Sahai, A, Waters, B (2014) Indistinguishability obfuscation from the multilinear subgroup elimination assumption. IACR Cryptology ePrint Archive 2014: pp. 309
22. Gentry, C, Lewko, A, Waters, B Witness encryption from instance independent assumptions. In: Garay, JA, Gennaro, R eds. (2014) Advances in Cryptology 鈥?CRYPTO 2014. Springer, Heidelberg, pp. 426-443 CrossRef
23. Lewi, K, Montgomery, H, Raghunathan, A Improved constructions of PRFs secure against related-key attacks. In: Boureanu, I, Owesarski, P, Vaudenay, S eds. (2014) Applied Cryptography and Network Security. Springer, Heidelberg, pp. 44-61 CrossRef
24. Lee, HT, Seo, JH Security analysis of multilinear maps over the integers. In: Garay, JA, Gennaro, R eds. (2014) Advances in Cryptology 鈥?CRYPTO 2014. Springer, Heidelberg, pp. 224-240 CrossRef
25. Scott, M (2002) Authenticated ID-based key exchange and remote log-in with simple token and PIN number. IACR Cryptology ePrint Archive 2002: pp. 164
26. Storjohann, A.: Integer matrix rank certification. In: Proceedings of ISSAC, pp. 333鈥?40. ACM (2009)
27. Zhandry, M (2014) Adaptively secure broadcast encryption with small system parameters. IACR Cryptology ePrint Archive 2014: pp. 757
28. Zimmerman, J (2014) How to obfuscate programs directly. IACR Cryptology ePrint Archive 2014: pp. 776 - 作者单位：Advances in Cryptology -- EUROCRYPT 2015
- 丛书名：978-3-662-46799-2
- 刊物类别：Computer Science
- 刊物主题：Artificial Intelligence and Robotics
Computer Communication Networks
Software Engineering
Data Encryption
Database Management
Computation by Abstract Devices
Algorithm Analysis and Problem Complexity - 出版者：Springer Berlin / Heidelberg
- ISSN：1611-3349
文摘
We describe a polynomial-time cryptanalysis of the (approximate) multilinear map of Coron, Lepoint and Tibouchi (CLT). The attack relies on an adaptation of the so-called zeroizing attack against the Garg, Gentry and Halevi (GGH) candidate multilinear map. Zeroizing is much more devastating for CLT than for GGH. In the case of GGH, it allows to break generalizations of the Decision Linear and Subgroup Membership problems from pairing-based cryptography. For CLT, this leads to a total break: all quantities meant to be kept secret can be efficiently and publicly recovered.