1 Search Results for "Weinreb, Enav"

Document

Secure Linear Algebra Using Linearly Recurrent Sequences

Authors: Eike Kiltz and Enav Weinreb

Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)

Abstract

In this work we present secure two-party protocols for various core problems in linear algebra. Our main building block is a protocol to obliviously decide singularity of an encrypted matrix: Bob holds an $n imes n$ matrix $M$, encrypted with Alice's secret key, and wants to learn whether the matrix is singular or not (and nothing beyond that). We give an interactive protocol between Alice and Bob that solves the above problem with optimal communication complexity while at the same time achieving low round complexity. More precisely, the number of communication rounds in our protocol is $polylog(n)$ and the overall communication is roughly $O(n^2)$ (note that the input size is $n^2$). At the core of our protocol we exploit some nice mathematical properties of linearly recurrent sequences and their relation to the characteristic polynomial of the matrix $M$, following [Wiedemann, 1986]. With our new techniques we are able to improve the round complexity of the communication efficient solution of [Nissim and Weinreb, 2006] from $n^{0.275}$ to $polylog(n)$. Based on our singularity protocol we further extend our result to the problems of securely computing the rank of an encrypted matrix and solving systems of linear equations.

Cite as

Eike Kiltz and Enav Weinreb. Secure Linear Algebra Using Linearly Recurrent Sequences. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{kiltz_et_al:DagSemProc.06111.16,
  author =	{Kiltz, Eike and Weinreb, Enav},
  title =	{{Secure Linear Algebra Using Linearly Recurrent Sequences}},
  booktitle =	{Complexity of Boolean Functions},
  pages =	{1--19},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6111},
  editor =	{Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.16},
  URN =		{urn:nbn:de:0030-drops-6101},
  doi =		{10.4230/DagSemProc.06111.16},
  annote =	{Keywords: Secure Linear Algebra, Linearly Recurrent Sequences, Wiedemann's Algorithm}
}

Refine by Author
1 Kiltz, Eike
1 Weinreb, Enav

Refine by Classification

Refine by Keyword
1 Linearly Recurrent Sequences
1 Secure Linear Algebra
1 Wiedemann's Algorithm

Refine by Type
1 document

Refine by Publication Year
1 2006

1 Search Results for "Weinreb, Enav"

Secure Linear Algebra Using Linearly Recurrent Sequences

Abstract

Cite as

Thanks for your feedback!

Could not send message