Verificando equivalência de um segredo

votos
4

Alice & Bob são ambos agentes quádruplos secretas que poderiam estar trabalhando para os EUA, a Rússia ou a China. Eles querem vir para cima com um esquema que faria:

  1. Se eles estão trabalhando para o mesmo lado, provar isso um ao outro para que eles possam falar livremente.

  2. Se eles estão trabalhando para lados diferentes, não expor qualquer informação adicional sobre que lado eles estão.

Ah, e por causa da natureza sensível do que eles fazem, não há uma terceira parte confiável que pode fazer a comparação para ambos.

O protocolo seria capaz de satisfazer essas duas necessidades?

Idealmente, qualquer protocolo também seria capaz de generalizar para múltiplos participantes e múltiplos estados, mas isso não é essencial.

Eu intrigado com isso por um tempo e eu não consigo encontrar uma solução satisfatória, principalmente devido à condição 2.

Edit: Aqui está o problema original que me motivou a procurar uma solução. Charlie tinha algumas fotos pessoais que ele compartilhou comigo e eu descobri mais tarde que ele também tinha compartilhado com eles Bob. Ambos queriam saber se tivéssemos o mesmo conjunto de fotos, mas, ao mesmo tempo, se Charlie não tinha compartilhado uma determinada foto com qualquer um de nós, ele provavelmente tinha uma boa razão para não e nós não querem vazar em formação.

Meu primeiro pensamento seria para cada um de nós para concatenar todas as fotografias e fornecer a soma MD5. Se eles correspondiam, então tivemos as mesmas fotos, mas se não o fizessem, nenhuma das partes saberia quais fotos o outro tinha. No entanto, percebi logo depois que este regime ainda iria vazar informações porque Bob poderia gerar um MD5 para cada subconjunto de fotos que ele tinha e se algum deles correspondeu meu soma, ele saberia que fotos que eu não tinha. Eu ainda tenho que encontrar uma solução satisfatória para este problema particular, mas eu pensei que eu iria generalizar-lo para evitar que as pessoas com foco nas particularidades da minha situação.

Publicado 26/08/2009 em 23:52
fonte usuário
Em outras línguas...                            


9 respostas

votos
1

Para ambos os problemas, você poderia usar um de dois partidos computação segura igualdade algoritmo. Há muitos esquemas, por exemplo, este por Damgard, Fitzi, Kiltz, Nielsen e Toft: Incondicionalmente seguros constante Redonda Multi-Partido Computação para a Igualdade, Comparação, Bits e exponenciação .

É claro que um agente poderia tentar se passar por um agente de outro lado para ter uma chance de 1/3 para descobrir a verdadeira lado do outro agente, mas que parece inevitável.

Um esquema muito mais simples para a foto-problema, que deve ser quase tão bom quanto o cálculo multipartidária seguro, é o seguinte:

  1. Alice e Bob classifica suas fotos e gerar um hash SHA-512.
  2. Alice envia o primeiro bit de seu hash para Bob.
  3. Bob compara a pouco para o primeiro bit de seu hash. Se for diferente, eles sabem que eles têm recebido diferentes fotos. Caso contrário, eles continuam.
  4. Bob envia o segundo bit de seu hash para Alice.
  5. Alice verifica este bit e decide se deseja continuar.
  6. Continue até que o protocolo aborta ou todos os bits tiverem sido verificados.
Respondeu 09/09/2009 em 11:24
fonte usuário

votos
1

Para o seu problema fotos, criar hashes para todos os subconjuntos de suas fotos; seleccionar aleatoriamente um subconjunto destes, e misturar em uma quantidade acordada de valores hash gerados aleatoriamente. Bob faz o mesmo, e você trocar esses conjuntos. Se a proporção de hashes no que Bob lhe enviou que coincide com aqueles que você pode gerar por hashing subconjuntos de suas fotos difere significativamente do que o esperado, é provável que você tenha um corpus significativamente diferente de fotos dele. Se a proporção de hashes aleatórios você concordar é alta, corre o risco de ser incapaz de detectar pequenas diferenças em suas coleções de fotos; se a proporção é baixa, o risco de expor informações sobre fotos faltando; você terá que selecionar um ponto adequado para a troca.

Respondeu 27/08/2009 em 00:44
fonte usuário

votos
1

Então, eles são garantidos para ser agentes quádruplos? Isso é que eles são garantidos para ser secretamente trabalhando para uma facção fingindo trabalhar para um segundo enquanto fingindo trabalhar para uma terceira fingindo trabalhar para uma quarta? Eles estão limitados a apenas os EUA, a Rússia ou a China? Se assim for, então isso significa que sempre haverá pelo menos uma facção ambos estão fingindo trabalhar para e são simultaneamente realmente trabalhando para. Isso parece negar sua capacidade de serem agentes quádruplos, porque certamente um deles não pode estar trabalhando para os americanos, enquanto secretamente trabalhando para os americanos, enquanto secretamente trabalhando para os americanos, enquanto secretamente trabalhando para os americanos.

Você diz que a solução ideal seria generalizar a números arbitrários de estados e espião-stacks. Pode o grau de agente secreto-ness ser maior, igual ou menor que o número de estados? Isso pode ser importante. Além disso, é Alice sempre a garantia de ter o mesmo grau de agente-ness como Bob? ou seja, eles sempre tanto ser agentes triplos, ou Sempre ambos por agentes quintuplicar? O operador módulo vem à mente ...

Mais detalhes agradar.

Como uma resposta potencial, você pode enumerar os estados em um campo de bits. US = 1 = 2 Rússia, China = 4, Madagáscar = 8, Tuva = 16 etc construir um dispositivo que é, essencialmente, uma porta AND. Alice constrói e traz metade e Bob constrói e traz o outro. Separados por um pano, cada um deles, pressione o botão do estado eles estão realmente trabalhando. Se a saída da porta AND é alta, então eles estão do mesmo lado. Se não, então eles calmamente derrubar o pano, e partem com as respectivas metades de sua máquina para que o botão não pode ser determinado por impressão digital.

Esta não é teórica ou rigorosa, mas prático.

Respondeu 27/08/2009 em 00:03
fonte usuário

votos
0

O Cenário Foto é impossível de alcançar:

O esquema é impossível pelas razões que você nomear.

Considere uma função f, que leva dois conjuntos de fotos, S1 e S2. f (S1, S2) retorna true se s1 = s2 e falso se S1! = s2. Ou seja, esta função implementa o esquema que você deseja.

Bob sempre pode fornecer um subconjunto de fotos do que ele tem, e saber quais charlie de foto não tem. Não há maneira de contornar isso, qualquer função que tem a propriedade que você deseja não pode ter a segurança que você deseja.

O Cenário Spy é ainda mais impossível:

Como Kent Fredric apontou o cenário espião tem ainda maiores fraquezas inerentes. Tem todos os problemas do cenário foto, além da fraqueza adicional de ter somente quatro segredos.

No cenário foto que seria altamente improvável que Bob seria aleatoriamente acho que uma das fotografias Charlies. É trivial no cenário espião para Bob adivinhar Alices escolha (1/4). Os spys só tem quatro países podem pertencem, pois eles são os dois agentes quádruplos ambos sabem todas as palavras de código secreto para cada país. Assim, Bob poderia fingir estar a trabalhar para os chineses para testar Alice.

Um tipo diferente de Solução:

Alguns cartazes notaram, a segurança pode ser aumentada se você enfraquecer a precisão de f. Claro, se ele não é exato o que é o ponto. I propor um outro tipo de solução.

  • Não deixe que eles comparar as mesmas fotografias mais de uma vez.

A parte que deseja iniciar a comparação deve primeiro mostrar que esta é uma nova comparação e não usar qualquer das imagens de antes.

EDIT: Problemas com Hash Duplo

Estou fazendo algumas suposições sobre o protocolo doublhash, mas ...

  1. Para o esquema de fotografia, o protocolo doublehash não é melhor que f, porque o segredo 62 bit deve ser construído a partir de um conjunto de fotografias para a comparação ser meaningfull. O ataque subconjunto mencionado na pergunta original ainda se aplica aqui. Tente todos os subconjuntos de fotografias para a força bruta os segredos que você pode gerar, assim, Bob pode ver se ele pode gerar o mesmo segredo de Alice.

Usando a propriedade doublehash Bob pode forçar ainda brute o segredo.

doubleHash(s1+doubleHash(b)) != doubleHash(aliceSecret+doubleHash(a))

doubleHash(s2+doubleHash(b)) != doubleHash(aliceSecret+doubleHash(a))

doubleHash(s3+doubleHash(b)) == doubleHash(aliceSecret+doubleHash(a))

Bingo, aliceSecret == s3.

DoubleHash é tão forte quanto é difícil Bruteforce a ou b

que regulamentou o DoubleHash

Em vez disso doubleHash (a + doubleHash (b)), tentar doubleHash (a, MD5 (b)). DoubleHash (a + doubleHash (b)) é ruim porque Bob poderia gerar colidindo hashes assim:

doubleHash((12 + doubleHash(34)) + doubleHash(5678))  
= doubleHash((34 + doubleHash(12)) + doubleHash(5678))
= doubleHash(5678 + doubleHash(12 + doubleHash(34)) 
= doubleHash(5678 + doubleHash(34 + doubleHash(12)) 

Aqui é uma implementação do doubleHash utilizando a nova formulação,

Doublehash(a, hashOfB){
   hashOfA = md5(a)
   combinedHash = hashOfA xor hashOfB
   return md5(combinedHash)
}

Pode-se também usar a matemática por trás assinaturas cegas impliment versão do doubleHash.

Respondeu 28/08/2009 em 06:58
fonte usuário

votos
0

A coisa mais simples que posso pensar com as fotos que possivelmente trabalhar é como assim:

  1. Hash todas as fotos com um 4096 pouco hash.
  2. Classificar as fotos por valor hash. (Hashes são afinal, apenas uma representação de cadeia de um grande número)
  3. usando essa ordem de classificação, use um sistema de streaming para cachimbo e haxixe, essas fotos, como se fossem um arquivo singular.
  4. Compartilhe seus hashes.
  5. Se os hashes corresponderem, você tem os mesmos arquivos. (Baixo baixo risco de correspondência positiva incorreta, mas em 4K hashing, é um pouco improvável)

Há, naturalmente, alguns pontos fracos aqui:

  1. Não compartilhar quantas fotos você tem. Fazer isso pode permitir que o partido com o maior número de fotos fazer permutação inteligente dos dados e remover fotos a partir do hash definir eles suspeitam que provavelmente você não tem, usando o número como um guia, e encontrar (em grande mente despesa computacional) um conjunto de imagens que corresponde ao seu hash.
  2. Eles podem fazer um sem o número, mas a sua mais difícil, e eles estão fora da sorte se eles realmente têm menos fotos.
  3. Eles poderiam criar um hash falso, simplesmente com um gerador de números aleatórios, e enviá-lo para você, dando-lhe a impressão que você teve diferentes conjuntos de dados quando você realmente tinha a mesma.

Os pontos fracos acima também são predominantes em seu sistema de identificação por código de país, exceto, é claro, você tem muito menos entropia para ficar no caminho, e sua muito mais fácil de fraudes no sistema. (E, portanto, muito longe, muito mais fácil de trabalhar para fora quem são por pura força bruta, ou tem-se trabalhado por força bruta, independentemente de como a fantasia seu algoritmo de hash é) Se não fosse este o caso, você já teria sido encontrada pelas próprias agências onde você trabalha, porque algo que confiável e segura seria uma certeza fogo maneira de fazer uma verificação de antecedentes seguro.

Respondeu 27/08/2009 em 02:06
fonte usuário

votos
0

Aqui está o mais próximo que eu vim a uma solução:

Assuma que existe uma função tal que doubleHash

doubleHash(a+doubleHash(b)) == doubleHash(b+doubleHash(a))

Alice gera um segredo 62 bit e acrescenta o código do país 2 bit para o fim de tudo, hashes e dá Bob doubleHash (a).

Bob faz a mesma coisa e dá Alice doubleHash (b).

Alice acrescenta o segredo original para o hash que Bob lhe deu, hashes-lo e publica-lo como doubleHash (a + doubleHash (b)).

Bob faz a mesma coisa e publica doubleHash (b + doubleHash (a)).

Se ambos os hashes corresponderem, então eles são do mesmo país. Por outro lado, se eles não corresponderem, em seguida, Bob não pode decifrar o hash, porque ele não sabe versa segredo e vice de Alice.

No entanto, tal esquema se baseia na existência de uma função doubleHash e eu não tenho certeza se é que isso é possível.

Respondeu 27/08/2009 em 00:28
fonte usuário

votos
0

Interessante.

Eu acho que, não importa qual o esquema, ele vai precisar de envolver um componente de falha aleatória. Isso é por causa das exigências conflitantes. Você precisaria de um esquema que, de vez em quando, mesmo quando eles estão do mesmo lado, não funciona. Porque se ele sempre trabalhou, eles iriam imediatamente ser capaz de determinar que eles não estão no mesmo lado.

Seu ponto de 'B' também é vaga. Você diz que não quer expor o que lado estão. Isso significa que a informação não pode apontar para especificamente um dos lados? Está tudo bem se Alice acha que Bob é a partir de qualquer um dos outros?

Além disso, você já tentou e-mail isso para a lista de discussão criptografia ? Pode obter uma melhor resposta lá. É interessante pensar sobre :)

Respondeu 27/08/2009 em 00:21
fonte usuário

votos
-1

RSA não funcionaria aqui? Cada nação conhece a sua chave privada, você publicar sua chave pública, e somente as nações que são os mesmos podem descriptografar as informações. Eu acho que a segunda pessoa saberia que o primeiro não é do mesmo lado como eles são, no entanto.

Hmm.

Respondeu 26/08/2009 em 23:57
fonte usuário

votos
-2

Como cerca de criptografia de chave pública ?

Respondeu 26/08/2009 em 23:59
fonte usuário

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more