înregistrare Logare
Puncte:2
Sean avatar Crypto

Problema sumei submulțimii rare

drapel yt
Sean

În rezultatele fundamentale ale lui Gentry privind FHE (https://dl.acm.org/doi/10.1145/1536414.1536440), se presupune că problema setului de subseturi rare e greu. Se pare că există o lucrare de urmărire cu privire la parametrul concret al dimensiunea subsetului (https://eprint.iacr.org/2011/567.pdf), care menționează că alegerea lui Gentry a mărimii subsetului este prea agresivă (de exemplu, 15). Dar în secțiunea 5 (Discuție), a menționat, de asemenea, că ipoteza reală folosită în lucrarea lui Gentry este Ascuns Problema subsetului rar și analiza acesteia nu se aplică.

Deci, în ceea ce privește alegerea mărimii subsetului, ceea ce este considerat un parametru „sigur” pentru problema subsetului ascuns acum (de exemplu, având în vedere că dimensiunea întregului set de greutăți este de 32k utilizată în lucrarea lui Gentry)?

108
0 + 0
Puncte:1
Mark avatar Crypto
drapel ng
Mark

Au existat atacuri mai puternice împotriva schemei FHE a lui Gentry, în special cred că lucrarea din 2016 a lui Biasse + Song (cuantic) o rupe în timp polinomial (și clasic în timp sub-exponențial). Având în vedere această slăbiciune relativă în comparație cu alte scheme FHE, nu am văzut oameni care încearcă să instanțieze în mod concret munca lui Gentry (să zicem în ultimii ~5 ani --- desigur că au existat lucrări timpurii în acest sens).

Discuția despre acest lucru poate fi găsită în lucrarea lui Bernstein, de exemplu acest. În general, dacă vă faceți griji cu privire la dimensiunile parametrilor concreti pentru implementările FHE, v-aș îndruma către Standard de criptare homomorfă. Nu include schema lui Gentry, probabil din cauza atacurilor menționate mai sus. Acest lucru înseamnă în mod explicit că nu este clar dacă există o parametrizare „sigură” asupra căreia criptografii ar fi de acord --- majoritatea încearcă să lucreze cu problemele standard ale LWE/SIS (și variantele lor algebrice) acum.

0 + 0
Sean avatar
drapel yt
Sean
Multumesc mult pentru informatii!
1
Răspunde
drapel romania
SEF 777
întrebarea această in alte limbi:

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.