Merkle-Hellman

Merkle-Hellman (MH) fu uno dei primi crittosistemi a chiave pubblica creato da Ralph Merkle e Martin Hellman nel 1978. Nonostante l'idea sia elegante, e più semplice di quella dell'RSA, l'algoritmo è stato forzato. Il sistema Merkle-Hellman è basato sul problema della somma di sottoinsiemi (un caso speciale del problema dello zaino): data una lista di numeri e un altro numero, il quale è la somma di un sottoinsieme dei numeri precedenti, determinare il sottoinsieme. In generale, questo problema è conosciuto essere NP-completo; tuttavia, esistono alcuni casi 'facili' che possono essere risolti efficientemente. Lo schema Merkle-Hellman è basato sulla trasformazione di casi facili in casi difficili, e viceversa. Tuttavia, lo schema fu forzato da Adi Shamir, non attaccando il problema dello zaino, ma piuttosto forzando la trasformazione dal problema facile a quello difficile.