Fundamentos da Cryptography Dr. Ashish Choudhury Department of Computer Science Indian Institute of Science – Bengaluru Lecture-56 Secret Sharing (Consulte Slide Time: 00:29) Olá a todos. Bem-vindo a esta palestra. Por isso, nesta palestra discutiremos sobre protocolos interativos. Ou seja, o nosso foco até agora foi na resolução do problema da comunicação segura onde tínhamos duas entidades um emissor e um receptor e discutimos extensivamente como projetar algoritmos para resolver o problema da comunicação segura. Mas agora o que vamos discutir é um cenário, um problema bem conhecido, onde temos várias entidades. E nosso objetivo é projetar protocolo criptográfico que exige interação entre as entidades. Por isso, especificamente o roteiro para esta palestra é o seguinte. Introduziremos o problema da partilha secreta. Veremos aditivo compartilhamento secreto, compartilhamento secreto replicado e então veremos a construção clássica de esquema de compartilhamento secreto devido a Adi Shamir. (Consulte O Slide Time: 01:17)Então, vejamos a motivação do compartilhamento secreto. Então imagine que temos uma aplicação bancária, digamos onde o armário no banco é acessível apenas pelos gerentes da seguinte maneira. A senha para o armário é compartilhada entre os três gerentes e ela compartilhou de tal forma que, se apenas dois dos gerentes se unirem e entrarem em suas respectivas senhas, o armário poderá ser acessado. Mas se apenas um único gestor tentar inserir a senha e acessar o armário, o acesso não é possível. Então, por exemplo, se o segundo gerente vai e tenta abrir o armário, ele não deve fazer isso. Da mesma forma, se o terceiro gestor for sozinho, deve falhar. Mas se levarmos qualquer conjunto de dois ou mais número de gerentes e eles forem e entrarem em suas respectivas senhas, eles devem ser capazes de acessar o armário. Portanto, é isso que exigimos aqui. (Consulte O Slide Time: 02:14)Da mesma forma, considere outro cenário do mundo real. Esse é um cenário do mundo real, que realmente aconteceu durante 90s. Então, isso é em relação a como a Rússia ’ s Armas Nucleares era acessível pelos principais líderes dos países. Por isso, acredita-se que a senha para lançar a arma nuclear da Rússia ’ foi compartilhada entre as três principais entidades do país a saber, o presidente, primeiro-ministro e ministro da Defesa de tal forma que a arma poderia ser acessada ou lançada apenas se pelo menos 2 das 3 entidades se unam e entrarem em suas senhas, enquanto que se apenas uma única entidade tentar lançar ou acessar a arma, o acesso será negado. (Consulte O Slide Time: 02:55) Assim, ambos os aplicativos podem ser abstrados pelo seguinte problema, que chamamos como (Sharing secreto. E esse problema foi formulado de forma independente por Shamir em 1979 e Blakley em 1979. Portanto, o que nos é dado aqui é, nos dá a seguinte configuração. Nós temos um conjunto de festas 1, elas e elas estão conectadas por par-sábio canal privado e autêntico. O que significa que é, se alguma informação quiser enviar para, assumimos que ela tem um canal dedicado com o qual está conectado. E qualquer coisa manda sobre esse canal para, ele será recebido de forma correta e segura por. Se você está se perguntando como exatamente que tais canais estão disponíveis em real-mundo, bem, podemos usar qualquer um do conhecido protocolo de comunicação segura que temos extensamente discutido até agora, para garantir que tais canais estejam disponíveis entre cada par de partes. Agora fora essas festas, temos um partido designado entre esses partidos e todos saberão a identidade daquele partido e ele é chamado como traficante. E o revendedor tem alguma entrada privada, um segredo de um espaço maior, que é um conjunto de todos os segredos possíveis. Agora o objetivo deste negociante é distribuir seu segredo entre as partes, ao chegar ou computar uma parte para cada uma dessas partes e distribuir as ações. Assim, primeiro acionista ganha uma participação de 1, segundo partido deve obter a segunda parte e o partido deve receber a parte. E essas ações são distribuídas sobre o canal de par-wise com o qual o revendedor está conectado com os acionistas individuais. Agora, exigimos as seguintes propriedades a partir dessas distribuições de ações. Exigimos que seja impossível que qualquer conjunto de ou menos número de acionistas troque suas ações e reconstrua de volta o segredo. E dependendo se o conjunto de acionistas que estão tentando reconstruir de volta o segredo, sejam eles computacionalmente delimitado ou eles são computacionalmente ilimitado, nós alcançamos sigilo perfeito ou sigilo computacional. Sendo assim, esse é o primeiro requisito a partir desta distribuição de ações. Por outro lado, se algum conjunto de ou mais acionistas puxar juntas suas ações então deverá ser possível reconstruir de volta o segredo. Por isso, o parâmetro aqui está agindo como um limite para você. Isso significa que exigimos um mecanismo de compartilhamento de tal forma que, se qualquer conjunto de ou menos número de acionistas se unir, eles devem deixar de ter acesso ou eles devem deixar de reconstruir o segredo. As ações devem ser completamente independentes do segredo subjacente. Por outro lado, se algum conjunto de ou mais número de acionistas se unir, o segredo deverá ser reconstruído, deve ser possível reconstruir de volta o segredo. (Consulte O Slide Time: 05:39) Então, vamos ver uma construção muito simples de (aditivo esquema de compartilhamento secreto. Então basicamente aqui o meu limiar. Isso significa que eu necessito de um mecanismo de compartilhamento onde todos os acionistas devem se unir para reconstruir de volta o segredo. Mas se algum accionista único está desaparecido então não deve ser possível reconstruir de volta o segredo. E por que ele é chamado de compartilhamento secreto aditivo, ficaria claro para você muito em breve. Então aqui o meu espaço secreto l. O algoritmo de compartilhamento é o seguinte. Então imagine que traficante tem um segredo. Para compartilhá-lo, ele escolhe ações aleatoriamente do conjunto. Isso significa que o primeiro share 1 é uma string aleatória l-bit, a segunda parte é uma string aleatória l-bit e da mesma forma a parte é também uma string aleatória l-bit. Agora uma vez que as primeiras ações são fixadas pelo concessionário, a última parcela é definida como = 1 vezes melhor. E uma vez que as ações sejam computadas, as concessionárias enviam as respectivas ações para os respectivos acionistas. A saber, a parte é dada à parte sobre o canal dedicado e autêntico entre o concessionário e o partido. Assim, o imóvel de correção aqui é trivial para esta partilha secreta, nomeadamente se todos os accionistas se juntam e trocam as suas acções uns com os outros então realmente podem executar a xor de todas as acções e vão com exclusividade receber de volta o segredo subjacente que foi partilhado pelo concessionário. W próximo prove formalmente a propriedade de privacidade aqui. Por isso, para a privacidade nosso objetivo é mostrar que, se entre esses acionistas, quaisquer acionistas se unem e puxam suas ações, eles não devem aprender nada sobre segredo subjacente. Por isso, dividimos a prova em dois casos. Considere o caso quando o conjunto de acionistas que estão corrompidos e que estão tentando reconstruir o segredo são os primeiros acionistas. Acontece que se os primeiros acionistas são corruptos, então a partir de suas ações eles não aprendem absolutamente nada sobre segredo subjacente. Porque se você ver o algoritmo de compartilhamento, as primeiras ações elas são colhidas independentemente do segredo real do revendedor. Então, isso significa que se o adversário controla os primeiros acionistas e acesse suas ações, o adversário não aprende absolutamente nada sobre o segredo do traficante. Esse é o caso um. Por outro lado, considere o caso quando o conjunto de acionistas incluir definitivamente o nésimo acionista, em que a parte é uma função de um segredo e de uma ação restante. Assim, o segundo caso é quando coligação de acionistas exclui algum partido, onde definitivamente é diferente do partido. Por isso, pela simplicidade você pode imaginar que o meu = 1, isso significa que o adversário está corrompendo os últimos acionistas aqui. Acontece que faltou a parte que faltava o conjunto de acionistas, que neste exemplo é o share 1, que é independente do segredo. Porque isso foi colhida aleatoriamente pelo traficante e isso garante que mesmo que o adversário aprenda, é a parcela também é independente do segredo. Porque por exemplo, se estamos considerando o caso em que 1 está faltando na coligação, então, da parte de vista do atacante, atacante sabe que o valor = 1 letras letras, onde e 1are não é conhecido do adversário. E onde 1 é de forma independente e aleatoriamente colhida pelo traficante. Assim, pode-se imaginar que isso não passa de um onetime pad criptografia da mensagem com uma chave, onde a chave não passa de xor das ações 2, meia, que são conhecidas do adversário e o valor aleatório 1, que não é conhecido do atacante. Isso significa que, apesar de adversário estar vendo, não pode se descobrir se na verdade é uma parcela correspondente ao segredo ou correspondente a um segredo. Pois não se sabe o valor da participação de desaparecidos 1, que foi colhida aleatoriamente e colhida de forma independente do segredo real do traficante. Isso garante que mesmo que o adversário controle o último acionista não aprenderá absolutamente nada sobre o segredo subjacente. E é por isso que o compartilhamento secreto satisfaz os requisitos de um (esquema de compartilhamento secreto. (Consulte O Slide Time: 11:01) Então acontece que o compartilhamento secreto aditivo que nós discutimos, ele funciona apenas se o meu limite for. Mas em geral eu poderia estar interessado em projetar um compartilhamento secreto onde meu limite pode não ser, meu limite poderia ser estritamente menor do que. Por isso, agora, vamos ver uma solução, uma solução ingênua de chegar a um esquema de compartilhamento secreto para qualquer limite. Então, a ideia aqui é a gente tomar todo o subconjunto adequado do conjunto das partes, digamos, em que o tamanho do é e executar uma instância independente dedicada de compartilhamento secreto aditivo entre as partes na como os acionistas, com o limite sendo. E a ideia aqui é que se fizermos isso para cada subconjunto de tamanho, então, quando se trata da real coalizão de acionistas que pode tentar aprender sobre o segredo, essa coalizão de acionistas sentirá falta de pelo menos uma parte para reconstruir de volta o segredo compartilhado real. Então o que eu estou tentando dizer é melhor demonstrado por este exemplo. Então imagine o meu e eu quero projetar um esquema onde o meu limite. Isso significa que qualquer subconjunto de três acionistas deve ser capaz de reconstruir de volta o segredo, mas qualquer conjunto de dois acionistas, se eles tentarem puxar suas ações eles devem deixar de reconstruir de volta o segredo. Então, a ideia aqui é que o traficante divide esse conjunto de quatro partes em subconjuntos diferentes 1,2, 3, 4 de tamanho três partidos. Agora no primeiro subconjunto 1 = {1, 2, 3}, corretor executa uma instância de esquema de compartilhamento de segredo aditivo com o limite sendo t = 2. Namely dealer escolhe ações aleatórias 11, 12, 13, tais que 11 ⨁12 ⨁13, e então as ações são dadas ao respectivo acionista 1,2,3. Da mesma forma, o concessionário dirige uma instância independente de (3, 3) partilha aditiva para o subconjunto 2, 3 e 4. Agora a participação global para 1 será de todas as ações que recebe em várias instâncias do compartilhamento aditivo (3, 3), dependendo dos vários subconjuntos em que está presente. A saber, a sua participação será de 11, 21 e 31. Agora é fácil perceber que independentemente de quais dois partidos ficam corruptos, porque o meu limiar em todas as instâncias de partilha aditiva, esses dois acionistas não aprendem absolutamente nenhuma informação sobre os secretos s. Então por exemplo se 1 e 2 ficam corruptos, se estão sob o controle do adversário então com base em suas ações que eles aprendem, devido à sua presença no subconjunto 1, as partes 1,2 falham em aprender o segredo, pois faltarão a parcela 13. Da mesma forma com relação ao subconjunto 2, estes dois partidos estarão a faltar ao share 23 e é por isso que o segredo não será conhecido por eles e assim por diante. Por isso, não importa qual subconjunto de partidos fique corrupto, com base em suas ações eles falham em aprender o segredo real. Então agora você pode estar se perguntando que agora nós temos um esquema de compartilhamento secreto para qualquer limite com relação ao valor de. Mas verifica-se que esse esquema é ineficiente porque o número de subconjuntos de tamanho é (1), que se torna uma quantidade exponencial se for aproximadamente. Isso significa que as concessionárias basicamente têm que lidar com o número exponencial de valores aqui e o mesmo é o caso de todo acionista. Portanto, esta é uma solução ineficiente. (Consulte O Slide Time: 15:53)E deixe-nos saber discutir uma solução muito inteligente para (Secret-Sharing devido a Adi Shamir. E esta é uma das construções criptográficas mais simples que você pode pensar. Este é o meu favorito pessoal. E isso é baseado em aritmética simples que você pode ter aprendido durante o seu ensino médio. Então, a ideia aqui é, se você quer compartilhar um segredo, então para compartilhá-lo você escolhe um polinomial aleatório de grau, tal que o termo constante do polinômio é o segredo que você deseja compartilhar. E deixe que as ações sejam os pontos distintos ou valores deitados sobre esse polinômio. Para demonstrar o meu ponto, imagine o meu limite e eu tenho um segredo e eu sou o traficante. O que eu posso fazer é, compartilhar o segredo, já que o meu limite, eu escolho uma linha reta aleatória, poderia ser qualquer linha reta no avião com a única restrição foi que o seu termo constante deveria ser o segredo que eu quero compartilhar. E o que eu agora faço é, eu computo o valor da linha reta em alguns valores distintos publicamente conhecidos, digamos em 1, em 2 e em 3. E estas são as ações para o primeiro partido, segundo partido e terceiro, respectivamente. Será publicamente conhecido a todos que o primeiro partido está obtendo o valor de linha reta que o traficante escolheu em 1 e assim por diante. Por isso, esses valores, são publicamente conhecidos e todos saberão que está associado ao partido. Agora, vamos tentar provar que por que intuitivamente ele satisfaz os requisitos de (compartilhamento secreto. Por isso, é fácil perceber que se os acionistas se unem então eles podem, exclusivamente, reconstruir de volta o grau polinomial que o concessionário escolheu. Porque valores distintos em um grau polinomial de grau desconhecido para reconstrua exclusivamente aquele polinômio. Assim, por exemplo se e dizer que os dois primeiros acionistas surgem com suas ações 1 e 2, então eles podem encontrar com exclusividade a reta que passa pelos pontos (1, 1) e (2, 2) encaixando uma equação de reta. Uma vez que obtenham a linha reta, eles podem tirar o termo constante da linha reta para ser o segredo recuperado. Por outro lado, o segundo fato que podemos usar para polinômios de grau é que, se você pegar algum acionistas que são os bandidos e eles estão tentando reconstruir de volta o segredo do negociante, eles vão deixar de fazer isso. Porque valores distintos não bastam para recuperar com exclusividade a polinomial de grau desconhecido que foi colhida pelo traficante. Mais especificamente, neste exemplo desde então, dizer que o primeiro acionista é corrupto. Então a partir do seu ponto de vista poderia haver infinito número de linhas retas possíveis no avião passando pelo ponto (1, 1) e, portanto, infinito número de segredos possíveis. Isso significa apenas com base em compartilhamentos, o adversário falhará completamente para reconstruir de forma exclusiva o revendedor ’ s original polinomial e daí o revendedor ’ s original secret. Essa é a ideia intuitiva. Acontece que temos que executar todas as computações acima sobre algum campo finito para alcançar a segurança e evitar trabalhar por um domínio infinito. (Consulte O Slide Time: 20:01) Então, vamos tentar primeiro entender alguns fatos básicos sobre polinômios sobre um campo finito. Então imagine que eu sou dado um campo finito (. Um polinomial de grau sobre é do formato 0 + 1 minutos de vida, sendo que 0, …, ∈. Um valor é chamado de raiz de (), se () = 0I ressaltar aqui que todas as operações aqui são as operações + e de operações sobre o campo. Agora um outro fato bem conhecido da álgebra abstrata que podemos utilizar aqui é o seguinte. Se você for dado um grau polinomial sobre um campo, então ele pode ter na maioria das raízes. Por exemplo, se, então uma reta sobre um campo encontra o eixo y no ateu ponto. E isto é verdade para qualquer polinomial de t grau sobre um campo. E com base nesse resultado, podemos afirmar que dois polinômios de grau distinto (), () sobre podem ter em valores mais comuns. Portanto, por exemplo se você tiver 2 linhas retas distintas elas podem se cruzarem no ponto mais um ponto. Eles não podem se cruzarem em 2 pontos porque se cruzarem em dois pontos comuns então as 2 linhas retas são basicamente a mesma linha reta e em geral, esta generaliza para qualquer valor de. Novamente eu não estou provando este teorema. Estes são alguns resultados bem conhecidos da álgebra abstrata. E o resultado final que eu vou utilizar para dar a descrição do compartilhamento de Shamir ’ é a fórmula de interpolação de Lagrange. Então o que esse teorema basicamente diz é se você for dado t + 1 pares de valores (1, 1), …, (,) a partir do campo, onde 1, …, são distintos. Em seguida, existe um polinomial de grau único sobre, tal que) =, para 1 ≤ Para ver como exatamente podemos computar este polinômio, deixe-me definir uma sequência de polinômios, onde o polinômio ((− 2) (− 1) (− − 1) (− 1) (− 2) (− 2) (− − 1) (− 1) (− 1) (− 1), que possui grau. E a forma como eu defini esse polinômio (ele segue isso () = 1, enquanto (1) = (2) = deve-se () = () = 0. Isso significa que estes (polinômios são tais que sobrevivem a =, enquanto que desaparecem em todos os outros valores. Agora meu polinomial desconhecido passando pelo t + 1 dado pares de valores (xi, yi). E eu posso representar aquele desconhecido polinomial 1 (1 + simples + (. (Consulte o Tempo do slide: 24:43)E é fácil perceber que realmente 1) = 1, pois para 1, meu 1 (polinomial vai sobreviver e dar o valor 1 e 1 multiplicado por 1 será 1, enquanto que todo o outro (polinômios vai sumir. Da mesma forma para 2, todos os meus polinômios delta desaparecerão, exceto o 2 (polinomial, que dará o valor 1 e 1 multiplicado por 2 vai me dar 2, o que satisfaz minha condição. Sendo assim, esse é o polinômio de grau único, que você pode descobrir passando pelos pontos indicados (1, 1), …, (,), em que 1, …, são distintos. Agora você pode estar se perguntando que por que 1, …, são distintos têm que ser distintos? Eles têm de ser distintos para garantir que cada um dos (polinômios tem um denominador que é diferente de zero. E se denominador for diferente de zero então basicamente esse numerador dividido por denominador deve ser interpretado como se esse numerador fosse multiplicado pelo inverso multiplicativo do meu denominador, porque eu estou fazendo a divisão aqui. E essa divisão deve ser interpretada como multiplicando o numerador com o inverso multiplicativo do denominador. E o inverso multiplicativo do denominador existirá apenas se o meu denominador for diferente de zero. (Consulte O Slide Time: 26:08)Então agora deixe-nos ir para a descrição de Shamir ’ s Secret Sharing. Como parte da configuração pública, receberemos algum campo finito onde o tamanho do campo será pelo menos, o número de acionistas. E associados com os acionistas serão publicamente conhecidos valores distintos de zero, a saber, 1, …, que são os valores do campo finito. O algoritmo de compartilhamento do compartilhamento secreto Shamir é o seguinte. Se o traficante tem um valor secreto, que ele quer compartilhar então escolhe um polinomial aleatório sobre o campo escolhendo elementos aleatórios como os coeficientes do campo, tal que o termo constante do polinômio é o segredo que o negociante quer compartilhar. E agora o accionista, nomeadamente o partido, recebe a parte, onde não passa de nada senão o valor deste polinomial colhido pelo traficante. A correção desta partilha secreta é trivial. Isso significa, imagine-se fora desses acionistas, qualquer subconjunto de acionistas se unir trocando suas ações, então eles podem unificar exclusivamente o grau polinomial usando a fórmula de interpolação de Lagrange ’ que já discutimos anteriormente. E para provar a privacidade vamos provar que, se tomarmos qualquer conjunto de acionistas entre esses acionistas, então suas ações são independentes do segredo de compartilhamento subjacente, pois intuitivamente isso vem do fato de que os coeficientes de polinomial que são colhidos por negociante por compartilhar o segredo, são escolhidos uniformemente ao acaso do campo subjacente. (Consulte O Slide Time: 27:55)Então, deixe-nos torná-lo mais rigoroso. Por isso, deixe-me definir um conjunto Fto denote o conjunto de polinômios de todos os graus selecionados a partir do campo finito cujo termo constante é o segredo. Por isso, verifica-se que o número de tal polinomial de grau cujo termo constante é o segredo não é nada, mas |. Isso porque em cada um desses polinômios, além do termo constante que é, há outros coeficientes 1, melhores, colhidos do campo e para cada um desses coeficientes, há |candidatos. Daí | F | = |. Pela simplicidade e sem perda de genialidade, suponha que os primeiros acionistas são corruptos, isso significa que viram as ações 1, …,. E sabem que essas ações não passam de valor de algum polinomial de grau desconhecido, avaliado em 1, …,. Mostraremos que a distribuição de probabilidade dessas ações é independente do segredo colhida pelo traficante. Para isso, notamos pela primeira vez que, dadas quaisquer ações arbitrárias 1, …, existe uma polinomial F, com =), para. Isto decorre do fato de que os pontos distintos (0,), (1, 1), …, (,) pode mentir apenas em um polinomial de grau único. Agora com base em todas essas coisas, eu afirme que as ações 1, …, são independentes do segredo real compartilhado pelo negociante. E para provar esta afirmação, consideremos um par de segredos arbitrários (′) de, tal que. Mostraremos que a partir do ponto de vista do adversário, 1, …, poderiam ser as ações de bem como com igual probabilidade. Let (ser polinomial exclusivo do conjunto Fque teria produzido as ações 1, …, para o segredo. E similarmente, let ′ (sejam os polinômios únicos do conjunto F ′,, que teria produzido as ações 1, …, para o segredo. Agora a probabilidade de que determinado adversário tenha visto as ações 1, …,, revendedor ’ s secret is é o mesmo que revendedor usou o polinomial (para compartilhamento. E este evento ocorre com probabilidade 1/ |, como revendedor ’ s polinomial é captado aleatoriamente, onde todos os coeficientes, exceto o termo constante, são selecionados aleatoriamente de. Usando exatamente o mesmo argumento, concluímos que a probabilidade de que determinado adversário tenha visto as ações 1, …,, revendedor ’ s secret is é o mesmo que revendedor tem usado o polinomial ′ (para compartilhamento. E este evento ocorre com probabilidade 1/ |. Isso prova que a distribuição de probabilidade de 1, …, é independente do segredo subjacente e, portanto, ao ver essas ações, o adversário será despreocupado se o traficante compartilhou o segredo ou o segredo. Então isso me leva até o final desta palestra. Só para resumir. Nesta palestra introduzimos o problema de (compartilhamento secreto e vimos três construções. Vimos a construção de um compartilhamento secreto aditivo onde está o limite. E então usando isso (compartilhamento secreto