Please find a schedule below. In person at Burrill 140, on UIUC campus.
Parking: There is ample all-day metered parking around or inside Krannert Center for the Performing Arts, which is within walking distance to Burrill. It will be convenient to pay with the MobileMeter app. There are also a few metered parking spaces on the street between Burrill and Illini Union (you will again find it convenient to use the app). Most other outdoor parking lots in the area will require a permit, please be careful that you do not accidentally park in a permit-only space!
Eating: We will have breakfast, boxed lunches and coffee available. The Illini Union next door has Starbucks coffee, bagels and a couple of other restaurants (https://union.illinois.edu/food). There are also plenty of other dining options within a 5-min walking radius.
We are grateful for support from the UIUC CS department, and the National Science Foundation.
Parking: There is ample all-day metered parking around or inside Krannert Center for the Performing Arts, which is within walking distance to Burrill. It will be convenient to pay with the MobileMeter app. There are also a few metered parking spaces on the street between Burrill and Illini Union (you will again find it convenient to use the app). Most other outdoor parking lots in the area will require a permit, please be careful that you do not accidentally park in a permit-only space!
Eating: We will have breakfast, boxed lunches and coffee available. The Illini Union next door has Starbucks coffee, bagels and a couple of other restaurants (https://union.illinois.edu/food). There are also plenty of other dining options within a 5-min walking radius.
We are grateful for support from the UIUC CS department, and the National Science Foundation.
Time |
Speaker/Event Abstracts below! |
10 - 10.50, 10.50 - 11 |
Coffee/Networking, Opening Remarks Plaza outside Burrill Hall |
11 - 11.40 |
Hemanta Maji (Purdue) Burrill 140 |
11.40 - 12.10 |
Nerla Jean-Louis (UIUC) Burrill 140 |
12.10 - 12.40 |
Lightning Talks session Bolton Bailey, Sourav Das, Amit Agarwal, Peiyuan Liu, Seunghoon Lee, Alex Hoover, Mohammad Hassan Ameri |
12.40 - 2.00 |
Lunch |
2.00 - 2.30 |
Yanyi Liu (Cornell) Burrill 140 |
2.30 - 3.00 |
Blake Holman (Purdue) Burrill 140 |
3.00 - 3.40 |
David Heath (UIUC) Burrill 140 |
3.40 - 4.00 |
Coffee |
4.00 - 4.30 |
Chenkai Weng (Northwestern) Burrill 140 |
4.30 - 5.00 |
Xiuyu Ye (Purdue) Burrill 140 |
5 - 5.30 |
Haris Mughees (UIUC) Burrill 140 |
Titles and Abstracts:
HEMANTA MAJI
Title: Geometry of Secure Computation
Abstract: Reducing the overhead of security solutions increases their adoption. Motivated by such efficiency considerations, characterizing secure computation's round and communication complexity is natural.
The seminal results of Chor-Kushilevitz-Beaver (STOC-1989, FOCS-1989, DIMACS-1989) determine these complexities for deterministic computations. Determining randomized-output functions' round and communication complexity remained open for over three decades. This talk will present how we settled this long-standing open problem.
Our technical innovation is a geometric framework for this research -- opening a wormhole connecting it to geometry research. This framework encodes all candidate secure protocols as points. Studying mathematical properties of novel generalizations of their convex hull implies round and communication complexity results.
NERLA JEAN-LOUIS
Title: SGXonerated: Finding (and Partially Fixing) Privacy Flaws in TEE-based Smart Contract Platforms Without Breaking the TEE
Abstract: TEE-based smart contracts are an emerging blockchain architecture, offering fully programmable privacy with better performance than alternatives like secure multiparty computation. They can also support compatibility with existing smart contract languages, such that existing (plaintext) applications can be readily ported, picking up privacy enhancements automatically. While previous analysis of TEE-based smart contracts have focused on failures of TEE itself, we asked whether other aspects might be understudied. We focused on state consistency, a concern area highlighted by Li et al., as well as new concerns including access pattern leakage and software upgrade mechanisms. We carried out a code review of a cohort of four TEE-based smart contract platforms. These include Secret Network, the first to market with in-use applications, as well as Oasis, Phala, and Obscuro, which have at least released public test networks.
The first and most broadly applicable result is that access pattern leakage occurs when handling persistent contract storage. On Secret Network, its fine-grained access pattern is catastrophic for the transaction privacy of SNIP-20 tokens. If ERC-20 tokens were naively ported to Oasis they would be similarly vulnerable; the others in the cohort leak coarse-grained information at approximately the page level (4 kilobytes). Improving and characterizing this will require adopting techniques from ORAMs or encrypted databases. Second, the importance of state consistency has been underappreciated, in part because exploiting such vulnerabilities is thought to be impractical. We show they are fully practical by building a proof-of-concept tool that breaks all advertised privacy properties of SNIP-20 tokens, able to query the balance of individual accounts and the token amount of each transfer. We additionally demonstrate MEV attacks against the Sienna Swap application. As a final consequence of lacking state consistency, the developers have inadvertently introduced a decryption backdoor through their software upgrade process. We have helped the Secret developers mitigate this through a coordinated vulnerability disclosure, after which their state consistency should be roughly on par with the rest.
YANYI LIU
Title: One-way Functions and Hardness of (Probabilistic) Time-Bounded Kolmogorov Complexity w.r.t. Samplable Distributions
Abstract: Consider the recently introduced notion of \emph{probabilistic time-bounded Kolmogorov Complexity}, pK^t (Goldberg et al, CCC'22), and let MpK^tP denote the language of pairs (x,k) such that pK^t(x) \leq k. We show the equivalence of the following:
- MpK^{poly}P is (mildly) hard-on-average w.r.t. \emph{any} samplable distribution $\D$;
- MpK^{poly}P is (mildly) hard-on-average w.r.t. the \emph{uniform} distribution;
- Existence of one-way functions.
As far as we know, this yields the first natural class of problems where hardness with respect to any samplable distribution is equivalent to hardness with respect to the uniform distribution.
Under standard derandomization assumptions, we can show the same result also w.r.t. the standard notion of time-bounded Kolmogorov
complexity, K^t.
BLAKE HOLMAN
Title: Sustained Space and Cumulative Complexity Trade-offs for Data-Dependent Memory-Hard Functions
Abstract: Memory-hard functions (MHFs) are a useful cryptographic primitive which can be used to design egalitarian proof of work puzzles and to protect low entropy secrets like passwords against brute-force attackers. Intuitively, a memory-hard function is a function whose evaluation costs are dominated by memory costs even if the attacker uses specialized hardware (FPGAs/ASICs), and several cost metrics have been proposed to quantify this intuition. For example, space-time cost looks at the product of running time and the maximum space usage over the entire execution of an algorithm. Alwen and Serbinenko (STOC 2015) observed that the space-time cost of evaluating a function multiple times may not scale linearly in the number of instances being evaluated and introduced the stricter requirement that a memory-hard function has high cumulative memory complexity (CMC) to ensure that an attacker's amortized space-time costs remain large even if the attacker evaluates the function on multiple different inputs in parallel. Alwen et al. (EUROCRYPT 2018) observed that the notion of CMC still gives the attacker undesirable flexibility in selecting space-time trade-offs e.g., while the MHF Scrypt has maximal CMC Ω(N^2), an attacker could evaluate the function with constant O(1) memory in time O(N^2). Alwen et al. introduced an even stricter notion of Sustained Space complexity and designed an MHF which has s = Ω(N/ log N) sustained complexity t = Ω(N) i.e., any algorithm evaluating the function in the parallel random oracle model must have at least t = Ω(N) steps where the memory usage is at least Ω(N/ log N). In this work, we use dynamic pebbling games and dynamic graphs to explore trade-offs between sustained space complexity and cumulative memory complexity for data-dependent memory-hard functions such as Argon2id and Scrypt. We design our own dynamic graph (dMHF) with the property that any dynamic pebbling strategy either (1) has Ω(N) rounds with Ω(N) space, or (2) has CMC Ω(N^{3−ϵ}), substantially larger than N^2. For Argon2id we show that any dynamic pebbling strategy either (1) has Ω(N) rounds with Ω(N^{1−ϵ}) space, or (2) has CMC ω(N^2). We also present a dynamic version of DRSample (Alwen et al. 2017) for which any dynamic pebbling strategy either (1) has Ω(N) rounds with Ω(N/ log N) space, or (2) has CMC Ω(N^3 / log N).
DAVID HEATH
Title: Garbled RAM from Tri-State Circuits
Abstract: Secure Multiparty Computation (MPC) is a subfield of cryptography that allows mutually untrusting parties to work together to securely execute programs on their joint private inputs. One of the most exciting promises of MPC is the ability for end users to write ordinary programs that automatically inherit strong privacy-preserving properties.
Garbled RAM (GRAM) is a powerful and rapidly evolving technology which enables powerful MPC protocols that run in only a few protocol rounds and that can handle random access machine (RAM) programs. It is relatively easy and efficient to compile end user programs to RAM programs, and thus GRAM is a crucial ingredient for delivering on the promise of MPC for end user programs. Until very recently, GRAM constructions were both practically expensive and required deep technical expertise to understand.
In this talk, I will discuss recent advances to the GRAM primitive which make GRAM both far more efficient and far easier to understand. The centerpiece of the talk will be a new circuit model which we call "tri-state circuits". Tri-state circuits are similar in their complexity to Boolean circuits, but they support an additional control-flow-like mechanism, and this mechanism is powerful enough to implement random access memory. Tri-state circuits are compatible with garbling techniques, and this compatibility allows significant advances to GRAM. In the talk, I will focus on high-level explanations of the tri-state circuit model, showing how it can implement memory and why it is naturally suitable to garbling.
CHENKAI WENG
Abstract: Recent works on interactive zero-knowledge (ZK) protocols provide a new paradigm with high efficiency and scalability. However, these protocols suffer from high communication overhead, often linear to the circuit size. In this talk, I will present two new ZK protocols with communication sublinear to the circuit size, while maintaining a similar level of computational efficiency.
1. We designed a ZK protocol that can prove B executions of any circuit C in communication O(B + |C|) field elements (with free addition gates), while the best prior work requires a communication of O(B|C|) field elements. Our protocol is enabled by a new tool called information-theoretic polynomial authentication code, which may be of independent interest.
2. We developed an optimized implementation of this protocol which shows high practicality. For example, with B = 2048, |C| = 220, and under 50 Mbps bandwidth and 16 threads, QuickSilver, a state-of-the-art ZK protocol based on vector oblivious linear evaluation (VOLE), can only prove 0.78 million MULT gates per second (mgps) and send one field element per gate; our protocol can prove 14 mgps (18× improvement) and send 0.0064 field elements per gate (156× improvement) under the same hardware configuration.
3. Extending the above idea, we constructed a ZK protocol that can prove a single execution of any circuit C in communication O(|C|3/4). This is the first ZK protocol with sublinear communication for an arbitrary circuit in the VOLE-based ZK family.
XIUYU YE
Title: Improving the Security of Shamir's Secret-Sharing
Abstract:
Additive and Shamir's secret-sharing are fundamental building blocks of nearly all cryptography. They find numerous applications in threshold cryptography, secure storage, and secure computation. However, side-channel attacks pose a significant threat to these building blocks, endangering any primitive built on top of them. For example, probing one physical bit from each secret share completely breaks additive secret-sharing's security. Shamir's secret-sharing inherits these insecurities if its modulus and evaluation places are carelessly chosen. In light of these threats, NIST called for submissions to develop future recommendations and guidelines to make Shamir's secret-sharing more secure.
Previously, we had showed that most evaluation places were secure against physical bit probes. However, explicit algorithms to distinguish secure evaluation places from insecure ones were unknown. Recently, our research fully derandomizes this result. We characterize modulus and evaluation places that make Shamir's secret-sharing robust to these attacks. Our technical contributions connect this research to the orthogonality properties of a system of square wave functions, similar to Haar, Walsh, and Rademacher systems. The quality of this connection depends on finding good simultaneous rational approximation -- a Dirichlet-type approximation problem.
HARIS MUGHEES
Title: Enhancing the Real-World Performance of Private Information Retrieval
Abstract: During this presentation, I will be discussing private information retrieval (PIR) protocols that leverage Somewhat/Fully Homomorphic Encryption (SHE/FHE). PIR protocols enable clients to retrieve records from a server-hosted database in a confidential manner. I will begin by outlining the general framework of PIR protocols, followed by various optimizations to improve request size, computation time, and response overhead. The discussion will include the results from ACM CCS’21 and IEEE SP'23.
HEMANTA MAJI
Title: Geometry of Secure Computation
Abstract: Reducing the overhead of security solutions increases their adoption. Motivated by such efficiency considerations, characterizing secure computation's round and communication complexity is natural.
The seminal results of Chor-Kushilevitz-Beaver (STOC-1989, FOCS-1989, DIMACS-1989) determine these complexities for deterministic computations. Determining randomized-output functions' round and communication complexity remained open for over three decades. This talk will present how we settled this long-standing open problem.
Our technical innovation is a geometric framework for this research -- opening a wormhole connecting it to geometry research. This framework encodes all candidate secure protocols as points. Studying mathematical properties of novel generalizations of their convex hull implies round and communication complexity results.
NERLA JEAN-LOUIS
Title: SGXonerated: Finding (and Partially Fixing) Privacy Flaws in TEE-based Smart Contract Platforms Without Breaking the TEE
Abstract: TEE-based smart contracts are an emerging blockchain architecture, offering fully programmable privacy with better performance than alternatives like secure multiparty computation. They can also support compatibility with existing smart contract languages, such that existing (plaintext) applications can be readily ported, picking up privacy enhancements automatically. While previous analysis of TEE-based smart contracts have focused on failures of TEE itself, we asked whether other aspects might be understudied. We focused on state consistency, a concern area highlighted by Li et al., as well as new concerns including access pattern leakage and software upgrade mechanisms. We carried out a code review of a cohort of four TEE-based smart contract platforms. These include Secret Network, the first to market with in-use applications, as well as Oasis, Phala, and Obscuro, which have at least released public test networks.
The first and most broadly applicable result is that access pattern leakage occurs when handling persistent contract storage. On Secret Network, its fine-grained access pattern is catastrophic for the transaction privacy of SNIP-20 tokens. If ERC-20 tokens were naively ported to Oasis they would be similarly vulnerable; the others in the cohort leak coarse-grained information at approximately the page level (4 kilobytes). Improving and characterizing this will require adopting techniques from ORAMs or encrypted databases. Second, the importance of state consistency has been underappreciated, in part because exploiting such vulnerabilities is thought to be impractical. We show they are fully practical by building a proof-of-concept tool that breaks all advertised privacy properties of SNIP-20 tokens, able to query the balance of individual accounts and the token amount of each transfer. We additionally demonstrate MEV attacks against the Sienna Swap application. As a final consequence of lacking state consistency, the developers have inadvertently introduced a decryption backdoor through their software upgrade process. We have helped the Secret developers mitigate this through a coordinated vulnerability disclosure, after which their state consistency should be roughly on par with the rest.
YANYI LIU
Title: One-way Functions and Hardness of (Probabilistic) Time-Bounded Kolmogorov Complexity w.r.t. Samplable Distributions
Abstract: Consider the recently introduced notion of \emph{probabilistic time-bounded Kolmogorov Complexity}, pK^t (Goldberg et al, CCC'22), and let MpK^tP denote the language of pairs (x,k) such that pK^t(x) \leq k. We show the equivalence of the following:
- MpK^{poly}P is (mildly) hard-on-average w.r.t. \emph{any} samplable distribution $\D$;
- MpK^{poly}P is (mildly) hard-on-average w.r.t. the \emph{uniform} distribution;
- Existence of one-way functions.
As far as we know, this yields the first natural class of problems where hardness with respect to any samplable distribution is equivalent to hardness with respect to the uniform distribution.
Under standard derandomization assumptions, we can show the same result also w.r.t. the standard notion of time-bounded Kolmogorov
complexity, K^t.
BLAKE HOLMAN
Title: Sustained Space and Cumulative Complexity Trade-offs for Data-Dependent Memory-Hard Functions
Abstract: Memory-hard functions (MHFs) are a useful cryptographic primitive which can be used to design egalitarian proof of work puzzles and to protect low entropy secrets like passwords against brute-force attackers. Intuitively, a memory-hard function is a function whose evaluation costs are dominated by memory costs even if the attacker uses specialized hardware (FPGAs/ASICs), and several cost metrics have been proposed to quantify this intuition. For example, space-time cost looks at the product of running time and the maximum space usage over the entire execution of an algorithm. Alwen and Serbinenko (STOC 2015) observed that the space-time cost of evaluating a function multiple times may not scale linearly in the number of instances being evaluated and introduced the stricter requirement that a memory-hard function has high cumulative memory complexity (CMC) to ensure that an attacker's amortized space-time costs remain large even if the attacker evaluates the function on multiple different inputs in parallel. Alwen et al. (EUROCRYPT 2018) observed that the notion of CMC still gives the attacker undesirable flexibility in selecting space-time trade-offs e.g., while the MHF Scrypt has maximal CMC Ω(N^2), an attacker could evaluate the function with constant O(1) memory in time O(N^2). Alwen et al. introduced an even stricter notion of Sustained Space complexity and designed an MHF which has s = Ω(N/ log N) sustained complexity t = Ω(N) i.e., any algorithm evaluating the function in the parallel random oracle model must have at least t = Ω(N) steps where the memory usage is at least Ω(N/ log N). In this work, we use dynamic pebbling games and dynamic graphs to explore trade-offs between sustained space complexity and cumulative memory complexity for data-dependent memory-hard functions such as Argon2id and Scrypt. We design our own dynamic graph (dMHF) with the property that any dynamic pebbling strategy either (1) has Ω(N) rounds with Ω(N) space, or (2) has CMC Ω(N^{3−ϵ}), substantially larger than N^2. For Argon2id we show that any dynamic pebbling strategy either (1) has Ω(N) rounds with Ω(N^{1−ϵ}) space, or (2) has CMC ω(N^2). We also present a dynamic version of DRSample (Alwen et al. 2017) for which any dynamic pebbling strategy either (1) has Ω(N) rounds with Ω(N/ log N) space, or (2) has CMC Ω(N^3 / log N).
DAVID HEATH
Title: Garbled RAM from Tri-State Circuits
Abstract: Secure Multiparty Computation (MPC) is a subfield of cryptography that allows mutually untrusting parties to work together to securely execute programs on their joint private inputs. One of the most exciting promises of MPC is the ability for end users to write ordinary programs that automatically inherit strong privacy-preserving properties.
Garbled RAM (GRAM) is a powerful and rapidly evolving technology which enables powerful MPC protocols that run in only a few protocol rounds and that can handle random access machine (RAM) programs. It is relatively easy and efficient to compile end user programs to RAM programs, and thus GRAM is a crucial ingredient for delivering on the promise of MPC for end user programs. Until very recently, GRAM constructions were both practically expensive and required deep technical expertise to understand.
In this talk, I will discuss recent advances to the GRAM primitive which make GRAM both far more efficient and far easier to understand. The centerpiece of the talk will be a new circuit model which we call "tri-state circuits". Tri-state circuits are similar in their complexity to Boolean circuits, but they support an additional control-flow-like mechanism, and this mechanism is powerful enough to implement random access memory. Tri-state circuits are compatible with garbling techniques, and this compatibility allows significant advances to GRAM. In the talk, I will focus on high-level explanations of the tri-state circuit model, showing how it can implement memory and why it is naturally suitable to garbling.
CHENKAI WENG
Abstract: Recent works on interactive zero-knowledge (ZK) protocols provide a new paradigm with high efficiency and scalability. However, these protocols suffer from high communication overhead, often linear to the circuit size. In this talk, I will present two new ZK protocols with communication sublinear to the circuit size, while maintaining a similar level of computational efficiency.
1. We designed a ZK protocol that can prove B executions of any circuit C in communication O(B + |C|) field elements (with free addition gates), while the best prior work requires a communication of O(B|C|) field elements. Our protocol is enabled by a new tool called information-theoretic polynomial authentication code, which may be of independent interest.
2. We developed an optimized implementation of this protocol which shows high practicality. For example, with B = 2048, |C| = 220, and under 50 Mbps bandwidth and 16 threads, QuickSilver, a state-of-the-art ZK protocol based on vector oblivious linear evaluation (VOLE), can only prove 0.78 million MULT gates per second (mgps) and send one field element per gate; our protocol can prove 14 mgps (18× improvement) and send 0.0064 field elements per gate (156× improvement) under the same hardware configuration.
3. Extending the above idea, we constructed a ZK protocol that can prove a single execution of any circuit C in communication O(|C|3/4). This is the first ZK protocol with sublinear communication for an arbitrary circuit in the VOLE-based ZK family.
XIUYU YE
Title: Improving the Security of Shamir's Secret-Sharing
Abstract:
Additive and Shamir's secret-sharing are fundamental building blocks of nearly all cryptography. They find numerous applications in threshold cryptography, secure storage, and secure computation. However, side-channel attacks pose a significant threat to these building blocks, endangering any primitive built on top of them. For example, probing one physical bit from each secret share completely breaks additive secret-sharing's security. Shamir's secret-sharing inherits these insecurities if its modulus and evaluation places are carelessly chosen. In light of these threats, NIST called for submissions to develop future recommendations and guidelines to make Shamir's secret-sharing more secure.
Previously, we had showed that most evaluation places were secure against physical bit probes. However, explicit algorithms to distinguish secure evaluation places from insecure ones were unknown. Recently, our research fully derandomizes this result. We characterize modulus and evaluation places that make Shamir's secret-sharing robust to these attacks. Our technical contributions connect this research to the orthogonality properties of a system of square wave functions, similar to Haar, Walsh, and Rademacher systems. The quality of this connection depends on finding good simultaneous rational approximation -- a Dirichlet-type approximation problem.
HARIS MUGHEES
Title: Enhancing the Real-World Performance of Private Information Retrieval
Abstract: During this presentation, I will be discussing private information retrieval (PIR) protocols that leverage Somewhat/Fully Homomorphic Encryption (SHE/FHE). PIR protocols enable clients to retrieve records from a server-hosted database in a confidential manner. I will begin by outlining the general framework of PIR protocols, followed by various optimizations to improve request size, computation time, and response overhead. The discussion will include the results from ACM CCS’21 and IEEE SP'23.