Fondamenta di CryptographyProf. Dr. Ashish Choudhury (Ex) Infosys Foundation Career Development Chair ProfessorIndian Institute of Technology – BangaloreLecture – 6Introduction alla Sicurezza computazionale (Fare Slide Time: 00 :31) Ciao a tutti, benvenuti alla lezione 6. Il piano per questa lezione è il seguente. Discuteremo della nascita della crittografia moderna, ovvero l'approccio che utilizziamo nella crittografia moderna. Discuteremo anche della nozione di sicurezza computazionale e di mali necessari che sono associati alla sicurezza computazionale, infine, definiremo matematicamente cosa intendiamo per algoritmi efficienti e probabilità trascurabili. (Fare Slide Time: 00 :54) Quindi, solo per ricordare nell'ultimo paio di lezioni, abbiamo discusso della nozione di segretezza perfetta, sempre auspicabile perché questa è la nozione più forte di segretezza che possiamo ottenere. Perché la segretezza si ottiene contro un avversario che è computazionalmente sconfinato, il cui tempo di esecuzione è illimitato, ma abbiamo anche discusso che dobbiamo pagare un prezzo pesante per ottenere una perfetta segretezza, ovvero in qualsiasi processo di crittografia perfettamente garantito, la tua chiave deve essere la più grande come un messaggio e ogni istanza della crittografia deve usare una chiave fresca.Quindi queste 2 restrizioni sono un po' impossibili, perché in pratica puntiamo a progettare un processo di crittografia dove poter utilizzare un tasto breve per criptare i messaggi lunghi e vorremmo avere uno schema di crittografia in cui lo stesso short key potrebbe essere utilizzato per la codifica della sequenza di più messaggi. Questo significa che la crittografia praticamente perfettamente sicura è semplicemente non possibile, questo è un tipo di imbrogli. Quindi se qualcuno sostiene che il suo processo di crittografia è pratico così come vi fornisce una perfetta segretezza, allora questo è il chiaro imbrogli. Questo ci porta all'approccio che la crittografia moderna segue. Il principio che seguiamo nella crittografia moderna è che invece di ottenere una perfetta segretezza, cercheremo di avvicinarci il più possibile alla perfetta segretezza e in cambio, realizziamo due obiettivi pratici che puntiamo. Ovvero, realizziamo un processo di crittografia dove possiamo utilizzare lo stesso short key per la codifica di più messaggi. Ecco allora il tipo di tradeoff che usiamo nella crittografia moderna. (Fare Slide Time: 02 :35) Quindi, vediamo l'approccio che usiamo nella crittografia moderna. Ricordate, nel perfetto modello di segretezza, il nostro avversario è computazionalmente sconfinato e un obiettivo di segretezza nel modello di segretezza perfetta è che vogliamo garantire che gli avversari non imparino assolutamente nulla sul testo di pianura e poi formalizziamo rigorosamente questa nozione: cosa intendiamo per imparzialità imparate assolutamente nulla sul testo di pianura? Abbiamo anche discusso che le conseguenze di questo obiettivo, ovvero l'obiettivo di raggiungere quell' avversario imparano assolutamente nulla è che bisogna avere una chiave grande come il testo di pianura e non si può permettere di riutilizzare la chiave. Così, che sono state le conseguenze o le restrizioni di perfetta segretezza. (Fare Slide Time: 03 :33) Ora, i cambiamenti che faremo nella crittografia moderna sono i seguenti: invece di ipotizzare che il nostro avversario sia computazionalmente illimitato o computazionalmente illimitato, supponiamo che il nostro avversario sia di tecniche computazionalmente delimitate, questo significa che non ci assumiamo più che l'avversario possa eseguire il suo algoritmo per spezzare lo schema o attaccare lo schema per un periodo di tempo illimitato. Vedremo come formulare matematicamente questa nozione di avversario delimitato computazionalmente. Il secondo relax che stiamo per fare nel modello di perfetta segretezza è che invece di pretendere che l'avversario impara assolutamente nulla sul testo in chiaro, ci proponiamo di raggiungere il seguente obiettivo: ci proponiamo di raggiungere quell' avversario dovrebbe imparare ulteriori informazioni sul testo in chiaro con una probabilità trascurabile. Il che significa che ora siamo disposti a lasciare che l'avversario imparino qualcosa sul testo in chiaro, ma che siano informazioni aggiuntive o la probabilità con cui l'avversario potrebbe imparare le informazioni aggiuntive è talmente piccola, è talmente trascurabile che per quasi tutti gli scopi pratici possiamo ignorare. (Vedi Slide Time: 04 :42) Appena facciamo queste due relax e il modello di perfetta segretezza, dovremmo sperare di ottenere le seguenti due implicazioni e cioè che il nostro processo di crittografia dovrebbe essere usato con la chiave breve e lo stesso short key dovrebbe essere utilizzabile per criptare una sequenza di messaggi. Si scopre che effettivamente se facciamo queste due relax nel modello di perfetta segretezza, possiamo raggiungere i due obiettivi desiderati, ovvero lo stesso short key può essere usato per criptare sequenza di messaggi lunghi e questo è quello che l'approccio moderno crittografa. La nozione di segretezza che otteniamo facendo di questi due relax è quella che ci chiamiamo segretezza computazionale, perché la sicurezza è raggiunta contro un avversario il cui potere computazionale è ormai limitato, piuttosto che dire che la potenza di calcolo adversariale è illimitata. Ecco, questo è l'approccio che seguiremo nella crittografia moderna. (Fare Slide Time: 05 :38) Così i due relax che stiamo per fare siamo ora puntando a raggiungere la sicurezza solo contro gli avversari efficienti, e ciò che intendo per un avversario efficiente è informalmente quegli algoritmi o quegli algoritmi avversari il cui tempo di esecuzione è pratico o il cui tempo di esecuzione che impiega una quantità di tempo che è fattibile in praticità. Definiremo matematicamente cosa intendiamo esattamente con gli avversari efficienti molto presto. Il secondo relax che stiamo per fare ora è quello di ipotizzare che gli avversari abbiano permesso di spezzare lo schema con qualche probabilità, ma la probabilità con cui l'avversario può rompere lo schema è talmente piccola da non preoccuparci di una così piccola probabilità. Anche in questo caso, andiamo molto presto a definire matematicamente e rigorosamente cosa intendiamo esattamente con una tale probabilità di errore. Inoltre, come vedremo durante il corso, come procede il corso, che sotto certi aspetti supplisce la quantità di tempo che l'avversario richiederà di spezzare lo schema con quella piccola probabilità sarà di ordine di poche vite. Questo è in contrasto con ciò che realizziamo in perfetta segretezza. In perfetta segretezza, anche se diamo il tempo adversamente illimitato, c'è assolutamente zero probabilità che impara qualcosa sul sottostante testo di pianura. Ma nella sicurezza computazionale, in modello di sicurezza computazionale dove il nostro obiettivo è raggiungere la riusabilità chiave se diamo enorme quantità di tempo all'avversario, allora c'è la possibilità che l'avversario possa imparare qualcosa sul messaggio sottostante, ma che qualcosa sarà così piccolo che per la maggior parte dei fini pratici, possiamo ignorarlo. Del resto, la quantità di tempo che ci vuole per l'avversario per imparare il messaggio, è alcuni che una piccola probabilità che sarà di ordine di poche vite. Si scopre che questo è accettabile per la maggior parte delle applicazioni pratiche perché nella maggior parte delle applicazioni pratiche non richiediamo una sicurezza everduratura. Quello che intendo con quest' ultima affermazione è il seguente: immaginate di avere un sistema sicuro per mantenere la segretezza dei dettagli della vostra carta di credito. Quindi se ho un processo di crittografia, che assicura che preservi la privacy dei tuoi dettagli della tua carta di credito, con notevole quantità di probabilità. Questo significa la probabilità che l'avversario possa imparare i dettagli della tua carta di credito considerando la crittografia dei dettagli della tua carta di credito con molto, molto piccola probabilità e la quantità di tempo che l'avversario prenderà per conoscere i tuoi dettagli della tua carta di credito è di ordine diciamo 35 anni o 40 anni, poi va bene perché idealmente, richiedici la segretezza dei dettagli della tua carta di credito da mantenere solo per pochi anni. Non si richiede la segretezza, o la privacy dei dettagli della propria carta di credito da mantenere per sempre duratura. Quindi questo è accettabile. Come si scoprirà che al di sopra di due rilassamenti che stiamo facendo nel modello di segretezza computazionale è assolutamente necessario se il nostro obiettivo finale è raggiungere la riusabilità chiave. Ovvero, nella prossima coppia di diaposili, si discuterà che effettivamente se vogliamo progettare il processo di crittografia in cui il nostro obiettivo è quello di garantire che lo stesso short key sia usato per criptare più messaggi, allora sicuramente dobbiamo rendere le due rilassazioni che sto discutendo qui, ovvero il primo rilassamento è che dovremmo essere disposti a lasciare che l'avversario impara qualcosa sul messaggio sottostante con una piccola probabilità e un secondo relax è che dovremmo puntare sulla sicurezza solo contro gli avversari efficienti. (Fare Slide Time: 09 :16) Vediamo la necessità di questi due relax. Ovvero, il primo rilassamento è che ora dovremmo puntare sulla sicurezza solo contro gli avversari efficienti. Quindi, per capire che perché questo rilassamento è necessario, consideriamo un processo di crittografia arbitrario, dove si andrà ad utilizzare lo stesso tasto per la codifica della sequenza di messaggi e cioè, la stessa chiave verrà utilizzata per la codifica di più messaggi. E immaginate di essere nel noto modello di attacco di attacco (KPA). Solo per ricordare, nel modello di attacco KPA, supponiamo che l'avversario veda le crittografie di diversi messaggi, e significa che conosce sia i messaggi sottostanti, sia le loro crittografie sotto una chiave sconosciuta, dove verrà mantenuta la stessa chiave per criptare i nuovi messaggi. Immaginate di avere un processo di crittografia arbitrario mentre diciamo che il mittente ha messaggi m1, m2. ..., mt e i testi cifrati resultanti sono C1, C2, ..., Ct e avversario hanno avuto accesso a questa (plain text, cifertext) coppie. Sa che ogni cifratura in ognuna di queste coppie ha la crittografia del corrispondente testo di pianura sotto qualche chiave sconosciuta k, che la chiave non è nota all'aggressore. L'avversario conosce anche la descrizione del processo di crittografia e sa anche che la stessa chiave sconosciuta verrà trattenuta dal mittente per criptare la prossima sequenza di messaggi. Quindi, in questo scenario, l'avversario può sempre eseguire quello che chiamiamo l'attacco di key-recovery brutale. Idea alla base di questo attacco di key-recovery brutale è che quello che l'avversario può fare è dato che conosce la descrizione dello spazio chiave, può provare per ogni candidato chiave k appartenente allo spazio chiave e decriptare ciascuno il testo cifrato nelle sue coppie di (??,?) e vedere che esiste una chiave candidata k ∈? ognuno dei?? nelle sue coppie di (??,??) decodifica al corrispondente testo di pianura sotto quella chiave candidata k?Se poteva, sicuramente c'è qualche chiave candidata k e non appena ha colpito quel tasto di candidato k, può scoprire qual è la chiave che il mittente sta per utilizzare per crittografare la prossima sequenza di messaggi. Quindi potete vedere che la probabilità di successo di questa chiave di forza brutale? l'attacco di recupero è uno perché per qualche k ∈?, tale per Deck (?? ): = ??, per ciascuno (??,?? ), il tempo di esecuzione di questo algoritmo di key-recovery brutale è? (|? |). Se suppitiamo che il nostro spazio chiave sia significativamente grande per noi, per esempio, immaginate che lo spazio chiave sia il set di tutte le possibili 256 - bit stringhe. Questo significa immaginare il mio spazio chiave è 2256. Ora questa forza bruta over |? | = 2256 ci vorrà una quantità enorme di tempo, questo è un po' impraticabile. Questo significa che se faccio il rilassamento che non tollererò o non mi infastidire gli avversari il cui tempo di esecuzione è poco pratico, allora questo attacco di recupero brutale non sarà considerato come un attacco nel mio modello di attacco. Così questa è la necessità del primo relax se il vostro obiettivo è quello di realizzare uno schema di crittografia, dove la stessa chiave verrà utilizzata per criptare più messaggi. Questo ci mostra la necessità del primo rilassamento. (Vedi Slide Time: 12 :54) Ora vediamo la necessità del secondo relax se il tuo obiettivo è raggiungere la riusabilità chiave. Il secondo relax è che si dovrebbe permettere di spedire lo schema con una piccola probabilità. Ancora, consideriamo un'istanza di un processo di crittografia arbitrario dove lo stesso k chiave è stato usato per criptare più messaggi in sequenza e dire che l'avversario è nel modello di attacco KPA, dove ha avuto accesso a diversi (??,?) coppie e la chiave non è nota all'avversario. Ma l'avversario conosce il corrispondente testo cifrato o le crittografie del corrispondente testo di pianura in ognuna delle coppie, e l'avversario sa che la stessa chiave sconosciuta verrà trattenuta dal mittente per criptare la prossima sequenza di messaggi. Ora, l'avversario può sempre lanciare quello che lo chiamiamo come un attacco di indovinare. L'idea alla base di un attacco indovino è avversaria può semplicemente ottenere un valore candidato di chiave, dire k dallo spazio chiave e verificare se quella chiave candidata che ha indovinato è effettivamente la chiave giusta o non eseguendo la seguente operazione: indovinare casualmente un k ∈?, e controllare se Deck (?? ): = ??,, per ciascuno (??,?? ), poi ha colpito la chiave giusta. Ora, qual è la probabilità di successo di questo attacco? La probabilità di successo di questo attacco è di 1 / |? |. Qual è il tempo di esecuzione dell'attacco o l'algoritmo di Attacker? Il tempo di esecuzione dell'algoritmo degli avversari è? (| 1 |) perché ora non sta facendo brutti - forza sullo spazio chiave, heis indovina solo il valore della chiave candidata.Quindi ancora, se presumo che il mio spazio chiave sia estremamente grande, questo significa immaginare ancora per il momento che il vostro spazio chiave se ordine 2256, allora la probabilità di successo di questo attacco è di 1/2256, che è molto, molto piccola. Il che significa anche se l'avversario ha la possibilità di rompere lo schema, cioè di imparare la chiave, la possibilità che possa imparare la chiave è così piccola che, cioè, è il 1/2256 che possiamo ignorarlo per lo scopo più pratico. Quindi, questo dimostra ancora una volta che se la riusabilità chiave è il tuo obiettivo finale, allora dobbiamo fare il secondo relax nel nostro modello, ovvero, dovremmo essere disposti a lasciare che l'avversario rompi lo schema con una probabilità più piccola e che sia così piccolo che possiamo ignorarlo. (Fare Slide Time: 15 :19) Quindi, solo per riepilogare i due mali necessari che sono associati al nostro obiettivo finale di riusabilità chiave sono i seguenti. Ci sono due possibili attacchi, due attacchi estremi che possono sempre essere lanciati contro uno schema arbitrario dove la riusabilità chiave è l'obiettivo finale. Il primo attacco è l'attacco di key-recovery brutale, il cui tempo di esecuzione è molto grande, ma la probabilità di successo è del 100%. C'è il secondo attacco estremo contro tale schema in cui la riusabilità chiave è l'obiettivo, dove il tempo di esecuzione dell'aggressore è molto meno, è costante, ma la probabilità di successo dell'aggressore è molto piccola, è talmente piccola che per la maggior parte pratica possiamo ignorare. Così ora se ci accorgiamo che se facciamo i due rilassamenti di cui ho parlato, ovvero il primo relax dove ci proponiamo di raggiungere la segretezza solo contro gli avversari efficienti, allora l'attacco della forza bruta non sarebbe considerato un attacco nel nostro modello di attacco perché come dicevo, la complessità temporale della ripresa della forza bruta l'attacco sarà enormemente grande. Se faccio il secondo relax, ovvero dove sono disposto a lasciare che l'avversario impara o spezzi lo schema con una probabilità di errore molto piccola, allora il secondo attacco, ovvero l'attacco di recupero chiave non sarebbe considerato come un attacco nel nostro modello di attacco. (Fare Slide Time: 16 :42) Quindi questo è il riassunto dei due mali necessari che sono associati a qualsiasi processo di crittografia, dove la riusabilità chiave è l'obiettivo. Il primo rilassamento che dovresti fare nel tuo modello è invece di puntare sulla sicurezza contro un avversario computazionalmente sconfinato, dovresti puntare al segreto solo contro gli avversari computazionalmente efficienti. E il secondo relax che dovresti fare nel tuo modello è invece di pretendere che assolutamente nulla del sottostante testo in chiaro debba essere rivelato, dovresti essere disposto a lasciare che l'avversario impara qualcosa sul sottostante querelante con qualche piccola probabilità di errore e che la probabilità debba essere così piccola che per la maggior parte dei fini pratici, puoi ignorarlo. Ora, le sfide come esattamente definiamo matematicamente gli avversari efficienti, ovvero quali algoritmi, quali algoritmi avversariali, che si può dire è un algoritmo adversariale efficiente? La seconda sfida qui è la quantità che si definirà, oppure si chiamerà come una piccola quantità o una piccola probabilità di errore. Quindi, quello che faremo qui è definire matematicamente questi due termini in notazione asintotica. (Fare Slide Time: 17 :53) Quindi, persone che conoscono il concetto di algoritmi, sapranno cosa esattamente intendiamo per notazione asinttotica. Quindi, quando voglio misurare il tempo di esecuzione di un algoritmo, ci sono due approcci con cui possiamo misurare il tempo di esecuzione dell'algoritmo. Uno è l'approccio concreto, dove confrontiamo due algoritmi per lo stesso obiettivo, in base al tempo di esecuzione esatto. Quindi, hai detto, algoritmo 1 algoritmo 2 per un compito. Si esegue l'algoritmo 1 su campioni di varie dimensioni, si esegue l'algoritmo 2 su campioni di varie dimensioni e poi si confronta i livelli esatti dell'algoritmo 1 e l'algoritmo 2, ovviamente su quale processore si dà andso. In base a questo, si confronta se l'algoritmo 1 è migliore? o algoritmo 2 è meglio? Ma la discesa di questo approccio è anche se si ottiene il confronto concreto dell'algoritmo 1 contro algoritmo 2, questo approccio non prende in considerazione la velocità di calcolo sottostante, il progresso nella velocità di calcolo e così via. Il secondo approccio che seguiamo nel mondo degli algoritmi per confrontare 2 algoritmi è la notazione asintotica, dove confrontiamo il tempo di esecuzione dei 2 algoritmi per risolvere lo stesso compito in notazioni asintotiche, ovvero nella notazione big O. Confrontiamo il tempo di esecuzione misurando il numero di fasi fondamentali dell'algoritmo 1 e il numero di passi di base che algoritmo 2 dove il numero di passi di base viene calcolato in funzione della dimensione di input. A seconda di quale algoritmo impiega meno passaggi, definiamo se l'algoritmo 1 è migliore? o algoritmo 2 è meglio? Si hanno varie notazioni asintotiche come big O notazione, notazione theta, notazione omega in base alla quale è possibile confrontare 2 algoritmi. Quindi, quando vogliamo definire ciò che intendiamo per efficienza, algoritmo trascurabile di probabilità nel contesto della crittografia, seguiremo quest' ultimo approccio, ovvero definiremo questi termini asintoticamente. Per definire questi termini asintoticamente, dobbiamo introdurre qualcosa di quello che chiamiamo un parametro di sicurezza che denottiamo da n. Il motivo per cui vogliamo introdurre questo parametro di sicurezza è che una volta introdotto il parametro di sicurezza n, poi tutte le tre quantita ' ovvero il tempo di esecuzione degli utenti, il tempo di esecuzione dell'algoritmo di generazione della chiave, il tempo di esecuzione dell'algoritmo di codifica, il tempo di esecuzione dell'algoritmo di decodifica. Allo stesso modo, il tempo di esecuzione dell'algoritmo adversariale dell'aggressore, e la probabilità di successo dell'aggressore, tutti saranno espressi in funzione del parametro di sicurezza. Tipicamente, nel contesto del processo di codifica della chiave simmetrica, il parametro di sicurezza è la dimensione della chiave segreta, che tipicamente per la maggior parte dei fini pratici è di 128, 256 e così via. (Fare Slide Time: 20 :41) Quindi, prima definiamo cosa intendiamo per algoritmi efficienti asintoticamente. Informalmente diciamo che un algoritmo è efficiente se il suo tempo di esecuzione è una qualche funzione polinomiale del parametro di sicurezza. Ovvero, Algoritmo? ha un tempo di esecuzione polinomiale, se esiste un polinomio? (.), tale per ogni input? ∈ {0, 1} ∗, il calcolo di? (?) termina all'interno? (|? |) passi, dove |?. | denota la lunghezza della stringa? .Se questo è il caso, allora diciamo che il nostro algoritmo A ha tempo di esecuzione polinomiale e chiameremo il nostro algoritmo A per essere un algoritmo efficiente. Mentre, se non possiamo vincolare il tempo di esecuzione del nostro algoritmo A da qualche funzione polinomiale nella dimensione del suo input, allora diciamo che il nostro algoritmo non è efficiente. Ecco la definizione di algoritmo efficiente. Ora, una volta definito una nozione di algoritmo efficiente, il requisito che mettiamo su qualsiasi cifratura è il seguente: ricordate che abbiamo il requisito della correttezza, abbiamo il requisito della privacy e a parte che ora abbiamo il terzo requisito da qualsiasi processo di codifica. Il nuovo requisito è che il tempo di esecuzione dell'algoritmo di generazione chiavi, algoritmo di codifica e algoritmo di decodifica dovrebbe essere una qualche funzione polinomiale di questo parametro di sicurezza n. Se il tempo di esecuzione non è una funzione polinomiale, allora non consideriamo che algoritmo o cifratura sia un cifrario efficiente. (Fare Slide Time: 22 :15) Ora, definiamo la nozione di probabilità trascurabile in funzione del parametro di sicurezza. Così informalmente diciamo che una funzione del parametro di sicurezza è trascurabile se diventa quasi 0as il valore del tuo parametro di sicurezza n tende a infinito o la funzione del parametro di sicurezza sarà chiamata come una funzione trascurabile se è asintoticamente più piccola dell'inverso di ogni polinomiale funzion.Namely, se f (n) è una funzione trascurabile se f (n) è una funzione trascurabile se per ogni funzione polinomiale p (n) esiste un qualche valore di n, cioè N, tale che f (n) è rigorosamente inferiore all'inverso della funzione polinomiale p (n) per tutti i valori di n > N. Se questo vale, allora diciamo che il nostro funzione f (n) è una funzione trascurabile. Un'altra definizione equivalente di questa funzione trascurabile è per ogni costante?, esiste qualche?, tale? (?) <? (−?), per tutti? >?, poi diciamo che la nostra funzione f (n) è una funzione trascurabile. Il motivo per cui queste 2 definizioni sono equivalenti è che qualsiasi funzionp polinomiale (n), puoi sempre scriverlo come qualche nc. Quindi, se f (n) è rigorosamente inferiore all'inverso della funzione polinomiale per ogni funzione polinomiale, allora posso riscriverlo come? (?) <? (−?) per ogni costante c.So, è possibile utilizzare una qualsiasi di queste due definizioni per provare o smentire se una determinata funzione f (n) è una funzione trascurabile in n oppure no. Ecco, ecco, esempio alcune funzioni che sono tutte funzioni trascurabili. Ognuna delle funzioni è strettamente inferiore all'inverso di ogni funzione polinomiale, dove il valore di N è diverso per le corrispondenti funzioni polinomiali. Quindi, anche se tutte queste funzioni sono funzioni trascurabili, cioè se continuo a rendere grande il valore del piccolo n per essere grande e come n tende all'infinito, ognuna di queste funzioni candidate diventerà zero alla fine. Tuttavia, il tasso a cui ognuna di queste funzioni si avvicina a zero è diverso. Quindi, per esempio se considero la funzione 2-nand se considero la seconda funzione, allora sicuramente 2-n si avvicinerà al valore zero più velocemente rispetto al valore della funzione e così via. D'altra parte, se considero la funzione 1 /n10, allora non è una funzione trascurabile. Poiché il requisito da una funzione trascurabile è che la funzione debba essere rigorosamente inferiore all'inverso di ogni funzione polinomiale, ma si può facilmente vedere che per nessun valore di n, la funzione, ciò non è possibile per ogni valore di n. Di conseguenza, viola la definizione di probabilità trascurabile. (Vedi Slide Time: 25 :34) Quindi, abbiamo definito matematicamente cosa intendiamo per algoritmo efficiente e abbiamo definito quale probabilità si possa considerare come una piccola probabilità. Così ora la famiglia di funzioni trascurabili e polinomiali soddisfa alcune belle proprietà di chiusura. Vediamo le proprietà di chiusura soddisfatte dalla classe delle funzioni polinomiali. Quindi se si considerano le funzioni polinomiali twoarbitrari, diciamo P1 (n) e P2 (n), così come sono funzioni polinomiali. Qual è l'implicazione della prima proprietà di chiusura? Dice che supponiamo di avere due subroutine il modo di interpretare la prima proprietà di chiusura è la seguente: immaginate di avere due subroutine, dove il tempo di esecuzione della prima sottoroutine è qualche funzione polinomiale in n e il tempo di esecuzione della seconda procedura è anche qualche funzione polinomiale in n, e se si ha una routine più grande, che in realtà richiama questa sub procedure in sequenza, allora anche il tempo di esecuzione dell'algoritmo più grande sarà una funzionalità polinomiale, un algoritmo più grande che causa queste due funzioni minori in sequenza sarà anche considerato un efficiente algoritmo. Ecco qual è l'interpretazione della prima proprietà di chiusura. Tanto per riassumere, in questa lezione, abbiamo discusso che se la riusabilità chiave è il nostro obiettivo finale, ovvero se vogliamo progettare uno schema in cui vogliamo conservare la stessa chiave per criptare più messaggi, allora dobbiamo fare a meno di relax al modello di perfetta segretezza.Il primo relax che dobbiamo fare è che invece di ipotizziamo che il nostro avversario sia computazionalmente sconfinato, dobbiamo supporre che il nostro avversario sia computazionalmente delimitato e abbiamo anche visto che cosa intendiamo per, come misurare se il tempo degli avversari è computazionalmente delimitato o meno. Allo stesso modo, il secondo relax che dobbiamo fare nel nostro modello è invece di dire che l'avversario non dovrebbe non imparare assolutamente nulla del messaggio sottostante, dovremmo dare all'avversario qualche possibilità di infrangere il tuo schema. Che qualche possibilità di rompere lo schema debba essere così piccolo che per lo scopo più pratico possiamo ignorarlo. Così, abbiamo anche visto come definire matematicamente una così piccola probabilità di avversario che spezza lo schema. Abbiamo visto che questi due rilassamenti sono un tipo di mali necessari per qualsiasi schema di crittografia dove l'obiettivo è raggiungere la riusabilità chiave. Perché se non si fanno questi due rilassamenti, poi ci sono sempre attacchi 2extreme possibili, ovvero l'attacco indovinare e un attacco di forza bruta. La probabilità di successo dell'attacco di indovinare sarà molto, molto piccola, ma il tempo di esecuzione di questo attacco di indovinare sarà pratico, mentre la probabilità di successo dell'attacco della forza bruta sarà del 100% ma il tempo di esecuzione dell'attacco della forza bruta sarà estremamente grande. Quindi, dobbiamo assolutamente fare questi due relax. Spero che ti sia piaciuta questa lezione. Grazie.