Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Hardness ofk-LWE and Applications in Traitor Tracing

  • Conference paper

Part of the book series:Lecture Notes in Computer Science ((LNSC,volume 8616))

Included in the following conference series:

  • 4464Accesses

  • 35Citations

Abstract

We introduce thek-LWEproblem, a Learning With Errors variant of thek-SIS problem. The Boneh-Freeman reduction from SIS tok-SIS suffers from an exponential loss in k. We improve and extend it to an LWE tok-LWE reduction with a polynomial loss ink, by relying on a new technique involving trapdoors for random integer kernel lattices. Based on this hardness result, we present the first algebraic construction of a traitor tracing scheme whose security relies on the worst-case hardness of standard lattice problems. The proposed LWE traitor tracing is almost as efficient as the LWE encryption. Further, it achieves public traceability, i.e., allows the authority to delegate the tracing capability to ”untrusted” parties. To this aim, we introduce the notion ofprojective sampling family in which each sampling function is keyed and, with a projection of the key on a well chosen space, one can simulate the sampling function in a computationally indistinguishable way. The construction of a projective sampling family fromk-LWE allows us to achieve public traceability, by publishing the projected keys of the users. We believe that the new lattice tools and the projective sampling family are quite general that they may have applications in other areas.

Similar content being viewed by others

Keywords

References

  1. Aggarwal, D., Regev, O.: A note on discrete gaussian combinations of lattice vectors (2013), Draft Available at,http://arxiv.org/pdf/1308.2405v1.pdf

  2. Agrawal, S., Gentry, C., Halevi, S., Sahai, A.: Discrete gaussian leftover hash lemma over infinite domains. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013, Part I. LNCS, vol. 8269, pp. 97–116. Springer, Heidelberg (2013)

    Chapter  Google Scholar 

  3. Ajtai, M.: Generating hard instances of lattice problems (extended abstract). In: Proc. of STOC, pp. 99–108. ACM (1996)

    Google Scholar 

  4. Ajtai, M.: Generating hard instances of the short basis problem. In: Wiedermann, J., Van Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol. 1644, pp. 1–9. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

  5. Alwen, J., Peikert, C.: Generating shorter bases for hard random lattices. Theor. Comput. Science 48(3), 535–553 (2011)

    MathSciNet MATH  Google Scholar 

  6. Billet, O., Phan, D.H.: Efficient Traitor Tracing from Collusion Secure Codes. In: Safavi-Naini, R. (ed.) ICITS 2008. LNCS, vol. 5155, pp. 171–182. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  7. Boneh, D., Franklin, M.K.: An efficient public key traitor scheme (Extended abstract). In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 338–353. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

  8. Boneh, D., Freeman, D.M.: Linearly homomorphic signatures over binary fields and new tools for lattice-based signatures. In: Catalano, D., Fazio, N., Gennaro, R., Nicolosi, A. (eds.) PKC 2011. LNCS, vol. 6571, pp. 1–16. Springer, Heidelberg (2011), Full version available at,http://eprint.iacr.org/2010/453

    Chapter  Google Scholar 

  9. Boneh, D., Waters, B.: A fully collusion resistant broadcast, trace, and revoke system. In: Proc. of ACM CCS, pp. 211–220. ACM (2006)

    Google Scholar 

  10. Boneh, D., Naor, M.: Traitor tracing with constant size ciphertext. In: Ning, P., Syverson, P.F., Jha, S. (eds.) ACM CCS 2008, pp. 501–510. ACM Press (2008)

    Google Scholar 

  11. Boneh, D., Sahai, A., Waters, B.: Fully collusion resistant traitor tracing with short ciphertexts and private keys. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 573–592. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  12. Boneh, D., Zhandry, M.: Multiparty key exchange, efficient traitor tracing, and more from indistinguishability obfuscation. Cryptology ePrint Archive, Report 2013/642 (2013),http://eprint.iacr.org/

  13. Brakerski, Z., Langlois, A., Peikert, C., Regev, O., Stehlé, D.: Classical hardness of learning with errors. In: STOC, pp. 575–584. ACM (2013)

    Google Scholar 

  14. Chabanne, H., Phan, D.H., Pointcheval, D.: Public traceability in traitor tracing schemes. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 542–558. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  15. Chor, B., Fiat, A., Naor, M.: Tracing traitors. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 257–270. Springer, Heidelberg (1994)

    Google Scholar 

  16. Cramer, R., Shoup, V.: Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 45–64. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  17. Garg, S., Gentry, C., Halevi, S.: Candidate multilinear maps from ideal lattices. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 1–17. Springer, Heidelberg (2013)

    Chapter  Google Scholar 

  18. Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: Proc. of FOCS, pp. 40–49. IEEE Computer Society Press (2013)

    Google Scholar 

  19. Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Proc. of STOC, pp. 197–206. ACM (2008), Full version available at,http://eprint.iacr.org/2007/432.pdf

  20. Gordon, S.D., Katz, J., Vaikuntanathan, V.: A group signature scheme from lattice assumptions. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 395–412. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  21. Kiayias, A., Pehlivanglu, S.: Encryption For Digital Content. Springer, Heidelberg (2010)

    Book MATH  Google Scholar 

  22. Kiayias, A., Yung, M.: Breaking and repairing asymmetric public-key traitor tracing. In: Digital Rights Management Workshop, pp. 32–50 (2002)

    Google Scholar 

  23. Kiayias, A., Yung, M.: Traitor tracing with constant transmission rate. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 450–465. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  24. Komaki, H., Watanabe, Y., Hanaoka, G., Imai, H.: Efficient asymmetric self-enforcement scheme with public traceability. In: Kim, K.-c. (ed.) PKC 2001. LNCS, vol. 1992, pp. 225–239. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  25. Langlois, A., Stehlé, D., Steinfeld, R.: GGHLite: More efficient multilinear maps from ideal lattices. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 239–256. Springer, Heidelberg (2014)

    Chapter  Google Scholar 

  26. Langlois, A., Stehlé, D., Steinfeld, R.: Improved and simplified security proofs in lattice-based cryptography: using the Rényi divergence rather than the statistical distance (2014); Available on the webpages of the authors.

    Google Scholar 

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

    Article MathSciNet MATH  Google Scholar 

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

    Chapter  Google Scholar 

  29. Micciancio, D., Regev, O.: Worst-case to average-case reductions based on gaussian measures. SIAM J. Comput 37(1), 267–302 (2007)

    Article MathSciNet MATH  Google Scholar 

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

    Chapter  Google Scholar 

  31. Naor, M., Pinkas, B.: Efficient trace and revoke schemes. In: Frankel, Y. (ed.) FC 2000. LNCS, vol. 1962, pp. 1–20. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  32. O’Neill, A., Peikert, C., Waters, B.: Bi-deniable public-key encryption. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 525–542. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

  33. Peikert, C.: Public-key cryptosystems from the worst-case shortest vector problem. In: Proc. of STOC, pp. 333–342. ACM (2009)

    Google Scholar 

  34. Peikert, C.: An efficient and parallel gaussian sampler for lattices. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 80–97. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  35. Pfitzmann, B.: Trials of traced traitors. In: Anderson, R. (ed.) IH 1996. LNCS, vol. 1174, pp. 49–64. Springer, Heidelberg (1996)

    Chapter  Google Scholar 

  36. Pfitzmann, B., Waidner, M.: Asymmetric fingerprinting for larger collusions. In: ACM CCS 1997, pp. 151–160. ACM Press (April 1997)

    Google Scholar 

  37. Phan, D.H., Safavi-Naini, R., Tonien, D.: Generic construction of hybrid public key traitor tracing with full-public-traceability. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4052, pp. 264–275. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  38. Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Proc. of STOC, pp. 84–93. ACM (2005)

    Google Scholar 

  39. Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6) (2009)

    Google Scholar 

  40. Regev, O.: The learning with errors problem. In: Invited survey in CCC 2010 (2010),http://www.cims.nyu.edu/~regev/

  41. Sirvent, T.: Traitor tracing scheme with constant ciphertext rate against powerful pirates. In: Augot, D., Sendrier, N., Tillich, J.-P. (eds.) Workshop on Coding and Cryptography—WCC 2007, pp. 379–388 (April 2007)

    Google Scholar 

  42. Watanabe, Y., Hanaoka, G., Imai, H.: Efficient asymmetric public-key traitor tracing without trusted agents. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 392–407. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore

    San Ling

  2. Laboratoire LAGA (CNRS, U. Paris 8, U. Paris 13), U. Paris 8, France

    Duong Hieu Phan

  3. Laboratoire LIP (U. Lyon, CNRS, ENSL, INRIA, UCBL), ENS de Lyon, France

    Damien Stehlé

  4. Faculty of Information Technology, Monash University, Clayton, Australia

    Ron Steinfeld

Authors
  1. San Ling
  2. Duong Hieu Phan
  3. Damien Stehlé
  4. Ron Steinfeld

Editor information

Editors and Affiliations

  1. Yahoo Labs, 701 Firstz Avenue, 94089, Sunnyvale, CA, USA

    Juan A. Garay

  2. The City College of New York, 160 Convent Avenue, 10031, New York, NY, USA

    Rosario Gennaro

Rights and permissions

Copyright information

© 2014 International Association for Cryptologic Research

About this paper

Cite this paper

Ling, S., Phan, D.H., Stehlé, D., Steinfeld, R. (2014). Hardness ofk-LWE and Applications in Traitor Tracing. In: Garay, J.A., Gennaro, R. (eds) Advances in Cryptology – CRYPTO 2014. CRYPTO 2014. Lecture Notes in Computer Science, vol 8616. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-44371-2_18

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp