Top

Designs, Codes and Cryptography

Published in:

02-03-2021

SO-CCA secure PKE from pairing based all-but-many lossy trapdoor functions

Authors: Dingding Jia, Benoît Libert

Published in: Designs, Codes and Cryptography | Issue 5/2021

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

search-config

AI-assisted search

Off

Abstract

In a selective-opening chosen ciphertext (SO-CCA) attack on an encryption scheme, an adversary A has access to a decryption oracle, and after getting a number of ciphertexts, can then adaptively corrupt a subset of them, obtaining the plaintexts and corresponding encryption randomness. SO-CCA security requires the privacy of the remaining plaintexts being well protected. There are two flavors of SO-CCA definition: the weaker indistinguishability-based (IND) and the stronger simulation-based (SIM) ones. In this paper, we study SO-CCA secure PKE constructions from all-but-many lossy trapdoor functions (ABM-LTFs) in pairing-friendly prime order groups. Concretely,

we construct two ABM-LTFs with \(O(n/\log \lambda )\) size tags for n bits inputs and security parameter \(\lambda \), which lead to IND-SO-CCA secure PKEs with ciphertext size \(O(n/\log \lambda )\) to encrypt n bits messages. In addition, our second ABM-LTF enjoys tight security, so as the resulting PKE.
by equipping a lattice trapdoor for opening randomness, we show our ABM-LTFs are SIM-SO-CCA compatible.

previous article On the Resilience of Even-Mansour to Invariant Permutations

next article Lattice-based zero-knowledge arguments for additive and multiplicative relations

Available only for authorised users

We suppose that the tightly multi-pesudorandom MAC given in [30] can also be used here, however, the security loss of their construction is larger than that of the MAC in [42], although in the same level.

Here note that \({\mathcal {T}}\supset {\mathcal {T}}_{\mathsf {loss}}\cup {\mathcal {T}}_{\mathsf {inj}}\), there may exist a tag \(t\in {\mathcal {T}}\) but \(t\notin {\mathcal {T}}_{\mathsf {loss}}\cup {\mathcal {T}}_{\mathsf {inj}}\).

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).CrossRef

Bellare M., Dowsley R., Waters B., Yilek S.: Standard security does not imply security against selective-opening. In: Pointcheval D., Johansson T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 645–662. Springer, Heidelberg (2012).CrossRef

Bellare M., Hofheinz D., Yilek S.: Possibility and impossibility results for encryption and commitment secure under selective opening. In: Joux A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 1–35. Springer, Heidelberg (2009).CrossRef

Bellare M., Rogaway P.: Optimal asymmetric encryption. In: Santis A.D. (ed.) EUROCRYPT’94. LNCS, vol. 950, pp. 92–111. Springer, Heidelberg (1995).

Bellare M., Waters B., Yilek S.: Identity-based encryption secure against selective opening attack. In: Ishai Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 235–252. Springer, Heidelberg (2011).

Bellare M., Yilek S.: Encryption schemes secure under selective opening attack. Cryptology ePrint Archive, Report 2009/101 (2009).

Blazy O., Kiltz E., Pan J.: (Hierarchical) identity-based encryption from affine message authentication. In: Garay J.A., Gennaro R. (eds.) CRYPTO 2014, Part I. LNCS, vol. 8616, pp. 408–425. Springer, Heidelberg (2014).

Böhl F., Hofheinz D., Kraschewski D.: On definitions of selective opening security. In: Fischlin M., Buchmann J., Manulis M. (eds.) PKC 2012. LNCS, vol. 7293, pp. 522–539. Springer, Heidelberg (2012).

Boneh D., Boyen X.: Short signatures without random oracles and the SDH assumption in bilinear groups. J. Cryptol. 21(2), 149–177 (2008).MathSciNetMATHCrossRef

10.

Boyen X., Li Q.: All-but-many lossy trapdoor functions from lattices and applications. In: Katz J., Shacham H. (eds.) CRYPTO 2017, Part III. LNCS, vol. 10403, pp. 298–331. Springer, Heidelberg (2017).CrossRef

11.

Boyen X., Waters B.: Shrinking the keys of discrete-log-type lossy trapdoor functions. In: Zhou J., Yung M. (eds.) ACNS 10. LNCS, vol. 6123, pp. 35–52. Springer, Heidelberg (2010).

12.

Brakerski Z., Langlois A., Peikert C., Regev O., Stehlé D.: Classical hardness of learning with errors. In: Boneh D., Roughgarden T., Feigenbaum J. (eds.) 45th ACM STOC, pp. 575–584. ACM Press, New York (2013).

13.

Canetti R., Halevi S., Katz J.: Adaptively-secure, non-interactive public-key encryption. In: Kilian J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 150–168. Springer, Heidelberg (2005).

14.

Dodis Y., Reyzin L., Smith A.: Fuzzy extractors: how to generate strong keys from biometrics and other noisy data. In: Cachin C., Camenisch J. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 523–540. Springer, Heidelberg (2004).CrossRef

15.

Dwork C., Naor M., Reingold O., Stockmeyer L.J.: Magic functions. In: 40th FOCS, pp. 523–534. IEEE Computer Society Press (1999).

16.

Escala A., Herold G., Kiltz E., Ràfols C., Villar J.: An algebraic framework for Diffie-Hellman assumptions. In: Canetti R., Garay J.A. (eds.) CRYPTO 2013, Part II. LNCS, vol. 8043, pp. 129–147. Springer, Heidelberg (2013).CrossRef

17.

Fehr S., Hofheinz D., Kiltz E., Wee H.: Encryption schemes secure against chosen-ciphertext selective opening attacks. In: Gilbert H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 381–402. Springer, Heidelberg (2010).CrossRef

18.

Fujisaki E.: All-but-many encryption—a new framework for fully-equipped UC commitments. In: Sarkar P., Iwata T. (eds.) ASIACRYPT 2014, Part II. LNCS, vol. 8874, pp. 426–447. Springer, Heidelberg (2014).

19.

Gentry C., Sahai A., Waters B.: Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based. In: Canetti R., Garay J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 75–92. Springer, Heidelberg (2013).CrossRef

20.

Goldwasser S., Micali S.: Probabilistic encryption. J. Comput. Syst. Sci. 28, 270–299 (1984).MathSciNetMATHCrossRef

21.

Hara K., Kitagawa F., Matsuda T., Hanaoka G., Tanaka K.: Simulation-based receiver selective opening CCA secure PKE from standard computational assumptions. In: Catalano D., De Prisco R. (eds.) SCN 18. LNCS, vol. 11035, pp. 140–159. Springer, Heidelberg (2018).

22.

Hazay C., Patra A., Warinschi B.: Selective opening security for receivers. In: Iwata T., Cheon J.H. (eds.) ASIACRYPT 2015, Part I. LNCS, vol. 9452, pp. 443–469. Springer, Heidelberg (2015).

23.

Hemenway B., Libert B., Ostrovsky R., Vergnaud D.: Lossy encryption: constructions from general assumptions and efficient selective opening chosen ciphertext security. In: Lee D.H., Wang X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 70–88. Springer, Heidelberg (2011).CrossRef

24.

Heuer F., Jager T., Kiltz E., Schäge S.: On the selective opening security of practical public-key encryption schemes. In: Katz J. (ed.) PKC 2015. LNCS, vol. 9020, pp. 27–51. Springer, Heidelberg (2015).

25.

Heuer F., Poettering B.: Selective opening security from simulatable data encapsulation. In: Cheon J.H., Takagi T. (eds.) ASIACRYPT 2016, Part II. LNCS, vol. 10032, pp. 248–277. Springer, Heidelberg (2016).

26.

Hoang V.T., Katz J., O’Neill A., Zaheri M.: Selective-opening security in the presence of randomness failures. In: Cheon J.H., Takagi T. (eds.) ASIACRYPT 2016, Part II. LNCS, vol. 10032, pp. 278–306. Springer, Heidelberg (2016).

27.

Hofheinz D.: All-but-many lossy trapdoor functions. In: Pointcheval D., Johansson T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 209–227. Springer, Heidelberg (2012).CrossRef

28.

Hofheinz D.: Circular chosen-ciphertext security with compact ciphertexts. In: Johansson T., Nguyen P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 520–536. Springer, Heidelberg (2013).CrossRef

29.

Hofheinz D., Jager T., Rupp A.: Public-key encryption with simulation-based selective-opening security and compact ciphertexts. In: Hirt M., Smith A.D. (eds.) TCC 2016-B, Part II. LNCS, vol. 9986, pp. 146–168. Springer, Heidelberg (2016).

30.

Hofheinz D., Jia D., Pan J.: Identity-based encryption tightly secure under chosen-ciphertext attacks. In: Peyrin T., Galbraith S. (eds.) ASIACRYPT 2018, Part II. LNCS, vol. 11273, pp. 190–220. Springer, Heidelberg (2018).

31.

Hofheinz D., Kiltz E.: Programmable hash functions and their applications. In: Wagner D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 21–38. Springer, Heidelberg (2008).CrossRef

32.

Hofheinz D., Rao V., Wichs D.: Standard security does not imply indistinguishability under selective opening. In: Hirt M., Smith A.D. (eds.) TCC 2016-B, Part II. LNCS, vol. 9986, pp. 121–145. Springer, Heidelberg (2016).

33.

Huang Z., Lai J., Chen W., Au M.H., Peng Z., Li J.: Simulation-based selective opening security for receivers under chosen-ciphertext attacks. Des. Codes Cryptogr. 87(6), 1345–1371 (2019).MathSciNetMATHCrossRef

34.

Huang Z., Liu S., Qin B.: Sender-equivocable encryption schemes secure against chosen-ciphertext attacks revisited. In: Kurosawa K., Hanaoka G. (eds.) PKC 2013. LNCS, vol. 7778, pp. 369–385. Springer, Heidelberg (2013).

35.

Jarecki S., Lysyanskaya A.: Adaptively secure threshold cryptography: introducing concurrency, removing erasures. In: Preneel B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 221–242. Springer, Heidelberg (2000).CrossRef

36.

Jia D., Lu X., Li B.: Receiver selective opening security from indistinguishability obfuscation. In: Dunkelman O., Sanadhya S.K. (eds.) INDOCRYPT 2016. LNCS, vol. 10095, pp. 393–410. Springer, Heidelberg (2016).CrossRef

37.

Jia D., Lu X., Li B.: Constructions secure against receiver selective opening and chosen ciphertext attacks. In: Handschuh H. (ed.) CT-RSA 2017. LNCS, vol. 10159, pp. 417–431. Springer, Heidelberg (2017).

38.

Krawczyk H., Rabin T.: Chameleon signatures. In: NDSS 2000. The Internet Society (2000).

39.

Kunz-Jacques S., Pointcheval D.: About the security of MTI/C0 and MQV. In: Prisco R.D., Yung M. (eds.) SCN 06. LNCS, vol. 4116, pp. 156–172. Springer, Heidelberg (2006).

40.

Lai J., Deng R.H., Liu S., Weng J., Zhao Y.: Identity-based encryption secure against selective opening chosen-ciphertext attack. In: Nguyen P.Q., Oswald E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 77–92. Springer, Heidelberg (2014).CrossRef

41.

Lewko A.B., Sahai A., Waters B.: Revocation systems with very small private keys. In: 2010 IEEE Symposium on Security and Privacy, pp. 273–285. IEEE Computer Society Press (2010).

42.

Libert B., Qian C.: Lossy algebraic filters with short tags. In: Lin D., Sako K. (eds.) PKC 2019, Part I. LNCS, vol. 11442, pp. 34–65. Springer, Heidelberg (2019).

43.

Libert B., Sakzad A., Stehlé D., Steinfeld R.: All-but-many lossy trapdoor functions and selective opening chosen-ciphertext security from LWE. In: Katz J., Shacham H. (eds.) CRYPTO 2017, Part III. LNCS, vol. 10403, pp. 332–364. Springer, Heidelberg (2017). Cryptology ePrint Archive, Report 2017/876 (2017).CrossRef

44.

Liu S., Paterson K.G.: Simulation-based selective opening CCA security for PKE from key encapsulation mechanisms. In: Katz J. (ed.) PKC 2015. LNCS, vol. 9020, pp. 3–26. Springer, Heidelberg (2015).

45.

Lyu L., Liu S., Han S., Gu D.: Tightly SIM-SO-CCA secure public key encryption from standard assumptions. In: Abdalla M., Dahab R. (eds.) PKC 2018, Part I. LNCS, vol. 10769, pp. 62–92. Springer, Heidelberg (2018).

46.

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).CrossRef

47.

Micciancio D., Regev O.: Worst-case to average-case reductions based on Gaussian measures. In: 45th FOCS, pp. 372–381. IEEE Computer Society Press (2004).

48.

Paillier P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern J. (ed.) EUROCRYPT’99. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999).

49.

Peikert C., Waters B.: Lossy trapdoor functions and their applications. In: Ladner R.E., Dwork C. (eds.) 40th ACM STOC, pp. 187–196. ACM Press, New York (2008).

50.

Regev O.: On lattices, learning with errors, random linear codes, and cryptography. In: Gabow H.N., Fagin R. (eds.) 37th ACM STOC, pp. 84–93. ACM Press, New York (2005).

51.

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

Title: SO-CCA secure PKE from pairing based all-but-many lossy trapdoor functions
Authors: Dingding Jia
Benoît Libert
Publication date: 02-03-2021
Publisher: Springer US
Published in: Designs, Codes and Cryptography / Issue 5/2021
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-021-00849-9

Springer Professional

SO-CCA secure PKE from pairing based all-but-many lossy trapdoor functions

Abstract

Premium Partner

Springer Professional

Abstract

Please log in to get access to your license.

Other articles of this Issue 5/2021

A note on Assmus–Mattson type theorems

Near-MDS codes from elliptic curves

Self-dual codes over and Jacobi forms over a totally real subfield of

Constructions of doubly resolvable Steiner quadruple systems

On the Resilience of Even-Mansour to Invariant Permutations

Design-theoretic analogies between codes, lattices, and vertex operator algebras

Premium Partner