Criptografia basada en gelosia

La criptografia basada en gelosia és el terme genèric per a construccions de primitives criptogràfiques que involucren gelosies, ja sigui en la pròpia construcció o en la prova de seguretat. Les construccions basades en gelosia admeten estàndards importants de criptografia postquàntica. A diferència dels esquemes de clau pública més àmpliament utilitzats i coneguts com el RSA, Diffie-Hellman o els criptosistemes de corba el·líptica, que teòricament es podrien derrotar mitjançant l'algorisme de Shor en un ordinador quàntic, algunes construccions basades en gelosia semblen ser resistents als atacs, amb ordinadors clàssics i quàntics. A més, es considera que moltes construccions basades en gelosia són segures sota el supòsit que determinats problemes de gelosia computacionals ben estudiats no es poden resoldre de manera eficient.

Història

L'any 1996, Miklós Ajtai va introduir la primera construcció criptogràfica basada en gelosia la seguretat de la qual es podia basar en la duresa de problemes de gelosia ben estudiats,^[1] i Cynthia Dwork va demostrar que un cert problema de gelosia de cas mitjà, conegut com a solucions senceres curtes (SIS), és almenys tan difícil de resoldre com un problema de gelosia en el pitjor dels casos. A continuació, va mostrar una funció hash criptogràfica la seguretat de la qual és equivalent a la duresa computacional del SIS.

El 1998, Jeffrey Hoffstein, Jill Pipher i Joseph H. Silverman van introduir un esquema de xifratge de clau pública basat en gelosia, conegut com NTRU.^[2] Tanmateix, no se sap que el seu esquema sigui almenys tan difícil com resoldre un problema de gelosia en el pitjor dels casos.

El primer esquema de xifratge de clau pública basat en gelosia la seguretat del qual es va demostrar sota els supòsits de duresa del pitjor dels casos va ser introduït per Oded Regev el 2005,^[3] juntament amb el problema d'aprenentatge amb errors (LWE). Des de llavors, gran part del treball de seguiment s'ha centrat a millorar la prova de seguretat de Regev ^[4]^[5] i millorar l'eficiència de l'esquema original.^[6]^[7]^[8]^[9] S'ha dedicat molt més treball a la construcció de primitives criptogràfiques addicionals basades en LWE i problemes relacionats. Per exemple, el 2009, Craig Gentry va introduir el primer esquema de xifratge totalment homomòrfic, que es basava en un problema de gelosia.

Fons matemàtic

En àlgebra lineal, una xarxa $L\subset \mathbb {R} ^{n}$ és el conjunt de totes les combinacions lineals senceres de vectors a partir d'una base $\{\mathbf {b} _{1},\ldots ,\mathbf {b} _{n}\}$ de $\mathbb {R} ^{n}$ . En altres paraules, $L={\Big \{}\sum a_{i}\mathbf {b} _{i}:a_{i}\in \mathbb {Z} {\Big \}}.$ Per exemple, $\mathbb {Z} ^{n}$ és una gelosia, generada per la base estàndard per $\mathbb {R} ^{n}$ . De manera crucial, la base d'una gelosia no és única. Per exemple, els vectors $(3,1,4)$ , $(1,5,9)$ , i $(2,-1,0)$ constituir una base alternativa per $\mathbb {Z} ^{3}$ .

El problema computacional més important basat en gelosia és el problema vectorial més curt (SVP o de vegades GapSVP), que ens demana aproximar la longitud euclidiana mínima d'un vector de gelosia diferent de zero. Es creu que aquest problema és difícil de resoldre de manera eficient, fins i tot amb factors d'aproximació polinomials $n$ , i fins i tot amb un ordinador quàntic. Se sap que moltes construccions criptogràfiques basades en gelosia (tot i que no totes) són segures si SVP és difícil en aquest règim.

Referències

↑ Ajtai, Miklós. «Generating Hard Instances of Lattice Problems». A: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (en anglès), 1996, p. 99–108. DOI 10.1145/237814.237838. ISBN 978-0-89791-785-8.
↑ Hoffstein, Jeffrey. «NTRU: A ring-based public key cryptosystem». A: Algorithmic Number Theory (en anglès). 1423, 1998, p. 267–288 (Lecture Notes in Computer Science). DOI 10.1007/bfb0054868. ISBN 978-3-540-64657-0.
↑ Regev, Oded. «On lattices, learning with errors, random linear codes, and cryptography». A: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing – STOC '05 (en anglès). ACM, 2005, p. 84–93. DOI 10.1145/1060590.1060603. ISBN 978-1581139600.
↑ Peikert, Chris. «Public-key cryptosystems from the worst-case shortest vector problem». A: Proceedings of the 41st annual ACM symposium on Symposium on theory of computing – STOC '09 (en anglès). ACM, 2009, p. 333–342. DOI 10.1145/1536414.1536461. ISBN 9781605585062.
↑ Brakerski, Zvika. «Classical hardness of learning with errors». A: Proceedings of the 45th annual ACM symposium on Symposium on theory of computing – STOC '13 (en anglès). ACM, 2013, p. 575–584. DOI 10.1145/2488608.2488680. ISBN 9781450320290.
↑ Lyubashevsky, Vadim. «On Ideal Lattices and Learning with Errors over Rings». A: Advances in Cryptology – EUROCRYPT 2010 (en anglès). 6110, 2010-05-30, p. 1–23 (Lecture Notes in Computer Science). DOI 10.1007/978-3-642-13190-5_1. ISBN 978-3-642-13189-9.
↑ Peikert, Chris. «Lattice cryptography for the Internet» (en anglès). IACR, 16-07-2014. [Consulta: 11 gener 2017].
↑ Alkim, Erdem; Ducas, Léo; Pöppelmann, Thomas; Schwabe, Peter Cryptology ePrint Archive, 01-01-2015.
↑ Bos, Joppe; Costello, Craig; Ducas, Léo; Mironov, Ilya; Naehrig, Michael Cryptology ePrint Archive, 01-01-2016.

[:1-1] Ajtai, Miklós. «Generating Hard Instances of Lattice Problems». A: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (en anglès), 1996, p. 99–108. DOI 10.1145/237814.237838. ISBN 978-0-89791-785-8.

[2] Hoffstein, Jeffrey. «NTRU: A ring-based public key cryptosystem». A: Algorithmic Number Theory (en anglès). 1423, 1998, p. 267–288 (Lecture Notes in Computer Science). DOI 10.1007/bfb0054868. ISBN 978-3-540-64657-0.

[:2-3] Regev, Oded. «On lattices, learning with errors, random linear codes, and cryptography». A: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing – STOC '05 (en anglès). ACM, 2005, p. 84–93. DOI 10.1145/1060590.1060603. ISBN 978-1581139600.

[:3-4] Peikert, Chris. «Public-key cryptosystems from the worst-case shortest vector problem». A: Proceedings of the 41st annual ACM symposium on Symposium on theory of computing – STOC '09 (en anglès). ACM, 2009, p. 333–342. DOI 10.1145/1536414.1536461. ISBN 9781605585062.

[5] Brakerski, Zvika. «Classical hardness of learning with errors». A: Proceedings of the 45th annual ACM symposium on Symposium on theory of computing – STOC '13 (en anglès). ACM, 2013, p. 575–584. DOI 10.1145/2488608.2488680. ISBN 9781450320290.

[:4-6] Lyubashevsky, Vadim. «On Ideal Lattices and Learning with Errors over Rings». A: Advances in Cryptology – EUROCRYPT 2010 (en anglès). 6110, 2010-05-30, p. 1–23 (Lecture Notes in Computer Science). DOI 10.1007/978-3-642-13190-5_1. ISBN 978-3-642-13189-9.

[:0-7] Peikert, Chris. «Lattice cryptography for the Internet» (en anglès). IACR, 16-07-2014. [Consulta: 11 gener 2017].

[8] Alkim, Erdem; Ducas, Léo; Pöppelmann, Thomas; Schwabe, Peter Cryptology ePrint Archive, 01-01-2015.

[9] Bos, Joppe; Costello, Craig; Ducas, Léo; Mironov, Ilya; Naehrig, Michael Cryptology ePrint Archive, 01-01-2016.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]