SRVB Cryptosystem: an attempt to revive Knapsack-based public-key encryption schemes

Abstract

Criptografia de chave pública é um elemento onipresente da telecomunicação moderna. Dentre os esquemas de encriptação historicamente importantes, os baseados no ?problema da mochila?, já nos primeiros anos da criptografia de chave pública, performaram particularmente bem em termos de recursos computacionais (tempo e memória), e simplicidade matemática e de algoritmo. Embora criptanálises efetivas tenham prontamente impedido a adoção massiva de diferentes tentativas, o problema da possibilidade de uso real de encriptação assimétrica baseada no problema da mochila continua não resolvido. Esta dissertação de Mestrado objetiva apresentar uma nova construção que oferece avanços consistentes em criptografia baseada no problema da mochila. Propomos duas melhorias no criptossistema de mochila original, respondendo aos ataques mais importantes: os baseados nas aproximações Diofantinas e os baseados nos oráculos de problemas de retículos. As defesas propostas demonstradamente evitam tais ataques, o que contribui para ou reviver os esquemas de problema da mochila, ou confirmar a impossibilidade dessa questão. Por fim, apresentamos o Nep.Sec, um concurso oferecendo um prêmio em dinheiro para quem quebrar o criptossistema proposto.

Abstract: Public-key cryptography is a ubiquitous building-block of modern telecommunication technology. Among the most historically important, the knapsack-based encryption schemes, from the early years of public-key cryptography, performed particularly well in computational resources (time and memory), and mathematical and algorithmic simplicity. Although effective cryptanalyses readily curtailed their widespread adoption to several different attempts, the possibility of actual usage of knapsack-based asymmetric encryption schemes remains unsettled. This Master?s dissertation aims to present a novel construction that offers consistent security improvements on knapsack-based cryptography. We propose two improvements upon the original knapsack cryptosystem that address the most important types of attacks: the Diophantine approximations-based attacks and the lattice problems oracle attacks. The proposed defences demonstrably preclude the types of attacks mentioned above, thus contributing to revive knapsack schemes or settle the matter negatively. Finally, we present the Nep.Sec, a contest that is offering a prize for breaking our proposed cryptosystem.