DeCompute 2023

Talks

Benny Pinkas-Multiple Facets of MPC: In a captivating presentation, Benny Pinkas illuminated the evolutionary journey of Multi-Party Computation (MPC), spanning from Yao’s Millionaire Problem to its contemporary applications in the realm of Blockchain. Throughout his engaging discourse, Pinkas shed light on the transformative power of generic MPC implementations, unearthing underlying issues that were previously confined to theoretical complexities.

Key Takeaways:

1. Historical Context and Evolution: Benny Pinkas masterfully navigated the audience through the annals of MPC, starting with the Yao’s Millionare Problem — the first attempt to answer how two parties exchanged values without disclosing each other. He emphasised on the fact that Yao’s millionare problem is not only useful for comparing numbers rather it can be translated to any function computation and thats how two approaches to computing a function with private inputs evolved namely: Garbled circuit and Secret Sharing .
2. Trust on Central Entities: He emphasised that MPC may not secure information exchanged between parties which leads to low trust in the entities like auctioneer in a bidding scenario.
3. Unveiling Inherent Challenges: Pinkas astutely pointed out that the implementation of generic MPCs unearthed a new set of challenges, transcending beyond mere asymptotic complexities. The work on Fairplay Systems brought out new issues like cache, memory and communication leakage even though security proofs have been rigorously proved in academia. He pointed that generic MPCs may not be be efficient for practical applications like Private Set Intersections or Encrypting Database Operations. This crucial insight underscores the importance of practical, real-world applications in the ongoing development of MPC.
4. Blockchain Integration: Pinkas emphasized a pivotal advancement in MPC technology — its seamless integration with Blockchain. He elucidated how this fusion could serve as an underlying communication layer, enabling the verification of computations by players without the need to repose trust in any central entities.

Pratyay Mukherjee — Classgroup based DKG protocol: Pratyay Mukherjee unveiled a pioneering approach to achieving robust public verifiability in Verifiable Secret Sharing (VSS) through the ingenious application of Classgroups. Their work not only advances the state-of-the-art in VSS but also introduces a Non-Interactive Distributed Key Generation (NI-DKG) with unmatched efficiency.

Key Innovations:

1. Strong Public Verifiability in VSS: Mukherjee’s work represents a significant leap forward in the realm of Verifiable Secret Sharing. He emphasises the Public verifiability can enjoy correctness gurantees yet can fail to provide privacy if the number of corrupt adversaries are more than the threshold.
2. Hard to Achieve Strong Verifiability in Interactive Protocol: He pointed out that it is hard to achieve strong verifiability gurantees in interactive protocols because if there are enough signatories it can be proven to anyone that it is publicy verifiable but it cannot achieve strong pub;ic verifiability as not all receipents might respond due to corruptions or synchronous requirement in the network.
3. Strong Verifiability in Non Interactive Modes: Mukherjee directs his presentation towards zero knowledge proofs that can be used to achieve strong verifiability. By attaching a Non-Interactive Zero Knowledge Proof to an encrypted share, anyone can verify its truthfulness without relying on all all parties or being downsized by adversaries
4. Classgroups as a Approach towards Strong Verifiability: Pratyay highlighted some prior work towards strong public verifiability using Lattice based cryptography and Cyclic group based solutions. But both relied on range proofs make it inefficient. With this he introduces Class Groups as a subgroup in Discrete Log ios easy but has a generator g in group G where Discrete Log is hard. This structure results in simple, efficient and strong publicly veriable VSS without range proofs.
5. Efficiency Surpassing State-of-the-Art: Mukherjee’s Non-Interactive Distributed Key Generation (NI-DKG) with Class group based VSS stands out for its exceptional efficiency, surpassing existing VSS implementations with public verifiability. This represents a substantial stride towards more streamlined and scalable cryptographic processes.

Opal Wright -Fiat-Shamir vulnerabilities: Opal Wright’s impassioned presentation delved into a critical aspect of cryptographic protocols: the verification of inputs and outputs in Fiat Shamir Transforms. Through a compelling demonstration, she illuminated the potential pitfalls, particularly in the context of Bullet Proofs, where missed input values can lead to minting attacks, resulting in counterfeit yet seemingly valid proofs. Wright advocated for a proactive approach, emphasizing the importance of code reviews, meticulous documentation of inputs and outputs, and comprehensive hashing as essential strategies to fortify the integrity of cryptographic processes.

Key Takeaways:

1. Fiat Shamir Transforms: A Crucial Component: Wright emphasized the pivotal role played by Fiat Shamir Transforms in cryptographic protocols. She highlighted how the verification of inputs and outputs forms the bedrock of secure and reliable cryptographic operations.
2. Vulnerabilities in Bullet Proofs: Through a vivid demonstration, Wright unveiled a potential vulnerability in Bullet Proofs arising from missed input values during the Fiat Shamir Transform. This oversight could lead to minting attacks, enabling the generation of fraudulent yet seemingly legitimate proofs.
3. Preventive Measures through Code Reviews: Wright advocated for rigorous code reviews as a first line of defense against vulnerabilities. Thoroughly scrutinizing the codebase helps identify and rectify potential weaknesses, ensuring the robustness of cryptographic implementations.
4. Comprehensive Documentation of Inputs and Outputs: Wright underscored the significance of clear and detailed documentation. By meticulously listing all inputs and outputs, developers can create an invaluable resource for verification, reducing the likelihood of oversights that may lead to vulnerabilities.
5. Hashing for Enhanced Security: Wright proposed a powerful strategy: comprehensive hashing of all transmitted data. This approach serves as an additional layer of security, safeguarding against potential tampering or manipulation of critical information.

Yashvanth Kondi — Threshold ECDSA in Three Rounds: With a focus on DKLS t-out-of-n and 2-out-of-n protocols, Kondi introduces a novel three-round Threshold ECDSA signing protocol with malicious security against dishonest majority. In this work, he highlights the protocols’s realization in the Universal Composability (UC) model, leveraging ideal commitment and two-party multiplication primitives.

Key Contributions:

1. Non linear computations in ECDSA: Kondi’s talk touches upon the challenges posed by the non-linear signing equation in ECDSA, particularly in distributed computing settings. He underlines that traditional methods involve sequential subprotocols contributing to multiple rounds of protocol and inefficiency
2. The Protocol: The protocol presented by Kondi address the challenges of distributed signing with ECDSA . It is derived from existing t-of-n and 2-of-n signing DKLS protocol, with integrated consistency checks for intermediate computations, a technique pioneered by Abram et al. and further developed by Groth and Shoup. He highlights a significant reduction in round complexity of this protocol, aligning it with the efficiency of Schnorr scheme for threshold signing with this protocol.

Nikos Makriyannis — Practical Key-Extraction attacks in leading wallets: In a groundbreaking demonstration, Nikos Makriyannis revealed a series of sophisticated attacks targeting prominent Multi-Party Computation (MPC) protocols and the wallets they are implemented on. These attacks shed light on vulnerabilities that can lead to private key exfiltration, underscoring the critical importance of robust cryptographic defense measures.

Key Demonstrations:

1. Denial of Service Attack on 2PC Signing Protocol: Makriyannis showcased a potent attack on a 2PC signing protocol, exposing a vulnerability that allowed for the retrieval of partial signatures through malicious means. This painstaking attack required a staggering 256 signature runs to successfully retrieve the secret key shares of a party.
2. GG18 Protocol Exploitation: The second demonstration targeted the GG18 protocol, highlighting a clever bypass of Zero-Knowledge (ZK) range proofs. By strategically selecting Paillier primes and leveraging the Chinese Remainder Theorem, this attack was able to expose the complete secret key share of a party with remarkable efficiency, requiring only 16 signatures.
3. Signature Scheme Without ZK Proofs Vulnerability: The final attack honed in on a signature scheme lacking Zero-Knowledge Proofs. In a startling revelation, Makriyannis illustrated how just one signature could be leveraged to acquire the secret key share of a user, underscoring the critical need for comprehensive security measures.

Johnathan Katz Securing WalletsThreshold Cryptography in a Federated Key Management Network: Johnathan Katz’s presentation provided a compelling vision of the Federal Key Management Network’s potential to redefine threshold cryptography. By shifting the burden of key management to servers, this approach offers a powerful fusion of enhanced security, usability, and availability. Furthermore, its ability to address the challenges of non-federated architecture through aggregate preprocessing, batch signing, and key-independent presignatures showcases its transformative impact on the field of MPC.

Daniel Nobel -Moral Foundations of MPC: In a thought-provoking discourse, Daniel Nobel underscored the paramount importance of trust in the deployment of Multi-Party Computation (MPC) in real-world scenarios. He eloquently elucidated that while complete trustlessness may be an elusive ideal, understanding and establishing trust channels between senders and receivers is a critical facet of secure MPC implementation:

Key Insights:

1. Trust Dynamics in MPC Deployment: Nobel examined the intricacies of trust within the context of MPC deployment. He posed that while achieving complete trustlessness may be a theoretical ambition, it remains practically unattainable. Instead, understanding and managing trust channels between parties emerge as pivotal factors in ensuring the security of MPC protocols.
2. The Human Element: Guardians of Trust: Nobel highlighted a crucial aspect in the realm of secure MPC — the indispensable role played by experts. These experts encompass a diverse spectrum, ranging from protocol developers and software engineers to auditors and reviewers. Their collective expertise forms the bedrock upon which secure MPC deployments are built.
3. Shifting Focus: From Eliminating to Developing Trust: Nobel’s insight reframes the narrative surrounding trust in MPC. Rather than striving for the unattainable goal of absolute trustlessness, MPC practitioners must pivot towards establishing mechanisms to cultivate and bolster trust. This paradigm shift recognizes the human element as an integral component of secure MPC deployment.
4. A Holistic Approach to Trust Management: Nobel’s perspective advocates for a comprehensive approach to trust management. This entails meticulous protocol development, rigorous software engineering practices, and thorough auditing and review processes. By fortifying each link in the trust chain, MPC practitioners can foster an environment of confidence and reliability.

Dolev Mutzari — 2PC-MPC — Large Scale MPC for Permissionless Networks: Dolev Mutzari’s presentation shines a spotlight on the formidable challenges facing Multi-Party Computation (MPC) in the unicast setting, particularly when dealing with a large number of participants. In response, he introduces — 2PC MPC, wherein distributed parties collectively emulate a single entity. However, this advancement poses critical questions about key management and rotation. Mutzari addresses this by unveiling the pivotal building block, Threshold Paillier, which forms the bedrock of 2PC-MPC. This innovative approach not only allows for batch signatures for the first time but also achieves a remarkable increase in throughput and decryption rates across extensive networks of participants.

Key Innovations:

1. The Challenge of Large Scale MPC: Mutzari navigates through the inherent obstacles of deploying MPC in the unicast setting with a substantial number of participants. He addresses the critical need for an efficient solution that can accommodate this level of scale.
2. 2PC MPC: By enabling distributed parties to seamlessly emulate a single entity, Mutzari pioneers a solution that promises to revolutionize the landscape of large-scale MPC.
3. Key Management and Rotation: A Critical Consideration: Mutzari acknowledges the pivotal importance of managing and rotating keys within the 2PC MPC framework. This acknowledgment serves as a testament to his comprehensive approach, ensuring the protocol’s long-term viability.
4. Threshold Paillier: A Building Block: The unveiling of Threshold Paillier stands as a monumental contribution. This foundational element not only facilitates batch signatures for the first time but also achieves a substantial increase in throughput and decryption rates, especially in the context of extensive networks comprising 100 or 1000 parties.

Ying Tong Lai — Crossover: MPC and zk-SNARKs: Ying Tong Lai illuminated a compelling convergence between Multi-Party Computation (MPC) and zk-SNARKs, forging a dynamic alliance with far-reaching implications. Her discussion zeroed in on applications poised to benefit from this synergy, notably Public Auditability and Multiparty Proving for zk-SNARKs. Lai went on to spotlight cutting-edge advancements in multiparty proving systems, including collaborative zk-SNARKs, which distribute proving responsibilities among multiple nodes, thereby amplifying the efficiency and security of zk-SNARKs proof generation.

Key Insights:

1. Harmonizing MPC and zk-SNARKs: Lai’s presentation unveiled an enthralling intersection between Multi-Party Computation and zk-SNARKs, unlocking a realm of possibilities for secure and private computations.
2. Applications of Convergence: Lai accentuated the potential applications that can harness this crossover, notably Public Auditability and Multiparty Proving for zk-SNARKs. This fusion promises to fortify the security and efficiency of cryptographic operations.
3. Collaborative zk-SNARKs: A Leap Forward: Lai shone a spotlight on the frontier of multiparty proving systems, particularly collaborative zk-SNARKs. This innovative approach delegates proving responsibilities across multiple nodes, not only enhancing the efficiency of proof generation but also dispersing the witness among a distributed network of nodes.
4. Efficiency and Security Amplified: Through this collaborative approach, Lai envisions a future where zk-SNARKs not only thrive in terms of efficiency but also fortify their security posture.

Dima Kogan -How to share a share: key distribution in institutional MPC wallets : Dima Kogan’s insightful presentation zeroed in on a critical aspect of multiparty wallet scenarios: fortifying security against server-side attacks, notably Man-in-the-Middle (MiTM) intrusions when incorporating a new node into an existing network. He delved into innovative solutions for distributing shares among nodes during this process, with a special focus on leveraging Trusted Hardware and employing an Out-of-Band Channel for share distribution via Password Authenticated Key Exchange (PAKE).

Key Insights:

1. Mitigating Server-Side Attacks in Multiparty Wallets: Kogan’s talk revolved around the imperative need to safeguard against server-side attacks, particularly in scenarios involving multiparty wallets. He emphasized the significance of fortifying security measures during the addition of a new node to the network.
2. Trusted Hardware: A Pillar of Security: Kogan discussed Trusted Hardware as an approach where users can authenticate using the enclave. But this setup relies on the underlying auth setup’s security.
3. Key Exchange with Out-of-Band Channel: Kogan advocated for a strategic approach involving Key Exchange through an Out-of-Band Channel. This method ensures that the distribution of shares remains secure and impervious to potential attacks, offering an additional layer of protection.
4. PAKE: A Shield Against Intrusions: The use of Password Authenticated Key Exchange (PAKE) emerged as a linchpin in Kogan’s strategy. By employing this powerful tool, he demonstrated the process of share distribution where Admin encrypts the shares and stores . Next with out of band communication he invites the user to access the shares. The user can authenticate decrypt his key share and authenticate itself.

Panel Discussion

Panel 1 : Revisiting Design and Audit Cycle

Question 1: How does the audit cycle goes from production to practice? What is the process of audit cycle and how does the end report look like?

The Panelists align on the process of audit cycle with few twitches on their individual practices. They press on the importance of scoping as the first step towards auditing process. Apart from the usual process of Code review the panelist emphasize on threat modeling specially in MPC. They prepare their findings in form of a test report and make recommendations accordingly.

Question 2: Academia is incentive by exploring novel solutions and grants associated with it whereas industries incentivize on building upon these peer reviewed papers. This creates an inherent trust between academia and the industry. What is the role of audit companies in this scenario ? Is there a need of other third party to handle this mismatch?

The Panelist acknowledged that they often come across such scenarios, they use proofs presented in the paper in the audit process. Joop from Trail of Bits pressed on the his opinion that the academia should be responsible for checking the security proofs and expecting audit companies for proof checking can lead to disappointment. He went further by highlighting that some scenarios Trail of Bits does proof checks but there is no gurantee of any findings. Kang Li agress with Joop on the fact that audit companies focuses on product not the algorithm. He further explains that most of the bugs in MPC is caused by implementation rather than the algorithm. He ends with a note that auditing does not give bug free guarantee it helps companies to find them and lower their risks.

Question 3: Companies that implement MPC protocols make some tweaks in communication protocol or change the architecturewhich is rarely detailed in academic paper? How does audit companies handle these tweaks? What role do audit companies take in this scenario and how it is fixed?

Nguyen explained that auditing companies in these scenarios make note of assumptions and security concerns about the protocol. They investigate that the protocols are strictly following those requirements and assumptions. Kang Li shares one of his experiences of a similar situation where the protocol was changed from two party to n party . They contributed to this auditing by not claiming that they found a bug rather reminding them of the difference between their implementation and the protocol in the paper. Joop adds that audit companies look at various products where they come across various problems. They can identify common problems arising because of the tweak that can potentially lead to attacks. Mikerah adds that its very common for companies to reach out to audit firms specifically for tweaks. She explains that sometimes tweaks do not break the system but most common tweaks in MPC are based on Aborts and sometimes the network layer does not support it.