Transferência inconsciente - Oblivious transfer

Na criptografia , um protocolo de transferência inconsciente ( OT ) é um tipo de protocolo no qual um remetente transfere uma das potencialmente muitas peças de informação para um receptor, mas permanece alheio quanto a que peça (se houver) foi transferida.

A primeira forma de transferência inconsciente foi introduzida em 1981 por Michael O. Rabin . Desta forma, o remetente envia uma mensagem ao receptor com probabilidade 1/2, enquanto o remetente permanece alheio se o receptor recebeu ou não a mensagem. O esquema de transferência inconsciente de Rabin é baseado no criptossistema RSA . Uma forma mais útil de transferência alheia, chamada transferência alheia 1-2 ou " transferência alheia 1 de 2", foi desenvolvida posteriormente por Shimon Even , Oded Goldreich e Abraham Lempel , a fim de construir protocolos para computação multipartidária segura . É generalizado para " transferência 1 de n inconsciente", em que o usuário obtém exatamente um elemento do banco de dados sem que o servidor saiba qual elemento foi consultado e sem que o usuário saiba nada sobre os outros elementos que não foram recuperados. A última noção de transferência inconsciente é um fortalecimento da recuperação de informação privada , na qual o banco de dados não é mantido privado.

Claude Crépeau mostrou que a transferência inconsciente de Rabin é equivalente a 1-2 transferência inconsciente.

Trabalhos posteriores revelaram que a transferência inconsciente é um problema fundamental e importante na criptografia. É considerado um dos problemas críticos da área, devido à importância das aplicações que podem ser construídas a partir dele. Em particular, é completo para computação multipartidária segura : isto é, dada uma implementação de transferência inconsciente, é possível avaliar com segurança qualquer função computável em tempo polinomial sem qualquer primitiva adicional.

Protocolo de transferência inconsciente de Rabin

No protocolo de transferência inconsciente de Rabin, o remetente gera um módulo público RSA N = pq onde p e q são grandes números primos e um expoente e relativamente primo para λ (N) = ( p  - 1) ( q  - 1). O remetente cifra a mensagem m como m ^e mod N .

1. O remetente envia N , e , e m ^e  mod  N para o receptor.
2. O receptor escolhe um x  módulo  N aleatório e envia x ²  mod  N ao remetente. Note-se que GCD ( x , N ) = 1 com esmagadora probabilidade, o que assegura que há 4 raízes quadradas de x ²  mod  N .
3. O remetente encontra uma raiz quadrada y de x ²  mod  N e envia y para o receptor.

Se o receptor encontra y não é nem x nem - x módulo N , o receptor será capaz de fator N e, portanto, descriptografar m ^e recuperar m (ver criptografia Rabin para mais detalhes). No entanto, se y for x ou - x  mod  N , o receptor não terá informações sobre m além da criptografia dele. Uma vez que cada módulo de resíduo quadrático N tem quatro raízes quadradas, a probabilidade de que o receptor aprenda m é 1/2.

1-2 transferência inconsciente

Em um protocolo de transferência esquecido 1-2, Alice, o remetente, tem duas mensagens m ₀ e m ₁ , e Bob, o receptor, tem um bit b , e o receptor deseja receber m _b , sem que o remetente aprenda b , enquanto o remetente deseja certifique-se de que o receptor receba apenas uma das duas mensagens. O protocolo de Even, Goldreich e Lempel (que os autores atribuem parcialmente a Silvio Micali ) é geral, mas pode ser instanciado usando criptografia RSA da seguinte maneira.

Alice				Prumo
Cálculo	Segredo	Público		Público	Segredo	Cálculo
Mensagens a serem enviadas	${\ displaystyle m_ {0}, m_ {1}}$
Gerar par de chaves RSA e enviar parte pública para Bob	${\ displaystyle d}$	${\ displaystyle N, e}$	${\ displaystyle \ Rightarrow}$	${\ displaystyle N, e}$		Receber chave pública
Gere duas mensagens aleatórias		${\ displaystyle x_ {0}, x_ {1}}$	${\ displaystyle \ Rightarrow}$	${\ displaystyle x_ {0}, x_ {1}}$		Receber mensagens aleatórias
					${\ displaystyle k, b}$	Escolha e gere aleatoriamente${\ displaystyle b \ in \ {0,1 \}}$${\ displaystyle k.}$
		${\ displaystyle v}$	${\ displaystyle \ Leftarrow}$	${\ displaystyle v = (x_ {b} + k ^ {e}) \ mod N}$		Calcule a criptografia de , cego com e envie para Alice ${\ displaystyle k}$${\ displaystyle x_ {b}}$
Um deles será igual , mas Alice não sabe qual. ${\ displaystyle k}$	${\ displaystyle {\ begin {alinhados} k_ {0} & = (v-x_ {0}) ^ {d} \ mod N \\ k_ {1} & = (v-x_ {1}) ^ {d} \ mod N \ end {alinhado}}}$
Envie ambas as mensagens para Bob		${\ displaystyle {\ begin {alinhado} m '_ {0} = m_ {0} + k_ {0} \\ m' _ {1} = m_ {1} + k_ {1} \ end {alinhado}}}$	${\ displaystyle \ Rightarrow}$	${\ displaystyle m '_ {0}, m' _ {1}}$		Receba ambas as mensagens
					${\ displaystyle m_ {b} = m '_ {b} -k}$	Bob descriptografa o, pois sabe qual selecionou anteriormente. ${\ displaystyle m '_ {b}}$${\ displaystyle x_ {b}}$

1. Alice tem duas mensagens, e deseja enviar exatamente uma delas para Bob. Bob não quer que Alice saiba qual ele recebe.${\ displaystyle m_ {0}, m_ {1}}$
2. Alice gera um par de chaves RSA, compreendendo o módulo , o expoente público e o expoente privado${\ displaystyle N}$${\ displaystyle e}$${\ displaystyle d}$
3. Ela também gera dois valores aleatórios e os envia a Bob junto com seu módulo público e expoente.${\ displaystyle x_ {0}, x_ {1}}$
4. Bob escolhe 0 ou 1 e seleciona o primeiro ou o segundo .${\ displaystyle b}$${\ displaystyle x_ {b}}$
5. Ele gera um valor aleatório e blinds por computação , que ele envia para Alice.${\ displaystyle k}$${\ displaystyle x_ {b}}$${\ displaystyle v = (x_ {b} + k ^ {e}) \ mod N}$
6. Alice não sabe (e espero que não possa determinar) qual de e Bob escolheu. Ela aplica ambos os seus valores aleatórios e apresenta dois valores possíveis para : e . Um deles será igual a e pode ser descriptografado corretamente por Bob (mas não por Alice), enquanto o outro produzirá um valor aleatório sem sentido que não revela nenhuma informação sobre .${\ displaystyle x_ {0}}$${\ displaystyle x_ {1}}$${\ displaystyle k}$${\ displaystyle k_ {0} = (v-x_ {0}) ^ {d} \ mod N}$${\ displaystyle k_ {1} = (v-x_ {1}) ^ {d} \ mod N}$${\ displaystyle k}$${\ displaystyle k}$
7. Ela combina as duas mensagens secretas com cada uma das chaves possíveis e , e as envia para Bob.${\ displaystyle m '_ {0} = m_ {0} + k_ {0}}$${\ displaystyle m '_ {1} = m_ {1} + k_ {1}}$
8. Bob sabe com qual das duas mensagens pode ser desvendado , então ele é capaz de calcular exatamente uma das mensagens${\ displaystyle k}$${\ displaystyle m_ {b} = m '_ {b} -k}$

Transferência 1 fora de n esquecido e transferência k fora de n esquecido

Um protocolo de transferência oblivious 1-out-of- n pode ser definido como uma generalização natural de um protocolo de transferência esquecido 1-out-of-2. Especificamente, um remetente tem n mensagens e o receptor tem um índice i , e o receptor deseja receber o i -ésimo entre as mensagens do remetente, sem que o remetente aprenda i , enquanto o remetente deseja garantir que o receptor receba apenas um dos as n mensagens.

A transferência oblivious 1-out-of- n é incomparável à recuperação de informação privada (PIR). Por um lado, a transferência alheia 1-out-of- n impõe um requisito de privacidade adicional para o banco de dados: a saber, que o receptor aprenda no máximo uma das entradas do banco de dados. Por outro lado, o PIR requer comunicação sublinear em n , enquanto a transferência 1-out-of- n esquecida não tem tal requisito. No entanto, presumir que o PIR de servidor único é uma suposição suficiente para construir a Transferência Oblivious 1-out-of-2.

O protocolo de transferência oblivious 1-out- of - n com comunicação sublinear foi construído pela primeira vez (como uma generalização do PIR de servidor único) por Eyal Kushilevitz e Rafail Ostrovsky . Construções mais eficientes foram propostas por Moni Naor e Benny Pinkas , William Aiello , Yuval Ishai e Omer Reingold , Sven Laur e Helger Lipmaa . Em 2017, Kolesnikov et al. , propôs um protocolo de transferência desatento 1-n eficiente que requer aproximadamente 4x o custo de uma transferência alheia 1-2 em configuração amortizada.

Brassard , Crépeau e Robert generalizaram ainda mais essa noção para k - n transferência inconsciente, em que o receptor obtém um conjunto de k mensagens da coleção de n mensagens. O conjunto de k mensagens pode ser recebido simultaneamente ("não adaptativamente"), ou podem ser solicitadas consecutivamente, com cada solicitação baseada em mensagens anteriores recebidas.

Transferência inconsciente generalizada

k - n Transferência esquecida é um caso especial de transferência esquecida generalizada, que foi apresentado por Ishai e Kushilevitz. Nesse cenário, o remetente tem um conjunto L de n mensagens, e as restrições de transferência são especificados por um conjunto Um dos subconjuntos permitidos de U . O receptor pode obter qualquer subconjunto das mensagens em U que aparece na coleção A . O remetente deve permanecer alheio à seleção feita pelo receptor, enquanto o receptor não pode aprender o valor das mensagens fora do subconjunto de mensagens que escolheu obter. A coleção A é monótona decrescente, no sentido de que está fechada sob contenção (ou seja, se um dado subconjunto B está na coleção A , todos os subconjuntos de B também estão ). A solução proposta por Ishai e Kushilevitz usa as invocações paralelas de 1-2 transferência inconsciente enquanto faz uso de um modelo especial de protocolos privados. Mais tarde, outras soluções baseadas no compartilhamento secreto foram publicadas - uma por Bhavani Shankar, Kannan Srinathan e C. Pandu Rangan , e outra por Tamir Tassa.

Origens

No início dos anos 70, Stephen Wiesner introduziu um primitivo chamado multiplexação em seu artigo seminal "Codificação Conjugada", que foi o ponto de partida da criptografia quântica . Infelizmente, demorou mais de dez anos para ser publicado. Embora esse primitivo fosse equivalente ao que mais tarde foi chamado de transferência 1–2 inconsciente , Wiesner não viu sua aplicação à criptografia.

Transferência inconsciente quântica

Protocolos para transferência inconsciente podem ser implementados com sistemas quânticos . Em contraste com outras tarefas na criptografia quântica , como distribuição de chave quântica , foi demonstrado que a transferência esquecida quântica não pode ser implementada com segurança incondicional, ou seja, a segurança dos protocolos de transferência esquecida quântica não pode ser garantida apenas pelas leis da física quântica .

Veja também

• k-anonimato
• Cálculo multipartidário seguro
• Prova de conhecimento zero
• Recuperação de informação privada

Referências

• ^ 0. Stephen Wiesner, "Conjugate coding", Sigact News, vol. 15, não. 1, 1983, pp. 78-88; manuscrito original escrito por volta de 1970.
• ^ 1. Michael O. Rabin. "Como trocar segredos com transferência alheia." Relatório Técnico TR-81, Laboratório de Computação Aiken, Universidade de Harvard, 1981.Escrita à mão digitalizada + versão digitada no arquivo eprint.iacr.org. Versão digitada disponível napágina inicial da Dousti.
• ^ 2. S. Even, O. Goldreich e A. Lempel, "A Randomized Protocol for Signing Contracts",Communications of the ACM, Volume 28, Issue 6, pg. 637–647, 1985.Artigo na página de Catuscia Palamidessi
• ^ 3. Claude Crépeau. "Equivalência entre dois sabores de transferência inconsciente". Em Advances in Cryptology: CRYPTO '87, volume 293 de Lecture Notes in Computer Science, páginas 350–354. Springer, 1988
• ^ 4. Joe Kilian. "Founding Cryptography on Oblivious Transfer", Proceedings, 20th Annual ACM Symposium on the Theory of Computation (STOC), 1988. Artigono portal ACM (assinatura necessária)
• ^ 5. Gilles Brassard,Claude CrépeaueJean-Marc Robert. "Divulgação de segredos tudo ou nada." Em Advances in Cryptology: CRYPTO '86, volume 263 de LNCS, páginas 234–238. Springer, 1986.
• ^ 6. Moni NaoreBenny Pinkas. "Transferência alheia com consultas adaptativas." Em Advances in Cryptology: CRYPTO '99, volume 1666 de LNCS, páginas 573–590. Springer, 1999.
• ^ 7. Yuval Ishai e Eyal Kushilevitz. "Protocolos privados de mensagens simultâneas com aplicativos." Em Proc. of ISTCS'97, IEEE Computer Society, páginas 174-184, 1997.
• ^ 8. Bhavani Shankar, Kannan Srinathan e C. Pandu Rangan. "Protocolos alternativos para transferência inconsciente generalizada". Em Proc. de ICDCN'08, LNCS 4904, páginas 304–309, 2008.
• ^ 9. Tamir Tassa. "Transferência inconsciente generalizada por compartilhamento secreto". Designs, Codes and Cryptography, Volume 58: 1, páginas 11–21, janeiro de 2011.Artigo em openu.ac.il
• ^ 10. Moni NaoreBenny Pinkas(1990). Avaliação polinomialesquecida 31º STOC
• ^ 11. William Aiello,Yuval IshaieOmer Reingold(2001)Priced Oblivious Transfer: How to Sell Digital GoodsEUROCRYPT '01 Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, pages 119–135
• ^ 12. Sven Laur e Helger Lipmaa (2007). "Um novo protocolo para divulgação condicional de segredos e suas aplicações". Em Jonathan Katz e Moti Yung, editores,ACNS,Lecture Notes in Computer Science 4521: 207–225. Springer, Heidelberg.
• ^ 13. Vladimir Kolesnikov, Ranjit Kumaresan, Mike Rosulek e Ni Trieu (2017). "Prf esquecido em lote eficiente com aplicativos para interseção de conjunto privado". Em Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers e Shai Halevi, editores, ACM CCS 16, páginas 818-829. ACM Press, outubro de 2016.
• ^ 14. Giovanni Di Crescenzo, Tal Malkin, Rafail Ostrovsky: A Recuperação de Informação Privada de Banco de Dados Único Implica Transferência Esquecida. EUROCRYPT 2000: 122-138
• ^ 15. Eyal Kushilevitz, Rafail Ostrovsky: A replicação NÃO É Necessária: SINGLE Database, Computationally-Private Information Retrieval. FOCS 1997: 364-373

links externos

• Coleção de links da Web de Helger Lipmaa sobre o assunto