License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.06111.16
URN: urn:nbn:de:0030-drops-6101
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2006/610/
Go to the corresponding Portal

Kiltz, Eike ; Weinreb, Enav

Secure Linear Algebra Using Linearly Recurrent Sequences

pdf-format:
06111.KiltzEike.ExtAbstract.610.pdf (0.2 MB)

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.

BibTeX - Entry

@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.dagstuhl.de/opus/volltexte/2006/610},
  URN =		{urn:nbn:de:0030-drops-6101},
  doi =		{10.4230/DagSemProc.06111.16},
  annote =	{Keywords: Secure Linear Algebra, Linearly Recurrent Sequences, Wiedemann's Algorithm}
}

Keywords: Secure Linear Algebra, Linearly Recurrent Sequences, Wiedemann's Algorithm
Collection: 06111 - Complexity of Boolean Functions
Issue Date: 2006
Date of publication: 20.11.2006

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI