criptosistemas de mochila

Los criptosistemas de la mochila son criptosistemas cuya seguridad se basa en la dificultad de resolver el problema de la mochila . Siguen siendo bastante impopulares porque las versiones simples de estos algoritmos han sido vulneradas durante varias décadas. ^{[ 1 ]} Sin embargo, este tipo de criptosistema es un buen candidato para la criptografía postcuántica .

El criptosistema de mochila más famoso es el criptosistema de clave pública Merkle-Hellman , uno de los primeros criptosistemas de clave pública , publicado el mismo año que el criptosistema RSA . Sin embargo, este sistema ha sido vulnerado por varios ataques: uno de Shamir , ^{[ 2 ]} uno de Adleman, ^{[ 3 ]} y el ataque de baja densidad .

Sin embargo, existen criptosistemas modernos de mochila que se consideran seguros hasta el momento: entre ellos se encuentra Nasako-Murakami 2006. ^{[ 4 ]}

Se cree que los criptosistemas de la mochila, cuando no están sujetos al criptoanálisis clásico, son difíciles incluso para las computadoras cuánticas. Ese no es el caso de los sistemas que se basan en la factorización de grandes enteros, como RSA , o en el cálculo de logaritmos discretos , como ECDSA , problemas que se resuelven en tiempo polinomial con el algoritmo de Shor . ^{[ 5 ]}

• Adleman, Leonard (1983). «Sobre la ruptura del criptosistema de clave pública iterado Merkle-Hellman». Avances en criptología . Springer. págs. 303–308 . doi : 10.1007/978-1-4757-0602-4_29 . ISBN  978-1-4757-0604-8.
• Shamir, Adi (1982), "Un algoritmo de tiempo polinomial para romper el criptosistema básico de Merkle-Hellman", XXIII Simposio Anual sobre Fundamentos de la Informática (SFCS 1982) , págs. 145–152 , doi : 10.1109/SFCS.1982.5 
• Nasako, T.; Murakami, Y. (2006), "Un criptosistema de mochila de alta densidad que utiliza una trampilla combinada" , Japan Society for Industrial and Applied Mathematics , 16 (4): 519– 605, doi : 10.11540/jsiamt.16.4_591