×

zbMATH — the first resource for mathematics

Concurrently secure identification schemes based on the worst-case hardness of lattice problems. (English) Zbl 1206.94076
Pieprzyk, Josef (ed.), Advances in cryptology – ASIACRYPT 2008. 14th international conference on the theory and application of cryptology and information security, Melbourne, Australia, December 7–11, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-89254-0/pbk). Lecture Notes in Computer Science 5350, 372-389 (2008).
Summary: In this paper, we show that two variants of J. Stern’s identification scheme [J. Stern, “A new paradigm for public key identification”, IEEE Trans. Inf. Theory 42, No. 6, Pt. 1, 749–765 (1996; Zbl 0944.94008)] are provably secure against concurrent attack under the assumptions on the worst-case hardness of lattice problems. These assumptions are weaker than those for the previous lattice-based identification schemes of D. Micciancio and S. P. Vadhan [“Statistical zero-knowledge proofs with efficient provers: lattice problems and more”, Lect. Notes Comput. Sci. 2729, 282–298 (2003; Zbl 1122.68448)] and of V. Lyubashevsky [“Lattice-based identification schemes secure under active attacks”, Lect. Notes Comput. Sci. 4939, 162–179 (2008; Zbl 1162.94388)]. We also construct efficient ad hoc anonymous identification schemes based on the lattice problems by modifying the variants.
For the entire collection see [Zbl 1155.94008].

MSC:
94A60 Cryptography
94A62 Authentication, digital signatures and secret sharing
Software:
SWIFFT
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ajtai, M.: Generating hard instances of lattice problems (extended abstract). In: STOC 1996, pp. 99–108 (1996) · Zbl 0921.11071 · doi:10.1145/237814.237838
[2] Ajtai, M., Dwork, C.: A public-key cryptosystem with worst-case/average-case equivalence. In: STOC 1997, pp. 284–293 (1997) · Zbl 0962.68055 · doi:10.1145/258533.258604
[3] Bellare, M., Palacio, A.: GQ and Schnorr identification schemes: Proofs of security against impersonation under active and concurrent attacks. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 162–177. Springer, Heidelberg (2002) · Zbl 1026.94521 · doi:10.1007/3-540-45708-9_11
[4] Damgård, I.B., Pedersen, T.P., Pfizmann, B.: On the existence of statistically hiding bit commitment schemes and fail-stop signatures. Journal of Cryptology 10(3), 163–194 (1997) · Zbl 0899.94011 · doi:10.1007/s001459900026
[5] Damgård, I.B., Pedersen, T.P., Pfizmann, B.: Statistical Secrecy and Multibit Commitments. IEEE Transactions on Information Theory 44(3), 1143–1151 (1998) · Zbl 0906.94016 · doi:10.1109/18.669255
[6] De Santis, A., Di Crescenzo, G., Persiano, G., Yung, M.: On monotone formula closure of SZK. In: FOCS 1994, pp. 454–465 (1994) · doi:10.1109/SFCS.1994.365745
[7] Dodis, Y., Kiayias, A., Nicolosi, A., Shoup, V.: Anonymous identification in ad hoc groups. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 609–626. Springer, Heidelberg (2004) · Zbl 1122.94414 · doi:10.1007/978-3-540-24676-3_36
[8] Feige, U., Shamir, A.: Witness indistinguishable and witness hiding protocols. In: STOC 1990, pp. 416–426 (1990) · doi:10.1145/100216.100272
[9] Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: STOC 2008, pp. 197–206 (2008) · Zbl 1231.68124 · doi:10.1145/1374376.1374407
[10] Goldreich, O.: Foundations of Cryptography: Volume I – Basic Tools. Cambridge University Press, Cambridge (2001) · Zbl 1007.94016 · doi:10.1017/CBO9780511546891
[11] Goldreich, O., Goldwasser, S., Halevi, S.: Collision-free hashing from lattice problems. ECCC 3(42) (1996) · Zbl 1343.94055
[12] Halevi, S., Micali, S.: Practical and provably-secure commitment scheme from collision-free hashing. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 201–215. Springer, Heidelberg (1996) · Zbl 1329.94061 · doi:10.1007/3-540-68697-5_16
[13] Katz, J., Lindell, Y.: Introduction to Modern Cryptography. Chapman & Hall/CRC (2007) · Zbl 1143.94001
[14] Lyubashevsky, V.: Lattice-based identification schemes secure under active attacks. In: Cramer, R. (ed.) PKC 2008. LNCS, vol. 4939, pp. 162–179. Springer, Heidelberg (2008) · Zbl 1162.94388 · doi:10.1007/978-3-540-78440-1_10
[15] Lyubashevsky, V., Micciancio, D.: Generalized compact knapsacks are collision resistant. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006, Part II. LNCS, vol. 4052, pp. 144–155. Springer, Heidelberg (2006) · Zbl 1133.68353 · doi:10.1007/11787006_13
[16] Lyubashevsky, V., Micciancio, D., Peikert, C., Rosen, A.: SWIFFT: A modest proposal for FFT hashing. In: Nyberg, K. (ed.) FSE 2008. LNCS, vol. 5086, pp. 54–72. Springer, Heidelberg (2008) · Zbl 1154.68403 · doi:10.1007/978-3-540-71039-4_4
[17] Micciancio, D.: Generalized compact knapsacks, cyclic lattices, and efficient one-way functions. Computational Complexity 16, 365–411 (2007) · Zbl 1133.68024 · doi:10.1007/s00037-007-0234-9
[18] Micciancio, D., Goldwasser, S.: Complexity of Lattice Problems: a cryptographic perspective. Kluwer Academic Publishers, Dordrecht (2002) · Zbl 1140.94010 · doi:10.1007/978-1-4615-0897-7
[19] Micciancio, D., Regev, O.: Worst-case to average-case reductions based on Gaussian measures. SIAM Journal on Computing 37(1), 267–302 (2007) · Zbl 1142.68037 · doi:10.1137/S0097539705447360
[20] Micciancio, D., Vadhan, S.: Statistical zero-knowledge proofs with efficient provers: Lattice problems and more. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 282–298. Springer, Heidelberg (2003) · Zbl 1122.68448 · doi:10.1007/978-3-540-45146-4_17
[21] Ohta, K., Okamoto, T.: On concrete security treatment of signatures derived from identification. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 354–369. Springer, Heidelberg (1998) · Zbl 0931.94035 · doi:10.1007/BFb0055741
[22] Peikert, C.: Limits on the hardness of lattice problems in l p norms. Computational Complexity 17(2), 300–351 (2008) · Zbl 1149.68039 · doi:10.1007/s00037-008-0251-3
[23] Peikert, C., Rosen, A.: Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 145–166. Springer, Heidelberg (2006) · Zbl 1112.94020 · doi:10.1007/11681878_8
[24] Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: STOC 2005, pp. 84–93 (2005) · Zbl 1192.94106 · doi:10.1145/1060590.1060603
[25] Shamir, A.: A polynomial-time algorithm for breaking the basic Merkle-Hellman cryptosystem. IEEE Transactions on Information Theory 30(5), 699–704 (1984) · Zbl 0552.94007 · doi:10.1109/TIT.1984.1056964
[26] Stern, J.: A new paradigm for public key identification. IEEE Transactions on Information Theory 42(6), 749–765 (1996) · Zbl 0944.94008 · doi:10.1109/18.556672
[27] Wu, Q., Chen, X., Wang, C., Wang, Y.: Shared-key signature and its application to anonymous authentication in ad hoc group. In: Zhang, K., Zheng, Y. (eds.) ISC 2004. LNCS, vol. 3225, pp. 330–341. Springer, Heidelberg (2004) · Zbl 1109.68492 · doi:10.1007/978-3-540-30144-8_28
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.