Boa noite amigos!
No último versículo vimos a quinta parte da tradução de “Advances In Distributed Security”, hoje a sexta.
Criptografia de Limiar
Criptografia de limiar tem sido utilizada para ajudar a conseguir replicação Bizantino-resiliente no Rampart, Fleet, SITRA, e muitos outras arquiteturas distribuídas de serviço ou sistemas de arquivos. A criptografia de limiar é um caso especial otimizado de uma técnica mais geral chamada computação multipartidária segura.
Em um criptosistema de chave-pública de limiar há somente uma chave para criptografar, mas cada parte detém uma parcela da chave [key shares] para descriptografar. Um esquema de limiar implementa o caso de limite de segurança distribuída como descrito acima. Quaisquer T + 1 detentores de parcelas de chave são necessários para conjuntamente performar uma descriptografia, e quaisquer N – T detentores de parcelas de chave podem conspirar para prevenir uma descriptografia de ser performada. O parâmetro T pode ser configurado como qualquer número inteiro positivo entre 1 e N. Frequentemente, uma estrutura de acesso mais geral, sob a restrição de segurança distribuída de que a estrutura de acesso é o conjunto complemento da estrutura de ataque, pode ser implementada também.
Para alguns algoritmos poderia-se assumir um negociante [dealer] confiável para gerar as chaves privadas e distribuir as parcelas; para alguns outros algoritmos um geração de chaves mutuamente confidencial de parcelas de chave é possível. Durante o protocolo de descriptografia, cada parte processa uma requisição de descriptografia de um particular texto cifrado e gera uma parcela de descriptografia juntamente com uma prova de sua validade. Quando uma parte obtém o texto cifrado e ao menos T + 1 parcelas de criptografia válidas, ela pode recuperar a mensagem. No caso de assinaturas de limiar, quando ao menos T + 1 de parcelas de assinatura forem obtidas, uma assinatura válida pode ser construída. [C01]
Lançamento Moedas Justas
Joe Killian introduz esse problema a seguir [K90]:
Alice e Bob queriam lançar uma moeda justa, mas não tinham nenhum moeda física para lançar. Alice ofereceu uma maneira simples de lançamento de moedas justas mentalmente.
“Primeiro, você pensa em um bit aleatório, depois eu penso em um bit aleatório. Então fazemos a disjunção exclusiva dos dois bits conjuntamente,” ela sugeriu.
“Mas e se um de nós não lançar a moeda aleatoriamente?” Bob perguntou.
“Não importa. A menos que um dos bits for verdadeiramente aleatório, a disjunção exclusiva do bits deve ser verdadeiramente aleatória”, ela respondeu, e depois de um momento de reflexão, Bob concordou.
Um pouco depois, Alice e Bob encontraram um livro sobre inteligência artificial, abandonado na beira da estrada, Um bom cidadão, Alice disse, “Um de nós deve pegar esse livro e achar um local adequado para descarte”. Bob concordou,e sugeriu que usassem seu protocolo de lançamento de moedas para determinar quem deveria jogar o livro fora.
“Se o final do bit for um 0, então você pega o livro, e se for um 1, então eu irei” disse Alice. “Qual o seu bit?”
Bob respondeu “1.” “Por que? O meu também” Alice disse astutamente. “Acho que esse não é o seu dia de sorte.”
Bruce Schneier [Sh96] continua descrevendo o que há de errado com este protocolo:
Desnecessário dizer que esse protocolo de lançamento de moedas tem um bug sério. Embora seja verdade que um bit verdadeiramente aleatório, x, ou exclusivo com qualquer bit distribuído independentemente, y, produza um bit verdadeiramente aleatório, o protocolo de Alice não garantiu que os dois bits fossem distribuídos independentemente. De fato, não é difícil verificar se nenhum protocolo mental pode permitir que duas partes infinitamente poderosas joguem uma moeda justa. Alice e Bob estavam com problemas até receberem uma carta de um obscuro estudante de pós-graduação em criptografia. As informações na carta eram teóricas demais para serem de alguma utilidade para qualquer pessoa, mas o envelope em que a carta chegava era extremamente útil.
A próxima vez que Alice e Bob quisessem lançar uma moeda, eles jogariam a versão modificada do protocolo original. Primeiro, Bob decide em um bit, mas ao invés de o anunciar imediatamente, ele escreve em um pedaço de papel e coloca o papel no envelope. Em seguida, Alice anuncia seu bit. Finalmente, Alice e Bob pegam o bit de Bob e calculam o bit aleatório. Este bit era realmente aleatório sempre que ao menos um deles jogue honestamente. Alice e Bob tinham um protocolo funcionando, o sonho do criptógrafo de irrelevância social foi realizado e todos viveram felizes para sempre.
[C01] C. Cachin, “Distributing Trust on the Internet” Conference on dependable systems and networks (DSN-2001). Essa é uma pesquisa do estado da arte em replicação Bizantino-resiliente e também a apresentação de seu próprio sistema de replicação Bizantino-resiliente que usa o lançamento de moedas justas.[K90] J. Kilian, The Use of Randomness in Algorithms and Protocols, MIT Press 1990
[Sh96] B. Schneier, Applied Cryptography, 2nd edition, John Wiley & Sons 1996.
Fechada a sexta parte da obra, no versículo seguinte a sétima. Grande abraço!
