Applications for arithmetic tuples

Abstract

Secure Multi-Party Computation (SMPC) is a subfield of cryptography that allows multiple parties to compute a function without disclosing the inputs. Different types of specialised computation of specific (sub)functions are used to make SMPC computations more efficient. A recently published paper introduced Arithmetic Tuples, a new approach for evaluating multivariate polynomials and thereby, arithmetic circuits, in a minimal number of rounds and with practicable precomputation. In this thesis, we demonstrate the practicality of the new approach by applying it to a variety of real-world applications in which it has the potential to be particularly effective. These applications are multiplexers, permutations, demultiplexers and prefix products, which include functions with several outputs. We analyze each application and compare Arithmetic Tuples to the existing approaches Beaver Triples and Binomial Tuples. Comparison criteria are the number of rounds, the number of elements to be precalculated and the number of elements to be communicated.

Secure Multi-Party Computation (SMPC) ist ein Teilgebiet der Kryptographie, das es mehreren Parteien ermöglicht, eine Funktion zu berechnen, ohne die Eingaben offenzulegen. Um SMPC-Berechnungen effizienter zu machen, werden u.a. verschiedene Arten der spezialisierten Berechnung bestimmter (Teil-)Funktionen verwendet. In einer kürzlich veröffentlichten Arbeit wurden arithmetische Tupel vorgestellt, ein neuer Ansatz zur Berechnung multivariater Polynome und damit arithmetischer Schaltungen in einer minimalen Anzahl von Runden und mit praktikabler Vorberechnung. In dieser Arbeit, wenden wir den neuen Ansatz auf praxisrelevante Anwendungen an, für die der neue Ansatz vielversprechend erscheint. Diese Anwendungen sind Multiplexer, Permutationen, Demultiplexer und Präfixprodukte, die Funktionen mit mehreren Ausgängen beinhalten. Jede Anwendung wird analysiert und Arithmetic Tuples werden mit den bestehenden Ansätzen Beaver Triples und Binomial Tuples verglichen. Vergleichskriterien sind die Anzahl der Runden, die Anzahl der vorzuberechnenden Elemente und die Anzahl der zu übermittelnden Elemente.