Abstract
Xie et al. (SCN 2012) proposed the first deterministic identity-based encryption (DIBE) scheme with an adaptive security in the auxiliary-input setting, under the learning with errors (LWE) assumption. However, the master public key consists of \(\mathcal {O}(\lambda )\) number of basic matrices.
-
In this paper, we consider to construct adaptively secure DIBE schemes from partitioning functions (IACR’17). By instantiating the DIBE construction with two partitioning functions, we get two DIBE schemes in which the master public key consists of \(\mathcal {O}(\log ^3 \lambda )\) (respectively, \(\mathcal {O}(\log ^2 \lambda )\)) number of basic matrices in the first (respectively, the second) DIBE scheme.
-
We also change the identity-based encryption (IBE) scheme of Yamada16 (Eurocrypt’16) to construct DIBE scheme with the same security from the LWE problem. And the master public key consists of \(\mathcal {O}(\lambda ^{1/d})\) number of basic matrices, where \(d\ge 2\) is a flexible integer.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Agrawal, S., Boneh, D., Boyen, X.: Efficient lattice (H)IBE in the standard model. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 553–572. Springer, Heidelberg (2010). doi:10.1007/978-3-642-13190-5_28
Ajtai, M.: Generating hard instances of the short basis problem. In: Wiedermann, J., Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol. 1644, pp. 1–9. Springer, Heidelberg (1999). doi:10.1007/3-540-48523-6_1
Alwen, J., Peikert, C.: Generating shorter bases for hard random lattices. In: STACS 2009, pp. 75–86 (2009)
Bellare, M., Kiltz, E., Peikert, C., Waters, B.: Identity-based (lossy) trapdoor functions and applications. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 228–245. Springer, Heidelberg (2012). doi:10.1007/978-3-642-29011-4_15
Bogdanov, A., Guo, S., Masny, D., Richelson, S., Rosen, A.: On the hardness of learning with rounding over small modulus. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9562, pp. 209–224. Springer, Heidelberg (2016). doi:10.1007/978-3-662-49096-9_9
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). doi:10.1007/978-3-642-13190-5_27
Dodis, Y., Ostrovsky, R., Reyzin, L., Smith, A.D.: Fuzzy extractors: how to generate strong keys from biometrics and other noisy data. SIAM J. Comput. 38(1), 97–139 (2008)
Escala, A., Herranz, J., Libert, B., Ràfols, C.: Identity-based lossy trapdoor functions: new definitions, hierarchical extensions, and implications. In: Krawczyk, H. (ed.) PKC 2014. LNCS, vol. 8383, pp. 239–256. Springer, Heidelberg (2014). doi:10.1007/978-3-642-54631-0_14
Fang, F., Li, B., Xianhui, L., Liu, Y., Jia, D., Xue, H.: (Deterministic) Hierarchical identity-based encryption from learning with rounding over small modulus. In: AsiaCCS 2016, pp. 907–912 (2016)
Goldwasser, S., Kalai, Y.T., Peikert, C., Vaikuntanathan, V.: Robustness of the learning with errors assumption. In: ICS 2010, pp. 230–240 (2010)
Jager, T.: Verifiable random functions from weaker assumptions. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015. LNCS, vol. 9015, pp. 121–143. Springer, Heidelberg (2015). doi:10.1007/978-3-662-46497-7_5
Katsumata, S., Yamada, S.: Partitioning via non-linear polynomial functions: more compact ibes from ideal lattices and bilinear maps. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10032, pp. 682–712. Springer, Heidelberg (2016). doi:10.1007/978-3-662-53890-6_23
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). doi:10.1007/978-3-642-29011-4_41
Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: STOC 2005, pp. 84–93 (2005)
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). doi:10.1007/3-540-39568-7_5
Xie, X., Xue, R., Zhang, R.: Deterministic public key encryption and identity-based encryption from lattices in the auxiliary-input setting. In: Visconti, I., Prisco, R. (eds.) SCN 2012. LNCS, vol. 7485, pp. 1–18. Springer, Heidelberg (2012). doi:10.1007/978-3-642-32928-9_1
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). doi:10.1007/978-3-662-49896-5_2
Yamada, S.: Asymptotically compact adaptively secure lattice ibes and verifiable random functions via generalized partitioning techniques. Cryptology ePrint Archive, Report 2017/096 (2017). http://eprint.iacr.org/2017/096
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). doi:10.1007/978-3-662-53015-3_11
Acknowledgments
We thank the anonymous IWSEC’2017 reviewers for their helpful comments. This work is supported by the Foundation of Science and Technology on Communication Security Laboratory (9140C110206150C11049) and the National Nature Science Foundation of China (No.61379137, No.61502480, No.61572495, No.61602473).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
A Appendix
A Appendix
Homomorphic Computation. In [17], Yamada introduced the following function \(\textsf {PubEval}_{d}:(\mathbb {Z}_{q}^{n\times m})^d\rightarrow \mathbb {Z}_{q}^{n\times m}\) which takes a set of matrices \(\mathbf {B}_{1},\cdots ,\mathbf {B}_{d}\) as inputs and outputs a matrix in \(\mathbb {Z}_{q}^{n\times m}\).
In Sect. 3.2, in order to prove Eq. (1), we will use Lemma 28 in the full version of the work [1], which is described as follows.
Lemma 5
([1]). Let \(I^{*}\) be a \(Q+1\)-ID tuple \(\{id^{*},\{id_{j}\}_{j\in [Q]}\}\) denoted the challenge ID along with the queried ID’s, and \(\eta (I^{*})\) define the probability that an abort does not happen in \(\mathbf {Game_{2}}\). Let \(\gamma _{\mathrm {max}}=\mathsf {max}~\gamma (I^{*})\) and \(\gamma _{\mathrm {min}}=\mathsf {min}~\gamma (I^{*})\). For \(i=1,2\), we set \(X_{i}\) be the event that \(\widehat{\mathsf {coin}}=\mathsf {coin}\) at the end of \(\mathbf {Game_{i}}\). Then,
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Zhang, D., Fang, F., Li, B., Wang, X. (2017). Deterministic Identity-Based Encryption from Lattices with More Compact Public Parameters. In: Obana, S., Chida, K. (eds) Advances in Information and Computer Security. IWSEC 2017. Lecture Notes in Computer Science(), vol 10418. Springer, Cham. https://doi.org/10.1007/978-3-319-64200-0_13
Download citation
DOI: https://doi.org/10.1007/978-3-319-64200-0_13
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-64199-7
Online ISBN: 978-3-319-64200-0
eBook Packages: Computer ScienceComputer Science (R0)