CryptoDB
Ramp hyperinvertible matrices and their applications to MPC protocols
Authors: 


Download:  
Presentation:  Slides 
Conference:  ASIACRYPT 2023 
Abstract:  Beerliov{\'{a}}{}Trub{\'{\i}}niov{\'{a}} and Hirt introduced hyperinvertible matrix technique to construct the first perfectly secure MPC protocol in the presence of maximal malicious corruptions $\lfloor \frac{n1}{3} \rfloor$ with linear communication complexity per multiplication gate\cite{BH08}. This matrix allows MPC protocol to generate correct shares of uniformly random secrets in the presence of malicious adversary. Moreover, the amortized communication complexity of generating each sharing is linear. Due to this prominent feature, the hyperinvertible matrix plays an important role in the construction of MPC protocol and zeroknowledge proof protocol where the randomness needs to be jointly generated. However, the downside of this matrix is that the size of its base field is linear in the size of its matrix. This means if we construct an $n$party MPC protocol over $\F_q$ via hyperinvertible matrix, $q$ is at least $2n$. In this paper, we propose the ramp hyperinvertible matrix which can be seen as the generalization of hyperinvertible matrix. Our ramp hyperinvertible matrix can be defined over constantsize field regardless of the size of this matrix. Similar to the arithmetic secret sharing scheme, to apply our ramp hyperinvertible matrix to perfectly secure MPC protocol, the maximum number of corruptions has to be compromised to $\frac{(1\epsilon)n}{3}$. As a consequence, we present the first perfectly secure MPC protocol in the presence of $\frac{(1\epsilon)n}{3}$ malicious corruptions with constant communication complexity. Besides presenting the variant of hyperinvertible matrix, we overcome several obstacles in the construction of this MPC protocol. Our arithmetic secret sharing scheme over constantsize field is compatible with the player elimination technique, i.e., it supports the dynamic changes of party number and corrupted party number. Moreover, we rewrite the public reconstruction protocol to support the sharings over constantsize field. Putting these together leads to the constantsize field variant of celebrated MPC protocol in \cite{BH08}. We note that although it was widely acknowledged that there exists an MPC protocol with constant communication complexity by replacing Shamir secret sharing scheme with arithmetic secret sharing scheme, there is no reference seriously describing such protocol in detail. Our work fills the missing detail by providing MPC primitive for any applications relying on MPC protocol of constant communication complexity. As an application of our perfectly secure MPC protocol which implies perfect robustness in the MPCintheHead framework, we present the constantrate zeroknowledge proof with $3$ communication rounds. The previous work achieves constantrate with $5$ communication rounds \cite{IKOS07} due to the statistical robustness of their MPC protocol. Another application of our ramp hyperinvertible matrix is the informationtheoretic multiverifier zeroknowledge for circuit satisfiability\cite{YW22}. We manage to remove the dependence of the size of circuit and security parameter from the share size. 
BibTeX
@inproceedings{asiacrypt202333423, title={Ramp hyperinvertible matrices and their applications to MPC protocols}, publisher={SpringerVerlag}, author={Hongqing Liu and Chaoping Xing and Yanjiang Yang and Chen Yuan}, year=2023 }