A knapsack McEliece-based public key cryptosystem

Abstract A ROM IND-CCA2 Key Encapsulation Mechanism (KEM) supported by a Public Key Encryption (PKE) scheme based on the Weighted Modular Subset Sum Problem (WMSSP) is proposed. Concretely, it is proven that for certain sets of integers, whose inverses modulo a large predetermined integer have bounded bit size, an algorithm based on a truncated version of the extended Euclidean algorithm can effectively solve the WMSSP. The security analysis is conducted through the connection established between the Binary Subset Sum Problem and the Shortest Vector Problem. Various attacks against our proposal, relying on the computation of a shortest vector, have been analyzed. It is widely accepted that the problem supporting the security of this cryptosystem exhibits resilience against quantum threats. Moreover, the key generation and encryption-decryption processes exhibit remarkable time efficiency, as they rely exclusively on basic integer arithmetic.