Migliorata resilienza alle fughe locali per la condivisione di segreti di Shamir e intersezione polinomiale ottimale nel caso peggiore

Abstract degli autori

Studiamo due problemi: la resilienza alle fughe locali (LLR) per la condivisione di segreti di Shamir e l’intersezione polinomiale ottimale nel caso peggiore (OPI). Entrambi riguardano polinomi $Q(X)$ di grado inferiore a $k$ su un campo finito $\mathbb{F}_p$ di ordine primo. Nella LLR per la condivisione di segreti di Shamir, ci si chiede quante informazioni si possano apprendere su $Q(0)$ a fronte della fuga di pochi bit da ciascuno dei valori $Q(α_1), \ldots, Q(α_n)$, per punti di valutazione distinti e non nulli $α_i \in \mathbb{F}_p$. Nell’OPI, si ricevono in input le liste $S_1, \ldots, S_n \subset \mathbb{F}_p$ e si vuole trovare un polinomio $Q(X)$ di grado inferiore a $k$ tale che $Q(α_i) \in S_i$ per il maggior numero possibile di indici $i$. Sfruttando il recente collegamento tra questi due problemi dovuto a (Sun, Wootters 2026), miglioriamo i risultati allo stato dell’arte per entrambi. Per la LLR, dimostriamo che esiste una costante $δ> 0$ tale che, purché $R := k/n \geq 1/2 - δ$, la condivisione di segreti di Shamir è resiliente alle fughe locali di un bit (il che significa che si può apprendere solo una quantità trascurabile di informazioni su $Q(0)$). È il primo risultato a superare la cosiddetta «barriera della metà» per la LLR e migliora il precedente miglior risultato noto, che richiedeva $R \geq 0.668$ (Kasser, 2025). Per l’OPI, presentiamo un algoritmo quantistico che trova un polinomio $Q(X)$ che concorda con almeno una frazione $\mathsf{SCL}_ρ(R)-\varepsilon$ delle liste in media, per ogni $\varepsilon>0$ fissato, dove $\mathsf{SCL}_ρ$ è la \emph{legge del semicerchio} di (Jordan et al., 2025). Questo migliora i precedenti risultati algoritmici (ed esistenziali) di (Jo, 2026) e (Horinaga, Yamakawa, 2026). Presentiamo inoltre risultati esistenziali ulteriormente migliorati. Adattiamo anche il risultato di durezza di (Yamakawa, Zhandry, 2024) affinché si applichi all’OPI (anziché a una versione ripiegata); su campi grandi, ciò fornisce una separazione incondizionata tra la difficoltà quantistica e quella classica dell’OPI rispetto a un oracolo di appartenenza.