nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Proof of a Shuffle for Lattice-Based Cryptography

verfasst von : Nuria Costa, Ramiro Martínez, Paz Morillo

Erschienen in: Secure IT Systems

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this paper we present the first proof of a shuffle for lattice-based cryptography which can be used to build a universally verifiable mix-net capable of mixing votes encrypted with a post-quantum algorithm, thus achieving long-term privacy. Universal verifiability is achieved by means of the publication of a non-interactive zero knowledge proof of a shuffle generated by each mix-node which can be verified by any observer. This published data guarantees long-term privacy since its security is based on perfectly hiding commitments and also on the hardness of solving the Ring Learning With Errors (RLWE) problem, that is widely believed to be quantum resistant.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Generating Functionally Equivalent Programs Having Non-isomorphic Control-Flow Graphs

Nächstes Kapitel An Analysis of Bitcoin Laundry Services

Abe, M.: Mix-networks on permutation networks. In: Lam, K.-Y., Okamoto, E., Xing, C. (eds.) ASIACRYPT 1999. LNCS, vol. 1716, pp. 258–273. Springer, Heidelberg (1999). doi:10.1007/978-3-540-48000-6_21 CrossRef

Adida, B., Wikström, D.: How to shuffle in public. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 555–574. Springer, Heidelberg (2007). doi:10.1007/978-3-540-70936-7_30 CrossRef

Adida, B., Wikström, D.: Offline/Online mixing. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 484–495. Springer, Heidelberg (2007). doi:10.1007/978-3-540-73420-8_43 CrossRef

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 CrossRef

Benhamouda, F., Krenn, S., Lyubashevsky, V., Pietrzak, K.: Efficient zero-knowledge proofs for commitments from learning with errors over rings. In: Pernul, G., Ryan, P.Y.A., Weippl, E. (eds.) ESORICS 2015. LNCS, vol. 9326, pp. 305–325. Springer, Cham (2015). doi:10.1007/978-3-319-24174-6_16 CrossRef

Buchmann, J., Demirel, D., Graaf, J.: Towards a publicly-verifiable mix-net providing everlasting privacy. In: Sadeghi, A.-R. (ed.) FC 2013. LNCS, vol. 7859, pp. 197–204. Springer, Heidelberg (2013). doi:10.1007/978-3-642-39884-1_16 CrossRef

Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, FOCS 2001, Washington, USA, pp. 136–145. IEEE Computer Society (2001)

Chaum, D.L.: Untraceable electronic mail, return addresses, and digital pseudonyms. Commun. ACM 24(2), 84–90 (1981)CrossRef

Chillotti, I., Gama, N., Georgieva, M., Izabachène, M.: A homomorphic LWE based E-voting scheme. In: Takagi, T. (ed.) PQCrypto 2016. LNCS, vol. 9606, pp. 245–265. Springer, Cham (2016). doi:10.1007/978-3-319-29360-8_16 CrossRef

10.

Costa, N., Martínez, R., Morillo, P.: Proof of a shuffle for lattice-based cryptography. IACR Cryptology ePrint Archive (2017)

11.

Cramer, R., Gennaro, R., Schoenmakers, B.: A secure and optimally efficient multi-authority election scheme. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 103–118. Springer, Heidelberg (1997). doi:10.1007/3-540-69053-0_9 CrossRef

12.

Damgard, I.: On \(\sigma \)-protocols. Lecture on Cryptologic Protocol Theory, Faculty of Science, University of Aarhus (2010)

13.

Demirel, D., Henning, M., van de Graaf, J., Ryan, P.Y.A., Buchmann, J.: Prêt à voter providing everlasting privacy. In: Heather, J., Schneider, S., Teague, V. (eds.) Vote-ID 2013. LNCS, vol. 7985, pp. 156–175. Springer, Heidelberg (2013). doi:10.1007/978-3-642-39185-9_10 CrossRef

14.

Fauzi, P., Lipmaa, H.: Efficient culpably sound NIZK shuffle argument without random oracles. In: Sako, K. (ed.) CT-RSA 2016. LNCS, vol. 9610, pp. 200–216. Springer, Cham (2016). doi:10.1007/978-3-319-29485-8_12 CrossRef

15.

Fauzi, P., Lipmaa, H., Zając, M.: A shuffle argument secure in the generic model. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10032, pp. 841–872. Springer, Heidelberg (2016). doi:10.1007/978-3-662-53890-6_28 CrossRef

16.

Furukawa, J., Sako, K.: An efficient scheme for proving a shuffle. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 368–387. Springer, Heidelberg (2001). doi:10.1007/3-540-44647-8_22 CrossRef

17.

Golle, P., Jakobsson, M., Juels, A., Syverson, P.: Universal re-encryption for mixnets. In: Okamoto, T. (ed.) CT-RSA 2004. LNCS, vol. 2964, pp. 163–178. Springer, Heidelberg (2004). doi:10.1007/978-3-540-24660-2_14 CrossRef

18.

Groth, J.: A verifiable secret shuffe of homomorphic encryptions. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 145–160. Springer, Heidelberg (2003). doi:10.1007/3-540-36288-6_11 CrossRef

19.

Groth, J., Lu, S.: A non-interactive shuffle with pairing based verifiability. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 51–67. Springer, Heidelberg (2007). doi:10.1007/978-3-540-76900-2_4 CrossRef

20.

Lindner, R., Peikert, C.: Better key sizes (and attacks) for LWE-based encryption. In: Kiayias, A. (ed.) CT-RSA 2011. LNCS, vol. 6558, pp. 319–339. Springer, Heidelberg (2011). doi:10.1007/978-3-642-19074-2_21 CrossRef

21.

Ling, S., Nguyen, K., Stehlé, D., Wang, H.: Improved zero-knowledge proofs of knowledge for the ISIS problem, and applications. In: Kurosawa, K., Hanaoka, G. (eds.) PKC 2013. LNCS, vol. 7778, pp. 107–124. Springer, Heidelberg (2013). doi:10.1007/978-3-642-36362-7_8 CrossRef

22.

Lipmaa, H., Zhang, B.: A more efficient computationally sound non-interactive zero-knowledge shuffle argument. In: Visconti, I., Prisco, R. (eds.) SCN 2012. LNCS, vol. 7485, pp. 477–502. Springer, Heidelberg (2012). doi:10.1007/978-3-642-32928-9_27 CrossRef

23.

Locher, P., Haenni, R.: Verifiable internet elections with everlasting privacy and minimal trust. In: Haenni, R., Koenig, R.E., Wikström, D. (eds.) VOTELID 2015. LNCS, vol. 9269, pp. 74–91. Springer, Cham (2015). doi:10.1007/978-3-319-22270-7_5 CrossRef

24.

Locher, P., Haenni, R., Koenig, R.E.: Coercion-resistant internet voting with everlasting privacy. In: Clark, J., Meiklejohn, S., Ryan, P.Y.A., Wallach, D., Brenner, M., Rohloff, K. (eds.) FC 2016. LNCS, vol. 9604, pp. 161–175. Springer, Heidelberg (2016). doi:10.1007/978-3-662-53357-4_11 CrossRef

25.

Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. J. ACM 60(6), 43:1–43:35 (2013)CrossRefMATHMathSciNet

26.

Markus, J., Ari, J.: Millimix: mixing in small batches. Technical report (1999)

27.

Micciancio, D., Regev, O.: Lattice-based cryptography. In: Bernstein, D.J., Buchmann, J., Dahmen, E. (eds.) Post-Quantum Cryptography, pp. 147–191. Springer, Heidelberg (2009). doi:10.1007/978-3-540-88702-7_5 CrossRef

28.

Moran, T., Naor, M.: Split-ballot voting: everlasting privacy with distributed trust. In: Proceedings of the 14th ACM Conference on Computer and Communications Security, CCS 2007, pp. 246–255. ACM (2007)

29.

Andrew Neff, C.: A verifiable secret shuffle and its application to e-voting. In: Proceedings of the 8th ACM Conference on Computer and Communication Security, CCS 2001, pp. 116–125, NY, USA (2001)

30.

Park, C., Itoh, K., Kurosawa, K.: Efficient anonymous channel and all/nothing election scheme. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 248–259. Springer, Heidelberg (1994). doi:10.1007/3-540-48285-7_21 CrossRef

31.

Pedersen, T.P.: Non-interactive and information-theoretic secure verifiable secret sharing. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 129–140. Springer, Heidelberg (1992). doi:10.1007/3-540-46766-1_9

32.

Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing, STOC 2005, pp. 84–93, New York, NY, USA. ACM (2005)

33.

Regev, O.: The learning with errors problem. In: IEEE 25th Annual Conference on Computational Complexity (CCC), pp. 191–204 (2010)

34.

Rückert, M., Schneider, M.: Estimating the security of lattice-based cryptosystems. IACR Cryptology ePrint Archive, Report 2010/137 (2010). http://eprint.iacr.org/2010/137

35.

Sako, K., Kilian, J.: Receipt-free mix-type voting scheme. In: Guillou, L.C., Quisquater, J.-J. (eds.) EUROCRYPT 1995. LNCS, vol. 921, pp. 393–403. Springer, Heidelberg (1995). doi:10.1007/3-540-49264-X_32 CrossRef

36.

Singh, K., Pandu Rangan, C., Banerjee, A.K.: Lattice based universal re-encryption for mixnet. J. Int. Serv. Inf. Secur. (JISIS) 4(1), 1–11 (2014)

37.

Singh, K., Pandu Rangan, C., Banerjee, A.K.: Lattice based mix network for location privacy in mobile system. Mob. Inf. Syst. 1–9, 2015 (2015)

38.

Terelius, B., Wikström, D.: Proofs of restricted shuffles. In: Bernstein, D.J., Lange, T. (eds.) AFRICACRYPT 2010. LNCS, vol. 6055, pp. 100–113. Springer, Heidelberg (2010). doi:10.1007/978-3-642-12678-9_7 CrossRef

39.

Wikström, D.: The security of a mix-center based on a semantically secure cryptosystem. In: Menezes, A., Sarkar, P. (eds.) INDOCRYPT 2002. LNCS, vol. 2551, pp. 368–381. Springer, Heidelberg (2002). doi:10.1007/3-540-36231-2_29 CrossRef

40.

Wikström, D.: A universally composable mix-net. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 317–335. Springer, Heidelberg (2004). doi:10.1007/978-3-540-24638-1_18 CrossRef

41.

Wikström, D.: A sender verifiable mix-net and a new proof of a shuffle. In: Roy, B. (ed.) ASIACRYPT 2005. LNCS, vol. 3788, pp. 273–292. Springer, Heidelberg (2005). doi:10.1007/11593447_15 CrossRef

42.

Wikström, D.: A commitment-consistent proof of a shuffle. In: Boyd, C., González Nieto, J. (eds.) ACISP 2009. LNCS, vol. 5594, pp. 407–421. Springer, Heidelberg (2009). doi:10.1007/978-3-642-02620-1_28 CrossRef

Titel: Proof of a Shuffle for Lattice-Based Cryptography
verfasst von: Nuria Costa
Ramiro Martínez
Paz Morillo
Verlag: Springer International Publishing
Buch: Secure IT Systems
Print ISBN: 978-3-319-70289-6

Electronic ISBN: 978-3-319-70290-2

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-70290-2_17

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner