O comprometimento de bits gera transferência inconsciente no modelo de segurança teórico da informação?

16

Suponha que você tenha dois participantes arbitrariamente poderosos que não confiam um no outro. Eles têm acesso ao comprometimento de bits (por exemplo, envelopes selados contendo dados que um jogador pode entregar ao outro, mas que não podem ser abertos até que o primeiro jogador dê uma chave ao segundo). Você pode usar isso para criar um protocolo de transferência inconsciente. Isso é verdade mesmo que os jogadores concordem em abrir todos os envelopes no final para detectar trapaças (por exemplo, depois que a mão de pôquer é jogada, todos concordam em revelar suas cartas)?

Suponho que você não possa obter transferência inconsciente por comprometimento de bits, porque a transferência inconsciente é criptograficamente universal e não consigo encontrar referências que digam comprometimento em bits, mas existe uma prova em algum lugar de que você não pode fazê-lo?

Finalmente, alguém olhou para o problema se os jogadores são quânticos?

reference-request cr.crypto-security Peter Shor
fonte
2
Em um comentário sobre uma pergunta sobre mathoverflow, afirma-se que a transferência inconsciente quântica é equivalente ao comprometimento quântico de bits (com referências): mathoverflow.net/questions/32801/… .
M. Alaggan
4
Esses dois documentos mostram que o comprometimento de bits quânticos incondicionalmente seguro é impossível. Se você pudesse fazer uma transferência inconsciente quântica, isso implicaria que você poderia fazer um comprometimento quântico de bits, para que eles também mostrem uma transferência inconsciente e quântica incondicionalmente segura também é impossível. O que estou me perguntando é se você recebe um compromisso de bit (como uma caixa preta) que funciona para protocolos quânticos, você também pode fazer uma transferência inconsciente para protocolos quânticos.
Peter Shor
3
Talvez seja necessário um pouco mais de experiência. Eu acho que tenho um esquema bastante simples que, dado um pouco comprometido, o utiliza para obter uma transferência inconsciente em um protocolo quântico. Eu queria (1) saber quais eram as provas clássicas de que a transferência inconsciente é estritamente mais poderosa, garantir que elas não se aplicassem ao caso quântico e (2) saber se alguém já havia observado isso antes. A literatura sobre transferência quântica inconsciente e comprometimento de bits é difícil de pesquisar porque várias provas de segurança se desfizeram quando Mayers e Lo e Chau provaram seu teorema de proibição.
Peter Shor
4
Pesquisando um pouco mais na literatura, há uma prova de transferência de alívios pouco ==> no regime quântico em um artigo de 1991 de Bennett, Brassard, Crépeau e Skubiszewska ( springerlink.com/content/k6nye3kay7cm7yyx ), então isso é conhecido.
quer
2
@M. Alaggan: Deixe-me pedir desculpas por descartar seu comentário acima tão abruptamente. O autor do comentário do MathOverflow a que você se referiu provavelmente sabia que eles eram equivalentes e, de fato, esse comentário me colocou na trilha bibliográfica que levou à prova de referência que encontrei no meu comentário acima. Então, muito obrigado.
Peter Shor

Respostas:

14

Não, o compromisso tem uma complexidade estritamente menor que a OT. Penso que uma maneira fácil de ver isso é a abordagem adotada em Complexidade de problemas de computação multipartidária: o caso da avaliação simétrica de função segura de duas partes por Maji, Prabhakaran, Rosulek no TCC 2009 (exoneração de responsabilidade: auto-promoção!). Nesse artigo, temos um resultado que caracteriza o que você pode fazer com acesso ao comprometimento ideal no modelo de UC com segurança estatística.

πππ

Outra maneira de ver isso é através de Impagliazzo-Rudich . Se você possui partes ilimitadas computacionalmente e um oráculo aleatório, pode se comprometer (já que tudo o que precisa são de funções unidirecionais), mas não pode fazer coisas como o acordo principal e, portanto, o OT.

mikero
fonte
11
@ Mikero: é uma prova muito boa e simples.
quer
Para o AT de bits clássicos (isto é, mundo ideal clássico), o argumento será discutido para protocolos / adversários quânticos. Se o OT manipular qbits, pode haver complicações. A etapa "não é tão trivial quanto parece, mas não é difícil" envolve dizer que o WLOG, o simulador, sempre usa a entrada fornecida pelo ambiente. Esta é uma propriedade do OT que deve ser mostrada (se o simulador não enviasse o que foi fornecido, as saídas seriam incorretas com probabilidade perceptível, portanto, a simulação não seria adequada) e precisariam ser re-argumentadas se o ambiente puder fornecer / recebo qbits do OT.
Mikero
11
@ Mikero: Eu não entendo o seu comentário anterior. O que significa para o AT não manipular qubits? Você quer dizer que as duas partes apenas se comunicam com bits clássicos, mas podem ter processadores quânticos? Isso se deve ao fato de não existir um protocolo seguro teórico da informação para o AT, mesmo com pouco comprometimento.
Peter Shor
Estou pensando se um "protocolo quântico de OT" significa OT clássico (a funcionalidade do OT conhece apenas bits) com um protocolo quântico possível ou um OT no qual o ambiente conhece qubits e o OT envia / recebe qubits. No primeiro caso, acho que o mesmo argumento passa sem modificações. Presumivelmente, você quer dizer o último caso. Então, se realmente houver um contra-exemplo no mundo quântico, isso significaria que o AT dos qubits não tem a propriedade de que a simulação do WLOG mapeia adversários do mundo real honestos, mas curiosos, para adversários ideais honestos, mas curiosos. Interessante!
Mikero
11
Se entendi sua pergunta corretamente, tanto Bennett et al. paper e minha prova são para o AT clássico, com mensagens quânticas entre os participantes para implementar o AT.
Peter Shor
7

No caso quântico, o primeiro protocolo a construir transferência alheia (clássica) com base no comprometimento de bits (clássica) usando um protocolo quântico foi proposto em 1991 por Bennett, Brassard, Crépeau e Skubiszewska (http://www.springerlink.com/content / k6nye3kay7cm7yyx /), mas uma prova completa de segurança foi dada apenas recentemente por Damgaard, Fehr, Lunemann, Salvail e Schaffner em http://arxiv.org/abs/0902.3918

Para uma extensão da computação multipartidária e uma prova na estrutura universal de compabilidade, consulte o trabalho de Unruh: http://arxiv.org/abs/0910.2912

Christian Schaffner
fonte