Com o surgimento da criptografia de chave pública, muito esforço foi feito para a criação de protocolos de criptografia e de assinatura que fossem comprovadamente seguros contra indivíduos maliciosos. Existem várias definições de segurança, tanto para protocolos de criptografia como para protocolos de assinatura, e também existem vários modelos de adversários, que simulam um indivíduo malicioso tentando corromper o protocolo. A família de protocolos de assinatura Rabin possui os recordes de velocidade de vericação da assinatura, chegando a ser até 100 vezes mais rápida do que o RSA. Este trabalho apresenta uma redução eficiente de segurança no modelo do oráculo aleatório para uma variante do protocolo de assinatura Rabin descrito por Bernstein, onde não é necessário o uso de nenhuma função para geração de bits pseudo-aleatórios, o que torna o protocolo mais robusto. A redução apresentada é uma redução polinomial e eficiente do problema da fatoração de inteiros para o problema de quebrar o protocolo Principal Rabin-Williams B = 0.

With the development of public-key cryptography, many efforts were made to build encryption and signature protocols that were provably secure against malicious adversaries. There are many definitions of security for encryption and signature protocols, and there are many adversary models to simulate the behaviour of a malicious adversary against a given protocol. The Rabin family of signature protocols has the speed records for verification of signature, being up to 100 times faster than RSA. This work presents a tight security proof in the random oracle model for a variant of the Rabin signature protocol presented by Bernstein, that does not require the use of pseudo-random bits, making the protocol more robust. The proof presented here is a polynomially tight reduction for the problem of integer factorization to the problem of breaking the Principal Rabin-Williams B = 0 protocol.