IACR News
Updates on the COVID-19 situation are on the
Announcement channel.
Here you can see all recent updates to the IACR webpage. These updates are also available:
24 May 2022
Tadas Vaitiekūnas
Digital ledger technologies supporting smart contracts usually does not ensure any privacy for user transactions or state. Most solutions to this problem either use private network setups, centralized parties, hardware enclaves, or cryptographic primitives, which are novel, complex, and computationally expensive. This paper looks into an alternative way of implementing smart contracts. Our construction of a protocol for smart contracts employs an overlay protocol design pattern for decentralized applications, which separates transaction ordering from transaction validation. This enables consensus on application state while revealing only encrypted versions of transactions to public consensus protocol network. UTXO-based smart contract model allows partitioning state of distributed ledger in a way that participants would need to decrypt and reach consensus only on those transactions, which are relevant to them. We present security analysis, which shows that, assuming presence of a secure consensus protocol, our construction achieves consensus on UTXO-based transactions, while hiding most of transaction details from all protocol parties, except a limited subset of parties, which need particular transactions for construction of their state.
Giuseppe Persiano, Duong Hieu Phan, Moti Yung
Cryptosystems have been developed over the years under the typical prevalent setting which assumes that the receiver’s key is kept secure from the adversary, and that the choice of the message to be sent is freely performed by the sender and is kept secure from the adversary as well. Under these fundamental and basic operational assumptions, modern Cryptography has flourished over the last half a century or so, with amazing achievements: New systems (including public-key Cryptography), beautiful and useful models (including security definitions such as semantic security), and new primitives (such as zero-knowledge proofs) have been developed. Furthermore, these fundamental achievements have been translated into actual working systems, and span many of the daily human activities over the Internet.
However, in recent years, there is an overgrowing pressure from many governments to allow the government itself access to keys and messages of encryption systems (under various names: escrow encryption, emergency access, communication decency acts, etc.). Numerous non-direct arguments against such policies have been raised, such as "the bad guys can utilize other encryption system" so all other cryptosystems have to be declared illegal, or that "allowing the government access is an ill-advised policy since it creates a natural weak systems security point, which may attract others (to masquerade as the government)." It has remained a fundamental open issue, though, to show directly that the above mentioned efforts by a government (called here “a dictator” for brevity) which mandate breaking of the basic operational assumption (and disallowing other cryptosystems), is, in fact, a futile exercise. This is a direct technical point which needs to be made and has not been made to date.
In this work, as a technical demonstration of the futility of the dictator’s demands, we invent the notion of “Anamorphic Encryption” which shows that even if the dictator gets the keys and the messages used in the system (before anything is sent) and no other system is allowed, there is a covert way within the context of well established public-key cryptosystems for an entity to immediately (with no latency) send piggybacked secure messages which are, in spite of the stringent dictator conditions, hidden from the dictator itself! We feel that this may be an important direct technical argument against the nature of governments’ attempts to police the use of strong cryptographic systems, and we hope to stimulate further works in this direction.
However, in recent years, there is an overgrowing pressure from many governments to allow the government itself access to keys and messages of encryption systems (under various names: escrow encryption, emergency access, communication decency acts, etc.). Numerous non-direct arguments against such policies have been raised, such as "the bad guys can utilize other encryption system" so all other cryptosystems have to be declared illegal, or that "allowing the government access is an ill-advised policy since it creates a natural weak systems security point, which may attract others (to masquerade as the government)." It has remained a fundamental open issue, though, to show directly that the above mentioned efforts by a government (called here “a dictator” for brevity) which mandate breaking of the basic operational assumption (and disallowing other cryptosystems), is, in fact, a futile exercise. This is a direct technical point which needs to be made and has not been made to date.
In this work, as a technical demonstration of the futility of the dictator’s demands, we invent the notion of “Anamorphic Encryption” which shows that even if the dictator gets the keys and the messages used in the system (before anything is sent) and no other system is allowed, there is a covert way within the context of well established public-key cryptosystems for an entity to immediately (with no latency) send piggybacked secure messages which are, in spite of the stringent dictator conditions, hidden from the dictator itself! We feel that this may be an important direct technical argument against the nature of governments’ attempts to police the use of strong cryptographic systems, and we hope to stimulate further works in this direction.
Matteo Campanelli, Chaya Ganesh, Hamidreza Khoshakhlagh, Janno Siim
The celebrated result by Gentry and Wichs established a theoretical barrier for succinct non-interactive arguments (SNARGs), showing that for (expressive enough) hard-on-average languages we must assume non-falsifiable assumptions. We further investigate those barriers by showing new negative and positive results related to extractability and to the preprocessing model.
1. We first ask the question “are there further barriers to SNARGs that are knowledge-sound (SNARKs) and with a black-box extractor?”. We show it is impossible to have such SNARKs in the standard model. This separates SNARKs in the random oracle model (which can have black-box extraction) and those in the standard model.
2. We find positive results regarding the same question in the non-adaptive setting. Under the existence of SNARGs (without extractability) and from standard assumptions, it is possible to build SNARKs with black-box extractability for a non-trivial subset of NP.
3. On the other hand, we show that (under some mild assumptions) all NP languages cannot have SNARKs with black-box extractability even in the non-adaptive setting.
4. The Gentry-Wichs result does not account for the preprocessing model, under which fall several efficient constructions. We show that also in the preprocessing model it is impossible to construct SNARGs that rely on falsifiable assumptions in a black-box way.
Along the way, we identify a class of non-trivial languages, which we dub “trapdoor languages”, that bypass some of these impossibility results.
23 May 2022
Lisha Yao, Jian Weng, Bimei Wang
In attribute-based proxy re-encryption (AB-PRE) and attribute-based conditional proxy re-encryption (AB-CPRE) systems, the proxy transforms a ciphertext associated with policy $f$ to a ciphertext associated with policy $g$ or transforms a ciphertext for delegator satisfying a fine-grained condition to a ciphertext for delegatee. However, such PRE schemes have found many practical applications requiring fine-grained access control while keeping flexible delegation. Unfortunately, the existing PRE schemes are impossible to handle simultaneously with the above scenarios. In this work, we introduce the notion of conditional attribute-based proxy re-encryption (CAB-PRE), which enables a proxy only to transform a ciphertext associated with policy $f$ meeting the special delegation requirements by delegator to a ciphertext associated with policy $g$. We formalize its honestly re-encryption attacks (HRA) security model that implies CPA-secure, giving a concrete CAB-PRE scheme based on learning with errors (LWE) assumption. Finally, we show that CAB-PRE implies AB-PRE and AB-CPRE notions, and propose their constructions.
Vlad-Florin Dragoi, Brice Colombier, Pierre-Louis Cayrel, Vincent Grosso
Code-based cryptography received attention after
the NIST started the post-quantum cryptography standardization
process in 2016. A central NP-hard problem is the binary
syndrome decoding problem, on which the security of many
code-based cryptosystems lies. The best known methods to
solve this problem all stem from the information-set decoding
strategy, first introduced by Prange in 1962. A recent line of
work considers augmented versions of this strategy, with hints
typically provided by side-channel information. In this work,
we consider the integer syndrome decoding problem, where the
integer syndrome is available but might be noisy. We study
how the performance of the decoder is affected by the noise.
We provide experimental results on cryptographic parameters
for the BIKE and Classic McEliece cryptosystems, which are
finalist and alternate candidates for the third round of the NIST
standardization process, respectively.
Joppe W. Bos, Brian Carlson, Joost Renes, Marius Rotaru, Daan Sprenkels, Geoffrey P. Waters
The ability to trust a system to act safely and securely strongly relies on the integrity of the software that it runs. To guarantee
authenticity of the software one can include cryptographic data such as digital signatures on application images that can only be generated by trusted parties. These are typically based on cryptographic primitives such as Rivest-Shamir-Adleman (RSA) or Elliptic-Curve Cryptography (ECC), whose security will be lost whenever a large enough quantum computer is built. For that reason, migration towards Post-Quantum Cryptography (PQC) is necessary. This paper investigates the practical impact of migrating the secure boot flow on a Vehicle Network Processor (S32G274A) towards PQC. We create a low-memory fault-attack-
resistant implementation of the Dilithium signature verification algorithm and evaluate its impact on the boot flow.
Shweta Agrawal, Damien Stehle, Anshu Yadav
Threshold signature schemes enable distribution of the signature issuing capability to multiple users, to mitigate the threat of signing key compromise. Though a classic primitive, these signatures have witnessed a surge of interest in recent times due to relevance to modern applications like blockchains and cryptocurrencies. In this work, we study round-optimal threshold signatures in the post- quantum regime and improve the only known lattice-based construction by Boneh et al [CRYPTO’18] as follows:
• Efficiency. We reduce the amount of noise flooding used in the construction from $2^{\Omega(\lambda)}$ down to $\sqrt{Q}$, where $Q$ is the bound on the number of generated signatures and $\lambda$ is the security parameter. By using lattice hardness assumptions over polynomial rings, this allows to decrease the signature bit-lengths from $\widetilde{O}(\lambda^3)$ to~$\widetilde{O}(\lambda)$, bringing them significantly closer to practice. Our improvement relies on a careful analysis using Rényi divergence rather than statistical distance in the security proof.
• Instantiation. The construction of Boneh et al requires a standard signature scheme to be evaluated homomorphically. To instantiate this, we provide a homomorphism-friendly variant of Lyubashevsky’s signature [EUROCRYPT ’12] which achieves low circuit depth by being “rejection-free” and uses an optimal, moderate noise flooding of $\sqrt{Q}$, matching the above.
• Towards Adaptive Security. The construction of Boneh et al satisfies only selective security, where all the corrupted parties must be announced before any signing query is made. We improve this in two ways: in the Random Oracle Model, we obtain partial adaptivity where signing queries can be made before the corrupted parties are announced but the set of corrupted parties must be announced all at once. In the standard model, we obtain full adaptivity, where parties can be corrupted at any time but this construction is in a weaker pre-processing model where signers must be provided correlated randomness of length proportional to the number of signatures, in an offline preprocessing phase.
• Efficiency. We reduce the amount of noise flooding used in the construction from $2^{\Omega(\lambda)}$ down to $\sqrt{Q}$, where $Q$ is the bound on the number of generated signatures and $\lambda$ is the security parameter. By using lattice hardness assumptions over polynomial rings, this allows to decrease the signature bit-lengths from $\widetilde{O}(\lambda^3)$ to~$\widetilde{O}(\lambda)$, bringing them significantly closer to practice. Our improvement relies on a careful analysis using Rényi divergence rather than statistical distance in the security proof.
• Instantiation. The construction of Boneh et al requires a standard signature scheme to be evaluated homomorphically. To instantiate this, we provide a homomorphism-friendly variant of Lyubashevsky’s signature [EUROCRYPT ’12] which achieves low circuit depth by being “rejection-free” and uses an optimal, moderate noise flooding of $\sqrt{Q}$, matching the above.
• Towards Adaptive Security. The construction of Boneh et al satisfies only selective security, where all the corrupted parties must be announced before any signing query is made. We improve this in two ways: in the Random Oracle Model, we obtain partial adaptivity where signing queries can be made before the corrupted parties are announced but the set of corrupted parties must be announced all at once. In the standard model, we obtain full adaptivity, where parties can be corrupted at any time but this construction is in a weaker pre-processing model where signers must be provided correlated randomness of length proportional to the number of signatures, in an offline preprocessing phase.
Shiyu Shen, Hao Yang, Yu Liu, Zhe Liu, Yunlei Zhao
Homomorphic encryption (HE), which allows computation over encrypted data, has often been used to preserve privacy. However, the computationally heavy nature and complexity of network topologies make the deployment of HE schemes in the Internet of Things (IoT) scenario difficult. In this work, we propose CARM, the first optimized GPU implementation that covers BGV, BFV and CKKS, targeting for accelerating homomorphic multiplication using GPU in heterogeneous IoT systems. We offer constant-time low-level arithmetic with minimum instructions and memory usage, as well as performance- and memory-prior configurations, and exploit a parametric and generic design, and offer various trade-offs between resource and efficiency, yielding a solution suitable for accelerating RNS homomorphic multiplication on both high-performance and embedded GPUs. Through this, we can offer more real-time evaluation results and relieve the computational pressure on cloud devices. We deploy our implementations on two GPUs and achieve up to 378.4×, 234.5×, and 287.2× speedup for homomorphic multiplication of BGV, BFV, and CKKS on Tesla V100S, and 8.8×, 9.2×, and 10.3× on Jetson AGX Xavier, respectively.
Thomas Aulbach, Tobias Kovats, Juliane Krämer, Soundes Marzougui
Rainbow, a multivariate digital signature scheme and third round finalist in NIST's PQC standardization process, is a layered version of the unbalanced oil and vinegar (UOV) scheme.
We introduce two fault attacks, each focusing on one of the secret linear transformations $T$ and $S$ used to hide the structure of the central map in Rainbow. The first fault attack reveals a part of $T$ and we prove that this is enough to achieve a full key recovery with negligible computational effort for all parameter sets of Rainbow. The second one unveils $S$, which can be extended to a full key recovery by the Kipnis-Shamir attack.
Our work exposes the secret transformations used in multivariate signature schemes as an important attack vector for physical attacks, which need further protection.
Our attacks target the optimized Cortex-M4 implementation and require only first-order instruction skips and a moderate amount of faulted signatures.
Fuyuki Kitagawa, Ryo Nishimaki
We initiate the study of software watermarking against quantum adversaries.
A quantum adversary generates a quantum state as a pirate software that potentially removes an embedded message from a classical marked software.
Extracting an embedded message from quantum pirate software is difficult since measurement could irreversibly alter the quantum state.
In software watermarking against classical adversaries, a message extraction algorithm crucially uses the (input-output) behavior of a classical pirate software to extract an embedded message. Even if we instantiate existing watermarking PRFs with quantum-safe building blocks, it is not clear whether they are secure against quantum adversaries due to the quantum-specific property above.
Thus, we need entirely new techniques to achieve software watermarking against quantum adversaries.
In this work, we define secure watermarking PRFs for quantum adversaries (unremovability against quantum adversaries). We also present two watermarking PRFs as follows.
- We construct a privately extractable watermarking PRF against quantum adversaries from the quantum hardness of the learning with errors (LWE) problem. The marking and extraction algorithms use a public parameter and a private extraction key, respectively. The watermarking PRF is unremovable even if adversaries have (the public parameter and) access to the extraction oracle, which returns a result of extraction for a queried quantum circuit.
- We construct a publicly extractable watermarking PRF against quantum adversaries from indistinguishability obfuscation (IO) and the quantum hardness of the LWE problem. The marking and extraction algorithms use a public parameter and a public extraction key, respectively. The watermarking PRF is unremovable even if adversaries have the extraction key (and the public parameter).
We develop a quantum extraction technique to extract information (a classical string) from a quantum state without destroying the state too much. We also introduce the notion of extraction-less watermarking PRFs as a crucial building block to achieve the results above by combining the tool with our quantum extraction technique.
In this work, we define secure watermarking PRFs for quantum adversaries (unremovability against quantum adversaries). We also present two watermarking PRFs as follows.
- We construct a privately extractable watermarking PRF against quantum adversaries from the quantum hardness of the learning with errors (LWE) problem. The marking and extraction algorithms use a public parameter and a private extraction key, respectively. The watermarking PRF is unremovable even if adversaries have (the public parameter and) access to the extraction oracle, which returns a result of extraction for a queried quantum circuit.
- We construct a publicly extractable watermarking PRF against quantum adversaries from indistinguishability obfuscation (IO) and the quantum hardness of the LWE problem. The marking and extraction algorithms use a public parameter and a public extraction key, respectively. The watermarking PRF is unremovable even if adversaries have the extraction key (and the public parameter).
We develop a quantum extraction technique to extract information (a classical string) from a quantum state without destroying the state too much. We also introduce the notion of extraction-less watermarking PRFs as a crucial building block to achieve the results above by combining the tool with our quantum extraction technique.
Basavesh Ammanaghatta Shivakumar, Gilles Barthe, Benjamin Grégoire, Vincent Laporte, Swarn Priya
Cryptographic constant-time (CT) is a popular programming disci- pline used by cryptographic libraries to protect themselves against timing attacks. The CT discipline aims to enforce that program ex- ecution does not leak secrets, where leakage is defined by a formal leakage model. In practice, different leakage models coexist, some- times even within a single library, both to reflect different architec- tures and to accommodate different security-efficiency trade-offs. Constant-timeness is popular and can be checked automatically by many tools. However, most sound tools are focused on a baseline (BL) leakage model. In contrast, (sound) verification methods for other leakage models are less developed, in part because these mod- els require modular arithmetic reasoning. In this paper, we develop a systematic, sound, approach for enforcing fine-grained constant- time policies beyond the BL model. Our approach combines two main ingredients: a verification infrastructure, which proves that source programs are constant-time, and a compiler infrastructure, which provably preserves constant-timeness for these fine-grained policies. By making these infrastructures parametric in the leakage model, we achieve the first approach that supports fine-grained constant-time policies. We implement the approach in the Jasmin framework for high-assurance cryptography, and we evaluate our approach with examples from the literature: OpenSSL and wolfSSL. We found a bug in OpenSSL and provided a formally verified fix.
Alexandros Bakas, Antonis Michalas, Eugene Frimpong, Reyhaneh Rabbaninejad
Functional Encryption (FE) allows users who hold a specific decryption key, to learn a specific function of encrypted data while the actual plaintexts remain private. While FE is still in its infancy, it is our strong belief that in the years to come, this remarkable cryptographic primitive will have matured to the degree that will make it an integral part of access control systems, especially cloud-based ones. To this end, we believe it is of great importance to provide not only theoretical and generic constructions but also concrete instantiations of FE schemes from well-studied cryptographic assumptions. Therefore, in this paper, we undertake the task of presenting two instantiations of the generic work presented in [8] from the Decisional Die-Hellman (DDH) problem that also satisfies the property of verifiable decryption. Moreover, we present a novel multi-input FE (MIFE) scheme, that can be instantiated from Regev's cryptosystem, and thus remains secure even against quantum adversaries. Finally, we provide a multi-party computation (MPC) protocol that allows our MIFE construction to be deployed in the multi-client mode
Elizabeth Carter, Pengzhou He, Jiafeng Xie
Along the rapid development in building large-scale quantum computers, post-quantum cryptography (PQC) has drawn significant attention from research community recently as it is proven that the existing public-key cryptosystems are vulnerable to the quantum attacks. Following this direction, this paper presents a novel implementation of high-performance polynomial multiplication hardware accelerators for key encapsulation mechanism (KEM) Saber and NTRU, two PQC algorithms that are currently under the consideration by the National Institute of Standards and Technology (NIST) PQC standardization process. In total, we have carried out three layers of efforts to obtain the proposed work. First of all, we have proposed a new Dual Cyclic-Row Oriented Processing (Dual-CROP) technique to build a high-performance polynomial multiplication hardware accelerator for KEM Saber. Then, we have extended this hardware accelerator to NTRU with proper innovation and adjustment. Finally, through a series of complexity analysis and implementation based comparison, we have shown that the proposed hardware accelerators obtain better area-time complexities than known existing ones. It is expected that the outcome of this work can impact the ongoing NIST PQC standardization process and can be deployed further to construct efficient cryptoprocessors.
Xin Yin, Zhen Liu, Guomin Yang, Guoxing Chen, Haojin Zhu
Over the past decade, cryptocurrency has been undergoing a rapid development. Digital wallet, as the tool to store and manage the cryptographic keys, is the primary entrance for the public to access cryptocurrency assets.
Hierarchical Deterministic Wallet (HDW), proposed in Bitcoin Improvement Proposal 32 (BIP32), has attracted much attention and been widely used in the community, due to its virtues such as easy backup/recovery, convenient cold-address management, and supporting trust-less audits and applications in hierarchical organizations.
While HDW allows the wallet owner to generate and manage his keys conveniently, Stealth Address (SA) allows a payer to generate fresh address (i.e., public key) for the receiver without any interaction, so that users can achieve ``one coin each address" in a very convenient manner, which is widely regarded as a simple but effective way to protect user privacy. Consequently, SA has also attracted much attention and been widely used in the community.
However, as so far, there is not a secure wallet algorithm that provides the virtues of both HDW and SA. Actually, even for standalone HDW, to the best of our knowledge, there is no strict definition of syntax and models that captures the functionality and security (i.e., safety of coins and privacy of users) requirements that practical scenarios in cryptocurrency impose on wallet. As a result, the existing wallet algorithms either have (potential) security flaws or lack crucial functionality features.
In this work, we formally define the syntax and security models of Hierarchical Deterministic Wallet supporting Stealth Address (HDWSA), capturing the functionality and security (including safety and privacy) requirements imposed by the practice in cryptocurrency, which include all the versatile functionalities that lead to the popularity of HDW and SA as well as all the security guarantees that underlie these functionalities. We propose a concrete HDWSA construction and prove its security in the random oracle model. We implement our scheme and the experimental results show that the efficiency is suitable for typical cryptocurrency settings.
In this work, we formally define the syntax and security models of Hierarchical Deterministic Wallet supporting Stealth Address (HDWSA), capturing the functionality and security (including safety and privacy) requirements imposed by the practice in cryptocurrency, which include all the versatile functionalities that lead to the popularity of HDW and SA as well as all the security guarantees that underlie these functionalities. We propose a concrete HDWSA construction and prove its security in the random oracle model. We implement our scheme and the experimental results show that the efficiency is suitable for typical cryptocurrency settings.
Senpeng Wang, Dengguo Feng , Bin Hu , Jie Guan , Tairong Shi , Kai Zhang
As the first generic method for finding the optimal differential and linear characteristics, Matsui's branch and bound search algorithm has played an important role
in evaluating the security of symmetric ciphers. By combining the Matsui's bounding conditions with automatic search models, the search efficiency can be improved. All the previous methods realize the bounding conditions by adding a set of constraints. This may increase the searching complexity of models. In this paper, by
using Information Theory to quantify the effect of bounding conditions, we give the general form of bounding conditions that can use all the information
provided by Matsui's bounding conditions. Then, a new method of combining bounding conditions with sequential encoding method is proposed. Different from all the previous methods,
our new method can realize the bounding conditions by removing the variables and clauses from Satisfiability Problem (SAT) models based on the original sequential encoding method. With the help of some small size Mixed
Integer Linear Programming (MILP) models, we build the simplest SAT model of combining Matsui's bounding conditions with sequential encoding method. Then, we apply our new method
to search the optimal differential and linear characteristics of some SPN, Feistel, and ARX block ciphers. The number of variables, clauses and the solving time of the SAT models
are decreased significantly. And we find some new differential and linear characteristics covering more rounds. For example, the optimal differential probability of the full rounds GIFT128 is obtained for the first time.
Sisi Duan, Haibin Zhang, Xiao Sui, Baohan Huang, Changchun Mu, Gang Di, Xiaoyun Wang
State-of-the-art Byzantine fault-tolerant (BFT) protocols assuming partial synchrony such as SBFT and HotStuff use regular certificates obtained from $2f+1$ (partial) signatures. We show in this paper that one can use weak certificates obtained from only $f+1$ signatures to design more robust and much more efficient BFT protocols. We devise Dashing (a family of three HotStuff-style BFT protocols) and Star (a parallel BFT framework).
We begin with Dashing1 that targets both efficiency and robustness using weak certificates. Dashing1 is partition-tolerant and network-adaptive, and does not rely on fallback asynchronous BFT protocols. Dashing2 is a variant of Dashing1 and focuses on performance only. Then we show in Dashing3 how to further enable a fast path by using strong certificates obtained from $3f+1$ signatures, a challenging task we tackled in the paper.
We then leverage weak certificates to build a highly efficient BFT framework (Star) that delivers transactions from $n-f$ replicas using only a single consensus instance in the standard BFT model. Star completely separates bulk data transmission from consensus. Moreover, its data transmission process uses $O(n^2)$ messages only and can be effectively pipelined.
We demonstrate that the Dashing protocols achieve 10.7%-29.9% higher peak throughput than HotStuff. Meanwhile, Star, when being instantiated using PBFT, is an order of magnitude faster than HotStuff. Furthermore, unlike the Dashing protocols and HotStuff whose performance degrades as $f$ grows, the peak throughput of Star increases as $f$ grows. When deployed in a WAN with 91 replicas across five continents, Star achieves 243 ktx/sec, 15.8x the throughput of HotStuff.
We begin with Dashing1 that targets both efficiency and robustness using weak certificates. Dashing1 is partition-tolerant and network-adaptive, and does not rely on fallback asynchronous BFT protocols. Dashing2 is a variant of Dashing1 and focuses on performance only. Then we show in Dashing3 how to further enable a fast path by using strong certificates obtained from $3f+1$ signatures, a challenging task we tackled in the paper.
We then leverage weak certificates to build a highly efficient BFT framework (Star) that delivers transactions from $n-f$ replicas using only a single consensus instance in the standard BFT model. Star completely separates bulk data transmission from consensus. Moreover, its data transmission process uses $O(n^2)$ messages only and can be effectively pipelined.
We demonstrate that the Dashing protocols achieve 10.7%-29.9% higher peak throughput than HotStuff. Meanwhile, Star, when being instantiated using PBFT, is an order of magnitude faster than HotStuff. Furthermore, unlike the Dashing protocols and HotStuff whose performance degrades as $f$ grows, the peak throughput of Star increases as $f$ grows. When deployed in a WAN with 91 replicas across five continents, Star achieves 243 ktx/sec, 15.8x the throughput of HotStuff.
Andriyan Bilyk, Javad Doliskani, Zhiyong Gong
We investigate the security assumptions behind three public-key quantum money schemes. Aaronson and Christiano proposed a scheme based on hidden subspaces of the vector space $\mathbb{F}_2^n$ in 2012. It was conjectured by Pena et al in 2015 that the hard problem underlying the scheme can be solved in quasi-polynomial time. We confirm this conjecture by giving a polynomial time quantum algorithm for the underlying problem. Our algorithm is based on computing the Zariski tangent space of a random point in the hidden subspace.
Zhandry proposed a scheme based on multivariate hash functions in 2017. We give a polynomial time quantum algorithm for cloning a money state with high probability. Our algorithm uses the verification circuit of the scheme to produce a banknote from a given serial number.
Kane proposed a scheme based on modular forms in 2018. The underlying hard problem in Kane's scheme is cloning a quantum state that represents an eigenvector of a set of Hecke operators. We give a polynomial time quantum reduction from this hard problem to a linear algebra problem. The latter problem is much easier to understand, and we hope that our reduction opens new avenues to future cryptanalyses of this scheme.
Anders Dalskov, Daniel Escudero, Ariel Nof
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
Furthermore, the amortized communication complexity of our protocol is not only constant, but very small: only $1 + \frac{t-1}{n}<1\frac{1}{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 $2\frac{2}{3}$ \emph{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 $\le 1\frac{1}{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$).
Furthermore, the amortized communication complexity of our protocol is not only constant, but very small: only $1 + \frac{t-1}{n}<1\frac{1}{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 $2\frac{2}{3}$ \emph{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 $\le 1\frac{1}{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$).
Olive Chakraborty, Martin Zuber
We design and implement a new efficient and accurate Fully homomorphic argmin/min or argmax/max comparison operator, which finds its application in numerous real-world use cases as a classifier. In particular we propose two versions of our algorithms using different tools from TFHE's functional bootstrapping toolkit. Our algorithm scales to any number of input data points with linear time complexity and logarithmic noise-propagation. Our algorithm is the fastest on the market for non-parallel comparisons with a high degree of accuracy and precision. For MNIST and SVHN datasets, which work under the PATE framework, using our algorithm, we achieve an accuracy of around 99.95 % for both.
Arantxa Zapico, Vitalik Buterin, Dmitry Khovratovich, Mary Maller, Anca Nitulescu, Mark Simkin
We present position-hiding linkability for vector commitment schemes: one can prove in zero knowledge that one or $m$ values that comprise commitment cm all belong to the vector of size $N$ committed to in C. Our construction Caulk can be used for membership proofs and lookup arguments and outperforms all existing alternatives in prover time by orders of magnitude.
For both single- and multi-membership proofs Caulk beats SNARKed Merkle proofs by the factor of 100 even if the latter instantiated with Poseidon hash. Asymptotically our prover needs $O(m^2 + m\log N)$ time to prove a batch of $m$ openings, whereas proof size is $O(1)$ and verifier time is $O(\log(\log N))$.
As a lookup argument, Caulk is the first scheme with prover time sublinear in the table size, assuming $O(N\log N)$ preprocessing time and $O(N)$ storage. It can be used as a subprimitive in verifiable computation schemes in order to drastically decrease the lookup overhead.
Our scheme comes with a reference implementation and benchmarks.