| Fri. May 27 |
Sat. May 28 |
Sun. May 29 |
| Friday, May 27, 2022 |
Session Chair |
Chaoping Xing |
|
|
|
8:30 am to 9:20 am |
High-Rate Storage Codes on Triangle-Free Graphs
Speaker: Alexander Barg
show abstract ＋
Consider an assignment of bits to the vertices of a connected graph G(V,E) with the property that the value of each vertex is a function of the values of its neighbors. A collection of such assignments is called a storage code of length |V| on G. If G contains many cliques, it is easy to construct storage codes of rate close to 1, so a natural problem is to construct high-rate codes on triangle-free graphs, where finding codes of rate >1/2 is a nontrivial task. Previously only isolated examples of storage codes of rate ≥ 1/2 on triangle-free graphs were given in the literature. The class of graphs that we consider is coset graphs of linear binary codes (Cayley graphs of the group F_{2^r}). One of the main results of this work is an infinite family of linear storage codes with rate approaching 3/4. We also give a group of necessary conditions for such codes to have rate potentially close to 1 and state a number of open problems. Joint work with Gilles Zémor.
|
|
|
|
9:20 am to 10:10 am |
Fast Fully Secure Multi-Party Computation over Any Ring with Two-Thirds Honest Majority
Speaker: Daniel Escudero
show abstract ＋
We introduce a new MPC protocol to securely compute any functionality over an arbitrary black-box finite ring (which may not be commutative), tolerating t<n/3 active corruptions while guaranteeing output delivery (G.O.D.).
Our protocol is based on replicated secret-sharing, whose share size is known to grow exponentially with the number of parties n. However, even though the internal storage and computation in our protocol remains exponential, the communication complexity of our protocol is constant, except for a light constant-round check that is performed at the end before revealing the output.
Furthermore, the amortized communication complexity of our protocol is not only constant, but very small: only 1 + (t-1)/n<4/3 ring elements per party, per multiplication gate over two rounds of interaction. This improves over the state-of-the art protocol in the same setting by Furukawa and Lindell (CCS 2019), which has a communication complexity of 8/3 field elements per party, per multiplication gate and while achieving fairness only.
As an alternative, we also describe a variant of our protocol which has only one round of interaction per multiplication gate on average, and amortized communication cost of <=3/2 ring elements per party on average for any natural circuit. Motivated by the fact that efficiency of distributed protocols are much more penalized by high communication complexity than local computation/storage, we perform a detailed analysis together with experiments in order to explore how large the number of parties can be, before the storage and computation overhead becomes prohibitive.
Our results show that our techniques are viable even for a moderate number of parties (e.g., n>10).
|
|
|
|
10:10 am to 10:30 am |
Break |
|
|
|
10:30 am to 11:20 am |
Efficient and Affordable Zero-Knowledge Proofs: ResNet Inference and RAM Computation
Speaker: Xiao Wang
show abstract ＋
Zero-knowledge (ZK) proofs with an optimal memory footprint have attracted a lot of attention because such protocols can easily prove very large computation with a small memory requirement. In this talk, the speaker will talk about some recent progress on concretely efficient ZK protocols and their applications in this setting. These protocols are very cheap computationally and can prove large statements like ResNet inference or large RAM-based computation with ease; on the other hand, it is designated-verifier, and the proof size is often linear to the circuit size.
|
|
|
|
11:20 am to 2:00 pm |
Break |
|
|
|
Session Chair |
Ignacio Cascudo |
|
|
|
2:00 pm to 2:50 pm |
Secure and Verifiable Computation
Speaker: Huaxiong Wang
show abstract ＋
Outsourcing computation has gained significant popularity in recent years due to the prevalence of cloud computing. How to keep the confidentiality of the client's data and how to ensure the correctness of the server's computation are two fundamental problems to achieve. Verifiable computation, introduced by Gennaro, Gentry and Parno in 2010, allows to delegate the computation of a function f on outsourced data x to third parties, such that the data owner and/or other third parties can verify that the outcome y = f(x) has been computed correctly by the third party. Constructing efficient verifiable computation schemes has attracted a lot of attention during the past decade. In this talk, we will present a brief overview of the state-of-the-art and discuss a new (multi-server) model for verifiable computation, which allows unconditional security, practical efficiency, and public delegation.
|
|
|
|
2:50 pm to 3:40 pm |
Cryptography Using One-Way Noisy Communication via Obfuscation
Speaker: Yuval Ishai
show abstract ＋
We consider the traditional goals of secure communication and secure computation when allowing only one-way communication over noisy channels:
- Can Alice transmit a message to Bob without Eve learning this message?
- Can Alice transmit exactly one of two messages to Bob without learning which one?
We show how to circumvent information-theoretic impossibility results by settling for computational security and using the power of cryptographic obfuscation. In particular, we show (under plausible assumptions) that message transmission is possible whenever Alice's channel to Bob is not a degradation of the channel to Eve, and general secure computation is possible over simple channels such as a binary symmetric channel or a binary erasure channel.
The first part of the talk is based on joint work with Alexis Korb, Paul Lou, and Amit Sahai.
The second part is based on joint work with Shweta Agrawal, Eyal Kushilevitz, Varun Narayanan, Manoj Prabhakaran, Vinod M. Prabhakaran, and Alon Rosen.
|
|
|
|
3:40 pm to 4:00 pm |
Break |
|
|
|
4:00 pm to 4:50 pm |
Mersenne Ring and Noise Signatures
Speaker: Antoine Joux |
Saturday, May 28, 2022
|
Session Chair |
Huaxiong Wang |
|
|
|
8:30 am to 9:20 am |
Update Bandwidth for Distributed Storage
Speaker: Yung Hsiang Han
show abstract ＋
In this talk, we consider the update bandwidth in distributed storage systems (DSSs). The update bandwidth, which measures the trans- mission efficiency of the update process in DSSs, is defined as the average amount of data symbols transferred in the network when the data symbols stored in a node are updated. This talk contains the following contribu- tions. First, we establish the closed-form expression of the minimum update bandwidth attainable by irregular array codes. Second, after defining a class of irregular array codes, called Minimum Update Bandwidth (MUB) codes, which achieve the minimum update bandwidth of irregular array codes, we determine the smallest code redundancy attainable by MUB codes. Third, the code parameters, with which the minimum code redundancy of irreg- ular array codes and the smallest code redundancy of MUB codes can be equal, are identified, which allows us to define MR-MUB codes as a class of irregular array codes that simultaneously achieve the minimum code re- dundancy and the minimum update bandwidth. Last, we establish a lower bound of the update complexity of MR-MUB codes, which can be used to prove that the minimum update complexity of irregular array codes may not be achieved by MR-MUB codes.
|
|
|
|
9:20 am to 10:10 am |
Combinatorial List-Decoding: a Brief Introduction
Speaker: Chong Shangguan
show abstract ＋
The notion of list-decoding was introduced independently by Elias and Wozencraft in the 1950s. It is a generalization of the unique decoding model typically considered in coding theory, where given a received word the decoder might output a list of possible codewords, instead of a unique one. This allows for handling a greater number of errors than that allowed by unique decoding.
More interestingly, list-decoding can be viewed as a bridge that connects Shannon’s stochastic noise model and Hamming’s adversarial noise model: even under adversarial noise conditions, it is possible to achieve the information-theoretic optimal trade-off between the code rate and the list-decoding radius (i.e., the fraction of errors that can be corrected), at the lost of list size.
The fundamental problem of combinatorial list-decoding is to find the optimal tradeoff of the following three parameters: code rate, list-decoding radius, and list size. In this talk, we will briefly introduce some related problems and results, with particular focus on the combinatorial list-decoding of Reed-Solomon codes.
|
|
|
|
10:10 am to 10:30 am |
Break |
|
|
|
10:30 am to 11:20 am |
Ring-Based Identity Based Encryption–Asymptotically Shorter MPK and Tighter Security
Speaker: Zhedong Wang
show abstract ＋
Identity-based Encryption (IBE) is a generalization of the traditional public-key encryption (PKE) in which a publicly known string (id) of a party can serve as its public key pkid. This primitive is particularly useful in scenarios that require to manage a large amount of public keys, without the need to access a public-key infrastructure (PKI). In this talk, we show a construction of an identity based encryption from the ring learning with errors assumption (RLWE), with shorter master public keys and tighter security analysis. To achieve this, we develop three new methods: (1) a new homomorphic equality test method using nice algebraic structures of the rings, (2) a new family of hash functions with natural homomorphic evaluation algorithms, and (3) a new insight for tighter reduction analyses. These methods can be used to improve other important cryptographic tasks, and thus are of general interests.
|
|
|
|
11:20 am to 2:00 pm |
Break |
|
|
|
Session Chair |
Yuval Ishai |
|
|
|
2:00 pm to 2:50 pm |
Oblivious Transfer and Its Arithmetic Generalization
Speaker: Kang Yang
show abstract ＋
Oblivious transfer is the foundation of cryptography, and is also a crucial building block for secure multi-party computation (MPC). It is well-known that constructing OT requires public-key primitives. However, it is too expensive when a large number of OT correlations is needed for applications such as MPC and zero-knowledge (ZK) proofs. The practical approach is to extend a small number of “base OTs” to a large number of OT correlations using cheap operations, based on the idea of OT extension. All existing concretely efficient OT extension protocols first generate correlated OT (COT), and then transform it into the standard OT. Furthermore, COT can be directly used to design MPC protocols and ZK proofs. Compared to that COT is mainly used for Boolean circuits, its arithmetic generalization (i.e., vector oblivious linear-function evaluation, VOLE in short) is mainly applied for arithmetic circuits.
This talk will present the techniques to construct COT protocols in two lines, where one is the IKNP approach and the other is the PCG approach. Then, this talk will discuss how to extend PCG-based COT to VOLE. Finally, this talk will roughly show the MPC and ZK applications of COT and VOLE. Our results involved in this talk have been published in ACM CCS 2020, ACM CCS 2021, S&P 2021 and USENIX Security 2021.
|
|
|
|
2:50 pm to 3:40 pm |
Reverse Multiplication Friendly Embeddings and Applications in Secure Computation and Zero Knowledge
Speaker: Ignacio Cascudo
show abstract ＋
Secure multiparty computation and zero knowledge proofs are two of the most relevant cryptographic primitives nowadays. Many multiparty computation protocols and zero knowledge proofs require to represent the computations and statements they deal with as arithmetic circuits or related models of computation over large finite fields. This may however cause overheads, which may seem in principle unnecessary when a more natural way to represent such computations would be as an arithmetic circuit over a small field. One option to amortize these overheads is by batching together many computations over the smaller field and embedding them together as one computation over the large field. This batching can be achieved through the notion of reverse multiplication friendly embeddings (Crypto 18). In this talk I will discuss this notion and the application it has found in multiparty computation and zero knowledge in the last few years.
|
|
|
|
3:40 pm to 4:00 pm |
Break |
|
|
|
4:00 pm to 4:50 pm |
Non-Malleable Multi-Party Computation
Speaker: Fuchun Lin
show abstract ＋
We study a tamper-tolerant implementation security notion for general purpose Multi-Party Computation (MPC) protocols, as an analogue of the leakage-tolerant notion in the MPC literature. An MPC protocol is tamper-tolerant, or more specifically, non-malleable (with respect to a certain type of tampering) if the processing of the protocol under corruption of parties (and tampering of some ideal resource assumed by the protocol) can be simulated by an ideal world adversary who, after the trusted party spit out the output, further decides how the output for honest parties should be tampered with. Intuitively, we relax the correctness of secure computation in a privacy-preserving way, decoupling the two entangled properties that define secure computation. The rationale behind this relaxation is that even the strongest notion of correctness in MPC allows corrupt parties to substitute wrong inputs to the trusted party and the output is incorrect anyway, maybe the importance of insisting on that the adversary does not further tamper with the incorrect output is overrated, at least for some applications. Various weak privacy notions against malicious adversary play an important role in the study of two-party computation, where full security is hard to achieve efficiently.
We begin with the honest majority setting, where efficient constructions for general purpose MPC protocols with full security are well understood assuming secure point-to-point channels.
We then focus on non-malleability with respect to tampered secure point-to-point channels. (1) We show achievability of non-malleable MPC against the bounded state tampering adversary in the joint tampering model through a naive compiler approach, exploiting a known construction of interactive non-malleable codes. The construction is currently not efficient and should be understood as showing feasibility in a rather strong tampering model. (2) We show efficient constructions of non-malleable MPC protocols against weaker variants of bounded state tampering adversary in the independent tampering model, where the protocol obtained have the same asymptotic communication complexity as best MPC protocols against honest-but-curious adversary. These are all information-theoretic results and are to be contrasted against impossibility of secure MPC when secure point-to-point channels are compromised.
Though general non-malleable MPC in no honest majority setting is beyond the scope of this work, we discuss interesting applications of honest majority non-malleable MPC in the celebrated MPC-in-the-head paradigm. Other than an abstract result concerning non-malleability, we also derive, in standard model where there is no tampering, that strong (ideal/real world) privacy against malicious adversary can be achieved can be achieved in a conceptually very simple way.
|
| Sunday, May 29, 2022 |
Session Chair |
Yung Hsiang Han |
|
|
|
8:30 am to 9:20 am |
Recent Progress on Binary Deletion-Correcting Codes Speaker: Venkatesan Guruswami
show abstract ＋
In the worst-case (bit)-deletion noise model, a subset of up to t arbitrarily chosen bits are deleted from a sequence of n codeword bits. Crucially, the locations of the deleted bits are not known to the receiver who receives a subsequence of the transmitted bit-string. The goal is to design codes of low redundancy that allow recovery of the deleted bits and the original codeword. The study of deletion-correcting codes itself is quite old, dating back to optimal single-deletion codes in the 1960s, and positive rate codes to correct t = Ω(n) deletions in the 1990s. However, many basic questions remained open and our understanding of deletion-correcting codes significantly lagged the vast literature concerning error-correcting codes to correct bit flips.
After a long hiatus, there has been much progress on deletion-correcting codes in the last 6-7 years, covering regimes when the number of deletions t is a small constant, a small constant fraction of n, and a large proportion of n, as well as the list-decoding model. The talk will survey some of this progress.
|
|
|
|
9:20 am to 10:10 am |
Lattice-Based Signatures: Theory and Practice
Speaker: Jiang Zhang
show abstract ＋
Although lattices have been investigated since 1800, they were first used in cryptography, as a tool to attack some well-known cryptosystems (e.g., knapsack), only after the remarkable discovery of the LLL algorithm by Lenstra, Lenstra, and Lovasz in 1982. Fourteen years later, Ajtai made a breakthrough in constructing the first cryptosystem from lattices in 1996. To this day, lattices have found numerous applications in the construction of cryptosystems.
In this talk, we focus on lattice-based signatures. After a brief introduction, we will talk about the technologies and the current state of efficient lattice-based signatures in the random oracle model. Then, we introduce a general framework of designing lattice-based signatures in the standard model. Finally, we will give a short conclusion.
|
|
|
|
10:10 am to 10:30 am |
Break |
|
|
|
10:30 am to 11:20 am |
Bifurcated Cryptography: the Cases of Group Signature and Group Encryption
Speaker: Khoa Nguyen
show abstract ＋
In cryptography, one often encounters the situation where there are two desirable features for a cryptographic primitive, but these features cannot simultaneously live together. A commonly seen example is in the context of commitment schemes, where a scheme could be statistically hiding or statistically binding, but not both. A more involved example is in the contexts of multi-user privacy-preserving systems, where there is a tension between “absolute anonymity” and “anonymity with accountability”.
In this talk, I will discuss a new paradigm aiming to unify cryptographic systems with two competing properties, called “Bifurcated Cryptography”. I will illustrate how this paradigm can provide a reasonable balance between anonymity and accountability in multi-user privacy-preserving systems such as group signature and group encryption.
The talk will partially be based on this work (https://link.springer.com/chapter/10.1007/978-3-030-77883-5_18)
|
|
|
|
11:20 am to 2:00 pm |
Break |
|
|
|
Session Chair |
Khoa Nguyen |
|
|
|
2:00 pm to 2:50 pm |
The Generalized Covering Radii of Linear Codes
Speaker: Moshe Schwartz
show abstract ＋
Motivated by an application to database linear querying, such as private information-retrieval protocols, we suggest a fundamental property of linear codes - the generalized covering radius. The generalized covering-radius hierarchy of a linear code characterizes the trade-off between storage amount, latency, and access complexity, in such database systems. Several equivalent definitions are provided, showing this as a combinatorial, geometric, and algebraic notion. We derive bounds on the code parameters in relation with the generalized covering radii, study the effect of simple code operations, and describe a connection with generalized Hamming weights. As a case study, we can find bounds on the generalized covering radii of Reed-Muller codes in various asymptotic regimes.
|
|
|
|
2:50 pm to 3:40 pm |
Bounds and Constructions for Insertion and Deletion Codes
Speaker: Shu Liu
show abstract ＋
Insertion and deletion (insdel for short) errors are synchronization errors in communication systems caused by the loss of positional information in the message. Reed-Solomon codes have gained a lot of interest due to its encoding simplicity, well structuredness and list-decoding capability in the classical setting. This interest also translates to the insdel metric setting, as the Guruswami-Sudan decoding algorithm can be utilized to provide a deletion correcting algorithm in the insdel metric. Nevertheless, there have been few studies on the insdel error-correcting capability of Reed-Solomon codes. Our main contributions in this article are explicit constructions of two families of 2-dimensional Reed-Solomon codes with insdel errorcorrecting capabilities asymptotically reaching those provided by the Singleton bound. The first construction gives a family of ReedSolomon codes with insdel error-correcting capability asymptotic to its length. The second construction provides a family of ReedSolomon codes with an exact insdel error-correcting capability up to its length. Both our constructions improve the previously known construction of 2-dimensional Reed-Solomon codes whose insdel error-correcting capability is only logarithmic on the code length.
|
|
|
|
3:40 pm to 4:00 pm |
Break |
|
|
|
4:00 pm to 4:50 pm |
More Efficient Dishonest Majority Secure Computation over Z_2^k via Galois Rings
Speaker: Chen Yuan
show abstract ＋
We present a novel actively secure multiparty computation protocol in the dishonest majority setting, where the computation domain is a ring of type module 2^k. Instead of considering an ''extension ring'' of as in (Cramer et al, CRYPTO 2018) and its derivatives, we make use of an actual ring extension, or more precisely, a Galois ring extension of large enough degree, in order to ensure that the adversary cannot cheat except with negligible probability. These techniques have been used already in the context of honest majority MPC over ring of type module p^k, and to the best of our knowledge, our work constitutes the first study of the benefits of these tools in the dishonest majority setting. Reverse multiplication-friendly embeddings (RMFEs) have been used in the honest majority setting (e.g.~Cascudo et al, CRYPTO 2018), and more recently in the dishonest majority setting for computation over binary field (Cascudo and Gundersen, TCC 2020). We make use of the recent RMFEs over ring from (Cramer et al, CRYPTO 2021), together with adaptations of some RMFE optimizations introduced in (Abspoel et al, ASIACRYPT 2021) in the honest majority setting, to achieve an efficient protocol. We also instantiate the necessary offline phase using Oblivious Linear Evaluation (OLE) by generalizing the approach based on Oblivious Transfer (OT) proposed in MASCOT (Keller et al, CCS 2016). To this end, and as an additional contribution of potential independent interest, we present a novel technique using Multiplication-Friendly Embeddings (MFEs) to achieve OLE over Galois ring extensions using black-box access to an OLE protocol over the base ring without paying a quadratic cost in terms of the extension degree. This generalizes the approach in MASCOT based on Correlated OT Extension. This is a joint work with Escudero and Xing.
|
