Ankora: Notions of Multi-party Computation and Zero-knowledge Beyond Conventional Models

Abstract

In the era of digitalization, data privacy and integrity are of utmost importance. Secure multiparty computation (MPC) and zero-knowledge (ZK) facilitate data privacy and integrity. MPC enables privacy-preserving collaborative computation over sensitive data held by multiple mutually distrusting parties, while ZK allows a party to prove a claim without revealing any sensitive information about the same. This thesis studies the theoretical aspects as well as practical applications of various unconventional adversarial models MPC and ZK. The contributions of the thesis can be primarily divided into two parts.

MPC. The first part of the thesis studies unconventional adversarial models of MPC. In the presence of malicious adversaries, security guarantees of MPC protocols are categorized into three classes: (a) security with abort--where the adversary can choose to abort the protocol such that the honest parties are deprived of the output, however, the adversary learns the output. (b) fairness--where the adversary can abort the protocol, however, the adversary does not get the output if the honest parties do not get the output. (c) guaranteed output delivery (GOD)--irrespective of the adversarys strategy, all the honest parties get the output. It is known from the literature that GOD and fairness are not possible for dishonest majority protocols (protocols that can withstand the majority of the parties corrupted by the adversary). On the other hand, honest majority protocols (which ensure privacy and correctness guarantees only when less than half of the involved parties are corrupt) can ensure fairness and GOD. However, most of the honest majority protocols are vulnerable to view-leakage attacks (i.e., security does not hold when corrupt parties send non-protocol messages to an honest party). In traditional MPC, any leakage towards an honest party is not considered as a privacy breach. In reality, any honest party can be honest but curious, and thus, leakage towards the honest parties should also be handled by a protocol. Therefore, this work considers a new adversarial model of ``friends and foes which was introduced by Alon et al. (CRYPTO 2020), where a semi-honest adversary is considered in addition to the malicious adversary considered in the traditional model. The semi-honest adversary captures that every non-malicious party as semi-honest rather than purely honest. This work proves that information-theoretic MPC is not possible if the number of malicious parties (t) and the number of semi-honest parties ($h$) satisfy the following relation: n <= 2t + 2h by proving the necessity of oblivious transfer (OT) in this setting, which is known to be a cryptographic primitive. Furthermore, a new protocol, {bf QuadSquad}, is designed in the 4 party setting, which can withstand 1 malicious and 1 semi-honest corrupt parties. Also, this work extends QuadSquad to support privacy-preserving solutions for machine learning inference and liquidity matching.

Though this work addresses view-leakage attacks, the resilience is still not close enough to the full threshold (i.e., the number of corrupt parties = n-1). To meet this goal while ensuring a strong security guarantee of GOD and fairness, this thesis opts for another unconventional adversarial model introduced by Ishai et al. (TCC 2022), ``MPC with a friend, where there is an additional helper party (HP) along with the computational parties. This work considers an analogous model of friends and foes, where the helper party is semi-honest, and a malicious adversary corrupts up to n-1 parties. HP and the malicious adversary are not colluding. However, if the malicious adversary sends non-protocol messages to HP, this work proves that fairness and GOD are impossible to achieve. Therefore, this work considers either the malicious adversary corrupting up to n-1 parties or the helper party as semi-honest to design a generic $n$ party framework, {bf Asterisk}. This framework is more suitable where a centralized entity exists which maintains the integrity of the system. The dark pool (matching lists of buy and sell orders of Securities, obliviously) is an example that fits well in this setting, where the Securities and Exchange Commission (SEC) acts as the helper party. This work designs the required building blocks in the Asterisk framework to support the dark pool application.

The model discussed in the aforementioned paragraph is also relevant to the application of privacy-preserving ride-sharing services. This thesis designs a new ride-sharing protocol, {bf QuickPool}, which is much faster than the existing works, computationally extremely lightweight, and accommodates simultaneous multiple matching between riders and drivers. Currently, this work is under submission.

ZK. In the second part, the thesis focuses on ZK proofs. In standard ZK, a prover tries to convince a verifier about the correctness of a statement. Corresponding to the statement, a witness asserts that the statement is indeed correct, where the witness is known only to the prover. If the prover is correct, ZK proofs ensure that the verifier accepts the proof (completeness). On the other hand, if the prover is cheating, that is, the statement is not correct, or it does not have a witness, in that case, the verifier rejects the proof with a very high probability (soundness). Furthermore, from the proof, the verifier does not learn any information about the witness other than the correctness of the statement (zero-knowledge). ZK proofs find applications in various problems, such as validating the correctness of transactions on blockchains and ensuring honest behaviour in a system. However, in various scenarios, such as multi-wallet anonymous payments, where an individual party may not satisfy any certain predicate (e.g., the total transaction amount is greater than a publicly known value, but the value of the coins from individual parties may not require to satisfy any condition), although all the involved parties jointly must satisfy a predetermined predicate. In such scenarios, standard ZK protocols are not sufficient. In fact, it is not clear how to validate such predicates. Thus, this work formalizes the notion of distributed-prover ZK, where the proof of a public statement is generated jointly by a group of provers holding secret shares of witness. A significant amount of work has been done in the literature that focuses on improving the efficiency (proof size, proof generation time, and verification time) of ZK protocols to ensure practicality. Thus, it is desirable to also inherit such properties into the distributed-prover ZK. For that purpose, this work designs a compiler that takes a single-prover ZK protocol and compiles it into a distributed-prover ZK protocol. This work also designs a new ZK protocol that improves the proof size and verification time while achieving efficient distributed-proof generation.