💻 computer science

A Broadcast Authenticated Encryption with Keyword Search in the Standard Model: Tightly Secure in Multi-User, Multi-Challenge Settings

Questo articolo propone un nuovo schema di Broadcast Authenticated Encryption with Keyword Search (BAEKS) strettamente sicuro nel modello standard che affronta scenari realistici multi-utente e multi-challenge garantendo forti proprietà di hiding e unforgeability, insieme a una variante efficiente per singolo ricevitore e una valutazione sperimentale.

Autori originali: Sayantan Mukherjee

Pubblicato 2026-09-01

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Sayantan Mukherjee

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Nell'era digitale, le informazioni sensibili sono spesso custodite in caveau criptati, al sicuro da occhi indiscreti ma anche inaccessibili proprio alle persone che hanno bisogno di trovare dettagli specifici al loro interno. Immaginate un ospedale in cui le cartelle cliniche dei pazienti sono rimescolate per proteggere la privacy; un medico deve trovare un file relativo a una specifica allergia, ma non può semplicemente cercare nel testo rimescolato. Per risolvere questo problema, i crittografi hanno sviluppato un sistema chiamato crittografia ricercabile (searchable encryption). Questo permette a un utente di generare una chiave speciale, nota come trapdoor (botola), che funge da impronta digitale unica per una specifica parola chiave. Un server che detiene i file criptati può utilizzare questa impronta per controllare se un file contiene quella parola senza mai vedere la parola stessa o il contenuto del file. Tuttavia, questo sistema presenta un difetto critico: poiché le chiavi di cifratura sono pubbliche, un malintenzionato può indovinare parole comuni, creare i propri file di test e confrontarli con la trapdoor per l'ingegneria inversa della parola chiave segreta. Questo è noto come attacco di indovinamento delle parole chiave (keyword-guessing attack), e minaccia di esporre proprio i segreti che il sistema è stato progettato per proteggere.

I ricercatori hanno cercato di risolvere il problema introducendo l'autenticazione, garantendo che solo un mittente specifico possa creare un file ricercabile e solo un ricevente specifico possa effettuare la ricerca. Questo si è evoluto in uno scenario più complesso chiamato crittografia autenticata broadcast con ricerca di parole chiave (broadcast authenticated encryption with keyword search), in cui un singolo mittente potrebbe voler condividere un segreto con un gruppo di riceventi autorizzati, come un medico che condivide una diagnosi con un team di specialisti. Sebbene i precedenti tentativi di questa tecnologia offrissero una certa protezione, essi risultavano insufficienti in ambienti realistici e ad alto rischio. Spesso non tenevano conto di scenari in cui un attaccante potesse compromettere più utenti o effettuare migliaia di tentativi simultanei, e le loro prove di sicurezza si basavano su scorciatoie matematiche che le rendevano vulnerabili ad attacchi astuti. Le soluzioni esistenti erano come una serratura che funzionava perfettamente in un laboratorio di prova, ma che poteva fallire se qualcuno avesse cercato di scassinarla mentre la porta veniva abbattuta da una folla.

Un ricercatore dell'Indian Institute of Technology, Jammu, ha ora proposto una nuova costruzione che affronta direttamente queste debolezze. Ha progettato un sistema che rimane sicuro anche quando un attaccante può corrompere più utenti e compiere un numero vastissimo di query simultanee in modo caotico e intercalato. Il suo lavoro introduce una definizione rigorosa di sicurezza che assicura che la parola chiave, l'identità del mittente e l'identità del ricevente rimangano completamente nascoste, anche sotto gli attacchi più aggressivi. A differenza dei modelli precedenti che si affidavano ad assunzioni idealizzate, questo nuovo schema è dimostrato sicuro nel modello standard, il che significa che la sua sicurezza regge sotto l'esame matematico del mondo reale senza dover fare affidamento su scorciatoie ipotetiche di "random oracle" che spesso crollano sotto pressione.

Il ricercatore ha costruito la sua soluzione utilizzando un tipo specifico di struttura matematica nota come gruppi di accoppiamento bilineare (bilinear pairing groups), che agiscono come un filtro complesso e multistrato per i dati. Ha dimostrato che il suo sistema è "strettamente sicuro" (tightly secure), un termine tecnico che significa che la garanzia di sicurezza non degrada all'aumentare del numero di utenti o del numero di attacchi. In molti sistemi più vecchi, maggiore è il numero di utenti, più debole diventa la sicurezza, ma questo nuovo design mantiene la sua forza indipendentemente dalla scala. Ha inoltre dimostrato che il suo metodo impedisce a un attaccante di falsificare una chiave di ricerca o un file criptato, garantendo che solo il mittente e il ricevente genuini possano partecipare alla ricerca.

Per verificare che il suo design teorico potesse effettivamente funzionare nella pratica, il ricercatore ha implementato il sistema su una macchina virtuale standard. Ha eseguito esperimenti con un numero variabile di utenti e diverse dimensioni dei gruppi di riceventi, simulando tutto, da un singolo medico che cerca una cartella clinica a una grande rete ospedaliera che condivide dati tra cento specialisti. I risultati hanno mostrato che il sistema è abbastanza efficiente per l'uso nel mondo reale. Per una singola ricerca, il processo richiede meno di un secondo e, anche quando si effettua una ricerca su un gruppo di cento persone, il tempo richiesto rimane gestibile. Il costo computazionale scala linearmente, il che significa che man mano che il gruppo cresce, il tempo necessario per la ricerca aumenta in modo prevedibile e costante, piuttosto che esplodere in ritardi inutilizzabili.

Questo lavoro rappresenta un passo avanti significativo nella protezione dei dati criptati contro avversari sofisticati. Rafforzando le definizioni di sicurezza e fornendo una costruzione che resiste ad attacchi adattivi, il ricercatore ha offerto uno strumento robusto per ambienti in cui la privacy è fondamentale. I suoi risultati suggeriscono che è possibile avere un sistema in cui i dati siano non solo criptati, ma anche ricercabili e autenticati, senza sacrificare la sicurezza in nome della comodità o della scala. L'articolo conclude che, sebbene la sua attuale implementazione sia una prova di concetto, essa pone le basi per futuri sistemi in grado di resistere ad attori malintenzionati che cercano attivamente di violare la cifratura, garantendo che le informazioni sensibili rimangano veramente private anche in un panorama digitale affollato.

Riepilogo Tecnico: Crittografia Autenticata con Broadcast e Ricerca per Parole Chiave Tettamente Sicura in Ambienti Multi-Utente e Multi-Challenge

1. Definizione del Problema

La Ricerca su Dati Cifrati (Searchable Encryption - SE) consente agli utenti di cercare su dati criptati. Sebbene la Crittografia a Chiave Pubblica con Ricerca per Parole Chiave (PEKS) consenta questo, essa è vulnerabile agli attacchi di Indovinamento delle Parole Chiave (Keyword Guessing Attacks - KGA), in cui un avversario genera cifrari per testare una trapdoor e dedurre la parola chiave. Per mitigare ciò, è stata introdotta la Crittografia ad Autenticazione a Chiave Pubblica con Ricerca per Parole Chiave (PAEKS), che richiede la chiave segreta del mittente per la cifratura. Questa è stata successivamente generalizzata nella Crittografia ad Autenticazione con Broadcast con Ricerca per Parole Chiave (BAEKS) per supportare un mittente che cifra una parola chiave per un insieme di ricevitori autorizzati.

Nonostante gli esistenti lavori su BAEKS e PAEKS, rimangono diverse lacune critiche:

Modelli di Sicurezza: Gli schemi esistenti spesso mancano di definizioni di sicurezza per l'ambiente multi-utente, multi-challenge, che è più realistico per i sistemi implementati. Nello specifico, non tengono conto di corruzioni adattive (dove un avversario ottiene le chiavi segrete degli utenti) e query interleave (dove un avversario sfida simultaneamente cifrari e trapdoor).
Strettezza (Tightness): Le riduzioni di sicurezza attuali soffrono di perdite di sicurezza moltiplicative non banali (ad esempio, proporzionali al numero di query o utenti), il che significa che la garanzia di sicurezza degrada significativamente all'aumentare della scala del sistema.
Consistenza: Le precedenti prove di consistenza computazionale per BAEKS (specificamente nei lavori di Emura) sono state identificate come incomplete o prive di argomentazioni di riduzione formale.
Anonimato: Molti schemi non nascondono simultaneamente la parola chiave, l'identità del mittente e le identità dei ricevitori sia nei cifrari che nelle trapdoor sotto forti modelli avversari.

2. Metodologia e Costruzione

L'autore propone un nuovo schema BAEKS, denominato baeks, costruito in gruppi di accoppiamento bilineare (Tipo-3). La metodologia prevede:

Nuove Definizioni di Sicurezza: Il documento introduce la full-cpa security, una definizione che permette a un avversario di effettuare query di sfida interleave su cifrari, trapdoor e chiavi segrete (corruzioni adattive). Definisce inoltre nozioni di unforgeability (ct-cma e trap-cma), che l'autore sostiene siano implicite dalla full-cpa security.
Strategia di Codifica: A differenza delle costruzioni precedenti che utilizzavano codifiche hash di Boneh-Boyen (che si degradano in contesti multi-challenge a causa di dipendenze lineari), l'autore adotta una struttura ispirata alla crittografia basata su identità (IBE) e alla IBE gerarchica (HIBE) a sicurezza stretta, utilizzando strutture PRF di Naor-Reingold randomizzate.
- Gli utenti sono rappresentati da matrici $U_j$ (mittente) e $V_j$ (ricevitore).
- Le parole chiave sono codificate tramite matrici $K_{\iota, b}$ .
- Una tupla $(S, \omega, R)$ è codificata come somma di queste componenti: $\sum U_{S,i} + \sum K_{\omega,i} + \sum V_{R,i}$ .
- La casualità viene iniettata tramite una funzione casuale $RF(S||\omega||R)$ nelle codifiche del cifrario e della trapdoor.
Tecnica di Prova: La prova di sicurezza utilizza un argomento ibrido che coinvolge una serie di giochi ( $G_0$ $G_{0}$ a $G_6$ $G_{6}$ ). Un componente cruciale è un Core Lemma (Teorema 2) che stabilisce l'indistinguibilità del sistema sotto specifiche query di oracle. La prova si basa sull'assunzione Lateral Matrix Diffie-Hellman (lat-MDDH).
- La prova gestisce le corruzioni adattive assicurando che, anche quando le chiavi segrete di utenti non sfidati vengono rivelate, l'entropia delle chiavi degli utenti sfidati rimanga sufficiente per iniettare casualità senza rilevazioni.
- L'autore affronta la condizione di "non trivialità" limitando l'avversario dal richiedere chiavi segrete per utenti coinvolti in cifrari o trapdoor di sfida.

3. Contributi Chiave

Nuova Definizione di Sicurezza: Il documento definisce la full-cfa security per BAEKS, coprendo gli ambienti multi-utente, multi-challenge e corruzione adattiva con query interleave. Questa è la prima tale definizione per BAEKS (e PAEKS) che raggiunge una sicurezza stretta (la perdita di riduzione della sicurezza è costante, indipendente dal numero di query).
Costruzione a Sicurezza Stretta: L'autore presenta una nuova costruzione BAEKS che raggiunge la full-cpa security adattiva sotto la standard assunzione lat-MDDH nel modello standard. Limitando questa a un singolo ricevitore, si ottiene una PAEKS a sicurezza stretta.
Unforgeability: Il documento dimostra che la nozione di full-cpa security proposta implica intrinsecamente l'unforgeability sia per i cifrari che per le trapdoor.
Analisi della Consistenza: L'autore fornisce un'analisi rigorosa delle prove di consistenza nei lavori precedenti (specificamente quelli di Emura), identificando le lacune e offrendo una costruzione statisticamente consistente per il proprio schema.
Implementazione: Lo schema è stato implementato in Python utilizzando il framework Charm. Sono stati condotti esperimenti su una macchina virtuale per valutare le prestazioni al variare del numero di ricevitori ( $\ell$ ), dei livelli di sicurezza ( $k$ ) e delle dimensioni dello spazio delle parole chiave/utenti ( $\alpha, u$ ).

4. Risultati

Sicurezza: Lo schema è dimostrato sicuro nel modello standard sotto l'assunzione lat-MDDH. La riduzione della sicurezza è stretta (tight), evitando la perdita moltiplicativa ( $\Theta(|Q_{Ct}| + |Q_{Tr}|)$ ) riscontrata nei precedenti schemi BAEKS e PAEKS.
Prestazioni:
- Setup e KeyGen: Queste operazioni vengono eseguite una sola volta per sistema/utente. La complessità del setup scala linearmente con la dimensione dello spazio delle parole chiave $\alpha$ .
- SrchEnc e TrapGen: Sono efficienti. Il costo della cifratura e della generazione della trapdoor è ampiamente indipendente dal numero di utenti $u$ , scalando linearmente con la lunghezza della parola chiave $\alpha$ e il numero di ricevitori $\ell$ .
- Test: Il server cloud esegue $2\ell$ accoppiamenti bilineari per verificare una corrispondenza. Per PAEKS ( $\ell=1$ ), ciò richiede solo 2 accoppiamenti.
- Dati Sperimentali: L'autore riporta che per $\ell=1$ (PAEKS), lo schema è paragonabile in efficienza ai lavori esistenti pur offrendo una sicurezza più stretta. Per valori più elevati di $\ell$ , l'overhead è gestibile, sebbene si noti che lo schema sia leggermente meno efficiente in termini di dimensione di cifrari/chiavi rispetto allo schema a consistenza statistica di Mukherjee [42], ma superiore per garanzie di sicurezza.

5. Significato e Rivendicazioni

Il documento sostiene di aver rinnovato i modelli di sicurezza BAEKS affrontando gli scenari di minaccia più realistici: ambienti multi-utente con corruzioni adattive e sfide interleave. Il significato primario risiede nel raggiungere la sicurezza stretta in questi contesti, cosa che era precedentemente un problema aperto per BAEKS e PAEKS.

L'autore sottolinea che il proprio lavoro fornisce la prima formalizzazione per BAEKS che garantisce simultaneamente:

Occultamento della parola chiave.
Anonimato del mittente e del ricevitore.
Resistenza alle corruzioni adattive.
Riduzioni di sicurezza strette.

Il documento conclude con modestia, osservando che, sebbene l'attuale costruzione sia una prova di concetto pratica, i lavori futuri potrebbero mirare a costruzioni robuste contro avversari maliziosi che generano le proprie coppie di chiavi e potenzialmente ottimizzare ulteriormente la dimensione del cifrario. Il lavoro evidenzia inoltre come la sicurezza stretta della costruzione BAEKS si traduca immediatamente in una PAEKS a sicurezza stretta, colmando una lacuna nella letteratura per la ricerca a chiave pubblica autenticata con un singolo ricevitore.