Matrix operations in multi-party computation

Abstract

This document presents two novel techniques for Multi-Party Computation based on secret sharing where the objects of computation are square matrices over a finite field. Matrix Triples can be consumed during the evaluation phase to obtain the product of two matrices, and they have quadratic space complexity, which makes them more efficient for this purpose than ordinary multiplication triples. Matrix Power Tuples are costly to produce during the preprocessing phase but allow the parties to take a matrix to a power with just a single round of communication during the evaluation phase. The latter technique also has a considerably simpler and cheaper variant that can be applied in cases where multiplication is commutative. We provide a bottom-up explanation of the ideas behind Matrix Power Tuples, as well as a formal specification of both techniques in the form of protocols and ideal functionalities. We use the latter to provide a security proof in the iUC model. We also provide an introduction into the most widely used techniques for Multi-Party Computation in the modern literature.

Dieses Dokument präsentiert zwei neue Techniken für Multi-Party Computation, welches auf secret sharing basiert und in welchem die fundamentalen Elemente Matrizen über einem endlichen Körper sind. Matrix Triples können während der evaluation phase verbraucht werden um das Produkt zweier Matrizen zu berechnen und sie haben quadratische Speicherkomplexität, was sie effizienter für diesen Zweck macht als normale multiplication triples. Das Generieren von Matrix Power Tuples während der evaluation phase ist teuer, aber sie erlauben es den Parteien, mit nur einer einzigen Kommunikationsrunde während der preprocessing phase eine Matrix zu potenzieren. Für die letztere Technik existiert auch eine deutlich einfachere und billigere Variante. Diese kann in Fällen angewendet werden, in denen die Multiplikation kommutativ ist. Wir stellen ein Bottom-up Erklärung der Ideen, welche Matrix Power Tuples unterliegen, zur Verfügung, sowie eine formale Spezifikation in Form von Protokollen und Idealen Funktionalitäten. Wir nutzen Letztere um einen Sicherheitsbeweis in dem iUC Modell durchzuführen. Weiterhin stellen wir eine Einführung in die am häufigsten benutzten Techniken für Multi-Party Computation in der modernen Literatur zur Verfügung.