IACR News
Here you can see all recent updates to the IACR webpage. These updates are also available:
28 December 2022
Liyi Zhou, Xihan Xiong, Jens Ernstberger, Stefanos Chaliasos, Zhipeng Wang, Ye Wang, Kaihua Qin, Roger Wattenhofer, Dawn Song, Arthur Gervais
ePrint Report
Within just four years, the blockchain-based Decentralized Finance (DeFi) ecosystem has accumulated a peak total value locked (TVL) of more than 253 billion USD. This surge in DeFi’s popularity has, unfortunately, been accompanied by many impactful incidents. According to our data, users, liquidity providers, speculators, and protocol operators suffered a total loss of at least 3.24 billion USD from Apr 30, 2018 to Apr 30, 2022. Given the blockchain’s transparency and increasing incident frequency, two questions arise: How can we systematically measure, evaluate, and compare DeFi incidents? How can we learn from past attacks to strengthen DeFi security?
In this paper, we introduce a common reference frame to systematically evaluate and compare DeFi incidents, including both attacks and accidents. We investigate 77 academic papers, 30 audit reports, and 181 real-world incidents. Our open data reveals several gaps between academia and the practitioners’ community. For example, few academic papers address “price oracle attacks” and “permissonless interactions”, while our data suggests that they are the two most frequent incident types (15% and 10.5% correspondingly). We also investigate potential defenses, and find that: (i) 103 (56%) of the attacks are not executed atomically, granting a rescue time frame for defenders; (ii) SoTA bytecode similarity analysis can at least detect 31 vulnerable/23 adversarial contracts; and (iii) 33 (15.3%) of the adversaries leak potentially identifiable information by interacting with centralized exchanges.
In this paper, we introduce a common reference frame to systematically evaluate and compare DeFi incidents, including both attacks and accidents. We investigate 77 academic papers, 30 audit reports, and 181 real-world incidents. Our open data reveals several gaps between academia and the practitioners’ community. For example, few academic papers address “price oracle attacks” and “permissonless interactions”, while our data suggests that they are the two most frequent incident types (15% and 10.5% correspondingly). We also investigate potential defenses, and find that: (i) 103 (56%) of the attacks are not executed atomically, granting a rescue time frame for defenders; (ii) SoTA bytecode similarity analysis can at least detect 31 vulnerable/23 adversarial contracts; and (iii) 33 (15.3%) of the adversaries leak potentially identifiable information by interacting with centralized exchanges.
Min Zhang, Binbin Tu, Yu Chen
ePrint Report
Recently, Chen et al. (ASIACRYPT 2021) introduced a notion called hierarchical integrated signature and encryption (HISE), which provides a new principle for combining public key schemes. It uses a single public key for both signature and encryption schemes, and one can derive a decryption key from the signing key but not vice versa. Whereas, they left the dual notion where the signing key can be derived from the decryption key as an open problem.
In this paper, we resolve the problem by formalizing the notion called hierarchical integrated encryption and signature (HIES). Similar to HISE, it features a unique public key for both encryption and signature components and has a two-level key derivation mechanism, but reverses the hierarchy between signing key and decryption key, i.e. one can derive a signing key from the decryption key but not vice versa. This property enables secure delegation of signing capacity in the public key reuse setting. We present a generic construction of HIES from constrained identity-based encryption. Furthermore, we instantiate our generic HIES construction and implement it. The experimental result demonstrates that our HIES scheme is comparable to the best Cartesian product combined public-key scheme in terms of efficiency, and is superior in having richer functionality as well as retaining merits of key reuse.
In this paper, we resolve the problem by formalizing the notion called hierarchical integrated encryption and signature (HIES). Similar to HISE, it features a unique public key for both encryption and signature components and has a two-level key derivation mechanism, but reverses the hierarchy between signing key and decryption key, i.e. one can derive a signing key from the decryption key but not vice versa. This property enables secure delegation of signing capacity in the public key reuse setting. We present a generic construction of HIES from constrained identity-based encryption. Furthermore, we instantiate our generic HIES construction and implement it. The experimental result demonstrates that our HIES scheme is comparable to the best Cartesian product combined public-key scheme in terms of efficiency, and is superior in having richer functionality as well as retaining merits of key reuse.
Asuka Wakasugi, Mitsuru Tada
ePrint Report
Since 2016, NIST has been standardrizing Post-Quantum Cryptosystems, PQCs. Code-Based Cryptosystem, CBC, which is considered to be one of PQCs, uses the Syndrome Decoding Problem as the basis for its security. NIST's PQC standardization project is currently in its 4th round and some CBC encryption schemes remain there. In this paper, we consider the quantum security for these cryptosystems.
27 December 2022
Navid Alamati, Sikhar Patranabis
ePrint Report
A hinting pseudorandom generator (PRG) is a potentially stronger variant of PRG with a ``deterministic'' form of circular security with respect to the seed of the PRG (Koppula and Waters, CRYPTO 2019). Hinting PRGs enable many cryptographic applications, most notably CCA-secure public-key encryption and trapdoor functions. In this paper, we study cryptographic primitives with the hinting property, yielding the following results:
We present a novel and conceptually simpler approach for designing hinting PRGs from certain decisional assumptions over cyclic groups or isogeny-based group actions, which enables simpler security proofs as compared to the existing approaches for designing such primitives.
We introduce hinting weak pseudorandom functions (wPRFs), a natural extension of the hinting property to wPRFs, and show how to realize circular/KDM-secure symmetric-key encryption from any hinting wPRF. We demonstrate that our simple approach for building hinting PRGs can be extended to realize hinting wPRFs from the same set of decisional assumptions.
We propose a stronger version of the hinting property, which we call the functional hinting property, that guarantees security even in the presence of hints about functions of the secret seed/key. We show how to instantiate functional hinting PRGs/wPRFs for certain (families of) functions by building upon our simple techniques for realizing plain hinting PRGs/wPRFs. We also demonstrate the applicability of a functional hinting wPRF with certain algebraic properties in realizing KDM-secure public-key encryption in a black-box manner.
We show the first black-box separation between hinting wPRFs (and hinting PRGs) from public-key encryption using simple realizations of these primitives given only a random oracle.
We present a novel and conceptually simpler approach for designing hinting PRGs from certain decisional assumptions over cyclic groups or isogeny-based group actions, which enables simpler security proofs as compared to the existing approaches for designing such primitives.
We introduce hinting weak pseudorandom functions (wPRFs), a natural extension of the hinting property to wPRFs, and show how to realize circular/KDM-secure symmetric-key encryption from any hinting wPRF. We demonstrate that our simple approach for building hinting PRGs can be extended to realize hinting wPRFs from the same set of decisional assumptions.
We propose a stronger version of the hinting property, which we call the functional hinting property, that guarantees security even in the presence of hints about functions of the secret seed/key. We show how to instantiate functional hinting PRGs/wPRFs for certain (families of) functions by building upon our simple techniques for realizing plain hinting PRGs/wPRFs. We also demonstrate the applicability of a functional hinting wPRF with certain algebraic properties in realizing KDM-secure public-key encryption in a black-box manner.
We show the first black-box separation between hinting wPRFs (and hinting PRGs) from public-key encryption using simple realizations of these primitives given only a random oracle.
Reyhaneh Rabaninejad, Bin Liu, Antonis Michalas
ePrint Report
Secure cryptographic storage is one of the most important issues
that both businesses and end-users take into account before moving
their data to either centralized clouds or blockchain-based decen-
tralized storage marketplace. Recent work [4 ] formalizes the notion
of Proof of Storage-Time (PoSt) which enables storage servers to
demonstrate non-interactive continuous availability of outsourced
data in a publicly verifiable way. The work also proposes a stateful
compact PoSt construction, while leaving the stateless and transpar-
ent PoSt with support for proof of replication as an open problem.
In this paper, we consider this problem by constructing a proof
system that enables a server to simultaneously demonstrate con-
tinuous availability and dedication of unique storage resources for
encoded replicas of a data file in a stateless and publicly verifi-
able way. We first formalize Proof of Replication-Time (PoRt) by
extending PoSt formal definition and security model to provide
support for replications. Then, we provide a concrete instantia-
tion of PoRt by designing a lightweight replica encoding algorithm
where replicas’ failures are efficiently located through an efficient
comparison-based verification process, after the data deposit period
ends. PoRt’s proofs are aggregatable: the prover can take several
sequentially generated proofs and efficiently aggregate them into
a single, succinct proof. The protocol is also stateless in the sense
that the client can efficiently extend the deposit period by incre-
mentally updating the tags and without requiring to download the
outsourced file replicas. We also demonstrate feasible extensions
of PoRt to support dynamic data updates, and be transparent to
enable its direct use in decentralized storage networks, a property
not supported in previous proposals. Finally, PoRt’s verification
cost is independent of both outsourced file size and deposit length.
Kaisei Kajita, Keita Emura, Kazuto Ogawa, Ryo Nojima, Go Ohtake
ePrint Report
Secure messaging (SM) protocols allow users to communicate securely over an untrusted infrastructure. The IETF currently works on the standardization of secure group messaging (SGM), which is SM done by a group of two or more people. Alwen et al. formally defined the key agreement protocol used in SGM as continuous group key agreement (CGKA) at CRYPTO 2020. In their CGKA protocol, all of the group members have the same rights and a trusted third party is needed. On the contrary, some SGM applications may have a user in the group who has the role of an administrator. When the administrator as the group manager (GM) is distinguished from other group members, i.e., in a one-to-many setting, it would be better for the GM and the other group members to have different authorities. We achieve this flexible autho-rization by incorporating a ratcheting digital signature scheme (Cremers et al. at USENIX Security 2021) into the existing CGKA protocol and demonstrate that such a simple modification allows us to provide flexible authorization. This one-to-many setting may be reminiscent of a multi-cast key agreement protocol proposed by Bienstock et al. at CT-RSA 2022, where GM has the role of adding and removing group members. Although the role of the GM is fixed in advance in the Bienstock et al. protocol, the GM can flexibly set the role depending on the application in our protocol. On the other hand, in Alwen et al.’s CGKA protocol, an external public key infrastructure (PKI) functionality as a trusted third party manages the confidential information of users, and the PKI can read all messages until all users update their own keys. In contrast, the GM in our protocol has the same role as the PKI functionality in the group, so no third party outside the group handles confidential informa-tion of users and thus no one except group members can read messages regardless of key updates. Our proposed protocol is useful in the creation of new applications such as broadcasting services.
Orestis Alpos, Christian Cachin
ePrint Report
In distributed cryptography independent parties jointly perform some cryptographic task. In the last decade distributed cryptography has been receiving more attention than ever. Distributed systems power almost all applications, blockchains are becoming prominent, and, consequently, numerous practical and efficient distributed cryptographic primitives are being deployed.
The failure models of current distributed cryptographic systems, however, lack expressibility. Assumptions are only stated through numbers of parties, thus reducing this to threshold cryptography, where all parties are treated as identical and correlations cannot be described. Distributed cryptography does not have to be threshold-based. With general distributed cryptography the authorized sets, the sets of parties that are sufficient to perform some task, can be arbitrary, and are usually modeled by the abstract notion of a general access structure.
Although the necessity for general cryptography has been recognized long ago and many schemes have been explored in theory, relevant practical aspects remain opaque. It is unclear how the user specifies a trust structure efficiently or how this is encoded within a scheme, for example. More importantly, implementations and benchmarks do not exist, hence the efficiency of the schemes is not known.
Our work fills this gap. We show how an administrator can intuitively describe the access structure as a Boolean formula. This is then converted into encodings suitable for cryptographic primitives, specifically, into a tree data structure and a monotone span program. We focus on three general distributed cryptographic schemes: verifiable secret sharing, common coin, and distributed signatures. For each one we give the appropriate formalization and security definition in the general-trust setting. We implement the schemes and assess their efficiency against their threshold counterparts. Our results suggest that the general distributed schemes offer richer expressibility at no or insignificant extra cost. Thus, they are appropriate and ready for practical deployment.
Durba Chatterjee, Kuheli Pratihar, Aritra Hazra, Ulrich Rührmair, Debdeep Mukhopadhyay
ePrint Report
Physically Unclonable Functions~(PUFs) with large challenge space~(also called Strong PUFs) are promoted for usage in authentications and various other cryptographic and security applications. In order to qualify for these cryptographic applications, the Boolean functions realized by PUFs need to possess a high non-linearity~(NL). However, with a large challenge space~(usually $\geq 64$ bits), measuring NL by classical techniques like Walsh transformation is computationally infeasible. In this paper, we propose the usage of a heuristic-based measure called non-homomorphicity test which estimates the NL of Boolean functions with high accuracy in spite of not needing access to the entire challenge-response set. We also combine our analysis with a technique used in linear cryptanalysis, called Piling-up lemma, to measure the NL of popular PUF compositions. As a demonstration to justify the soundness of the metric, we perform extensive experimentation by first estimating the NL of constituent Arbiter/Bistable Ring PUFs using the non-homomorphicity test, and then applying them to quantify the same for their XOR compositions namely XOR Arbiter PUFs and XOR Bistable Ring PUF. Our findings show that the metric explains the impact of various parameter choices of these PUF compositions on the NL obtained and thus promises to be used as an important objective criterion for future efforts to evaluate PUF designs. While the framework is not representative of the machine learning robustness of PUFs, it can be a useful complementary tool to analyze the cryptanalytic strengths of PUF primitives.
Jiashuo Liu, Jiongjiong Ren, Shaozhen Chen
ePrint Report
In CRYPTO 2019, Gohr opens up a new direction for cryptanalysis. He successfully applied deep learning to differential cryptanalysis against the NSA block cipher SPECK32/64, achieving higher accuracy than traditional differential distinguishers. Until now, one of the mainstream research directions is increasing the training sample size and utilizing different neural networks to improve the accuracy of neural distinguishers. This conversion mindset may lead to a huge number of parameters, heavy computing load, and a large number of memory in the distinguishers training process. However, in the practical application of cryptanalysis, the applicability of the attacks method in a resource-constrained environment is very important. Therefore, we focus on the cost optimization and aim to reduce network parameters for differential neural cryptanalysis.
In this paper, we propose two cost-optimized neural distinguisher improvement methods from the aspect of data format and network structure, respectively. Firstly, we obtain a partial output difference neural distinguisher using only 4-bits training data format which is constructed with a new advantage bits search algorithm based on two key improvement conditions. In addition, we perform an interpretability analysis of the new neural distinguishers whose results are mainly reflected in the relationship between the neural distinguishers, truncated differential, and advantage bits. Secondly, we replace the traditional convolution with the depthwise separable convolution to reduce the training cost without affecting the accuracy as much as possible. Overall, the number of training parameters can be reduced by less than 50\% by using our new network structure for training neural distinguishers. Finally, we apply the network structure to the partial output difference neural distinguishers. The combinatorial approach have led to a further reduction in the number of parameters (approximately 30\% of Gohr's distinguishers for SPECK).
In this paper, we propose two cost-optimized neural distinguisher improvement methods from the aspect of data format and network structure, respectively. Firstly, we obtain a partial output difference neural distinguisher using only 4-bits training data format which is constructed with a new advantage bits search algorithm based on two key improvement conditions. In addition, we perform an interpretability analysis of the new neural distinguishers whose results are mainly reflected in the relationship between the neural distinguishers, truncated differential, and advantage bits. Secondly, we replace the traditional convolution with the depthwise separable convolution to reduce the training cost without affecting the accuracy as much as possible. Overall, the number of training parameters can be reduced by less than 50\% by using our new network structure for training neural distinguishers. Finally, we apply the network structure to the partial output difference neural distinguishers. The combinatorial approach have led to a further reduction in the number of parameters (approximately 30\% of Gohr's distinguishers for SPECK).
Karim Lounis
ePrint Report
Wi-Fi is a wireless communication technology that
has been around since the late nineties. Nowadays, it is the
most adopted wireless short-range communication technology in
various IoT (Internet of Things) applications and on many wireless
AI (Artificial Intelligent) systems. Although Wi-Fi security
has significantly improved throughout the past years, it is still
having some limitations. Some vulnerabilities still exist allowing
attackers to generate different types of attacks. These attacks
can breach the authentication, confidentiality, and data integrity
of Wi-Fi systems. At the same time, many vulnerabilities have
been fixed or patched, and the attacks that were relying on those
vulnerabilities would fail on modern Wi-Fi systems. Therefore, it
is important for security engineers, in general, and for wireless
intelligent system designers, in particular, to be aware of the
existing vulnerabilities and feasible attacks on modern Wi-Fi
systems and their respective countermeasures. That would help
them to not have to look back and care about attacks that can
no longer be generated on today’s Wi-Fi systems. In this light,
we devote this paper to extensively review the attacks on Wi-Fi.
We group the attacks into feasible and unfeasible. Also, for each
attack, we discuss the possible countermeasures to mitigate it.
Liam Eagen, Dario Fiore, Ariel Gabizon
ePrint Report
We present a protocol called $\mathsf{cq}$ for checking the values of a committed polynomial $f(X)\in \mathbb{F}_{
On the impossibility of surviving (iterated) deletion of weakly dominated strategies in rational MPC
Johannes Blömer, Jan Bobolz, Henrik Bröcher
ePrint Report
Rational multiparty computation (rational MPC) provides a framework for analyzing MPC protocols through the lens of game theory. One way to judge whether an MPC protocol is rational is through weak domination: Rational players would not adhere to an MPC protocol if deviating never decreases their utility, but sometimes increases it.
Secret reconstruction protocols are of particular importance in this setting because they represent the last phase of most (rational) MPC protocols. We show that most secret reconstruction protocols from the literature are not, in fact, rationally sound with respect to weak domination. Furthermore, we formally prove that (under certain assumptions) it is impossible to design a rationally sound secret reconstruction protocol if (1) shares are authenticated or (2) half of all players may form a coalition.
Umesh Kumar, V. Ch. Venkaiah
ePrint Report
A family of block ciphers parametrized by an optimal quasigroup is proposed in this paper. The proposed cipher uses sixteen $4\times 4$ bits S-boxes as an optimal quasigroup of order 16. Since a maximum of $16!$ optimal quasigroups of order 16 can be formed, the family consists of $C^{16!}_1$ cryptosystems. All the sixteen S-boxes have the highest algebraic degree and are optimal with the lowest linearity and differential characteristics. Therefore, these S-boxes are secure against linear and differential attacks. The proposed cipher is analyzed against various attacks, including linear and differential attacks, and we found it to be resistant to these attacks. The proposed cipher is implemented in C++, compared its performance with existing quasigroup based block
ciphers, and we found that our proposal is more efficient than existing quasigroup based proposals. We also evaluated our cipher using
various statistical tests of the NIST-STS test suite, and we found
it to pass these tests. We also established in this study that the
randomness of our cipher is almost the same as that of the AES-128.
Rachit Garg, Kristin Sheridan, Brent Waters, David J. Wu
ePrint Report
Non-interactive batch arguments for $\mathsf{NP}$ provide a way to amortize the cost of $\mathsf{NP}$ verification across multiple instances. In particular, they allow a prover to convince a verifier of multiple $\mathsf{NP}$ statements with communication that scales sublinearly in the number of instances.
In this work, we study fully succinct batch arguments for $\mathsf{NP}$ in the common reference string (CRS) model where the length of the proof scales not only sublinearly in the number of instances $T$, but also sublinearly with the size of the $\mathsf{NP}$ relation. Batch arguments with these properties are special cases of succinct non-interactive arguments (SNARGs); however, existing constructions of SNARGs either rely on idealized models or strong non-falsifiable assumptions. The one exception is the Sahai-Waters SNARG based on indistinguishability obfuscation. However, when applied to the setting of batch arguments, we must impose an a priori bound on the number of instances. Moreover, the size of the common reference string scales linearly with the number of instances.
In this work, we give a direct construction of a fully succinct batch argument for $\mathsf{NP}$ that supports an unbounded number of statements from indistinguishability obfuscation and one-way functions. Then, by additionally relying on a somewhere statistically binding (SSB) hash function, we show how to extend our construction to obtain a fully succinct and updatable batch argument. In the updatable setting, a prover can take a proof $\pi$ on $T$ statements $(x_1, \ldots, x_T)$ and "update" it to obtain a proof $\pi'$ on $(x_1, \ldots, x_T, x_{T + 1})$. Notably, the update procedure only requires knowledge of a (short) proof for $(x_1, \ldots, x_T)$ along with a single witness $w_{T + 1}$ for the new instance $x_{T + 1}$. Importantly, the update does not require knowledge of witnesses for $x_1, \ldots, x_T$.
In this work, we study fully succinct batch arguments for $\mathsf{NP}$ in the common reference string (CRS) model where the length of the proof scales not only sublinearly in the number of instances $T$, but also sublinearly with the size of the $\mathsf{NP}$ relation. Batch arguments with these properties are special cases of succinct non-interactive arguments (SNARGs); however, existing constructions of SNARGs either rely on idealized models or strong non-falsifiable assumptions. The one exception is the Sahai-Waters SNARG based on indistinguishability obfuscation. However, when applied to the setting of batch arguments, we must impose an a priori bound on the number of instances. Moreover, the size of the common reference string scales linearly with the number of instances.
In this work, we give a direct construction of a fully succinct batch argument for $\mathsf{NP}$ that supports an unbounded number of statements from indistinguishability obfuscation and one-way functions. Then, by additionally relying on a somewhere statistically binding (SSB) hash function, we show how to extend our construction to obtain a fully succinct and updatable batch argument. In the updatable setting, a prover can take a proof $\pi$ on $T$ statements $(x_1, \ldots, x_T)$ and "update" it to obtain a proof $\pi'$ on $(x_1, \ldots, x_T, x_{T + 1})$. Notably, the update procedure only requires knowledge of a (short) proof for $(x_1, \ldots, x_T)$ along with a single witness $w_{T + 1}$ for the new instance $x_{T + 1}$. Importantly, the update does not require knowledge of witnesses for $x_1, \ldots, x_T$.
Ittai Abraham, Philipp Jovanovic, Mary Maller, Sarah Meiklejohn, Gilad Stern
ePrint Report
In this work we present Bingo, an adaptively secure and optimally resilient packed asynchronous verifiable secret sharing (PAVSS) protocol that allows a dealer to share $f+1$ secrets or one high threshold secret with a total communication complexity of just $O(\lambda n^2)$ words. Bingo requires a public key infrastructure and a powers-of-tau setup. Using Bingo's packed secret sharing, we obtain an adaptively secure validated asynchronous Byzantine agreement (VABA) protocol that uses $O(\lambda n^3)$ expected words and constant expected time. Using this agreement protocol in combination with Bingo, we obtain an adaptively secure high threshold asynchronous distributed key generation (ADKG) of standard field element secrets that uses $O(\lambda n^3)$ expected words and constant expected time. To the best of our knowledge, Bingo is the first ADKG to have an adaptive security proof and have the same asymptotic complexity of the best known ADKG's that only have non-adaptive security proofs.
Abhiram Kothapalli, Srinath Setty
ePrint Report
This paper introduces SuperNova, a new recursive proof system for incrementally producing succinct proofs of correct execution of programs on a stateful machine with a particular instruction set (e.g., EVM, RISC-V). A distinguishing aspect of SuperNova is that the cost of proving a step of a program is proportional only to the size of the circuit representing the instruction invoked by the program step. This is a stark departure from prior works that employ universal circuits where the cost of proving a program step is proportional at least to the sum of sizes of circuits representing each supported instruction—even though a particular program step invokes only one of the supported instructions. Naturally, SuperNova can support a rich instruction set without affecting the per-step proving costs. SuperNova achieves its cost profile by building on Nova, a prior high-speed recursive proof system, and leveraging its internal building block, folding schemes, in a new manner. We formalize SuperNova’s approach as a way to realize non-uniform IVC, a generalization of IVC. Furthermore, SuperNova’s prover costs and the recursion overhead are the same as Nova’s, and in fact, SuperNova is equivalent to Nova for machines that support a single instruction.
Xiaohui Ding, Muhammed F. Esgin, Amin Sakzad, Ron Steinfeld
ePrint Report
The One-Way to Hiding (O2H) Lemma is a central component of proofs of chosen-ciphertext attack (CCA) security of practical
public-key encryption schemes using variants of the Fujisaki-Okamoto
(FO) transform in the Quantum Random Oracle Model (QROM). Recently, Kuchta et al. (EUROCRYPT ’20) introduced a new QROM proof technique, called Measure-Rewind-Measure (MRM), giving an improved variant of the O2H lemma, with a new security reduction that does not suffer from a square-root advantage security loss as in the earlier work of Bindel et al. (TCC ’19).However, the FO transform QROM CCA security reduction based on the improved MRM O2H lemma still requires an injectivity assumption on the underlying CPA-secure determinstic public-key encryption scheme. In particular, the tightness of the concrete security reduction relies on a sufficiently small injectivity bound, and obtaining such bounds for concrete schemes was left as an open problem by Kuchta et al. (EUROCRYPT ’20).
In this paper, we address the above problem by deriving concrete bounds on the injectivity of the deterministic CPA-secure variant of CRYSTALS-Kyber, the public-key encryption scheme selected for standardisation by the NIST Post-Quantum Cryptograpy (PQC) standardisation process. We evaluate our bounds numerically for the CRYSTALS-Kyber parameter sets, and show that the effect of injectivity on the tightness of the QROM CCA security of the Fujisaki-Okamoto transformed Kyber KEM is negligible, i.e. allows for a tight QROM CCA security reduction. Consequently, we give tightest QROM CCA security bounds to date for a simplified ‘single hashing’ variant of Kyber CCAKEM against attacks with low quantum circuit depth. Our bounds apply for all the Kyber parameter sets, based on the hardness of the Module Learning with Errors (MLWE) problem.
Behzad Abdolmaleki, Daniel Slamanig
ePrint Report
A critical aspect for the practical use of non-interactive zero-knowledge (NIZK) arguments in the common reference string (CRS) model is the demand for a trusted setup, i.e., a trusted generation of the CRS. Recently, motivated by its increased use in real-world applications, there has been a growing interest in concepts that allow to reduce the trust in this setup. In particular one demands that the zero-knowledge and ideally also the soundness property hold even when the CRS generation is subverted. One important line of work in this direction is the so-called updatable CRS for NIZK by Groth et al. (CRYPTO’18). The basic idea is that everyone can update a CRS and there is a way to check the correctness of an update. This guarantees that if at least one operation (the generation or one update) have been performed honestly, the zero-knowledge and the soundness properties hold. Later, Lipmaa (SCN’20) adopted this notion of updatable CRS to quasi-adaptive NIZK (QA-NIZK) arguments.
In this work, we continue the study of CRS-updatable QA-NIZK and analyse the most efficient asymmetric QA-NIZKs by González et al. (ASIACRYPT’15) in a setting where the CRS is fully subverted and propose an updatable version of it. In contrast to the updatable QA- NIZK by Lipmaa (SCN’20) which represents a symmetric QA-NIZK and requires a new non-standard knowledge assumption for the subversion zero-knowledge property, our technique to construct updatable asymmetric QA-NIZK is under a well-known standard knowledge assumption, i.e., the Bilinear Diffie-Hellman Knowledge of Exponents assumption. Furthermore, we show the knowledge soundness of the (updatable) asymmetric QA-NIZKs, an open problem posed by Lipmaa, which makes them compatible with modular zk-SNARK frameworks such as LegoS- NARK by Campanelli et al. (ACM CCS’19).
Andreas Klinger, Ulrike Meyer
ePrint Report
To date, ideal functionalities securely realized with secure multi-party computation (SMPC) mainly considers functions of the private inputs of a fixed number of a priori known parties. In this paper, we generalize these definitions such that protocols implementing online algorithms in a distributed fashion can be proven to be privacy-preserving. Online algorithms compute online functionalities that allow parties to arrive and leave over time, to provide multiple inputs and to obtain multiple outputs. In particular, the set of parties participating changes over time, i.e., at different points in time different sets of parties evaluate a function over their private inputs. To this end, we propose the notion of an online trusted third party that allows to prove the security of SMPC protocols implementing online functionalities or online algorithms, respectively. We show that any online functionality can be implemented perfectly secure in the presence of a semi-honest adversary, if strictly less than 1/2 of the parties participating are corrupted. We show that the same result holds in the presence of a malicious adversary if it corrupts strictly less than 1/3 of the parties and always allows the corrupted parties to arrive and provide input.
Note, this is the corrected and extended version of the work presented in [24].
zhenfei zhang
ePrint Report
In [BS22], the authors proposed a lattice based hash function that is useful for building zero-knowledge proofs with superior performance. In this short note we analysis the underlying lattice problem with the classic shortest vector problem, and show that 2 out of 15 proposed parameter sets for this hash function do not achieve the claimed security.