Fast Fully Secure Multi-Party Computation over Any Ring with Two-Thirds Honest Majority
Anders Dalskov, Daniel Escudero, Ariel Nof
2022Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security18 citationsDOI
Abstract
We introduce a new MPC protocol to securely compute any functionality over an arbitrary black-box finite ring (which may not be commutative), tolerating t < n/3 active corruptions whileguaranteeing output delivery (G.O.D.). Our protocol is based on replicated secret-sharing, whose share size is known to grow exponentially with the number of parties n. However, even though the internal storage and computation in our protocol remains exponential, the communication complexity of our protocol is constant, except for a light constant-round check that is performed at the end before revealing the output.
Topics & Concepts
Protocol (science)Computer scienceComputationConstant (computer programming)Secure multi-party computationSecure two-party computationSecret sharingRing (chemistry)Cryptographic protocolExponential functionTheoretical computer scienceComputer networkDistributed computingDiscrete mathematicsMathematicsCryptographyAlgorithmMathematical analysisPathologyAlternative medicineMedicineOrganic chemistryProgramming languageChemistryCryptography and Data SecurityComplexity and Algorithms in GraphsCryptography and Residue Arithmetic