More Web Proxy on the site http://driver.im/

Article

Partitioning via Non-linear Polynomial Functions: More Compact IBEs from Ideal Lattices and Bilinear Maps

Authors:

Shuichi Katsumata,

Shota YamadaAuthors Info & Claims

Proceedings, Part II, of the 22nd International Conference on Advances in Cryptology --- ASIACRYPT 2016 - Volume 10032

Pages 682 - 712

https://doi.org/10.1007/978-3-662-53890-6_23

Published: 04 December 2016 Publication History

Abstract

In this paper, we present new adaptively secure identity-based encryption IBE schemes. One of the distinguishing properties of the schemes is that it achieves shorter public parameters than previous schemes. Both of our schemes follow the general framework presented in the recent IBE scheme of Yamada Eurocrypt 2016, employed with novel techniques tailored to meet the underlying algebraic structure to overcome the difficulties arising in our specific setting. Specifically, we obtain the following:

- Our first scheme is proven secure under the ring learning with errors RLWE assumption and achieves the best asymptotic space efficiency among existing schemes from the same assumption. The main technical contribution is in our new security proof that exploits the ring structure in a crucial way. Our technique allows us to greatly weaken the underlying hardness assumption e.g., we assume the hardness of RLWE with a fixed polynomial approximation factor whereas Yamada's scheme requires a super-polynomial approximation factor while improving the overall efficiency.

- Our second IBE scheme is constructed on bilinear maps and is secure under the 3-computational bilinear Diffie-Hellman exponent assumption. This is the first IBE scheme based on the hardness of a computational/search problem, rather than a decisional problem such as DDH and DLIN on bilinear maps with sub-linear public parameter size.

References

[1]

Agrawal, S., Boneh, D., Boyen, X.: Efficient Lattice HIBE in the standard model. In: Gilbert, H. ed. EUROCRYPT 2010. LNCS, vol. 6110, pp. 553---572. Springer, Heidelberg 2010.

Digital Library

[2]

Applebaum, B., Cash, D., Peikert, C., Sahai, A.: Fast cryptographic primitives and circular-secure encryption based on hard learning problems. In: Halevi, S. ed. CRYPTO 2009. LNCS, vol. 5677, pp. 595---618. Springer, Heidelberg 2009.

Digital Library

[3]

Alperin-Sheriff, J.: Short signatures with short public keys from homomorphic trapdoor functions. In: Katz, J. ed. PKC 2015. LNCS, vol. 9020, pp. 236---255. Springer, Heidelberg 2015.

[4]

Apon, D., Fan, X., Liu, F.: Fully-secure lattice-based IBE as compact as PKE. In: IACR Cryptology ePrint Archive 2016, p. 125 2016

[5]

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.

[6]

Boneh, D., Boyen, X.: Secure identity based encryption without random oracles. In: Franklin, M. ed. CRYPTO 2004. LNCS, vol. 3152, pp. 443---459. Springer, Heidelberg 2004.

[7]

Boneh, D., Boyen, X., Goh, E.-J.: Hierarchical identity based encryption with constant size ciphertext. In: Cramer, R. ed. EUROCRYPT 2005. LNCS, vol. 3494, pp. 440---456. Springer, Heidelberg 2005.

Digital Library

[8]

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.

Digital Library

[9]

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.

[10]

Boneh, D., Gentry, C., Hamburg, M.: Space-efficient identity based encryption without pairings. In: FOCS, pp. 647---657 2007

Digital Library

[11]

Boneh, D., Gentry, C., Waters, B.: Collusion resistant broadcast encryption with short ciphertexts and private keys. In: Shoup, V. ed. CRYPTO 2005. LNCS, vol. 3621, pp. 258---275. Springer, Heidelberg 2005.

Digital Library

[12]

Boneh, D., Hamburg, M.: Generalized identity based and broadcast encryption schemes. In: Pieprzyk, J. ed. ASIACRYPT 2008. LNCS, vol. 5350, pp. 455---470. Springer, Heidelberg 2008.

Digital Library

[13]

Boyen, X.: Lattice Mixing and Vanishing Trapdoors: a framework for fully secure short signatures and more. In: Nguyen, P.Q., Pointcheval, D. eds. PKC 2010. LNCS, vol. 6056, pp. 499---517. Springer, Heidelberg 2010.

Digital Library

[14]

Bellare, M., Ristenpart, T.: Simulation without the Artificial Abort: simplified proof and improved concrete security for Waters' IBE scheme. In: Joux, A. ed. EUROCRYPT 2009. LNCS, vol. 5479, pp. 407---424. Springer, Heidelberg 2009.

[15]

Cash, D., Hofheinz, D., Kiltz, E., Peikert, C.: Bonsai Trees, or how to delegate a lattice basis. In: Gilbert, H. ed. EUROCRYPT 2010. LNCS, vol. 6110, pp. 523---552. Springer, Heidelberg 2010.

Digital Library

[16]

Chen, Y., Chen, L., Zhang, Z.: CCA secure IB-KEM from the computational bilinear Diffie-Hellman assumption in the standard model. In: Kim, H. ed. ICISC 2011. LNCS, vol. 7259, pp. 275---301. Springer, Heidelberg 2012.

Digital Library

[17]

Cocks, C.: An identity based encryption scheme based on quadratic residues. In: Honary, B. ed. Cryptography and Coding 2001. LNCS, vol. 2260, pp. 360---363. Springer, Heidelberg 2001.

Digital Library

[18]

Chen, J., Wee, H.: Fully, almost tightly secure IBE and dual system groups. In: Canetti, R., Garay, J.A. eds. CRYPTO 2013. LNCS, vol. 8043, pp. 435---460. Springer, Heidelberg 2013.

[19]

Ducas, L., Micciancio, D.: Improved short lattice signatures in the standard model. In: Garay, J.A., Gennaro, R. eds. CRYPTO 2014. LNCS, vol. 8616, pp. 335---352. Springer, Heidelberg 2014.

[20]

Ducas, L., Lyubashevsky, V., Prest, T.: Efficient identity-based encryption over NTRU lattices. In: Sarkar, P., Iwata, T. eds. ASIACRYPT 2014. LNCS, vol. 8874, pp. 22---41. Springer, Heidelberg 2014.

[21]

Ducas, L., Micciancio, D.: FHEW: bootstrapping homomorphic encryption in less than a second. In: Oswald, E., Fischlin, M. eds. EUROCRYPT 2015. LNCS, vol. 9056, pp. 617---640. Springer, Heidelberg 2015.

[22]

Galindo, D.: Chosen-ciphertext secure identity-based encryption from computational bilinear Diffie-Hellman. In: Joye, M., Miyaji, A., Otsuka, A. eds. Pairing 2010. LNCS, vol. 6487, pp. 367---376. Springer, Heidelberg 2010.

Digital Library

[23]

Gentry, C.: Practical identity-based encryption without random oracles. In: Vaudenay, S. ed. EUROCRYPT 2006. LNCS, vol. 4004, pp. 445---464. Springer, Heidelberg 2006.

Digital Library

[24]

Goldreich, O., Levin, L.: A hard-core predicate for all one-way functions. In: STOC, pp. 25---32 1989

Digital Library

[25]

Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: STOC, pp. 197---206 2008

Digital Library

[26]

Jutla, C.S., Roy, A.: Shorter Quasi-Adaptive NIZK proofs for linear subspaces. In: Sako, K., Sarkar, P. eds. ASIACRYPT 2013. LNCS, vol. 8269, pp. 1---20. Springer, Heidelberg 2013.

Digital Library

[27]

Lewko, A., Okamoto, T., Sahai, A., Takashima, K., Waters, B.: Fully Secure Functional Encryption: attribute-based encryption and hierarchical inner product encryption. In: Gilbert, H. ed. EUROCRYPT 2010. LNCS, vol. 6110, pp. 62---91. Springer, Heidelberg 2010.

Digital Library

[28]

Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. In: Gilbert, H. ed. EUROCRYPT 2010. LNCS, vol. 6110, pp. 1---23. Springer, Heidelberg 2010.

Digital Library

[29]

Lyubashevsky, V., Peikert, C., Regev, O.: A toolkit for ring-LWE cryptography. In: Johansson, T., Nguyen, P.Q. eds. EUROCRYPT 2013. LNCS, vol. 7881, pp. 35---54. Springer, Heidelberg 2013.

[30]

Langlois, A., Stehlé, D.: Worst-case to average-case reductions for module lattices. DES 753, 565---599 2015

Digital Library

[31]

Lewko, A., Waters, B.: New techniques for dual system encryption and fully secure HIBE with short ciphertexts. In: Micciancio, D. ed. TCC 2010. LNCS, vol. 5978, pp. 455---479. Springer, Heidelberg 2010.

Digital Library

[32]

Micciancio, D., Peikert, C.: Trapdoors for Lattices: simpler, tighter, faster, smaller. In: Pointcheval, D., Johansson, T. eds. EUROCRYPT 2012. LNCS, vol. 7237, pp. 700---718. Springer, Heidelberg 2012.

Digital Library

[33]

Naccache, D.: Secure and practical identity-based encryption. IET Inf. Sec. 12, 59---64 2007

[34]

Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: STOC, pp. 84---93. ACM Press 2005

Digital Library

[35]

Shamir, A.: Identity-based cryptosystems and signature schemes. In: Blakley, G.R., Chaum, D. eds. CRYPTO 1984. LNCS, vol. 196, pp. 47---53. Springer, Heidelberg 1985.

Digital Library

[36]

Sakai, R., Ohgishi, K., Kasahara, M.: Cryptosystems based on pairings. In: SCIS 2000. In Japanese

[37]

Singh, K., Pandu Rangan, C., Banerjee, A.K.: Adaptively secure efficient Lattice HIBE in standard model with short public parameters. In: Bogdanov, A., Sanadhya, S. eds. SPACE 2012. LNCS, vol. 7644, pp. 153---172. Springer, Heidelberg 2012.

Digital Library

[38]

Waters, B.: Efficient identity-based encryption without random oracles. In: Cramer, R. ed. EUROCRYPT 2005. LNCS, vol. 3494, pp. 114---127. Springer, Heidelberg 2005.

Digital Library

[39]

Waters, B.: Dual System Encryption: realizing fully secure IBE and HIBE under simple assumptions. In: Halevi, S. ed. CRYPTO 2009. LNCS, vol. 5677, pp. 619---636. Springer, Heidelberg 2009.

Digital Library

[40]

Xagawa, K.: Improved hierarchical inner-product encryption from lattices. In: Kurosawa, K., Hanaoka, G. eds. PKC 2013. LNCS, vol. 7778, pp. 235---252. Springer, Heidelberg 2013.

[41]

Yamada, S.: Adaptively secure identity-based encryption from lattices with asymptotically shorter public parameters. In: Fischlin, M., Coron, J.-S. eds. EUROCRYPT 2016. LNCS, vol. 9666, pp. 32---62. Springer, Heidelberg 2016.

[42]

Zhang, J., Chen, Y., Zhang, Z.: Programmable Hash Functions from Lattices: short signatures and IBEs with small key sizes. In: Robshaw, M., Katz, J. eds. CRYPTO 2016. LNCS, vol. 9816, pp. 303---332. Springer, Heidelberg 2016.

Digital Library

Cited By

Chen CLai QLu YYu Y(2024)More Efficient Two-Stage Sampling Technique and Its ApplicationsData Security and Privacy Protection10.1007/978-981-97-8546-9_5(88-108)Online publication date: 25-Oct-2024
https://dl.acm.org/doi/10.1007/978-981-97-8546-9_5
Hanaoka GKatsumata SKimura KTakemure KYamada S(2024)Tighter Adaptive IBEs and VRFs: Revisiting Waters’ Artificial AbortTheory of Cryptography10.1007/978-3-031-78020-2_5(124-155)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1007/978-3-031-78020-2_5
Tomita TShikata J(2024)Efficient Identity-Based Encryption with Tight Adaptive Anonymity from RLWEPost-Quantum Cryptography10.1007/978-3-031-62743-9_10(300-321)Online publication date: 12-Jun-2024
https://dl.acm.org/doi/10.1007/978-3-031-62743-9_10
Show More Cited By

Partitioning via Non-linear Polynomial Functions: More Compact IBEs from Ideal Lattices and Bilinear Maps
1. Theory of computation

Recommendations

Efficient KDM-CCA Secure Public-Key Encryption for Polynomial Functions
Proceedings, Part II, of the 22nd International Conference on Advances in Cryptology --- ASIACRYPT 2016 - Volume 10032

KDM $$[\mathcal {F}]$$ -CCA secure public-key encryption PKE protects the security of message fsk, with $$f\in \mathcal {F}$$ , that is computed directly from the secret key, even if the adversary has access to a decryption oracle. An efficient KDM $$[\...
CCA Security and Trapdoor Functions via Key-Dependent-Message Security
Advances in Cryptology – CRYPTO 2019
Abstract
We study the relationship among public-key encryption (PKE) satisfying indistinguishability against chosen plaintext attacks (IND-CPA security), that against chosen ciphertext attacks (IND-CCA security), and trapdoor functions (TDF). Specifically, ...
CCA Security and Trapdoor Functions via Key-Dependent-Message Security
Abstract
We study the relationship among public-key encryption (PKE) satisfying indistinguishability against chosen plaintext attacks (IND-CPA security), that against chosen ciphertext attacks (IND-CCA security), and trapdoor functions (TDF). Specifically, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Proceedings, Part II, of the 22nd International Conference on Advances in Cryptology --- ASIACRYPT 2016 - Volume 10032

December 2016

1027 pages

ISBN:9783662538890

Editors:
Jung Hee Cheon
Seoul National University, Seoul, Korea Republic of
,
Tsuyoshi Takagi
Kyushu University, Fukuoka, Japan

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 04 December 2016

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

32
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chen CLai QLu YYu Y(2024)More Efficient Two-Stage Sampling Technique and Its ApplicationsData Security and Privacy Protection10.1007/978-981-97-8546-9_5(88-108)Online publication date: 25-Oct-2024
https://dl.acm.org/doi/10.1007/978-981-97-8546-9_5
Hanaoka GKatsumata SKimura KTakemure KYamada S(2024)Tighter Adaptive IBEs and VRFs: Revisiting Waters’ Artificial AbortTheory of Cryptography10.1007/978-3-031-78020-2_5(124-155)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1007/978-3-031-78020-2_5
Tomita TShikata J(2024)Efficient Identity-Based Encryption with Tight Adaptive Anonymity from RLWEPost-Quantum Cryptography10.1007/978-3-031-62743-9_10(300-321)Online publication date: 12-Jun-2024
https://dl.acm.org/doi/10.1007/978-3-031-62743-9_10
Jia HHu YTang CWang L(2024)Towards Compact Identity-Based Encryption on Ideal LatticesTopics in Cryptology – CT-RSA 202410.1007/978-3-031-58868-6_14(354-378)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-58868-6_14
Abla P(2024)Identity-Based Encryption from LWE with More Compact Master Public KeyTopics in Cryptology – CT-RSA 202410.1007/978-3-031-58868-6_13(319-353)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-58868-6_13
Wang ZLai QLiu F(2024)Ring/Module Learning with Errors Under Linear Leakage – Hardness and ApplicationsPublic-Key Cryptography – PKC 202410.1007/978-3-031-57722-2_9(275-304)Online publication date: 15-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-57722-2_9
Fan JLu XAu M(2023)Adaptively Secure Identity-Based Encryption from Middle-Product Learning with ErrorsInformation Security and Privacy10.1007/978-3-031-35486-1_15(320-340)Online publication date: 5-Jul-2023
https://dl.acm.org/doi/10.1007/978-3-031-35486-1_15
Hoffmann CLibert BMomin CPeters TStandaert F(2023)POLKA: Towards Leakage-Resistant Post-quantum CCA-Secure Public Key EncryptionPublic-Key Cryptography – PKC 202310.1007/978-3-031-31368-4_5(114-144)Online publication date: 7-May-2023
https://dl.acm.org/doi/10.1007/978-3-031-31368-4_5
Wang XWang YWang M(2022)Lattice-Based Revocable Identity-Based Proxy Re-encryption with Re-encryption VerifiabilityWireless Algorithms, Systems, and Applications10.1007/978-3-031-19208-1_44(535-544)Online publication date: 24-Nov-2022
https://dl.acm.org/doi/10.1007/978-3-031-19208-1_44
Luo FAl-Kuwari SWang HHan W(2022)Generic Construction of Trace-and-Revoke Inner Product Functional EncryptionComputer Security – ESORICS 202210.1007/978-3-031-17140-6_13(259-282)Online publication date: 26-Sep-2022
https://dl.acm.org/doi/10.1007/978-3-031-17140-6_13
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents