Abstrakt. I detta arbete presenterar vi säkra tvåpartsprotokoll för olika kärnproblem i linjär algebra. Vårt huvudsakliga resultat är ett protokoll för att avundsvärt bestämma singularitet av en krypterad matris: Bob har en n × n matris, krypterad med Alice hemliga nyckel, och vill lära sig om matrisen är singular (även om läcker ingenting längre). Vi ger ett interaktivt protokoll mellan Alice och Bob som löser ovanstående problem i O(log n) kommunikationsrundor och med övergripande kommunikation komplexitet ungefär O(n 2 ) (observera att indatastorleken är n 2 ). Våra tekniker utnyttjar vissa fina matematiska egenskaper linjärt återkommande sekvenser och deras förhållande till den minimala och karakteristiska polynom av ingångsmatrisen, efter [Wiedemann, 1986]. Med våra nya tekniker kan vi förbättra den runda komplexiteten i kommunikationen effektiv lösning av [Nissim och Weinreb, 2006] från O(n 0.275 ) till O(log n). I kärnan av våra resultat använder vi ett protokoll som säkert beräknar minimal polynom av en krypterad matris. Baserat på detta protokoll utnyttjar vi vissa algebraiska minskningar för att ytterligare utöka våra resultat till problem med säker beräkning rank och determinant, och för att lösa system av linjära ekvationer (igen med låg runda och kommunikation komplexitet).
Senare, Kiltz et al. REF förbättrade rundans komplexitet för att få ett protokoll med O(log n) rundor och kommunikations komplexitet av ungefär O(n 2 ).
Secure Linear Algebra Using Linearly Recurrent Sequences
{'venue': 'In 5th TCC, Springer-Verlag (LNCS 4392', 'journal': None, 'mag_field_of_study': ['Computer Science']}