Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/84074
Full metadata record
DC FieldValueLanguage
dc.contributor.authorLing, Sanen
dc.contributor.authorPhan, Duong Hieuen
dc.contributor.authorStehlé, Damienen
dc.contributor.authorSteinfeld, Ronen
dc.date.accessioned2017-07-20T03:18:24Zen
dc.date.accessioned2019-12-06T15:37:46Z-
dc.date.available2017-07-20T03:18:24Zen
dc.date.available2019-12-06T15:37:46Z-
dc.date.issued2016en
dc.identifier.citationLing, S., Phan, D. H., Stehlé, D., & Steinfeld, R. (2016). Hardness of k-LWE and Applications in Traitor Tracing. Algorithmica, 79(4), 1318-1352.en
dc.identifier.issn0178-4617en
dc.identifier.urihttps://hdl.handle.net/10356/84074-
dc.description.abstractWe introduce the k-LWE problem, a Learning With Errors variant of the k-SIS problem. The Boneh-Freeman reduction from SIS to k-SIS suffers from an exponential loss in k. We improve and extend it to an LWE to k-LWE reduction with a polynomial loss in k, 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 of projective 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 from k-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.en
dc.description.sponsorshipNRF (Natl Research Foundation, S’pore)en
dc.description.sponsorshipMOE (Min. of Education, S’pore)en
dc.format.extent29 p.en
dc.language.isoenen
dc.relation.ispartofseriesAlgorithmicaen
dc.rights© 2016 Springer Science+Business Media New York. This is the author created version of a work that has been peer reviewed and accepted for publication by Algorithmica, Springer Science+Business Media New York. It incorporates referee’s comments but changes resulting from the publishing process, such as copyediting, structural formatting, may not be reflected in this document. The published version is available at: [http://dx.doi.org/10.1007/s00453-016-0251-7].en
dc.subjectLattice-based cryptographyen
dc.subjectTraitor tracingen
dc.titleHardness of k-LWE and Applications in Traitor Tracingen
dc.typeJournal Articleen
dc.contributor.schoolSchool of Physical and Mathematical Sciencesen
dc.identifier.doi10.1007/s00453-016-0251-7en
dc.description.versionAccepted versionen
item.fulltextWith Fulltext-
item.grantfulltextopen-
Appears in Collections:SPMS Journal Articles
Files in This Item:
File Description SizeFormat 
Hardness of k-LWE and Applications in Traitor Tracing.pdf556.07 kBAdobe PDFThumbnail
View/Open

SCOPUSTM   
Citations 50

4
Updated on Jul 17, 2024

Web of ScienceTM
Citations 50

2
Updated on Oct 26, 2023

Page view(s) 50

586
Updated on Jul 17, 2024

Download(s) 50

170
Updated on Jul 17, 2024

Google ScholarTM

Check

Altmetric


Plumx

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.