Loading
Study Reminders
Support
Text Version

Set your study reminders

We will email you at these times to remind you to study.
  • Monday

    -

    7am

    +

    Tuesday

    -

    7am

    +

    Wednesday

    -

    7am

    +

    Thursday

    -

    7am

    +

    Friday

    -

    7am

    +

    Saturday

    -

    7am

    +

    Sunday

    -

    7am

    +

Fondamenti di crittografia Dr. Ashish Choudhury Department of Computer Science Indian Institute of Science – Bengaluru Collezione - 56 Condivisione segreta (Riferimento Slide Time: 00.29) Ciao a tutti. Benvenuti a questa lezione. Così in questa lezione discuteremo di protocolli interattivi. Ovvero il nostro focus fino ad ora è stato quello di risolvere il problema della comunicazione sicura dove avevamo due entità un mittente e un ricevitore e abbiamo discusso diffusamente come progettare algoritmi per risolvere il problema della comunicazione sicura. Ma ora quello che stiamo per discutere è uno scenario, un problema ben noto, dove abbiamo più entità. E il nostro obiettivo è progettare protocollo crittografico che richiede interazione tra le entità. Quindi, nello specifico la roadmap per questa lezione è la seguente. Introdurremo il problema della condivisione segreta. Vedremo condivisione segreta additiva, condivisione segreta replicata e poi vedremo la classica costruzione di schema di condivisione segreta a causa di Adi Shamir. (Riferimento Slide Time: 01.17)Così vediamo la motivazione della condivisione segreta. Immaginate quindi di avere un'applicazione bancaria, diciamo dove la locandina in banca è accessibile solo dai gestori nel seguente modo. La password per l'armadietto è condivisa tra i tre manager e ha condiviso in modo tale che se solo due dei manager si mettono insieme ed entrano nelle rispettive password, si può accedere all'armadietto. Ma se solo un singolo manager cerca di inserire la password e accedere all'armadietto, l'accesso non è possibile. Così, per esempio se il secondo manager va e cerca di aprire la locandina, non dovrebbe farlo. Allo stesso modo, se il terzo manager va da solo, dovrebbe fallire. Ma se prendiamo qualsiasi insieme di due o più numero di manager e se ne vanno ed entrano nelle rispettive password, dovrebbero essere in grado di accedere all'armadietto. Ecco allora quello che richiediamo qui. (Riferimento Slide Time: 02.14)Allo stesso modo, considerare un altro scenario del mondo reale. Questo è uno scenario reale, che è realmente accaduto durante il 90s. Così si tratta di come le armi nucleari della Russia fossero accessibili dai vertici dei paesi. Così si crede che la parola d'ordine per lanciare l'arma nucleare della Russia, sia stata condivisa tra le prime tre entità del paese e cioè il presidente, primo ministro e ministro della difesa in modo tale che l'arma possa essere accesa o lanciata solo se almeno 2 delle 3 entità si uniscono e entrano nelle loro password, mentre se solo un'entità cerca di lanciare o accedere all'arma, l'accesso sarà negato. (Riferimento Slide Time: 02.55) Così entrambe queste applicazioni possono essere astratte dal seguente problema, che chiamiamo come (Condivisione Segreta. E questo problema fu formulato in modo indipendente da Shamir nel 1979 e Blakley nel 1979. Quindi quello che ci viene dato qui è, ci viene data la seguente impostazione. Abbiamo una serie di partiti 1, di sempre e sono collegati da un canale privato e autentico di coppia. Ciò che significa è, se qualsiasi informazione vuole inviarlo, suppitiamo che abbia un canale dedicato con cui è collegato. E qualsiasi cosa invia su quel canale a, sarà ricevuto correttamente e saldamente. Se vi state chiedendo come esattamente che tali canali siano disponibili nel mondo reale, beh, possiamo utilizzare qualsiasi sia il noto protocollo di comunicazione sicuro che abbiamo ampiamente discusso fino ad ora, per garantire che tali canali siano disponibili tra ogni coppia di partiti. Ora a parte queste parti, abbiamo un partito designato tra quelle parti e tutti conosceranno l'identità di quel partito e si chiama dealer. E dealer ha qualche input privato, un segreto da uno spazio più grande, che è un insieme di tutti i possibili segreti. Ora l'obiettivo di questo dealer è quello di ripartire il suo segreto tra le parti arrivando o calcolando una quota per ognuna di queste parti e distribuendo le azioni. Così primo azionista ottiene una quota 1, secondo partito dovrebbe ottenere la seconda quota e il partito dovrebbe ottenere la quota. E queste condivisioni sono distribuite sul canale di coppia con cui il dealer è collegato ai singoli azionisti. Ora richiediamo le seguenti proprietà da queste distribuzioni di condivisioni. Richiediamo che sia impossibile per qualsiasi insieme o meno numero di azionisti scambiare le proprie azioni e ricostruire il segreto. E a seconda che la serie di azionisti che stanno cercando di ricostruire indietro il segreto, siano essi computazionalmente delimitati o siano computazionalmente illimitati, si ottiene una perfetta segretezza o segretezza computazionale. Ecco allora il primo requisito da questa distribuzione di azioni. D'altra parte, se qualche insieme di azionisti o più azionisti tirano insieme le loro azioni allora dovrebbe essere possibile ricostruire il segreto. Quindi il parametro qui si comporta come una soglia per voi. Il che significa che richiediamo un meccanismo di condivisione tale che se ogni insieme di azionisti o meno numero di azionisti si uniscono, dovrebbero non accedere o non dovrebbero riuscire a ricostruire il segreto. Le azioni dovrebbero essere completamente indipendenti dal segreto sottostante. D'altra parte, se ogni insieme di azionisti o più di azionisti si uniscono, il segreto dovrebbe essere ricostruito, dovrebbe essere possibile ricostruire il segreto. (Riferimento Slide Time: 05.39) Così vediamo una costruzione molto semplice di (schema di condivisione segreta additiva. Quindi praticamente qui la mia soglia. Questo significa che richiedo un meccanismo di condivisione dove tutti gli azionisti dovrebbero riunirsi per ricostruire il segreto. Ma se manca qualsiasi azionista unico allora non dovrebbe essere possibile ricostruire il segreto. E perché si chiama condivisione segreta additiva, ti sarebbe chiaro molto presto. Così qui il mio spazio segreto l. L'algoritmo di condivisione è il seguente. Quindi immaginare dealer ha un segreto. Per condividerlo, picchia le azioni casualmente dal set. Questo significa che la prima quota 1 è una stringa casuale l bit, la seconda è una stringa casuale l bit e nello stesso modo la condivisione è anche una stringa casuale l bit. Ora una volta che le prime azioni sono fissate dal commerciante, l'ultima quota è fissata come = 1 minuti di vendita. E una volta computate le azioni, i concessionari inviano le rispettive quote ai rispettivi azionisti. Ovvero la quota è data alla festa sul canale sicuro e autentico dedicato tra il dealer e il partito. Quindi la proprietà di correttezza qui è banale per questa condivisione segreta, cioè se tutti gli azionisti si uniscono e si scambiano le loro azioni l'uno con l'altro allora possono eseguire la xor di tutte le azioni e riprendono in modo univoco il segreto sottostante che è stato condiviso dal dealer. W prossima prova formalmente la proprietà privacy qui. Quindi per la privacy il nostro obiettivo è dimostrare che se tra questi azionisti, gli eventuali azionisti si uniscono e tirano le loro azioni, non dovrebbero imparare nulla sul segreto sottostante. Così dividiamo la prova in due casi. Consideriamo il caso quando l'insieme degli azionisti che sono corrotti e che cercano di ricostruire il segreto sono i primi azionisti. Si scopre che se i primi azionisti sono corrotti, allora dalle loro azioni non imparano assolutamente nulla sul segreto sottostante. Perché se si vede l'algoritmo di condivisione, le prime azioni vengono prelevate indipendentemente dal segreto effettivo del dealer. Quindi questo significa che se l'avversario controlla i primi azionisti e accedono alle loro azioni, l'avversario impara assolutamente nulla sul segreto del dealer. Questo è il caso uno. D'altra parte, considerare il caso quando l'insieme degli azionisti include sicuramente l'ennesimo azionista, dove la quota è funzione di un segreto e di quote rimanenti. Quindi il secondo caso è quando la coalizione di azionisti esclude qualche partito, dove è decisamente diverso dal partito. Quindi per semplicità si può immaginare che il mio = 1, questo significa che l'avversario sta corrompendo gli ultimi azionisti qui. Si scopre che manca la quota mancante che l'insieme degli azionisti, che in questo esempio è la quota 1, è indipendente dal segreto. Perché questo è stato prelevato casualmente dal dealer e questo assicura che anche se l'avversario impara, è la quota è anche indipendente dal segreto. Perché per esempio, se stiamo valutando il caso in cui manca il 1 nella coalizione, poi dalla parte di vista dell'aggressore, l'aggressore sa che il valore = 1 minuti di libertà di stampa, dove e 1are non noti all'avversario. E dove 1 è in modo indipendente e casualmente scelto dal dealer. Così si può immaginare che questo non sia altro che una cifratura di pad onetime del messaggio con una chiave, dove la chiave non è altro che la xor delle condivisioni 2, le ultime, che sono note all'avversario e il valore casuale 1, che non è noto all'aggressore. Ciò significa anche se l'avversario sta vedendo, non può capire se in realtà sia una condivisione corrispondente al segreto o corrispondente a un segreto. Perché non conosce il valore della quota mancante 1, che è stata scelta casualmente e scegliendo in modo indipendente il segreto effettivo del dealer. Questo assicura che anche se l'avversario controlla l'ultimo azionista non imparerà assolutamente nulla del segreto sottostante. Ed è per questo che la condivisione segreta soddisfa i requisiti di un (schema di condivisione segreto. (Riferirsi Slide Time: 11.01) Così si scopre che la condivisione segreta additiva che abbiamo discusso, funziona solo se la mia soglia è. Ma in generale potrei essere interessato a progettare una condivisione segreta dove la mia soglia potrebbe non essere, la mia soglia potrebbe essere rigorosamente inferiore. Quindi ora vediamo una soluzione, una soluzione ingenua di arrivare con uno schema di condivisione segreto per qualsiasi soglia. Quindi l'idea qui è che prendiamo ogni corretto sottoinsieme del set delle parti, diciamo, dove le dimensioni di è e gestiscono una specifica istanza indipendente di condivisione segreta additiva tra le parti in quanto gli azionisti, con la soglia di essere. E l'idea qui è che se lo facciamo per ogni sottoinsieme di dimensioni, allora quando si tratta dell'effettiva coalizione di azionisti che potrebbe tentare di imparare il segreto, quella coalizione di azionisti mancherà almeno una quota per ricostruire il segreto condiviso effettivo. Quindi quello che sto cercando di dire è meglio dimostrato da questo esempio. Quindi immagina la mia e voglio progettare uno schema dove la mia soglia. Il che significa che qualsiasi sottoinsieme di tre azionisti dovrebbe essere in grado di ricostruire il segreto, ma qualsiasi insieme di due azionisti, se tentano di tirare le loro azioni dovrebbero non riuscire a ricostruire il segreto. Quindi l'idea qui è che il dealer divide questo insieme di quattro parti in diversi sottoinsiemi 1,2, 3, 4 di dimensione tre parti. Ora nel primo sottoinsieme 1 = {1, 2, 3}, il dealer gestisce un'istanza di schema di condivisione segreta additiva con la soglia in essere t = 2. Namely dealer picks azioni casuali 11, 12, 13, tale che 11 ⨁12 ⨁13, e poi le azioni sono date al rispettivo azionista 1,2,3. Analogamente, il dealer gestisce un'istanza indipendente di (3, 3) condivisione additiva per il sottoinsieme 2, 3 e 4. Ora la quota complessiva per il 1 sarà tutte le azioni che riceve in varie istanze della condivisione additiva (3, 3), a seconda dei vari sottoinsiemi in cui è presente. Ovvero la sua quota sarà di 11, 21 e 31. Ora è facile vedere che indipendentemente dal quale due parti si corrompono, perché la mia soglia in tutte le istanze di condivisione additiva, quei due azionisti non imparano assolutamente nulla sul segreto s. Così per esempio se 1 e 2 diventano corrotti, se sono sotto il controllo dell'avversario poi in base alle loro quote che imparano, a causa della loro presenza nel sottoinsieme 1, i partiti 1,2 non riescono a imparare il segreto, perché mancheranno la quota 13. Allo stesso modo rispetto al sottoinsieme 2, queste due parti mancheranno la quota 23 ed è per questo che il segreto non sarà noto a loro e così via. Quindi non importa quale sottoinsieme di partiti si corrompano, in base alle loro azioni non riescono a imparare il vero segreto. Quindi ora vi potreste chiedere che ora abbiamo uno schema di condivisione segreto per qualsiasi soglia rispetto al valore di. Ma si scopre che questo schema è inefficiente perché il numero di sottoinsiemi di dimensioni è (1), che diventa una quantità esponenziale se è circa. Il che significa che i commercianti in sostanza devono occuparsi di numero esponenziale di valori qui e lo stesso vale per ogni azionista. Quindi si tratta di una soluzione inefficiente. (Riferimento Slide Time: 15.53)E fateci discutere di una soluzione molto intelligente per (Secret - Sharing a causa di Adi Shamir. E questa è una delle costruzioni crittografiche più semplici a cui si possa pensare. Questo è il mio preferito. E questo si basa su semplice aritmetica che potreste aver imparato durante il vostro liceo. Quindi l'idea qui è, se volete condividere un segreto, allora condividerla scegliete un polinomio casuale di grado, tale che il termine costante del polinomio sia il segreto che volete condividere. E lasciare che le condivisioni siano i punti distinti o i valori sdraiati su quel polinomio. Per dimostrare il mio punto, immagina la mia soglia e ho un segreto e sono lo spacciatore. Quello che posso fare è, condividere il segreto, dalla mia soglia, scelgo una linea retta casuale, potrebbe essere qualsiasi linea retta in aereo con l'unica restrizione è stato che il suo termine costante dovrebbe essere il segreto che voglio condividere. E quello che ora faccio è, calcola il valore della retta ad alcuni valori distinti pubblicamente noti, diciamo a 1, a 2 e a 3. E queste sono le quote rispettivamente per il primo partito, secondo partito e terzo. Sarà pubblicamente noto a tutti che il primo partito sta ottenendo il valore della retta che il dealer ha prelevato a 1 e così via. Quindi questi valori, sono conosciuti pubblicamente e tutti sapranno che è associato alla festa. Ora cerchiamo di dimostrare che il perché intuitivamente soddisfa i requisiti di (condivisione segreta. Quindi è facile vedere che se gli azionisti si uniscono allora possono ricostruire in modo univoco il polinomio di laurea che commerciante ha scelto. Perché valori distinti su un polinomio di grado sconosciuto bastano a ricostruire in modo univoco quel polinomio. Così per esempio se e dire che i primi due azionisti arrivano con le loro condivisioni 1 e 2, allora possono trovare univocamente la retta che passa per i punti (1, 1) e (2, 2) allestendo un'equazione di linea retta. Una volta ottenuto la retta, possono prendere il termine costante della retta per essere il segreto recuperato. D'altra parte, il secondo fatto che possiamo usare per i polinomi di laurea è che, se prendete qualche azionista che sono i cattivi e stanno cercando di ricostruire il segreto del dealer, non mancheranno di farlo. Perché i valori distinti non bastano a recuperare in modo univoco il polinomio di grado sconosciuto prelevato dal dealer. Più precisamente, in questo esempio da quando, diciamo che il primo azionista è corrotto. Poi dal suo punto di vista potrebbe esserci un numero infinito di linee rette possibile nel piano che passa per il punto (1, 1) e da qui un numero infinito di possibili segreti. Il che significa solo basare su condivisioni, l'avversario non mancherà completamente di ricostruire in modo univoco il rivenditore del polinomio originale e da qui il rivenditore di un segreto originale. Questa è l'idea intuitiva. Si scopre che dobbiamo eseguire tutti i calcoli di cui sopra su qualche campo finito per ottenere la sicurezza e per evitare di lavorare su un dominio infinito. (Riferimento Slide Time: 20.01) Così cerchiamo di capire prima alcuni fatti di base sui polinomi su un campo finito. Immaginate quindi di essere dato un campo finito (. Un polinomio di grado superiore è del modulo 0 + 1 ° grado di precisione, dove 0, …, ∈. Un valore si chiama root di (), se () = 0I sottolineano qui che tutte le operazioni qui sono le operazioni + e le operazioni di controllo sul campo. Ora un altro fatto ben noto dall'algebra astratta che possiamo usare qui è il seguente. Se si ha un polinomio di laurea su un campo, allora può avere al massimo le radici. Ad esempio, se, poi un dritto su un campo incontra l'asse y al massimo un punto. E questo vale per qualsiasi polinomio di laurea su un campo. E in base a questo risultato, possiamo affermare che due polinomi distinti di grado (), () su possono avere a più valori comuni. Quindi per esempio se si hanno 2 linee rette distinte possono intersecarsi al massimo un punto. Non possono intersecarsi a 2 punti perché se si intersecano in due punti comuni poi le 2 linee rette sono sostanzialmente la stessa linea retta e in generale, questo generalizza per qualsiasi valore di. Ancora non sto dimostrando questo teorema. Questi sono alcuni risultati ben noti dall'algebra astratta. E il risultato finale che userò per dare la descrizione della condivisione di Shamir fa è la formula di interpolazione di Lagrange. Quindi ciò che questo teorema dice in sostanza è se ci si dà t + 1 coppie di valori (1, 1), …, (,) dal campo, dove 1, … sono distinti. Poi esiste un polinomio di grado unico, tale che) =, per 1 ≤ Per vedere come esattamente possiamo calcolare questo polinomio, lasciatemi definire una sequenza di polinomi, dove il polinomio ((− 1) (− 2) (− 1) (− 1) (− + 1) (− 1) (− 2) (− 2) (− 1) (− 1) (− 1) (− 1) (− 1), che ha la laurea (− 1). E il modo in cui ho definito questo polinomio (ne consegue che () = 1, mentre (1) = (2) = () = () = () = 0. Questo significa che questi (polinomi sono tali da sopravvivere a =, mentre svaniscono a tutti gli altri valori. Ora il mio polinomio sconosciuto che passa per il t + 1 date coppie di valori (xi, yi). E posso rappresentare quel polinomio sconosciuto 1 (1 + cotone + (. (Fare Slide Time: 24:43)Ed è facile vedere che effettivamente 1) = 1, perché per il 1, il mio 1 (polinomiale sopravviverà e darà il valore 1 e 1 moltiplicato per 1 sarà di 1, mentre tutti gli altri (polinomi svaniranno. Allo stesso modo per il 2, tutti i miei polinomi del delta svaniranno tranne il 2 (polinomiale, che darà il valore 1 e 1 moltiplicato per 2 mi darà 2, che soddisfa le mie condizioni. Ecco quindi il polinomio di grado unico, che potete scoprire passando per i punti indicati (1, 1), …, (,), dove 1, …, sono distinti. Ora vi potreste chiedere perché 1, …, sono distinti devono essere distinti? Devono essere distinti per garantire che ciascuno dei (polinomi abbiano un denominatore che sia non zero. E se il denominatore è non zero allora sostanzialmente questo numeratore diviso per denominatore dovrebbe essere interpretato come se questo numeratore si moltiplicasse per l'inverso moltiplicativo del mio denominatore, perché qui sto facendo la divisione. E questa divisione dovrebbe essere interpretata come moltiplicare il numeratore con l'inverso moltiplicativo del denominatore. E l'inverso moltiplicativo del denominatore esisterà solo se il mio denominatore è non zero. (Riferimento Slide Time: 26:08)Così ora lasciaci andare alla descrizione di Shamir's Secret Sharing. Nell'ambito del setup pubblico ci sarà dato qualche campo finito dove la dimensione del campo sarà almeno, il numero degli azionisti. E associati agli azionisti saranno noti valori distinti pubblicamente non zero, ovvero 1, …, che sono i valori dal campo finito. L'algoritmo di condivisione della condivisione segreta di Shamir è il seguente. Se il dealer ha un valore segreto, che vuole condividere allora picchia un polinomio casuale sul campo scegliendo elementi casuali come i coefficienti dal campo, tale che il termine costante del polinomio è il segreto che il dealer vuole condividere. E ora l'azionista, ovvero il partito, ottiene la quota, dove non è altro che il valore di questo polinomio prelevato dallo spacciatore a. La correttezza di questa condivisione segreta è banale. Il che significa, immaginate fuori da questi azionisti, qualsiasi sottoinsieme di azionisti si uniscono scambiando le loro azioni, poi possono internamente interpolare il polinomio di laurea utilizzando la formula di interpolazione di Lagrange che abbiamo discusso in precedenza. E a dimostrare la privacy proveremo che se prendiamo qualche insieme di azionisti tra questi azionisti, allora le loro azioni sono indipendenti dal segreto di condivisione sottostante, perché intuitivamente questo deriva dal fatto che i coefficienti di polinomiale che vengono prelevati da dealer per la condivisione del segreto, vengono scelti uniformemente a caso dal campo sottostante. (Riferimento Slide Time: 27:55)Così rendiamoci più rigoroso. Allora fatemi definire un set Fto denota il set di polinomi a tutti i gradi selezionati dal campo finito il cui termine costante è il segreto. Così si scopre che il numero di tale polinomio di grado il cui termine costante è il segreto non è nulla, ma |. Questo perché in ogni tanto polinomiale, al di là del termine costante che è, ci sono altri coefficienti 1, vaccini, prelevati dal campo e per ciascuno di questi coefficienti, ci sono |candidati. Da qui | F | = |. Per semplicità e senza perdita di genialità, supponiamo che i primi azionisti siano corrotti, questo significa che hanno visto le azioni 1, …. E sanno che queste azioni non sono altro che il valore di qualche polinomio di grado sconosciuto, valutato a 1, …. Dimostreremo che la distribuzione di probabilità di queste azioni è indipendente dal segreto prelevato dal dealer. Per questo, notiamo per la prima volta che date eventuali azioni arbitrarie 1, …, esiste un polinomio unico, con =), per. Ne consegue che i punti distinti (0,), (1, 1), …, (,) può mentire solo su un polinomio a singolo grado. Ora in base a tutte queste cose, dichiaro che le azioni 1, … sono indipendenti dal segreto effettivo condiviso dal dealer. E per provare questa affermazione, consideriamo un paio di segreti arbitrari (′) da, tale. Dimostreremo che dal punto di vista dell'avversario, 1, …, potrebbero essere le condivisioni di oltre che con pari probabilità. Let (essere unico polinomio dal set Fche avrebbe prodotto le condivisioni 1, … per il segreto. E similmente, lascia ′ (essere i polinomi unici dal set F ′, che avrebbe prodotto le azioni 1, … per il segreto. Ora la probabilità che un dato avversario abbia visto le condivisioni 1, …, il dealer di s secret è lo stesso che lo spacciatore ha usato il polinomio (per la condivisione. E questo evento si verifica con la probabilità 1/ |, come il polinomio di dealer viene prelevato casualmente, dove tutti i coefficienti tranne il termine costante vengono selezionati casualmente da. Usando esattamente lo stesso argomento, concludiamo che la probabilità che dato avversario abbia visto le condivisioni 1, …, il dealer di s secret è lo stesso che lo spacciatore ha usato il polinomiale ′ (per la condivisione. E questo evento si verifica con probabilità 1/ |. Questo dimostra che la distribuzione di probabilità del 1, …, è indipendente dal segreto sottostante e da qui a vedere queste condivisioni, avversario sarà cluso se il dealer ha condiviso il segreto o il segreto. Così questo mi porta alla fine di questa lezione. Solo per riepilogare. In questa lezione abbiamo introdotto il problema della (condivisione segreta e abbiamo visto tre costruzioni. Abbiamo visto la costruzione di una condivisione segreta additiva dove si trova la soglia. E poi usando questo (condivisione segreta