Limite de sistemas de criptografia totalmente homomórficos

9

recentemente, Craig Gentry publicou o primeiro esquema de criptografia de chave pública (sobre o espaço de texto sem formatação {0,1}) que é totalmente homomórfico, o que significa que é possível avaliar de forma eficiente e compacta AND e XOR em textos simples criptografados sem o conhecimento da chave de descriptografia secreta.

Gostaria de saber se existe alguma maneira óbvia de transformar esse sistema de criptografia de chave pública em um sistema de criptografia de chave pública de limite, para que todos possam criptografar AND e XOR, mas a descriptografia só é possível se algumas (todas) pessoas que compartilham a chave se unirem.

Eu estaria interessado em alguma idéia sobre esse assunto.

desde já, obrigado

fw


fonte
2
Isso é mais uma curiosidade e não se aplica diretamente à sua pergunta. Curiosamente, uma vez que o esquema é totalmente homomórfico, uma parte pode homomorficamente e recursivamente criar pares de chave pública-privada.
Ross Snider
11
Mais perto de responder à sua pergunta, mas ainda não o suficiente para postar como resposta: o FHE é inteiramente novo - existem apenas dois esquemas propostos (ambos da Gentry). Que eu saiba, nenhum trabalho foi publicado no Threshold FHE. Pode, no entanto, haver trabalhos realizados em sistemas parcialmente homomórficos (como Paillier, Goldwasser, etc.). Eu começaria a procurar lá para ver se os resultados podem ser facilmente 'portados' para o FHE.
Ross Snider

Respostas:

6

Um novo artigo de Steven Myers, Mona Sergi e Abhi Shelat sobre eprint, " Limiar de criptografia totalmente homomórfica e computação segura ", reivindica um esquema de criptografia de limiar totalmente homomórfico.

De seu resumo:

...

Gentry [Gen09a] mostra como combinar as duas idéias com criptografia totalmente homomórfica, a fim de construir um protocolo multipartidário seguro que permita avaliar uma função usando comunicação independente da descrição do circuito e computação polinomial em. Este artigo aborda as principais desvantagens da abordagem de Gentry: eliminamos o uso de métodos que não sejam da caixa preta que são inerentes ao compilador de Naor e Nissim.ff|f|

Para fazer isso, mostramos como modificar a construção de criptografia totalmente homomórfica de van Dijk et al. [vDGHV10] para ser o limite de esquemas de criptografia totalmente homomórficos.

...

No total, construímos o primeiro protocolo de computação multipartidário de caixa preta que permite a avaliação de uma função usando comunicação independente da descrição do circuito deff .

user686
fonte
3

Não conheço as especificidades do esquema de Gentry, mas todos os outros sistemas de criptografia de limite requerem dois homomorfismos (o terceiro está implícito) relacionados às chaves pública e secreta:

  1. KG(sk1)KG(sk2)=KG(sk1sk2)
  2. c=Encpk1(Encpk2(m,r))=Encpk1pk2(m,r)
  3. m=Decsk1(Decsk2(c))=Decsk1sk2(c)

( é uma função que, dada a chave secreta, retorna a chave pública: .)KGpk=KG(sk)

Se essas condições se mantiverem, para algumas operações e , é trivalentemente possível fazer descriptografia distribuída (n-fora-de-n) e pode ser possível para o limiar (m-fora-de-n) se o operação é, por exemplo, suficiente para interpolar um polinômio.

Por exemplo, no limiar Elgamal, é uma adição e isso permite interpolação.

Mesmo que ninguém tenha respondido à pergunta original, talvez alguém possa responder a estas perguntas: (1) O FHE de Gentry se encaixa no esquema acima (em termos de , , ). (2) Existem tais homomorfismos entre as chaves pública e secreta? (3) Em caso afirmativo, quais são as operações?KGEncDec

Além disso, não estou dizendo que essas condições são necessárias para ter um sistema de criptografia de limite. A falta de tal homomorfismo não implica (que eu saiba) que a descriptografia do limiar seja impossível.

PulpSpy
fonte