O que exatamente é um “ circuito distorcido ”?

Um circuito é apenas uma forma de representar um cálculo. Não há nada especificamente criptográfico sobre um circuito. Significa apenas uma computação em linha reta (sem loops ou construções de controle de fluxo) consistindo apenas em operações em bits , como AND, OR, NOT.

A circuito ilegível é uma maneira de “criptografar um cálculo” que revela apenas a saída do cálculo, mas não revela nada sobre as entradas ou quaisquer valores intermediários . Usamos o termo “circuito” porque os circuitos adulterados funcionam pegando o cálculo de seu interesse, expresso como um circuito , e depois fazendo algum material criptográfico para cada operação (AND, OR, NOT) no circuito .

Se quisermos ser um pouco mais precisos, um “esquema de distorção” consiste em:

• (Garble) Uma maneira de converter um (simples) circuito $ C $ em um truncado circuito $ \ widehat C $.

• (Codificar) Uma maneira de converter qualquer entrada (simples) $ x $ para o circuito em uma entrada truncada $ \ widehat x $. Você precisa da aleatoriedade secreta que foi usada para distorcer o circuito para codificar $ x $ em $ \ widehat x $.

• (Avaliar) Uma maneira de obter um truncado circuito $ \ widehat C $ e truncado introduza $ \ widehat x $ e calcula a saída do circuito $ C (x) $. Qualquer um pode fazer isso, você não precisa saber $ x $ ou a aleatoriedade secreta dentro de $ \ widehat C $ para avaliar e aprender $ C (x) $.

Estou simplificando um pouco aqui. Mas a ideia principal de segurança é que $ \ widehat C $ e $ \ widehat x $ juntos não vazam mais informações do que $ C (x) $. Em particular, eles não revelam nada sobre $ x $, mas permitem que o cálculo $ C (x) $ seja feito (inconscientemente). Isso é o que quero dizer com “criptografar uma computação”.

A principal aplicação para circuitos ilegíveis é a computação segura de duas partes. Imagine que Alice tem uma entrada privada $ x $ e Bob tem uma entrada privada $ y $. Eles concordam com alguma função $ f $ e concordam que ambos querem aprender $ f (x, y) $, mas não querem que seu oponente aprenda algo mais do que $ f (x, y ) $. Para conseguir isso, eles podem fazer o seguinte (este é o protocolo clássico de Yao):

1. As partes concordam em uma maneira de expressar $ f $ como um (simples ) o circuito. Alice distorce o circuito $ f \ mapsto \ widehat f $. Ela envia $ \ widehat f $ para Bob, bem como sua própria “entrada distorcida” $ \ widehat x $.

2. Alice sabe como codificar qualquer entrada de $ f $ em uma entrada “truncada”, mas apenas Bob conhece sua entrada privada $ y $. Assim, as partes combinam que Bob pegue uma versão distorcida $ \ widehat y $ sem que Alice saiba o que é $ y $. Isso pode ser feito com uma primitiva chamada transferência inconsciente.

3. Agora Bob tem o circuito truncado $ \ widehat f $ e uma entrada truncada $ \ widehat x, \ widehat y $ para esse circuito. Ele pode então executar o procedimento de avaliação e aprender $ f (x, y) $. Ele pode revelar $ f (x, y) $ para Alice.

Podemos argumentar que o protocolo revela não mais do que $ f (x, y) $ no seguinte forma:

• Alice não vê nada além da resposta final $ f (x, y) $ neste protocolo (a segurança da transferência inconsciente garante que ela não aprenda nada na etapa 2).

• Mesmo que Bob veja $ \ widehat f $, $ \ widehat x $ e $ \ widehat y $, a segurança de circuitos truncados garante que esses valores não ” não revelar nada além de $ f (x, y) $.

Essa abordagem funciona quando Alice & Bob é semi-honesto (ou seja, eles seguem o protocolo conforme as instruções). Mas quando Alice é mal-intencionada, ela pode distorcer alguma outra função $ f “$ em vez da $ f $ que eles combinaram.Portanto, outras coisas precisam ser adicionadas ao protocolo para evitar que isso aconteça, quando queremos segurança contra adversários maliciosos.

Material de referência:

• A construção Yao e sua prova de segurança (vídeo), Yehuda Lindell
• Uma prova do protocolo de Yao for Secure Two-Party Computation , Yehuda Lindell & Benny Pinkas
• Fundações de circuitos adulterados , Mihir Bellare, Viet Tung Hoang, Phillip Rogaway
• Uma breve história das otimizações práticas de circuitos adulterados , um vídeo meu . Os primeiros slides cobrem a construção “clássica” de circuitos truncados.

Comentários

• Como Bob tropeça y sem saber a aleatoriedade secreta que Alice escolheu quando surgiu com o esquema de distorção?
• A codificação distorcida funciona bit a bit. Veja Bob s primeiro bit. Alice pode pensar consigo mesma: " se Bob tiver o bit 0 de entrada, sua codificação truncada deve ser $ G_0 $. Se ele tiver inserido o bit 1, sua codificação distorcida deve ser $ G_1 $. " Transferência inconsistente é uma primitiva em que Alice fornece duas strings $ G_0, G_1 $ como entrada. Bob fornece um bit $ b $ como entrada e aprende $ G_b $ (mas não o outro $ G_ {1-b} $). Alice não ' não aprende $ b $. As partes podem realizar uma transferência inconsciente para cada bit de entrada de Bob '. Quanto a como a transferência inconsciente realmente funciona, essa é outra questão;)
• Ao lado de Yao ' o circuito truncado pode ' t ser reutilizado. Você pode resolver minha confusão de que " é permitido atribuir chaves diferentes cada vez que um circuito ilegível é executado ou as chaves são fixas para bits de entrada 0 e 1 "