Recuperação de informação privada - Private information retrieval

Na criptografia , um protocolo de recuperação de informação privada (PIR) é um protocolo que permite a um usuário recuperar um item de um servidor que possui um banco de dados sem revelar qual item foi recuperado. PIR é uma versão mais fraca da transferência alheia 1-out-of- n , onde também é necessário que o usuário não obtenha informações sobre outros itens do banco de dados.

Uma maneira trivial, mas muito ineficiente de obter o PIR, é o servidor enviar uma cópia inteira do banco de dados ao usuário. Na verdade, este é o único protocolo possível (na configuração clássica ou quântica ) que dá ao usuário privacidade teórica das informações para sua consulta em uma configuração de servidor único. Existem duas maneiras de resolver esse problema: tornar o servidor limitado computacionalmente ou assumir que há vários servidores não cooperantes, cada um com uma cópia do banco de dados.

O problema foi introduzido em 1995 por Chor, Goldreich, Kushilevitz e Sudan no cenário da teoria da informação e em 1997 por Kushilevitz e Ostrovsky no cenário computacional. Desde então, soluções muito eficientes foram descobertas. O PIR de banco de dados único (computacionalmente privado) PIR pode ser obtido com comunicação constante (amortizada) e o PIR de banco de dados k (teoria da informação) pode ser feito com comunicação. ${\ displaystyle n ^ {O \ left ({\ frac {\ log \ log k} {k \ log k}} \ right)}}$

Avanços em PIR computacional

O primeiro esquema PIR computacional de banco de dados único a atingir complexidade de comunicação menor do que foi criado em 1997 por Kushilevitz e Ostrovsky e alcançou complexidade de comunicação de para qualquer , onde é o número de bits no banco de dados. A segurança de seu esquema foi baseada no bem estudado problema de residuosidade Quadrática . Em 1999, Christian Cachin, Silvio Micali e Markus Stadler alcançaram a complexidade da comunicação polilogarítmica . A segurança de seu sistema é baseada na suposição de esconder Phi . Em 2004, Helger Lipmaa atingiu a complexidade da comunicação log-quadrada , onde é o comprimento das cordas e é o parâmetro de segurança. A segurança de seu sistema se reduz à segurança semântica de um criptossistema aditivamente homomórfico de comprimento flexível como o criptossistema Damgård-Jurik . Em 2005, Craig Gentry e Zulfikar Ramzan alcançaram a complexidade de comunicação do log-quadrado que recupera bits do log-quadrado (consecutivos) do banco de dados. A segurança de seu esquema também se baseia em uma variante da suposição de ocultação de Phi. A taxa de comunicação foi finalmente levado para baixo para por Aggelos Kiayias , Nikos Leonardos , Helger Lipmaa , Kateryna Pavlyk , Qiang Tang , em 2015. ${\ displaystyle n}$${\ displaystyle n ^ {\ epsilon}}$${\ displaystyle \ epsilon}$${\ displaystyle n}$${\ displaystyle O (\ ell \ log n + k \ log ^ {2} n)}$${\ displaystyle \ ell}$${\ displaystyle k}$${\ displaystyle 1}$

Todos os protocolos PIR computacionais de comunicação sublinear anteriores exigiam complexidade computacional linear de operações de chave pública. Em 2009, Helger Lipmaa projetou um protocolo PIR computacional com complexidade de comunicação e computação de pior caso de operações de chave pública. As técnicas de amortização que recuperam bits não consecutivos foram consideradas por Yuval Ishai , Eyal Kushilevitz , Rafail Ostrovsky e Amit Sahai . ${\ displaystyle \ Omega (n)}$${\ displaystyle O (\ ell \ log n + k \ log ^ {2} n)}$${\ displaystyle O (n / \ log n)}$

Conforme mostrado por Ostrovsky e Skeith, os esquemas de Kushilevitz e Ostrovsky e Lipmaa usam ideias semelhantes baseadas na criptografia homomórfica . O protocolo de Kushilevitz e Ostrovsky é baseado no criptossistema Goldwasser-Micali, enquanto o protocolo de Lipmaa é baseado no criptossistema Damgård-Jurik .

Avanços na teoria da informação PIR

Alcançar a segurança teórica da informação requer a suposição de que existem vários servidores não cooperantes, cada um com uma cópia do banco de dados. Sem essa suposição, qualquer protocolo PIR teoricamente seguro de informações requer uma quantidade de comunicação que é pelo menos do tamanho do banco de dados n . Os protocolos PIR de vários servidores tolerantes a servidores sem resposta ou mal-intencionados / em conluio são chamados de robustos ou robustos bizantinos, respectivamente. Essas questões foram consideradas pela primeira vez por Beimel e Stahl (2002). Um sistema ℓ-servidor que pode operar onde apenas k dos servidores respondem, ν dos servidores respondem incorretamente e que pode suportar até t servidores em conluio sem revelar a consulta do cliente é chamado de " t -privado ν-Bizantino robusto k -out -of-ℓ PIR "[DGH 2012]. Em 2012, C. Devet, I. Goldberg e N. Heninger (DGH 2012) propuseram um esquema otimamente robusto que é robusto ao bizantino para o qual é o valor máximo teórico. É baseado em um protocolo anterior de Goldberg que usa o compartilhamento secreto de Shamir para ocultar a consulta. Goldberg lançou uma implementação C ++ no Sourceforge . ${\ displaystyle \ nu <kt-1}$

Relação com outras primitivas criptográficas

Funções unilaterais são necessárias, mas não são suficientes, para recuperação de informação privada computacionalmente única de banco de dados não trivial (isto é, com comunicação sublinear). Na verdade, tal protocolo foi provado por Giovanni Di Crescenzo , Tal Malkin e Rafail Ostrovsky para implicar transferência alheia (veja abaixo).

A transferência alheia , também chamada de PIR simétrico, é um PIR com a restrição adicional de que o usuário não pode aprender nenhum item além do solicitado. É denominado simétrico porque tanto o usuário quanto o banco de dados têm um requisito de privacidade.

As funções de hash criptográficas resistentes à colisão estão implícitas em qualquer esquema PIR computacional de uma rodada, conforme mostrado por Ishai, Kushilevitz e Ostrovsky.

Variações PIR

A motivação básica para a Recuperação de informações privadas é uma família de protocolos de duas partes em que uma das partes (o remetente ) possui um banco de dados e a outra parte (o receptor ) deseja consultá-lo com certas restrições e garantias de privacidade. Portanto, como resultado do protocolo, se o receptor quiser o i-ésimo valor no banco de dados, ele deve aprender a i-ésima entrada, mas o remetente não deve aprender nada sobre i . Em um protocolo PIR geral, um remetente computacionalmente ilimitado não pode aprender nada sobre i, portanto, a privacidade é teoricamente preservada. Desde que o problema PIR foi colocado, diferentes abordagens para sua solução foram buscadas e algumas variações foram propostas.

Um protocolo CPIR (Computationally Private Information Retrieval) é semelhante a um protocolo PIR: o receptor recupera um elemento escolhido por ele da base de dados do remetente, de forma que o remetente não obtém nenhum conhecimento sobre qual elemento foi transferido. A única diferença é que a privacidade é protegida contra um remetente polinomialmente limitado.

Um protocolo CSPIR (Computationally Symmetric Private Information Retrieval) é usado em um cenário semelhante no qual um protocolo CPIR é usado. Se o remetente possui um banco de dados, e o receptor deseja obter o i-ésimo valor neste banco de dados, no final da execução de um protocolo SPIR, o receptor não deve ter aprendido nada sobre os valores no banco de dados além do i-ésimo 1.

Implementações PIR

Vários esquemas PIR computacional e PIR teórico da informação na literatura foram implementados. Aqui está uma lista incompleta:

• MuchPIR é uma implementação PIR de Teoria da Informação como uma extensão Postgres C / C ++. [GitHub, 2021]
• SealPIR é uma implementação rápida de CPIR [ACLS 2018].
• Popcorn é uma implementação PIR adaptada para mídia [GCMSAW 2016].
• Percy ++ inclui implementações de [AG 2007, DGH 2012, CGKS 1998, Goldberg 2007, HOG 2011, LG 2015].
• RAID-PIR é uma implementação do esquema ITPIR de [DHS 2014].
• XPIR é uma implementação rápida de CPIR [ABFK 2014].
• upPIR é uma implementação ITPIR [Cappos 2013].

Notas

Veja também

• k-anonimato
• Código decodificável localmente

Referências

links externos

• Links da web de Helger Lipmaa sobre transferência alheia e PIR
• Site de William Gasarch sobre PIR, incluindo artigos de pesquisa
• Site de Rafail Ostrovsky contendo artigos e pesquisas PIR