Criptosistema de mochila Naccache – Stern
El criptosistema Naccache – Stern Knapsack es un criptosistema de clave pública atípico desarrollado por David Naccache y Jacques Stern en 1997. Este criptosistema es determinista y, por lo tanto, no es semánticamente seguro . Aunque ininterrumpido hasta la fecha, este sistema también carece de seguridad demostrable .
Este sistema se basa en un tipo de problema de mochila . Específicamente, el problema subyacente es el siguiente: dados los números enteros c , n , p y v 0 , ..., v n , encuentre un vector tal que
La idea aquí es que cuando los v i son relativamente primos y mucho más pequeños que el módulo p, este problema se puede resolver fácilmente. Es esta observación la que permite el descifrado.