Joel Alwen New York University TITLE: Secure Linear Algebra Using Linearly Recurrent Sequences ABSTRACT: 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 communication. Authors: Eike Kiltz, Payman Mohassel, Enav Weinreb, and Matthew Franklin