BCD spring 2023
Welcome to the Bengaluru Crypto Day, spring-2023 edition. We will have a day full of exciting topics in cryptography presented by leading and early-career researchers.Speakers
Venue
CSA Seminar hall, room #254
Schedule
| Time | Speaker | Title |
|---|---|---|
| 09:30 - 09:35 | Welcome | |
Session: Foundations | ||
| 09:35 - 10:15 | Bhavana | Constant-rate Non-malleable Codes
Non-malleable codes are coding schemes which are resilient to tampering attacks. In this work, we will survey some recent progress in building rate-optimal NMCs.
|
| 10:15 - 10:30 | Girisha | Secure Auctions in presence of rational adversaries
Sealed bid auctions are used to allocate a resource among a set of interested parties. We construct the first concretely efficient and provably secure protocol for First Price Auctions in the rational setting.
|
| 10:30 - 10:45 | Shravani | Asymptotically Free Broadcast in Constant Expected Time via Packed VSS
Broadcast is an essential primitive for secure computation. We focus in this paper on optimal resilience (i.e., when the number of corrupted parties t is less than a third of the computing parties n), and with no setup or cryptographic assumptions. While broadcast with worst case t rounds is impossible, it has been shown [Feldman and Micali STOC88, Katz and Koo CRYPTO06] how to construct protocols with expected constant number of rounds in the private channel model. However, those constructions have large communication complexity, specifically O(n^2L + n^6log n) expected number of bits transmitted for broadcasting a message of length L. In this paper, we substantially improve the communication complexity of broadcast in constant expected time. Specifically, the expected communication complexity of our protocol is O(nL + n^4log n). We also consider parallel broadcast, where n parties wish to broadcast L bit messages in parallel. Our protocol has no asymptotic overhead for L = Ω(n^2log n), which is a common communication pattern in perfectly secure MPC protocols. As an independent interest, our broadcast is achieved by a packed verifiable secret sharing, a new notion that we introduce. We show a protocol that verifies O(n) secrets simultaneously with the same cost of verifying just a single secret. This improves by a factor of n the state-of-the-art.
|
| 10:30 - 10:45 | Ananya | Revisiting the Efficiency of Perfectly Secure Asynchronous Multi-Party Computation Against General Adversaries
Secure multi-party computation allows mutually distrusting parties to jointly compute a function without revealing their inputs. We consider the case when the distrust in the system is modelled as a general adversary characterized by an adversary structure Z, which enumerates all possible subsets of potentially corrupt parties. The work of Hirt and Tschudi (ASIACRYPT 2013) improved the amortized communication complexity of perfectly-secure multi-party computation against general adversaries in synchronous networks from O(|Z|^3) to O(|Z|^2) per multiplication gate. In this talk, we look at how we can extend this work to the asynchronous communication setting.
|
| 11:00 - 11:25 | Break
|
|
Session: Applied Cryptography | ||
| 11:25 - 12:05 | Dhinakaran | Private Certifier Intersection
Web 3.0 aims for decentralization of services and identity but the proposed protocols and standards often compromise on privacy as a tradeoff for decentralization. This talk focuses on providing privacy without compromising on decentralization for the presentation of verifiable credentials. We will introduce the notion of Private Certifier Intersection (PCI), which allows mutually distrusting parties to establish a trust basis for cross-validation of claims if they have one or more trust authorities (certifiers) in common. We will motivate, formally introduce PCI and then present protocols for different variants of PCI and their implementation on top of widely-used MP-SPDZ for MPC and OpenSSL and RELIC for elliptic-curve operations. Based on joint works with Bishakh Chandra Ghosh, Sikhar Patranabis, Venkatraman Ramakrishna, Krishnasuri Narayanam, and Sandip Chakraborty which appeared in ICBC’22 and NDSS’23.
|
| 12:05 - 12:20 | Moumita | Compute, but Verify: Efficient Multiparty Computation over Authenticated Inputs
Traditional notions of secure multiparty computation (MPC) allow mutually distrusting parties to jointly compute a function over their private inputs, but typically do not specify how these inputs are chosen. Motivated by real-world applications where corrupt inputs could adversely impact privacy and operational legitimacy, we consider a notion of authenticated MPC where the inputs are authenticated, e.g., signed using a digital signature by some certification authority. We propose a generic and efficient compiler that transforms any linear secret sharing based MPC protocol into one with input authentication.
|
| 12:20 - 12:35 | Nishat | Ruffle: Rapid 3-party shuffle protocols
Secure shuffle is an important primitive that finds use in several applications such as secure electronic voting, oblivious RAMs, secure sorting, to name a few. For time-sensitive shuffle-based applications that demand a fast response time, it is essential to design a fast and efficient shuffle protocol. In this work, we design secure and fast shuffle protocols relying on the techniques of secure multiparty computation. We make several design choices that aid in achieving highly efficient protocols. Specifically, we consider malicious 3-party computation setting with an honest majority and design robust protocols. Our shuffle protocols provide a fast online (i.e., input-dependent) phase compared to the state-of-the-art for the considered setting. To showcase the efficiency improvements brought in by our shuffle protocols, we consider two distinct applications of anonymous broadcast and secure graph computation via the GraphSC paradigm. In both cases, multiple shuffle invocations are required. Hence, going beyond standalone shuffle invocation, we identify two distinct scenarios of multiple invocations and provide customised protocols for the same. Further, we showcase that our customized protocols not only provide a fast response time, but also provide improved overall run time for multiple shuffle invocations. With respect to the applications, we not only improve in terms of efficiency, but also work towards providing improved security guarantees, thereby outperforming the respective state-of-the-art works. We benchmark our shuffle protocols and the considered applications to analyze the efficiency improvements with respect to various parameters.
|
| 12:35 - 12:50 | Anju | A faster third-order masking of lookup tables
Masking is an effective countermeasure to secure cryptographic implementations against side-channel attacks such as Differential Power Analysis (DPA) attacks. Such attacks exploit the physical leakages of a device like power consumption to reveal information about the secret key. The non-linear layers of Feistel and Substitution-Permutation Network (SPN) block ciphers are represented as S-boxes, and masking this layer is not straightforward. There exists two main types of S-box masking schemes: circuit-based masking and Table-Based Masking (TBM) schemes. Although Higher-Order TBM (HO-TBM) schemes can facilitate masking at any arbitrary order, they require a prohibitive amount of memory and overall execution time compared to circuit-based masking. Customised TBM schemes, particularly at first and second order, have shown to be more efficient than circuit-based schemes such as bit-sliced masking in terms of randomness requirement and execution time. Yet, currently, there are no customised third-order TBM scheme that are more efficient than instantiating a HO-TBM scheme at third-order. In this work, we propose a third-order TBM scheme for any S-boxes that is secure in the probing model and under composition, i.e. it is 3-SNI (Strong Non Interference) secure and also supports pre-processing. It is more efficient than current state-of-the-art HO-TBM methods instantiated at third-order, especially in terms of the overall execution time. For instance, when applied to masked AES-128, the running time is reduced by 80% without sacrificing the online execution speed. Our work highlights the potential for improving the performance of HO-TBM schemes at lower orders.
|
| 12:50 - 14:20 | Lunch
|
|
Session: MPC/PPML | ||
| 14:20 - 15:00 | Nishanth | Can Secure Two-party Computation be as fast as Cleartext?
Secure Two-party Computation (2PC) was introduced by Yao in the early 1980s and has since then captivated the attention of cryptography researchers for over four decades. While communication and computation overheads of these protocols can be quite high, remarkable progress has been made over the last few years to reduce these. In secure inference, a machine learning model owner can provide inference-as-a-service to clients, who hold input data points, in a cryptographically secure manner. While this problem is a special instance of 2PC, much work has gone into designing specific protocols and building systems to make secure inference practical. In this talk, I will describe new Function-Secret Sharing (FSS) based techniques for 2PC, in the correlated randomness model, that form the basis for a new secure inference system. By shifting overheads from communication to computation, these techniques lend themselves naturally to hardware acceleration. Using this, we obtain the first secure computation of ML inference algorithms on ImageNet scale datasets, that have almost the same cost as computing the algorithm in the clear!
|
| 15:00 - 15:15 | Kanav | Orca: FSS-based Secure Training with GPUs
Secure Two-party Computation (2PC) allows two parties to compute any function on their private inputs without revealing their inputs in the clear to each other. Since 2PC is known to have notoriously high overheads, one of the most popular computation models is that of 2PC with a trusted dealer, where a trusted dealer provides correlated randomness (independent of any input) to both parties during a preprocessing phase. Recent works construct efficient 2PC protocols in this model based on the cryptographic technique of function secret sharing (FSS). We build an end-to-end system ORCA to accelerate the computation of FSS-based 2PC protocols with GPUs. Next, we observe that the main performance bottleneck in such accelerated protocols is in storage (due to the large amount of correlated randomness), and we design new FSS-based 2PC cryptographic protocols for several key functionalities in ML which reduce storage by up to 5×. Compared to prior state-of-the-art on secure training accelerated with GPUs in the same computation model (PIRANHA, Usenix Security 2022), we show that ORCA has 4% higher accuracy, 123× lesser communication, and is 19× faster on CIFAR-10.
|
| 15:15 - 15:30 | Varsha | Secure Allegation Escrow System with Stronger Guarantees
The rising issues of harassment, exploitation, corruption, and other forms of abuse have led victims to seek comfort by acting in unison against common perpetrators (e.g., #MeToo movement). One way to curb these issues is to install allegation escrow systems that allow victims to report such incidents. The escrows are responsible for identifying victims of a common perpetrator and taking the necessary action to bring justice to them. However, users hesitate to participate in these systems due to the fear of such sensitive reports being leaked to perpetrators, who may further misuse them. Thus, to increase trust in the system, cryptographic solutions are being designed to realize secure allegation escrow (SAE) systems. In the work of Arun et al. (NDSS'20), which presents the state-of-the-art solution, we identify attacks that can leak sensitive information and compromise victim privacy. We also report issues present in prior works that were left unidentified. To arrest all these breaches, we put forth an SAE system that prevents the identified attacks and retains the salient features from all prior works. The cryptographic technique of secure multi-party computation (MPC) serves as the primary underlying tool in designing our system. At the heart of our system lies a new duplicity check protocol and an improved matching protocol. We also provide additional features such as allegation modification and deletion, which were absent in the state of the art. To demonstrate feasibility, we benchmark the proposed system with state-of-the-art MPC protocols and report the cost of processing an allegation. Different settings that affect system performance are analyzed, and the reported values showcase the practicality of our solution.
|
| 15:30 - 15:45 | Prateeti | Lower Bounds on Reconstructing Training Data from Private Learners
While differential privacy has evolved into the de facto notion of privacy in machine learning, the guarantees themselves are often difficult to interpret. In this talk, I’ll be focusing on a rigorous quantification of the question “how much data privacy does an $\epsilon$-DP guarantee actually confer?”, and develop an understanding of the theoretical underpinnings of a private algorithm’s resilience to data reconstruction adversaries (DRAs). In particular, I will be presenting a non-asymptotic analysis of the effectiveness of DRAs by well-informed adversaries against private learners, and derive lower bounds on the quality of reconstruction as a function of the privacy parameter and the adversary’s query budget.
|
| 15:45 - 16:10 | Break
|
|
Session: Applied cryptography | ||
| 16:10 - 16:50 | Vivek | Revisiting Driver Anonymity in ORide
Ride-Hailing Services (RHS) have become a popular means of transportation, and with their popularity comes the concerns of privacy of riders and drivers. ORide is one of the earliest privacy-preserving RHS protocols that was proposed at the USENIX Security Symposium 2017. ORide employs a Somewhat Homomorphic Encryption (SHE) scheme to protect the location information of riders and drivers from the eyes of the RHS Service Provider (SP). In the protocol, a rider and all drivers in a zone send their SHE encrypted location coordinates to SP who computes all the squared Euclidean distances between them and forwards them to the rider. The rider decrypts the ciphertext to obtain these distances and selects the optimal driver with the least Euclidean distance. In this talk, we demonstrate a location-harvesting attack on drivers in the ORide protocol by a group of colluding honest-but-curious riders. Though the ORide protocol aimed to thwart triangulation attacks by permuting the order of drivers for each ride request, we show that is still possible to mount a triangulation attack on ORide. Our work suggests that we need to carefully assess the threats arising from the specific application scenario considered while deploying somewhat homomorphic encryption schemes.
|
| 16:50 - 17:00 | Closing remarks
|
|