Scienziati e segreti
Non se se sia propriamente la sezione giusta. Il problema è questo:
11 scienziati hanno i risultati di una ricerca chiusi in una cassaforte protetta da 462 lucchetti distinti. Si vuole che qualsiasi gruppo di almeno 6 scienziati possa aprire la cassaforte ma che 5 o meno scienziati non possano farlo. A questo scopo, si dà ad ogni scienziato 252 chiavi (distinte ma, chiaramente, due scienziati diversi possono avere alcune chiavi uguali).
Abbiamo raggiunto il nostro scopo?
Ho visto dei teoremi che dimostrano che, se come sopra gli scienziati sono 11 e si vuole che i gruppi di 6 possano accedere, allora sicuramente bisogna proteggere la cassaforte con un numero $>=$ di 462 lucchetti e dare ad ognuno un numero $>=$ di 252 chiavi. Mi chiedevo se la situazione "minima" fosse effettivamente realizzabile.
Non riesco a risolvere questo problema. Ho provato a supporre che 6 persone possano accedere e 5 no. Ma non arrivo in questo modo ad una conclusione. Ad occhio mi sembrerebbe che la situazione non sia realizzabile e quindi stavo cercando di dimostrare che se fra ogni gruppo di 1512 chiavi (quelle possedute da 6 persone) ce ne sono 462 distinte, allora ci sono anche in almeno un gruppo di 1260 chiavi (quelle possedute da 5 persone).
Suggerimenti?
Grazie
11 scienziati hanno i risultati di una ricerca chiusi in una cassaforte protetta da 462 lucchetti distinti. Si vuole che qualsiasi gruppo di almeno 6 scienziati possa aprire la cassaforte ma che 5 o meno scienziati non possano farlo. A questo scopo, si dà ad ogni scienziato 252 chiavi (distinte ma, chiaramente, due scienziati diversi possono avere alcune chiavi uguali).
Abbiamo raggiunto il nostro scopo?
Ho visto dei teoremi che dimostrano che, se come sopra gli scienziati sono 11 e si vuole che i gruppi di 6 possano accedere, allora sicuramente bisogna proteggere la cassaforte con un numero $>=$ di 462 lucchetti e dare ad ognuno un numero $>=$ di 252 chiavi. Mi chiedevo se la situazione "minima" fosse effettivamente realizzabile.
Non riesco a risolvere questo problema. Ho provato a supporre che 6 persone possano accedere e 5 no. Ma non arrivo in questo modo ad una conclusione. Ad occhio mi sembrerebbe che la situazione non sia realizzabile e quindi stavo cercando di dimostrare che se fra ogni gruppo di 1512 chiavi (quelle possedute da 6 persone) ce ne sono 462 distinte, allora ci sono anche in almeno un gruppo di 1260 chiavi (quelle possedute da 5 persone).
Suggerimenti?
Grazie
Risposte
Ricapitolando: vogliamo trovare un modo intelligente per coniare $252 \times 11$ chiavi con $462$ scelte possibili in modo che, comunque se ne prendono $6 \times 252$ ce ne siano $462$ diverse e comunque se ne prendano $5 \times 252$ non ce ne siano $462$ diverse. Giusto? Ho paura si debba fare una marea di conti.
Forse c'entra poco, ma visto che siamo a parlare di chiavi di gruppo, riporto questa tecnica. In questo genere di problemi infatti, c'e' un modo molto carino per "chiudere una cassaforte" dando solo una chiave a ciascuno.
Un numero $k$ sara' la chiave che apre la cassaforte. Prendiamo un polinomio $P$ di grado $6$ che abbia $k$ come termine noto. Prendiamo $11$ punti distinti, non nulli, e che non siano radici di $P$; chiamiamo $(x_i,y_i)$ le coppie punto $x_1$ e $y_i = P(x_i)$. A questo punto la chiave di ogni scienziato e' una coppia $(x_i,y_i)$ entrambi non nulli.
Qualsiasi gruppo di $6$ scienziati, puo' facilmente ricostruire il polinomio $P$ (ad esempio usando i polinomi di Lagrange sui nodi corrispondenti alle loro chiavi) e dunque valutando $P(0)$ puo' trovare la chiave della cassaforte. D'altra parte nessun gruppo di $5$ scienziati puo' ricostruire il polinomio.
Problema di questa soluzione: e' necessario un garante che sia a conoscenza della chiave $k$ di partenza per permettere di generare le chiavi da dare a ogni scienziato. In effetti se si vuole evitare la necessita' di un garante, l'informazione da dare a ciascuno scienziato deve aumentare.
Forse c'entra poco, ma visto che siamo a parlare di chiavi di gruppo, riporto questa tecnica. In questo genere di problemi infatti, c'e' un modo molto carino per "chiudere una cassaforte" dando solo una chiave a ciascuno.
Un numero $k$ sara' la chiave che apre la cassaforte. Prendiamo un polinomio $P$ di grado $6$ che abbia $k$ come termine noto. Prendiamo $11$ punti distinti, non nulli, e che non siano radici di $P$; chiamiamo $(x_i,y_i)$ le coppie punto $x_1$ e $y_i = P(x_i)$. A questo punto la chiave di ogni scienziato e' una coppia $(x_i,y_i)$ entrambi non nulli.
Qualsiasi gruppo di $6$ scienziati, puo' facilmente ricostruire il polinomio $P$ (ad esempio usando i polinomi di Lagrange sui nodi corrispondenti alle loro chiavi) e dunque valutando $P(0)$ puo' trovare la chiave della cassaforte. D'altra parte nessun gruppo di $5$ scienziati puo' ricostruire il polinomio.
Problema di questa soluzione: e' necessario un garante che sia a conoscenza della chiave $k$ di partenza per permettere di generare le chiavi da dare a ogni scienziato. In effetti se si vuole evitare la necessita' di un garante, l'informazione da dare a ciascuno scienziato deve aumentare.
Grazie della riposta e del tuo metodo (il protocollo di Shamir) è sicuramente un metodo più efficace in un contesto di secret sharing.
In effetti il mio problema nasce da un'idea "grezza" di secret sharing ma la questione mi ha incuriosito indipendentemente dal contesto in cui l'ho trovata. Comunque il problema è diverso: le chiavi distinte sono $462$ in totale ma ogni scienziato ne ha solo $252$. E' per questo che, ad occhio, dico che dare 252 chiavi ad ognuno sia troppo perché in nessun caso, se sei persone possono accedere, cinque non ci riescano.
In effetti il mio problema nasce da un'idea "grezza" di secret sharing ma la questione mi ha incuriosito indipendentemente dal contesto in cui l'ho trovata. Comunque il problema è diverso: le chiavi distinte sono $462$ in totale ma ogni scienziato ne ha solo $252$. E' per questo che, ad occhio, dico che dare 252 chiavi ad ognuno sia troppo perché in nessun caso, se sei persone possono accedere, cinque non ci riescano.
Ma scusa eh..con casi piu' piccoli quanto sono grandi questi numeri?
Tipo, che ne so, $5$ scienziati e si vuole che in $3$ possano aprire la cassaforte.
Tipo, che ne so, $5$ scienziati e si vuole che in $3$ possano aprire la cassaforte.
Supponi di avere $n$ scienziati e vuoi che un gruppo di minimo $k$ persone possa accedere (nel mio esempio, $n=11$, $k=6$). Allora, se $N$ è il numero di lucchetti e $S$ il numero di chiavi che devi dare ad ogni scienziato, si mostra che
$ N>=((n), (k-1) ) $ e $ S>=((n-1), (k-1) ) $
Sottolineo che sono condizioni necessarie per creare la situazione voluta ma non ho risultati che mi dicano se siano anche sufficienti. Inoltre, anche ottenendo qualche risultato per certi $n$ e $k$, non credo sia per nulla facile generalizzarli.
$ N>=((n), (k-1) ) $ e $ S>=((n-1), (k-1) ) $
Sottolineo che sono condizioni necessarie per creare la situazione voluta ma non ho risultati che mi dicano se siano anche sufficienti. Inoltre, anche ottenendo qualche risultato per certi $n$ e $k$, non credo sia per nulla facile generalizzarli.
In questi casi a me piace sempre studiarmi i casi piccoli prima. Se riusciamo a realizzare l'uguaglianza per $n = 3$ e $k = 2$ si avrebbe $N = 3$ e $S = 2$. Coniamo dunque $2 \times 3 = 6$ chiavi (direi $2$ per ogni lucchetto, ma forse c'è un modo più intelligente). Tuttavia già in questo caso non è possibile garantire che comunque vengono date due chiavi a ciascuna delle tre persone, queste possano aprire i tre lucchetti della cassaforte.
D'altra parte se coniamo una settima chiave, allora a qualcuno toccherebbero tre chiavi e quindi se è fortunato potrebbe da solo aprire la cassaforte.
Quindi, almeno in questo caso base facile, sembra sia necessario un garante che distribuisce le chiavi in modo intelligente. Non so se con casi più grandi le cose si stabilizzano in modo diverso, ma così a occhio mi sembra difficile.
D'altra parte se coniamo una settima chiave, allora a qualcuno toccherebbero tre chiavi e quindi se è fortunato potrebbe da solo aprire la cassaforte.
Quindi, almeno in questo caso base facile, sembra sia necessario un garante che distribuisce le chiavi in modo intelligente. Non so se con casi più grandi le cose si stabilizzano in modo diverso, ma così a occhio mi sembra difficile.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo