Joel Alwen
New York University

Secure Linear Algebra Using Linearly Recurrent Sequences


In this work secure two-party protocols for various core problems in
linear algebra such as finding the minimal polynomial of a matrix, it's
singularity, rank and determinant are presented. These sub protocols (of
interest in their own right) are used to solve a linear system of
equations Ax=y in the following setting. Bob holds an encryption of A,
an n x n matrix and y, an n-element vector both encrypted (component
wise) under Alice's public key. After running the protocol Bob has an
encryption of y under (again under Alice's public key) such that Ax=y.
The protocol takes O(log n) communication rounds and has an overall
communication complexity of roughly O(n^2) which is improves on previous
results by Nissim and Weinreb which required O(n^0.275) rounds of

Eike Kiltz, Payman Mohassel, Enav Weinreb, and Matthew Franklin