Boa noite amigos!

No último versículo vimos a tradução da obra “Confidential Auditing”. Hoje veremos outra pequena obra de satoshi nakamoto Nick Szabo. “Intrapolynomial Cryptography”, publicada em 1999. É uma obra bem técnica.

Criptografia Intrapolinomial

Nick Szabo

1999

Pesquisadores propuseram uma variedade de propostas de “quebra-cabeças de clientes” ou de “trabalho ocupado” como hashcash, MicroMint, bit gold e postagem com custo de computação para criar moedas independentes ou tornar o envio de spams caro. A implicação matemática dessas propostas é que existe uma criptografia intrapolinomial. Quatro motivações para a teoria de criptografia intrapolinominal são (a) novas construções como as aplicações acima mencionadas, (b) estimativa mais precisa do custo computacional de quebrar uma cifra, (c) pode ser mais fácil provar limites inferiores, em vez de apenas conjecturá-las, como é o caso da criptografia superpolinomial (padrão) e (d) se não existem funções unidirecionais, a criptografia padrão é intrapolinomial e não super polinomial.

Proponho a seguinte formalização:

f: {0,1} * –> {0,1} * é chamado de uma função k-benchmark forte para o modelo de máquina M e k>= 1 se:

1. f é computável em tempo O(p(n)) em M, onde p é um polinômio.
2. f não reduza o input mais que q(n,k), onde q(n,k) é um polinômio de grau k.
3. Para cada algoritmo aleatório A rodando em M em um tempo menor que q(n,k)p(n), existe um N tal que n > N

        Pr [A(f(x)) = f^ -1(f(x))] <1 / q(n,k)p(n)

Em outras palavras, não há algoritmo funcionando mais rápido que q(n,k)p(n) que pode inverter f para mais do que um número insignificante de valores.

Pode-se definir de maneira semelhante funções de benchmark de caso médio, de melhor e de pior caso, de forma análoga às funções unidirecionais. Pergunta aberta (análogo à questão aberta na criptografia superpolinomial de se funções unidirecionais existem): pode-se provar (3) como limites inferior e superior para alguma função e k>= 1 em algum modelo de máquina real, como o RAM-log?

Casos fortes e médios são mais adequados a aplicações relacionadas à criptografia. Infelizmente, para esses propósitos, também precisamos:

1. uma lista de modelos de máquinas que é abrangente de todas as máquinas fisicamente realizáveis, no sentido de que qualquer máquina desse tipo pode ser simulada com uma sobrecarga muito pequena, como uma constante ou O(log(n)), por algum modelo na lista;
2. provar limites inferiores em uma função de benchmark para todos os modelos na lista

Como isso é pelo menos muito entediante, espera-se que, na prática, você possa obter uma pequena lista que cubra todas as arquiteturas de máquinas plausivelmente implementadas. Isso pode funcionar onde, por exemplo, a exposição total da quebra de um protocolo é menor do que os custos de P&D de projetar e construir uma nova arquitetura de máquina para derrotá-lo. A criptoanálise incluiria a descoberta das arquiteturas de máquina ideais para quebrar uma cifra intrapolinomial.

Há pelo menos duas implicações práticas da análise acima. Uma é que há muito pouco espaço para erros na análise e implementação de postagem de custo de computação, hashcash, bit gold, MicroMint e outros esquemas de criptografia intrapolinomial. Outra é que, a menos que o oponente tenha um orçamento muito baixo e seja, portanto, limitado a computadores pessoais padrão, não faz sentido analisar a segurança ou o custo desses esquemas sem referência à arquitetura da máquina. Por exemplo, os spammers podem ser capazes de derrotar a postagem de custo computacional usando chips personalizados otimizados para computar a função de quebra-cabeça específica.

Terminamos aqui “Intrapolynomial Cryptography”, nossa 24ª tradução. Espero que tenham gostado. Amanhã começamos a próxima. Abraço, fiquem com Deus!