×
Goyal, Rishab; Koppula, Venkata; Waters, Brent

Separating semantic and circular security for symmetric-key bit encryption from the learning with errors assumption. (English) Zbl 1415.94432

Coron, Jean-Sébastien (ed.) et al., Advances in cryptology – EUROCRYPT 2017. 36th annual international conference on the theory and applications of cryptographic techniques, Paris, France, April 30 – May 4, 2017. Proceedings. Part II. Cham: Springer. Lect. Notes Comput. Sci. 10211, 528-557 (2017).
Summary: In this work we separate private-key semantic security from 1-circular security for bit encryption using the learning with error assumption. Prior works used the less standard assumptions of multilinear maps or indistinguishability obfuscation. To achieve our results we develop new techniques for obliviously evaluating branching programs.
For the entire collection see [Zbl 1360.94006].

Cited in 12 Documents

MSC:

94A60 Cryptography
Cite Review PDF
Full Text: DOI

References:

[1] Acar, T., Belenkiy, M., Bellare, M., Cash, D.: Cryptographic agility and its relation to circular encryption. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 403–422. Springer, Heidelberg (2010). doi: 10.1007/978-3-642-13190-5_21 · Zbl 1280.94034 · doi:10.1007/978-3-642-13190-5_21
[2] Adão, P., Bana, G., Herzog, J., Scedrov, A.: Soundness and completeness of formal encryption: the cases of key cycles and partial information leakage. J. Comput. Secur. 17, 737–797 (2009) · doi:10.3233/JCS-2009-0358
[3] Alamati, N., Peikert, C.: Three’s compromised too: circular insecurity for any cycle length from (ring-)LWE. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9815, pp. 659–680. Springer, Heidelberg (2016). doi: 10.1007/978-3-662-53008-5_23 · Zbl 1391.94721 · doi:10.1007/978-3-662-53008-5_23
[4] 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). doi: 10.1007/978-3-642-30057-8_20 · Zbl 1294.94030 · doi:10.1007/978-3-642-30057-8_20
[5] Applebaum, B.: Key-dependent message security: generic amplification and completeness. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 527–546. Springer, Heidelberg (2011). doi: 10.1007/978-3-642-20465-4_29 · Zbl 1291.94048 · doi:10.1007/978-3-642-20465-4_29
[6] 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). doi: 10.1007/978-3-642-03356-8_35 · Zbl 1252.94044 · doi:10.1007/978-3-642-03356-8_35
[7] Banerjee, A., Peikert, C., Rosen, A.: Pseudorandom functions and lattices. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 719–737. Springer, Heidelberg (2012). doi: 10.1007/978-3-642-29011-4_42 · Zbl 1297.68071 · doi:10.1007/978-3-642-29011-4_42
[8] Barak, B., Haitner, I., Hofheinz, D., Ishai, Y.: Bounded key-dependent message security. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 423–444. Springer, Heidelberg (2010). doi: 10.1007/978-3-642-13190-5_22 · Zbl 1280.94038 · doi:10.1007/978-3-642-13190-5_22
[9] Barrington, D.A.: Bounded-width polynomial-size branching programs recognize exactly those languages in \[ NC^{1} \] . In: STOC 1986 (1986) · Zbl 0667.68059
[10] Bishop, A., Hohenberger, S., Waters, B.: New circular security counterexamples from decision linear and learning with errors. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9453, pp. 776–800. Springer, Heidelberg (2015). doi: 10.1007/978-3-662-48800-3_32 · Zbl 1382.94069 · doi:10.1007/978-3-662-48800-3_32
[11] Boneh, D., Halevi, S., Hamburg, M., Ostrovsky, R.: Circular-secure encryption from decision Diffie-Hellman. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 108–125. Springer, Heidelberg (2008). doi: 10.1007/978-3-540-85174-5_7 · Zbl 1183.94025 · doi:10.1007/978-3-540-85174-5_7
[12] Borodin, A., Dolev, D., Fich, F.E., Paul, W.J.: Bounds for width two branching programs. SIAM J. Comput. 15(2), 549–560 (1986) · Zbl 0589.68034 · doi:10.1137/0215040
[13] Brakerski, Z., Goldwasser, S.: Circular and leakage resilient public-key encryption under subgroup indistinguishability. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 1–20. Springer, Heidelberg (2010). doi: 10.1007/978-3-642-14623-7_1 · Zbl 1280.94042 · doi:10.1007/978-3-642-14623-7_1
[14] Brakerski, Z., Goldwasser, S., Kalai, Y.T.: Black-box circular-secure encryption beyond affine functions. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 201–218. Springer, Heidelberg (2011). doi: 10.1007/978-3-642-19571-6_13 · Zbl 1295.94028 · doi:10.1007/978-3-642-19571-6_13
[15] Brakerski, Z., Langlois, A., Peikert, C., Regev, O., Stehlé, D.: Classical hardness of learning with errors. In: STOC 2013 (2013) · Zbl 1293.68159 · doi:10.1145/2488608.2488680
[16] Camenisch, J., Lysyanskaya, A.: An efficient system for non-transferable anonymous credentials with optional anonymity revocation. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 93–118. Springer, Heidelberg (2001). doi: 10.1007/3-540-44987-6_7 · Zbl 0981.94043 · doi:10.1007/3-540-44987-6_7
[17] Cash, D., Green, M., Hohenberger, S.: New definitions and separations for circular security. In: Fischlin, M., Buchmann, J., Manulis, M. (eds.) PKC 2012. LNCS, vol. 7293, pp. 540–557. Springer, Heidelberg (2012). doi: 10.1007/978-3-642-30057-8_32 · Zbl 1300.94044 · doi:10.1007/978-3-642-30057-8_32
[18] Cheon, J.H., Han, K., Lee, C., Ryu, H., Stehlé, D.: Cryptanalysis of the multilinear map over the integers. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 3–12. Springer, Heidelberg (2015). doi: 10.1007/978-3-662-46800-5_1 · Zbl 1365.94416 · doi:10.1007/978-3-662-46800-5_1
[19] Coron, J.-S., Gentry, C., Halevi, S., Lepoint, T., Maji, H.K., Miles, E., Raykova, M., Sahai, A., Tibouchi, M.: Zeroizing without low-level zeroes: new MMAP attacks and their limitations. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 247–266. Springer, Heidelberg (2015). doi: 10.1007/978-3-662-47989-6_12 · Zbl 1375.94114 · doi:10.1007/978-3-662-47989-6_12
[20] 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, 97–139 (2008) · Zbl 1165.94326 · doi:10.1137/060651380
[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). doi: 10.1007/978-3-540-24676-3_31 · Zbl 1122.94368 · doi:10.1007/978-3-540-24676-3_31
[22] Gentry, C.: Fully homomorphic encryption using ideal lattices. In: STOC (2009) · Zbl 1304.94059 · doi:10.1145/1536414.1536440
[23] Gentry, C., Gorbunov, S., Halevi, S.: Graph-induced multilinear maps from lattices. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015. LNCS, vol. 9015, pp. 498–527. Springer, Heidelberg (2015). doi: 10.1007/978-3-662-46497-7_20 · Zbl 1315.94076 · doi:10.1007/978-3-662-46497-7_20
[24] Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: STOC, pp. 197–206 (2008) · Zbl 1231.68124 · doi:10.1145/1374376.1374407
[25] Koppula, V., Ramchen, K., Waters, B.: Separations in circular security for arbitrary length key cycles. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015. LNCS, vol. 9015, pp. 378–400. Springer, Heidelberg (2015). doi: 10.1007/978-3-662-46497-7_15 · Zbl 1319.94074 · doi:10.1007/978-3-662-46497-7_15
[26] Koppula, V., Waters, B.: Circular security separations for arbitrary length cycles from LWE. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9815, pp. 681–700. Springer, Heidelberg (2016). doi: 10.1007/978-3-662-53008-5_24 · Zbl 1391.94770 · doi:10.1007/978-3-662-53008-5_24
[27] Laud, P.: Encryption cycles and two views of cryptography. In: NORDSEC 2002 (2002)
[28] Marcedone, A., Orlandi, C.: Obfuscation \[ \Rightarrow \] (IND-CPA security \[ \nRightarrow \] circular security). In: Abdalla, M., Prisco, R. (eds.) SCN 2014. LNCS, vol. 8642, pp. 77–90. Springer, Cham (2014). doi: 10.1007/978-3-319-10879-7_5 · Zbl 1423.68155 · doi:10.1007/978-3-319-10879-7_5
[29] Marcedone, A., Pass, R., Shelat, A.: Bounded KDM security from iO and OWF. In: Zikas, V., Prisco, R. (eds.) SCN 2016. LNCS, vol. 9841, pp. 571–586. Springer, Cham (2016). doi: 10.1007/978-3-319-44618-9_30 · Zbl 1482.94054 · doi:10.1007/978-3-319-44618-9_30
[30] 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 · Zbl 1297.94090 · doi:10.1007/978-3-642-29011-4_41
[31] Micciancio, D., Regev, O.: Worst-case to average-case reductions based on Gaussian measures. SIAM J. Comput. 37(1), 267–302 (2007) · Zbl 1142.68037 · doi:10.1137/S0097539705447360
[32] Peikert, C.: Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. In: STOC 2009 (2009) · Zbl 1304.94079 · doi:10.1145/1536414.1536461
[33] Peikert, C.: A decade of lattice cryptography. Found. Trends Theor. Comput. Sci. 10, 283–424 (2016) · Zbl 1391.94788 · doi:10.1561/0400000074
[34] Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: STOC, 2005 (2005) · Zbl 1192.94106 · doi:10.1145/1060590.1060603
[35] Rothblum, R.D.: On the circular security of bit-encryption. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 579–598. Springer, Heidelberg (2013). doi: 10.1007/978-3-642-36594-2_32 · Zbl 1315.94100 · doi:10.1007/978-3-642-36594-2_32
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.