×

Deniable attribute based encryption for branching programs from LWE. (English) Zbl 1400.94111

Hirt, Martin (ed.) et al., Theory of cryptography. 14th international conference, TCC 2016-B, Beijing, China, October 31 – November 3, 2016, Proceedings. Part II. Berlin: Springer (ISBN 978-3-662-53643-8/pbk; 978-3-662-53644-5/ebook). Lecture Notes in Computer Science 9986, 299-329 (2016).
Summary: Deniable encryption [R. Canetti et al., Crypto 1997, Lect. Notes Comput. Sci. 1294, 90–104 (1997; Zbl 0882.94019)] is an intriguing primitive that provides a security guarantee against not only eavesdropping attacks as required by semantic security, but also stronger coercion attacks performed after the fact. The concept of deniability has later demonstrated useful and powerful in many other contexts, such as leakage resilience, adaptive security of protocols, and security against selective opening attacks. Despite its conceptual usefulness, our understanding of how to construct deniable primitives under standard assumptions is restricted.{ } In particular from standard lattice assumptions, i.e. Learning with Errors (LWE), we have only flexibly and non-negligible advantage deniable public-key encryption schemes, whereas with the much stronger assumption of indistinguishable obfuscation, we can obtain at least fully sender-deniable PKE and computation. How to achieve deniability for other more advanced encryption schemes under standard assumptions remains an interesting open question.{ } In this work, we construct a flexibly bi-deniable attribute-based encryption (ABE) scheme for all polynomial-size branching programs from LWE. Our techniques involve new ways of manipulating Gaussian noise that may be of independent interest, and lead to a significantly sharper analysis of noise growth in dual Regev type encryption schemes. We hope these ideas give insight into achieving deniability and related properties for further, advanced cryptographic systems from lattice assumptions.
For the entire collection see [Zbl 1349.94008].

MSC:

94A60 Cryptography

Citations:

Zbl 0882.94019
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] 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) · Zbl 1227.94022 · doi:10.1007/978-3-642-13190-5_28
[2] Alperin-Sheriff, J., Peikert, C.: Circular and KDM security for identity-based encryption. In: Fischlin, M., Buchmann, J., Manulis, M. (eds.) PKC 2012. LNCS, vol. 7293, pp. 334–352. Springer, Heidelberg (2012) · Zbl 1294.94030 · doi:10.1007/978-3-642-30057-8_20
[3] Alperin-Sheriff, J., Peikert, C.: Faster bootstrapping with polynomial error. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part I. LNCS, vol. 8616, pp. 297–314. Springer, Heidelberg (2014) · Zbl 1336.94034 · doi:10.1007/978-3-662-44371-2_17
[4] Ananth, P., Brakerski, Z., Segev, G., Vaikuntanathan, V.: From selective to adaptive security in functional encryption. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 657–677. Springer, Heidelberg (2015) · Zbl 1351.94021 · doi:10.1007/978-3-662-48000-7_32
[5] Apon, D., Fan, X., Liu, F.-H.: Bi-deniable inner product encryption from LWE. IACR Cryptology ePrint Archive, 2015:993 (2015)
[6] Barrington, D.A.M.: Bounded-width polynomial-size branching programs recognize exactly those languages in nc \[ {^1} \] 1 . J. Comput. Syst. Sci. 38(1), 150–164 (1989) · Zbl 0667.68059 · doi:10.1016/0022-0000(89)90037-8
[7] 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) · Zbl 1239.94033 · doi:10.1007/978-3-642-01001-9_1
[8] Bendlin, R., Nielsen, J.B., Nordholt, P.S., Orlandi, C.: Lower and upper bounds for deniable public-key encryption. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 125–142. Springer, Heidelberg (2011) · Zbl 1227.94029 · doi:10.1007/978-3-642-25385-0_7
[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) · Zbl 1327.94035 · doi:10.1007/978-3-642-55220-5_30
[10] Boneh, D., Lewi, K., David, J.W.: Constraining pseudorandom functions privately. IACR Cryptology ePrint Archive 2015, 1167 (2015) · Zbl 1400.94124
[11] Boneh, D., Roughgarden, T., Feigenbaum, J. (eds.): 45th ACM STOC. ACM Press, June 2013
[12] Boneh, D., Sahai, A., Waters, B.: Functional encryption: definitions and challenges. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 253–273. Springer, Heidelberg (2011) · Zbl 1295.94027 · doi:10.1007/978-3-642-19571-6_16
[13] Brakerski, Z., Langlois, A., Peikert, C., Regev, O., Stehlé, D.: Classical hardness of learning with errors. In: Boneh et al. [11], pp. 575–584 (2013) · Zbl 1293.68159 · doi:10.1145/2488608.2488680
[14] Canetti, R., Dwork, C., Naor, M., Ostrovsky, R.: Deniable encryption. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 90–104. Springer, Heidelberg (1997) · Zbl 0882.94019 · doi:10.1007/BFb0052229
[15] Canetti, R., Feige, U., Goldreich, O., Naor, M.: Adaptively secure multi-party computation. In: 28th ACM STOC, pp. 639–648. ACM Press, May 1996 · Zbl 0922.68048 · doi:10.1145/237814.238015
[16] Canetti, R., Goldwasser, S., Poburinnaya, O.: Adaptively secure two-party computation from indistinguishability obfuscation. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015, Part II. LNCS, vol. 9015, pp. 557–585. Springer, Heidelberg (2015) · Zbl 1382.94077 · doi:10.1007/978-3-662-46497-7_22
[17] Angelo De Caro, Vincenzo Iovino, and Adam O’Neill. Deniable functional encryption. In Public-Key Cryptography - PKC –19th IACR International Conference on Practice and Theory in Public-Key Cryptography, Taipei, Taiwan, March 6–9, Proceedings, Part I, pp. 196–222, (2016) · Zbl 1388.94049
[18] 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) · Zbl 1280.94043 · doi:10.1007/978-3-642-13190-5_27
[19] Dachman-Soled, D., Katz, J., Rao, V.: Adaptively secure, universally composable, multiparty computation in constant rounds. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015, Part II. LNCS, vol. 9015, pp. 586–613. Springer, Heidelberg (2015) · Zbl 1382.94086 · doi:10.1007/978-3-662-46497-7_23
[20] Dachman-Soled, D., Liu, F.-H., Zhou, H.-S.: Leakage-resilient circuits revisited - optimal number of computing components without leak-free hardware, pp. 131–158 (2015) · Zbl 1326.94084
[21] Dodis, Y., Reyzin, L., Smith, A.: Fuzzy extractors: how to generate strong keys from biometrics and other noisy data. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 523–540. Springer, Heidelberg (2004) · Zbl 1122.94368 · doi:10.1007/978-3-540-24676-3_31
[22] Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: 54th FOCS, pp. 40–49. IEEE Computer Society Press, October 2013 · Zbl 1348.94048 · doi:10.1109/FOCS.2013.13
[23] Garg, S., Polychroniadou, A.: Two-round adaptively secure MPC from indistinguishability obfuscation. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015, Part II. LNCS, vol. 9015, pp. 614–637. Springer, Heidelberg (2015) · Zbl 1382.94108 · doi:10.1007/978-3-662-46497-7_24
[24] Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: 40th ACM STOC, pp. 197–206. ACM Press, May 2008 · Zbl 1231.68124 · doi:10.1145/1374376.1374407
[25] 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) · Zbl 1310.94148 · doi:10.1007/978-3-642-40041-4_5
[26] Gilbert, H. (ed.): EUROCRYPT 2010. LNCS, vol. 6110. Springer, Heidelberg (2010)
[27] Goldwasser, S., Kalai, Y.T., Popa, R.A., Vaikuntanathan, V., Zeldovich, N.: Reusable garbled circuits and succinct functional encryption. In: Boneh et al. [11], pp. 555–564 (2013) · Zbl 1293.68108 · doi:10.1145/2488608.2488678
[28] Gorbunov, S., Vaikuntanathan, V., Wee, H.: Attribute-based encryption for circuits. In: Boneh et al. [11], pp. 545–554 (2013) · Zbl 1293.68109 · doi:10.1145/2488608.2488677
[29] Gorbunov, S., Vaikuntanathan, V., Wee, H.: Predicate encryption for circuits from LWE. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 503–523. Springer, Heidelberg (2015) · Zbl 1369.94538 · doi:10.1007/978-3-662-48000-7_25
[30] Gorbunov, S., Vinayagamurthy, D.: Riding on asymmetry: efficient ABE for branching programs. In: Iwata, T., et al. (eds.) ASIACRYPT 2015. LNCS, vol. 9452, pp. 550–574. Springer, Heidelberg (2015). doi: 10.1007/978-3-662-48797-6_23 · Zbl 1380.94094 · doi:10.1007/978-3-662-48797-6_23
[31] Goyal, V., Pandey, O., Sahai, A., Waters, B.: Attribute-based encryption for fine-grained access control of encrypted data. In: ACM CCS 2006, pp. 89–98. ACM Press, October/November 2006. Available as Cryptology ePrint Archive Report 2006/309 · doi:10.1145/1180405.1180418
[32] Katz, J., Thiruvengadam, A., Zhou, H.-S.: Feasibility and infeasibility of adaptively secure fully homomorphic encryption. In: Kurosawa, K., Hanaoka, G. (eds.) PKC 2013. LNCS, vol. 7778, pp. 14–31. Springer, Heidelberg (2013) · Zbl 1314.94077 · doi:10.1007/978-3-642-36362-7_2
[33] Micciancio, D., Mol, P.: Pseudorandom knapsacks and the sample complexity of LWE search-to-decision reductions. In: Rogaway [37], pp. 465–484 · Zbl 1287.94085 · doi:10.1007/978-3-642-22792-9_26
[34] 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) · Zbl 1297.94090 · doi:10.1007/978-3-642-29011-4_41
[35] O’Neill, A., Peikert, C., Waters, B.: Bi-deniable public-key encryption. In: Rogaway [37], pp. 525–542 (2011) · Zbl 1290.94113 · doi:10.1007/978-3-642-22792-9_30
[36] Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: 37th ACM STOC, pp. 84–93. ACM Press, May 2005 · Zbl 1192.94106 · doi:10.1145/1060590.1060603
[37] Rogaway, P. (ed.): CRYPTO 2011. LNCS, vol. 6841. Springer, Heidelberg (2011) · Zbl 1219.94002
[38] Sahai, A., Waters, B.: How to use indistinguishability obfuscation: deniable encryption, and more. In: Shmoys, D.B. (eds.) 46th ACM STOC, pp. 475–484. ACM Press, May/June 2014 · Zbl 1315.94102 · doi:10.1145/2591796.2591825
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.