Este posibil să construiți un OT 1-out-of-N cu o complexitate de comunicare mai mică decât întreaga intrare a expeditorului?

Construcțiile de 1-din-$n$ OT pentru $l$- șirurile de biți pe care le-am văzut au o complexitate de comunicare proporțională cu $nl$. Mă întreb, este posibil să faci OT cu securitate activă și să transferi mai puțin de $O(nl)$ biți (ignor parametrul de securitate în $O$-notare aici)? Partea importantă pentru mine aici este să-l fac mai ieftin decât doar transferul de intrare a expeditorului către receptor.

Există o limitare inerentă care nu permite acestui tip de OT să transfere mai puțini biți decât intrarea expeditorului? Există limite inferioare de comunicare pentru asta?

Să presupunem că expeditorul are șiruri de caractere $x_1, \ldots, x_n$, fiecare de lungime $\ell$. Receptorul are de ales $y \in \{1, \ldots, n\}$ și vrea să învețe (doar) $x_y$. Protocolul poate proceda astfel:

• Receptorul generează o cheie $k$ pentru o schemă de criptare complet homomorfă cu cheie simetrică.
• Receptorul trimite $c = \textsf{Enc}(k,y)$.
• Sender își imaginează un circuit boolean $f$ pentru functie $y \mapsto x_y$ -- acest circuit are toate $x_i$ valorile încorporate.
• Sender folosește caracteristica de evaluare homomorfă pentru a calcula local $c' = \textsf{Enc}(k,f(y))$.
• Expeditorul trimite $c'$.
• Receptorul decriptează pentru a obține $f(y) = x_y$.

Doar două texte cifrate (fiecare criptând un $\ell$-bit șir) sunt trimise, deci acest lucru poate costa $O(\kappa)+2\ell$ biți pentru o schemă FHE adecvată. Notă: aveți nevoie de o schemă de criptare care este circuit-privat -- adică, $c'$ ar trebui să dezvăluie nu mai mult decât $f(y)$, chiar și la deținătorul cheii.

Acest protocol este sigur împotriva adversarilor semi-cinsti, dar există modalități de a-l extinde și la securitatea rău intenționată.

Pentru a completa răspunsul lui Mikero:

• Dacă vrei 1-din-$N$ OT pe biții de intrare aleși, metode cunoscute pentru a obține $o(N)$ comunicarea se bazează pe munca privind regăsirea subliniară a informațiilor private. Pe majoritatea soluțiilor se bazează criptare complet homomorfă, ca în răspunsul lui Mikero. Cu toate acestea, există și diverse construcții alternative sub alte ipoteze criptografice, cum ar fi DCR (prin criptosistemul DamgÃ¥rd-Jurik), sau DDH și QR (folosind funcțiile hash trapdoor).
• Dacă vrei 1-din-$N$ pseudoaleatoare OT (adică $N$ intrările expeditorului sunt rezultatul unei funcții pseudoaleatoare), atunci există soluții alternative, mai eficiente în variantele ipotezei LPN, vezi de ex. acest lucru.
• Există (multe) construcții de dovezi de cunoaștere zero-cunoaștere cu comunicare subliniară în dimensiunea martorului. Dacă le doriți să nu fie interactive, aveți nevoie de ipoteze puternice (modelul de oracol aleatoriu sau SNARG-uri), dar dacă sunteți în regulă cu interacțiunile, ele există din ipoteze la fel de simple precum existența funcțiilor hash rezistente la coliziuni (de ex. Aici). Puteți folosi orice astfel de sistem de dovezi într-un mod generic pentru a transforma un OT semi-onest (cum ar fi cel din răspunsul lui Mikero) într-o schemă cu securitate activă.
• Dacă vrei să faci doar 1-din-$N$ cu comunicarea mai mică decât dimensiunea bazei de date, se știe că acest lucru este posibil (deși comunicarea va fi doar puțin mai puțin) în ipoteze generice: existența permutărilor trapei (vezi Aici). Pentru securitate activă, veți avea nevoie de CRHF-uri în plus.