aplicações práticas de algoritmos de encriptação homomórfica?

Question

Parece que há havia coisas interessantes acontecendo em criptografia: a primeira homomorphic criptografia esquema apareceu recentemente ( explicação , HT ). Grosso modo, é uma forma de codificação x em f(x) de tal forma que você pode calcular f(x+y) facilmente sabendo f(x) e f(y) mesmo que você não pode facilmente restaura x e y (e mesmo para f(x*y)).

O que são aplicações práticas para os regimes deste tipo (uma vez que sua segurança foi estabelecida)? Para mim, parece que eles poderiam fazer escrevendo algoritmos para manipulação de dados privados muito mais fácil.

Aqui estão meus pensamentos :

1. votação eletrônica
2. a verificação da integridade dos dados privados
3. há uma chance de que iria ajudar a privacidade em geral?

Exemplo : Eu tenho contas com Bancos A, B, C. Entidade X quer confirmar Eu tenho total de mais de US $ 1000; ele ficaria feliz em aceitar declarações de Banks A, B, C ou D, mas infelizmente eu não tenho dinheiro suficiente em qualquer única conta. Bank A criptografa as informações sobre os meus US $ 500 dólares com minha chave pública; Da mesma forma, Banks B e C encriptar a informação que eu tenho $ 200 e $ 300 respectivamente. Eles enviam estes dados para X que os adiciona a algum número que eu demonstro ser de fato criptografado $ 1000 (criptografando $ 1000 com minha chave pública e demonstrando que o resultado é o mesmo). Eu provei algo sem revelar a X quanto dinheiro eu tenho em cada conta.

Outro exemplo : Bons cidadãos X_1, ..., X_n estão se unindo para selecionar um dos dois candidatos, um dos quais é liber latte-bebendo A l enquanto outro é um B ible-bearing amante da arma (todos os nomes são fictícios). Eles decidem que querem o voto a ser privado, mas rápido. Eles enviam seus votos no (1, vote_A, vote_B, vote_None) formato vetorial criptografada para a Comissão Eleitoral que lhes acrescenta publicamente e obtém o resultado na (count, count_A, count_B, count_None) formulário. Depois de verificar que count = count_A + count_B + count_None, os funcionários declarar a vitória de um dos candidatos, após o que a eleição seja declarada inválida pelo juiz por algum motivo não relacionado com o voto eletrônico e lutaram na corte para os próximos 10 anos, mas, hey, isso não é o meu problema de qualquer maneira.

Notas : - Eu acredito que aqueles exemplo particular foi possível com RSA mesmo antes, uma vez que exige apenas homomorphicity em uma operação. A esperança é que podemos ter coisas radicalmente mais interessantes com mais operações - por isso, venha com exemplos

• Em particular, gostaria de ver respostas que contenham código e / ou desenvolvimento de quadros que têm uma chance de ser utilizado na prática, a razão de ser, portanto, não é uma placa de ciência da computação discussão teórica.

• O algoritmo homomorphic, para repetir o que foi dito abaixo nos comentários, permite criar um programa que iria gerenciar dados sem conhecê-los. Infelizmente, os tipos de programas são um pouco limitadas:. Você não pode ter if (x=0) ... porque x é criptografada, e cada passo é muito lento (há algumas treliças envolvidos)

Answer 1

Aqui está uma foto selvagem no escuro:

Nós estamos pensando sobre como proteger o texto original da pessoa que faz o cálculo sobre ele. Mas e se o objetivo era proteger tanto o texto simples eo algoritmo?

Tome-se, por exemplo, máquinas de ressonância magnética. A parte mais cara do aparelho de ressonância magnética é o algoritmo no qual a máquina analisa os dados de ressonância magnética. Devido a isso, eles são fortemente protegido por dispositivos de hardware concebidos para destruir o programa antes de permitir-se a ser examinados por um partido não confiável (ou qualquer um para essa matéria).

Se um fabricante de MRI poderia centralizar computação de dados de MRI, seria uma redução fantástica em risco de perder seu algoritmo. No entanto, as leis de impedi-los de acessar dados do paciente privado.

Assim! encriptação homomórfica permite que isso aconteça onde os dados do paciente e o algoritmo são ambos protegidos. O 'totalmente' encriptação homomórfica (isto é, a indução de uma homomorphism anel sobre os dados codificados) permite um conjunto muito mais eficiente e robusta de cálculos para operar nos dados.

Answer 2

Como um geek PKI, se o cryptofunction homomorphic foram também um sistema de chave assimétrica, então você tem algumas possibilidades muito interessantes no mundo da assinatura. O assinante poderia assinar a mensagem e um destinatário pode retransmitir parte da mensagem e da parte correspondente do texto cifrado para um terceiro.

Em notação de função, que seria:

Signs Usuário:

sinal (texto simples, a chave privada) = texto cifrado

e transmite:

send (texto simples, texto cifrado, certificado)

aplicativo obtém segmentos:

texto simples = desiredPlaintext + otherPlaintext

e calcula a mesma conversão de texto cifrado, usando algo como:

se cifrado :: texto simples, em seguida ?? :: desiredPlaintext

para encontrar desiredCiphertext

Aplicação frente desejado conteúdo apenas para serviço externo:

send (desiredPlaintext, desiredCiphertext, certificado)

E o serviço pode verificar esta mensagem como se o usuário tivesse enviado diretamente.

Isso depende do algoritmo de hash usado para comprimir o texto plano também ser homomorphic. Se não, isso não vai funcionar ... ou que nenhum algoritmo de hash é aplicada.

Isto poderia ser muito útil em casos onde você quer um serviço externo para fazer algo em resposta a uma solicitação do usuário assinado, mas você não quer expor tudo o que o usuário enviado para esse serviço externo.

Um exemplo seria um sistema de pacotes de pedidos simples - eu envio uma aplicação web um pedido para comprar uma coleção de itens. Para ser super-secure assinar uma ordem de compra que confirma que eu quero (e promessa de pagar para) algumas # de itens, enviados para algum local específico, por alguma data específica, e com algumas informações de pagamento específico. Agora .. o aplicativo web vai querer ter várias coisas acontecem:

• Finanças precisa carregar a minha conta, e começar a receber um pagamento de mim
• necessidades de inventário para puxar os itens de estoque, ou lidar com qualquer fora de problemas de ações
• Shipping precisa receber de inventário e mover as coisas para o meu endereço

Não há nenhuma razão para Inventory ou envio de saber sobre como eu pagar minha conta. E pode haver nenhuma razão para o financiamento de saber o meu endereço de entrega ... Em cada caso, as mudanças desiredPlaintext e desiredCiphertext, dependendo de quem o receptor é. Isto é ainda mais potente em um sistema como o Amazon.com livros usados, onde a entidade que eu comprei de (Amazon) é diferente da entidade prestadora do item (o vendedor de livros usados).

Lendo o jornal sobre criptografia rede, soa mais como um sistema de chave simétrica ... que não é tão propício para assinar mensagens.

Sobre o conceito de "nunca diga nunca", eu não diria que foi razoável para usá-lo para aplicações de privacidade. Mas parece distintamente problemático que você pode encontrar várias maneiras de obter a partir de texto cifrado para texto simples.

Answer 3

A maior aplicação de criptografia homomorphic seria em mineração de dados, IMHO. O uso deste algo poderia resolver os problemas de privacidade e descoberta tendência ao mesmo tempo. Por exemplo, digamos que sua empresa hospeda-lo de informações de vendas em algum provedor SAS. Agora, esse provedor poderia dar-lhe serviços de mineração de dados sofisticados, sem você ter que revelar a sua informação real. Basicamente, você seria capaz de enviar seus dados para um provedor de computação, ter-lhe utilizar os seus ciclos de CPU para computar em seu nome, e enviar-lhe as costas de dados criptografados. Isso seria verdadeiramente fantástico para as empresas que estão olhando para mover para a nuvem sistemas baseados, mas tem privacidade preocupações / IP impedindo-os de fazê-lo.

Outra aplicação potencial, em um menor e um nível mais pessoal, seria no tratamento de todos os tipos de dados financeiros. exemplo de Ilya estendida pode aplicar a apresentação de declarações fiscais por seu contador sem realmente ver suas informações financeiras, cartões de crédito processamento etc.

No entanto, eu segurar minha emoção até o esquema é rigorosamente testados e considerados seguros. algos de criptografia têm o hábito notório de falhar o seu primeiro teste, indo para uma revisão e repetindo o ciclo até que eles são "certificado" por alguma autoridade governamental.

Answer 4

Você pode estar interessado em ver take sim retumbante negativo de Bruce Schneier em criptografia homomorphic em:

http://www.schneier.com /blog/archives/2009/07/homomorphic_enc.html?nc=11

Answer 5

Eu não sei o quão caro o cálculo f(x) + f(x) vai ser, mas talvez ele poderia ser usado como uma forma de implementar banco de dados criptografado.

Você pode armazenar 1 milhão de linhas de alguns dados criptografados como f(x_1), f(x_2), ... f(x_n). Você poderia fazer

SELECT SUM(x)
FROM Foo
WHERE y = 'some value'

O que poderia ser calculado fazendo primeiro SUM(f(x)) seguida, decifrando-lo para SUM(x).

Answer 6

Com isso, você pode executar um circuito não-recursiva arbitrária de profundidade limitada, assim, dado um comprimento de chave logarítmica você pode executar um algoritmo NC1 (circuito basicamente um feed-forward Boolean).

Então, como você pode usar isso?

Vamos olhar para Mapa / Reduzir um esquema de circuito e redução ao longo de um conjunto de entradas.

Primeiro os dados:

Nós provavelmente não deseja que o cliente tem que ter criptografado todos os dados que vamos procurar, para que possa fornecer uma criptografada 1 e um criptografado 0 para o servidor, e deixá-lo usar a estrutura do anel de construção arbitrário inteiros codificados para nós, ou podemos usar apenas aqueles diretamente como bits. Dessa forma, o servidor pode apresentar alguns ou todos os dados que estão procurando através. Para inteiros pode construí-los por aritmética camponês (duplo ou de casal e adicione 1 para cada bit), para bits ele apenas fornece o bit apropriado criptografada.

Nós podemos misturar e combinar valores booleanos e inteiros em nossos projetos, a obtenção de um if / then / else (que exige a avaliação de ambos os ramos estilo SIMD), avaliando cond * então + (1 - cond) * pessoa usando 1 como verdadeira e 0 como falso em cond, para que possa fugir com usando o construído em aritmética de seu anel para fazer seus circuitos mais superficial.

Por outro lado, podemos ter pré-criptografado alguns dados, bem como, mas desde que você terá que manter a reciclagem do mesmo conjunto chave para usá-lo, isso se torna seriamente complicado de acertar.

Então, agora temos os dados do servidor fornecido. Agora, criptografar as coisas que você não deseja que o servidor sabe, como o que é que você está procurando, e tê-los alimentar que no circuito nos pontos de direito, bem como, dizer como uma entrada extra para a sua função de mapa.

Devemos ser capazes de mapear um circuito NC1-like arbitrário sobre cada entrada para extrair um campo, multiplicam alguns valores e, geralmente, mapeá-lo em um formulário que você pode reduzir de forma barata.

Em seguida, reduzir os fragmentos usando mais pequenos circuitos, tais como por um simples monóide que tem um resultado bem delimitada-tamanho. (Ou seja, você mapear para obter um bit que indica se você encontrar um fósforo, e então você reduzir contando os bits com um circuito de adição pequeno)

Uma vez que você só precisa construir o circuito lógico e simular sua execução no esses bits criptografados no anel homomorphic, você provavelmente poderia implementá-lo de forma relativamente rápida, usando uma pequena DSL, ou seja, algo como Lava em Haskell, supondo que você tem a criptografia homomorphic peças em linha reta.

Além disso, mantenha em mente que cada porta é seriamente caro para executar.

Assim, para resumir,

1. Dar ao servidor um criptografados 1 e 0 e qualquer metainfo criptografado para o seu mapa e reduzir funções.
2. Para cada ponto de dados, que codificam para o seu anel homomórfica, alimentar o seu circuito mapa tanto a entrada e a informação de meta para obter um valor adequado para a redução.
3. Em uma árvore binária equilibrada (ou outro acordo equilibrado para minimizar a altura da árvore), aplicar a sua operação de redução para a saída do seu circuito e qualquer mapa metainfo criptografada.
4. mão o resultado para o cliente para a descodificação

Answer 7

O problema com o algoritmo de criptografia homomorphic existente é que você só pode executar um circuito polylogarithmic (NC1) com ele, o que exclui quase nada de interessante através de algoritmos.

Além disso, não parece que a complexidade da codificação é de forma alguma inferior a complexidade da execução do circuito polylogarithmic mesmo, para que você não pegou qualquer trabalho livre à primeira vista, a menos que você faça algo particularmente complicado com -lo.

Answer 8

A computação distribuída, como o SETI @ home, projectos de dobramento de proteínas, etc., são bastante populares porque alavancar a doação de tempo de CPU e eletricidade a partir de milhares de usuários. Ainda mais interessante seria um modelo onde as pessoas podem receber o pagamento para fornecer esses recursos para projetos comerciais. No entanto, nenhuma empresa responsável quer enviar seus dados para milhares de computadores anônimos para o processamento. Se você pode aplicar de forma eficiente algoritmos aos dados criptografados, torna-se possível delegar o processamento a qualquer pessoa sem uma relação de confiança.

Answer 9

O voto eletrônico é realmente uma aplicação prática de criptografia homomorphic, ou seja, http://heliosvoting.org/

Answer 10

Algumas aplicações bancárias talvez se tornar mais rápido com a ajuda de homomórfica Encryption.

Eles podem realizar operações com dados criptografados na nuvem, em vez de levá-lo de nuvem em local e colocar novamente em nuvem. Também não há necessidade de criptografar-descriptografar-executar gasoduto operações de criptografar, criptografar-executar operações seria OK.