Explore the advancement in secure multiparty computation for highly repetitive circuits, presenting efficient protocols, comparisons with existing methods, focusing on Single Instruction Multiple Data (SIMD) circuits, and proposing protocols for a broader range of circuits. Discover implementations and contributions, along with distinctive features of highly repetitive circuits, defining their composition and criteria.
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
Existing Efficient and Implemented Protocols [HN06, DN07, LN17, CGHIKLN18, NV18, FL19, GSZ20] No. of parties Size of circuit ? ? ? : Total computation/communication complexity Per-party work: ?(|?|) For large computations, parties need to have large computing resources. Limits the kind of parties who can participate.
Better than ? ? ? ? ?(|?|): Total computation and communication [DIKNS08, DIK10, GIP15] ? hides polynomial factors in log|?| and security parameter ? Not concretely efficient ?(|?|): Total computation and communication [DIK10, GIP15] Only for SIMD circuits No known implementations
Better than ? ? ? ? ?(|?|): Total computation and communication [DIKNS08, DIK10, GIP15] ? hides polynomial factors in log|?| and security parameter ? Not concretely efficient ?(|?|): Total computation and communication [DIK10, GIP15] Only for SIMD circuits No known implementations Main Question: Can we design an ?(|?|) MPC protocol for a larger class of circuits?
Our Contributions ?(|?|) MPC protocol for Highly Repetitive Circuits Semi-honest and maliciously secure protocols ? < ? ? static corruptions Information theoretic No setup assumptions Security with Abort Supports Division of labor Provide Implementation - first implementation of MPC that uses packed secret sharing 1 2 2
Defining Highly Repetitive Circuits Example of (3,3)-repetitive circuit ?,? -Repetitive Circuits: Composed of an arbitrary number of blocks of width at least ?, that recur at least ? times. ?,? - repetitive circuit is highly repetitive w.r.t. ? parties, if ? (?) and ? ? . Highly Repetitive Circuits:
?(|?|) and ?(|?|) template Existing Efficient ? ? ? Multiplication Protocols (eg. [DN07]) + Correlated Randomness of form ??,?2? Multiplication: mask, reconstruct, unmask Vectorized/SIMD version of Shamir SS over ?(|?|) sized vectors Packed Secret Sharing = Existing ?(|?|) and ?(|?|) Protocols
Differing Operations PSS Parties choose operation +, for each entry in the vector Realized by performing both operations and allowing the leader to select desired values Requires special correlated randomness Highly Repetitive Circuits Existing Efficient ? ? ? Multiplication Protocols (eg. [DN07]) + Realignment PSS Parties can efficiently swap elements within/between vectors Realized by having the leader permute entry order during before resharing and unmasking Requires special correlated randomness Modified Packed Secret Sharing Differing-operations PSS Realignment PSS = ?(|?|) MPC Protocol For Highly Repetitive Circuits Highly Repetitive Circuits required so special randomness generation is amortized?(|?|)
Conclusion ?(|?|) MPC protocols for Highly Repetitive Circuits ia.cr/2021/500
