Protocolo de comprometimento de BIT eficiente com segurança sequencial baseado no modelo de memória limitada

Abstract

O Comprometimento de Bit é uma primitiva criptográfica fundamental usada para construir provas de conhecimento nulo e computação segura distribuída. Ueli Maurer [Mau93] introduziu o modelo de memória limitada no contexto de criptografia incondicionalmente segura. O modelo de Maurer limita o tamanho máximo da memória de um participante desonesto, ao contrário da abordagem usual em criptografia moderna, que limita a capacidade de processamento do adversário. Dedicou-se no presente trabalho à elaboração de um protocolo de comprometimento de bit baseado apenas no paradigma de memória limitada, sem a adoção de hipóteses computacionais não comprovadas. Até a presente data, esse é o primeiro protocolo de comprometimento de bit no modelo de memória limitada clássico1. Embora se saiba que a existência da primitiva criptográfica conhecida como Oblivious Transfer, implementada no modelo de memória limitada pela primeira vez em [CCM98], implique na existência de comprometimento de bit, uma implementação direta tem a vantagem de ser mais eficiente e mais simples, em geral. A intenção do protocolo é maximizar a quantidade de bits que o emissor consegue se comprometer e, simultaneamente, minimizar a quantidade de bits amostrados pelo mesmo durante a fase de transmissão, de modo a atingir a máxima capacidade de comprometimento. O conceito de capacidade de comprometimento apresentado aqui difere em certos aspectos do conceito presente no trabalho [WNI03] sobre canais ruidosos, sendo o principal deles o fato de a capacidade de comprometimento definida aqui ser dependente do limite no tamanho da memória do adversário. Além disso, fez-se uma contribuição adicional com a elaboração de um modelo geral para os protocolos de comprometimento de bit baseados em memória limitada. Para essa família de protocolos foram demonstrados limites ótimos, como o tamanho mínimo da memória dos participantes e a quantidade máxima de bits que o emissor pode se comprometer. _______________________________________________________________________________ ABSTRACT

The Bit commitment is a fundamental cryptographic primitive used to construct zeroknowledge proofs and multi-party computation. Ueli Maurer introduced the bounded storage model in the context of information-theoretical security on [Mau93]. Unlike the usual approach in modern cryptography, the Maurer's bounded storage model restricts the adversaries' memory size instead of their computing power. In this thesis we develop a protocol of bit commitment based on solely in the bounded storage assumption, without the assumption of unproved hard problems. Up to date, there are no results in the literature about the implementation of commitment schemes in the classical bounded storage model 2. Although is known that the existence of a cryptographic primitive called oblivious transfer, implemented in the bounded storage model at rst time on [CCM98], implies the existence of bit commitment, a directly implementation usually is better in terms of simplicity and e ciency. The intention of our protocol is maximize the length of the string that the sender may commits to and, at the same time, minimize the length of the string sampled by the sender during the broadcast phase, to achieve the commitment capacity. The concept of commitment capability presented here di ers in some aspects of the concept on [WNI03] about noisy channels, and the main reason is due to the commitment capacity de ned here to depend on memory size of the opponent. In addition, we made a further contribution elaborating a general model for the bit commitment protocols based on bounded storage. For this family of protocols, we have demonstrated optimal bounds, as the minimum size of the player's memory and the maximum length of the string that the sender may commits to.