Forçando um comportamento honesto

9

Como você pode forçar uma parte a ser honesta (obedecer às regras do protocolo)?

Eu já vi alguns mecanismos, como compromissos, provas e etc., mas eles simplesmente não parecem resolver todo o problema. Parece-me que a estrutura do design do protocolo e esses mecanismos devem fazer o trabalho. Alguém tem uma boa classificação disso?
Editar
Ao projetar protocolos seguros, se você forçar uma parte a ser honesta, o design seria muito mais fácil, embora essa imposição tenha seu próprio pagamento. Eu vi, ao projetar protocolos seguros, os designers assumirem algo que não me parece realista, por exemplo, assumir todas as partes honestas na pior das hipóteses ou assumir a honestidade do servidor que mantém os dados do usuário. Mas, ao analisar o design de protocolos em modelos mais rígidos, você raramente vê essas suposições (pelo menos eu não a vi - eu estudo os protocolosEstrutura UC de Canetti, que eu acho que ainda não está totalmente formalizada). Eu queria saber, existe alguma boa classificação das maneiras pelas quais você pode forçar uma parte a ser honesta ou existe algum compilador que possa converter o protocolo de entrada em uma com partes honestas?
Agora vou explicar por que acho que isso simplesmente não funciona, embora possa parecer irrelevante. Ao projetar protocolos na estrutura da UC, que se beneficia do paradigma ideal / real, todos os links de comunicação no modelo ideal são autenticados, o que não é verdade no modelo real. Portanto, os projetistas de protocolos buscam métodos alternativos para implementar esse canal por meio de suposição de PKI ou um CRS (Common Reference String). Mas ao projetar protocolos de autenticação, assumindo que os canais autenticados estão errados. Suponha que estamos projetando um protocolo de autenticação na estrutura da UC, há um ataque no qual o adversário falsifica a identidade de uma parte, mas devido à suposição de links autenticados no modelo ideal, esse ataque não é assumido nessa estrutura! Você pode consultarModelagem de ataques internos a protocolos de troca de chaves de grupo . Você pode notar que Canetti, em seu trabalho seminal, noções universalmente composíveis de troca de chaves e canais seguros menciona uma noção anterior de segurança chamada SK-Security, que é simplesmente o suficiente para garantir a segurança dos protocolos de autenticação. De alguma forma, ele confessa (afirmando que esse é o problema da tecnicidade) que a definição de UC nesse contexto é muito restritiva e fornece uma variante relaxada chamada oráculo de não informação (o que me confundiu, porque eu não vi esse modelo de segurança em nenhum lugar , Não posso corresponder esse padrão de segurança a nenhum outro padrão de segurança, provavelmente minha falta de conhecimento: D).

[Como uma observação lateral, é quase possível converter qualquer protocolo Sk-secure para um protocolo UC seguro, independentemente do tempo do simulador. Por exemplo, você pode apenas remover as assinaturas das mensagens e fazer com que o simulador simule todas as interações de maneira simulada. Consulte Troca de chaves de grupos contributivos universalmente compostas para obter provas! Agora, suponha que este seja um protocolo de troca de chaves de grupo com muitas partes polinomialmente, qual seria a eficiência do simulador? Esta é a origem da minha outra pergunta neste fórum .]

De qualquer forma, devido à falta de comprometimento no modelo simples (sobre UC), procurei outros meios de tornar o protocolo seguro, ignorando a necessidade desse relaxamento. Essa ideia é muito básica em minha mente e me ocorreu apenas por ter estudado o mais recente esquema de compromisso de canetti no modelo simples: dureza adaptativa e segurança compostável no modelo simples a partir de premissas padrão .
BTW, não busco provas de conhecimento nulo porque, devido a razões que não conheço, sempre que alguém as utilizou em um protocolo simultâneo (na estrutura da UC), os outros mencionaram o protocolo como ineficiente (pode ser devido ao rebobinamento do simulador).

Yasser Sobhdel
fonte
2
Você pode dar uma olhada no seguinte: sabedoria.weizmann.ac.il/~oded/gmw2.html . Nesse documento, as partes desonestas são forçadas a agir honestamente, provando (com conhecimento nulo) que seguiram o protocolo na etapa anterior.
MS Dousti
4
Eu acho que "forçar um comportamento honesto" é uma definição possível para a criptografia moderna (que é mais do que apenas ocultar informações). Nesse caso, todas as subáreas da criptografia podem ser consideradas como uma abordagem para essa questão.
Marc
Eu estava prestes a escrever a mesma coisa que Marc. (A propósito, provas interativas ou mesmo a definição de NP também podem ser vistas como "forçando um comportamento honesto" no provador, embora não sejam geralmente consideradas como protocolos criptográficos.) A questão é realmente ampla e parece haver Não existe uma maneira única de impor um comportamento honesto em várias situações.
Tsuyoshi Ito
11
O que você quer dizer precisamente com "mas eles simplesmente não parecem resolver todo o problema?" Você poderia ser mais específico?
Alon Rosen
@Sadeq: Veja o último parágrafo! @ Marc & Tsuyoshi lto: Por favor, consulte a seção Editar. isso pode ajudar.
Yasser Sobhdel 5/12

Respostas:

6

Infelizmente, você não pode forçar as pessoas a fazer o que o protocolo diz que elas devem fazer.

Até pessoas bem-intencionadas que pretendiam seguir o protocolo ocasionalmente cometem erros.

Parece haver pelo menos três abordagens:

  • teoria criptográfica: suponha que agentes "bons" sempre sigam o protocolo, enquanto agentes "maliciosos" tentam subverter o protocolo. Projete o protocolo criptográfico para que bons agentes obtenham o que precisam, enquanto agentes mal-intencionados não recebem nada.
  • teoria dos jogos: suponha que todo agente cuide apenas do seu próprio interesse individual. Use o design do mecanismo para maximizar o benefício total para todos.
  • rede tolerante a falhas distribuída: suponha que todo agente cometa um erro ocasional e alguns poucos agentes bot emitem muitas mensagens criadas com códigos maliciosos. Detecte e isole os nós bot até que eles sejam corrigidos; use a detecção e correção de erros (EDAC) para corrigir erros ocasionais; use protocolos convergentes que eventualmente se estabeleçam em um estado útil, independentemente das informações erradas iniciais armazenadas nas tabelas de roteamento.

design de mecanismos Na teoria dos jogos, projetar uma situação (como estabelecer as regras de um leilão), de modo que as pessoas que egoisticamente cuidem apenas de seus próprios interesses individuais acabem fazendo o que o designer deseja que sejam chamadas de "design de mecanismo" . Em particular, usando a teoria da implementação , as situações podem ser projetadas de modo que o resultado final maximize o benefício total para todos, evitando situações mal projetadas, como a "tragédia do bem comum" ou o "dilema do prisioneiro", onde acontecem coisas que não estão nas mãos de ninguém. juros de longo prazo.

Alguns dos processos mais robustos são projetados para serem compatíveis com incentivos .

A teoria dos jogos normalmente assume que todos os agentes relevantes são "racionais". Na teoria dos jogos, "racional" significa que um agente prefere alguns resultados a outros, está disposto e é capaz de mudar suas ações da maneira que ele espera (dadas as informações disponíveis) resultará em um resultado mais preferido (seu próprio interesse próprio estreito), e ele é inteligente o suficiente para perceber que outros agentes racionais agirão de maneira semelhante para tentar obter o resultado mais preferido dentre todos os possíveis resultados que possam resultar dessa escolha de ação.

Um designer pode assumir temporariamente a suposição simplificadora de que todas as pessoas agem apenas de acordo com seu próprio interesse estreito. Essa suposição facilita o design de uma situação usando a teoria da implementação. No entanto, após o término do design, não importa se as pessoas agem de acordo com seu próprio interesse próprio (" Homo economicus ") ou se são altruístas e desejam maximizar o benefício líquido total para todos - em um Em uma situação projetada adequadamente, os dois tipos de pessoas fazem exatamente as mesmas escolhas e o resultado final maximiza o benefício total para todos.

protocolos convergentes

Ao projetar um protocolo de roteamento , cada nó da rede envia mensagens para seus vizinhos passando informações sobre quais outros nós são alcançáveis ​​a partir desse nó.

Infelizmente, ocasionalmente essas mensagens têm erros. Pior, às vezes um nó é configurado incorretamente e envia muitas mensagens enganosas e talvez até maliciosas.

Embora nós, humanos, saibamos que a mensagem pode estar incorreta, normalmente projetamos o protocolo para que um nó que funcione corretamente confie em todas as mensagens e armazene as informações em sua tabela de roteamento e tome suas decisões como se acreditasse que essas informações eram inteiramente verdadeiras.

Quando um humano desativa um nó com defeito (ou desconecta-o da rede), normalmente projetamos o protocolo para passar rapidamente boas informações para liberar as informações corrompidas e convergir rapidamente para um estado útil.

abordagens combinadas

O design do mecanismo algorítmico parece tentar combinar a abordagem de rede tolerante a falhas e a abordagem do mecanismo da teoria dos jogos.

@Yoichi Hirai e Aaron, obrigado por apontar algumas tentativas interessantes de combinar teoria dos jogos e criptografia.

David Cary
fonte
4

Joe Halpern tem um slide sobre esse tópico. http://games2009.dimi.uniud.it/Halpern.pdf

Trata-se de incentivar as partes a seguirem um protocolo. Esses mecanismos exigem racionalidade das partes e os argumentos são baseados na teoria dos jogos.

yhirai
fonte
11
Aqui está um artigo relacionado para acompanhar os slides: theory.stanford.edu/~vteague/STOC04.pdf - Essa abordagem não "força" as pessoas a seguir o protocolo, mas tenta projetá-lo para incentivar as pessoas a querer para fazer isso. Claro que, para fazer isso, você tem que fazer algumas suposições sobre o que exatamente as pessoas que seguem o protocolo quero fazer ...
Aaron Roth
se possível, você poderia explicar o que "racional" significa neste contexto? por exemplo, significa adesão a um conjunto global subjacente de axiomas? ou significa que as partes envolvidas compartilham o mesmo conjunto de axiomas subjacentes? a explicação anterior me parece absurda em qualquer cenário do mundo real, pois os indivíduos geralmente têm motivações subjacentes muito diferentes e, portanto, pode-se esperar que tratem 'incentivos' de maneiras muito diferentes.
S8soj3o289
@ Blackkettle: um jogador racional maximiza (a expectativa de) uma função de utilidade. pela razão que você aponta, é sempre difícil encontrar os axiomas certos que as empresas de serviços públicos precisam satisfazer. mas sempre tentamos o conjunto mínimo de axiomas. todos os livros bons microeconomia iria entrar em detalhes sobre este assunto
Sasho Nikolov
@blackkettle: sobre o artigo de Halpern: ele supõe que as partes no protocolo (compartilhamento secreto) preferem conhecer o segredo do que não o conhecem, e preferem que menos e mais outras partes o conheçam. também a noção de equilíbrio que ele usa é o equilíbrio de Nash sobre estratégias não-denominadas (ou seja, um jogador não jogaria uma estratégia se outra for sempre pelo menos tão boa; também, desde que outros jogadores não alterem suas estratégias e sua estratégia atual não seja pior que qualquer outro, ela também não mudaria).
Sasho Nikolov