Vanishing Short Integer Solution: Reductions, Trapdoors, and Applications
Loading...
URL
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu |
Master's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
2024-03-12
Department
Major/Subject
Applied Mathematics
Mcode
SCI3053
Degree programme
Master’s Programme in Mathematics and Operations Research
Language
en
Pages
91+2
Series
Abstract
The development of quantum computers has given rise to the field of post-quantum cryptography; that is, the study of cryptographic schemes that provide security even against quantum adversaries. One of the most promising directions is lattice-based cryptography, which studies schemes with security based on the hardness of computational problems over lattices. Short Integer Solution (SIS) is one of the well-established lattice-based problems. Given a set of vectors as input, it asks to find a non-zero linear function with short coefficients which sends each of the input vectors to zero. Vanishing Short Integer Solution (vSIS) was recently proposed as a structured variant of SIS [Cini et al., CRYPTO'23]. It asks to find a non-zero polynomial with short coefficients which vanishes at each of the input points. Despite recent progress of using vSIS for more efficient cryptographic constructions, notably lattice-based succinct arguments with quasi-linear time provers, not much research effort focused on the hardness of vSIS and the assumption has only been based on heuristic evidence. This thesis aims towards bridging this gap. We show that vSIS (in a certain parameter regime) is as hard as the problem of finding short elements in an ideal lattice (ideal-SVP). To complete the picture, we also explore the connections between different variants of vSIS. Finally, we aim to create tools for vSIS-based cryptography. Towards this, we showcase how to build trapdoors for the vSIS problem. This is a powerful result, since vSIS trapdoors can serve as drop-in replacements for the SIS trapdoors used in many advanced lattice-based constructions. Furthermore, we observe that vSIS polynomials have interesting homomorphic properties. We demonstrate this by constructing a new homomorphic signature scheme for low-degree polynomials.Kvanttitietokoneiden kehityksen myötä on alettu tutkia niin sanottuja kvanttiturvallisia kryptosysteemejä eli menetelmiä, jotka tarjoavat turvaa myös kvanttitietokoneella varustettua hyökkääjää vastaan. Yksi lupaavimmista lähestymistavoista on hilaperusteinen kryptografia. Se tutkii menetelmiä, joiden turvallisuus perustuu oletukseen eräiden laskennallisten hilaongelmien vaikeudesta. Lyhyt kokonaislukuratkaisu (SIS) on yksi vakiintuneista ongelmista hilaperusteisen kryptografian alalla. Siinä tavoitteena on löytää ei-triviaali lineaarinen funktio jonka kertoimet ovat pieniä ja joka kuvaa jokaisen annetuista vektoreista nollaksi. Häviävä lyhyt kokonaislukuratkaisu (vSIS) on vastikään esitelty SIS-ongelman rakenteinen variantti [Cini et al., CRYPTO'23]. Siinä tavoitteena on löytää ei-triviaali pienikertoiminen polynomi jolla on annetut pisteet nollakohtina. Tuoreessa tutkimuksessa vSIS-ongelman pohjalta onnistuttiin rakentamaan tehokkaita kryptografisia menetelmiä --- kenties huomionarvoisimpana hilapohjainen kompakti argumentti, jonka todistajan tarvitsema aika on kvasilineaarinen. Tästä huolimatta vSIS-ongelman laskennallista vaikeutta ei ole juuri tutkittu ja menetelmien oletukset ovat perustuneet heuristiselle näytölle. Tämä diplomityö täydentää ymmärrystä tältä osin. Työssä näytetään, että (tietyillä parametreilla) vSIS-ongelman ratkaiseminen on vähintään yhtä vaikeaa kuin lyhyen vektorin löytäminen (SVP-ongelma) ideaalihilassa. Kokonaiskuvan täydentämiseksi tutkitaan myös yhteyksiä vSIS-ongelman eri variaatioiden välillä. Diplomityön tavoitteena on aiemmin mainitun lisäksi myös luoda uusia työkaluja vSIS-pohjaisen kryptografian tarpeisiin. Tähän liittyen työssä näytetään, kuinka vSIS-ongelmaan voidaan sisällyttää takaportti. Tulos on merkittävä, sillä vSIS-takaportilla voidaan suoraan korvata SIS-takaportti lukuisissa olemassaolevissa hilapohjaisissa kryptografisissa sovelluksissa. vSIS-polynomeilla on lisäksi mielenkiintoisia homomorfisia ominaisuuksia. Tämän demonstroimiseksi työssä rakennetaan uusi homomorfinen digitaalinen allekirjoitusalgoritmi matalan asteluvun polynomeille.Description
Supervisor
Brzuska, ChristopherThesis advisor
Lai, Russell W. F.Keywords
lattice-based cryptography, post-quantum cryptography, vanishing short integer solution, trapdoor, ideal lattice, NTRU