International Association
for Cryptologic Research

Today, two-party secure messaging is well-understood and widely adopted on the Internet, e.g., Signal and WhatsApp. Multiparty protocols for secure group messaging on the other hand are less mature and many protocols with different tradeoffs exist. Generally, such protocols require parties to first agree on a shared secret group key and then periodically update it while preserving forward secrecy (FS) and post compromise security (PCS).

We present a new framework, called a key lattice, for managing keys in concurrent group messaging. Our framework can be seen as a ``key management'' layer that enables concurrent group messaging when secure pairwise channels are available. Proving security of group messaging protocols using the key lattice requires new game-based security definitions for both FS and PCS. Our new definitions are both simpler and more natural than previous ones, as our framework combines both FS and PCS into directional variants of the same abstraction, and additionally avoids dependence on time-based epochs.

Additionally, we give a concrete, standalone instantiation of a concurrent group messaging protocol for dynamic groups. Our protocol provides both FS and PCS, supports concurrent updates, and only incurs $O(1)$ overhead for securing the messaging payload, $O(n)$ update cost and $O(n)$ healing costs, which are optimal.

Logarithmic derivatives translate products of linear factors into sums of their reciprocals, turning zeroes into simple poles of same multiplicity. Based on this simple fact, we construct an interactive oracle proof for multi-column lookups over the boolean hypercube, which makes use of a single multiplicity function instead of working with a rearranged union of table and witnesses. For single-column lookups the performance is comparable to the well-known Plookup strategy used by Hyperplonk+. However, the real power of our argument unfolds in the case of batch lookups when multiple columns are subject to a single-table lookup: While the number of field operations is comparable to the Hyperplonk+ lookup (extended to multiple columns), the oracles provided by our prover are much less expensive. For example, for columns of length 2^12, paper-pencil operation counts indicate that the logarithmic derivative lookup is between 1.5 and 4 times faster, depending on the number of columns.

We present a key-recovery fault injection attack on the Classic McEliece Key Encapsulation Mechanism (KEM). The fault injections target the error-locator polynomial of the Goppa code and the validity checks in the decryption algorithm, making a chosen ciphertext attack possible. Faulty decryption outputs are used to generate a system of polynomial equations in the secret support elements of the Goppa code. After solving the equations, we can determine a suitable Goppa polynomial and form an alternative secret key. To demonstrate the feasibility of the attack on hardware, we simulate the fault injections on virtual prototypes of two RISC-V cores at register-transfer level.

At Eurocrypt`22 Tang, Duong, Joux, Plantard, Qiao, and Susilo proposed a digital signature algorithm based on the hardness of the isomorphism problem of alternating trilinear forms. They propose three concrete parameters in dimensions $9$, $10$, and $11$ respectively. We give new heuristic algorithms that solve this problem more efficiently. With our new algorithms, the first parameter set can be broken in less than a day on a laptop. For the second parameter set, we show there is a $2^{-17}$ fraction of the public keys that can also be broken in less than a day. We do not break the third parameter set in practice, but we claim it falls short of the target security level of $128$ bits.

Functional encryption features secret keys, each associated with a key function $f$, which allow to directly recover $f(x)$ from an encryption of $x$, without learning anything more about $x$. This property is particularly useful when delegating data processing to a third party as it allows the latter to perfom its task while ensuring minimum data leakage. However, this generic term conceals a great diversity in the cryptographic constructions that strongly differ according to the functions $f$ they support.

A recent series of works has focused on the ability to search a pattern within a data stream, which can be expressed as a function $f$. One of the conclusions of these works was that this function $f$ was not supported by the current state-of-the-art, which incited their authors to propose a new primitive called Stream Encryption supporting Pattern Matching (SEPM). Some concrete constructions were proposed but with some limitations such as selective security or reliance on non-standard assumptions.

In this paper, we revisit the relations between this primitive and two major subclasses of functional encryption, namely Hidden Vector Encryption (HVE) and Inner Product Encryption (IPE). We indeed first exhibit a generic transformation from HVE to SEPM, which immediately yields new efficient SEPM constructions with better features than existing ones. We then revisit the relations between HVE and IPE and show that we can actually do better than the transformation proposed by Katz, Sahai and Waters in their seminal paper on predicate encryption. This allows to fully leverage the vast state-of-the-art on IPE which contains adaptively secure constructions proven under standard assumptions. This results in countless new SEPM constructions, with all the features one can wish for. Beyond that, we believe that our work sheds a new light on the relations between IPE schemes and HVE schemes and in particular shows that some of the former are more suitable to construct the latter.

Alon et. al (Crypto 2020) initiated the study of MPC with Friends and Foes (FaF) security, which captures the desirable property that even up to $h^{*}$ honest parties should learn nothing additional about other honest parties’ inputs, even if the $t$ corrupt parties send them extra information. Alon et. al describe two flavors of FaF security: weak FaF, where the simulated view of up to $h^{*}$ honest parties should be indistinguishable from their real view, and strong FaF, where the simulated view of the honest parties should be indistinguishable from their real view even in conjunction with the simulated / real view of the corrupt parties. They give several initial FaF constructions with guaranteed output delivery (GOD); however, they leave some open problems. Their only construction which supports the optimal corruption bounds of $2t+h^{*} < n$ (where $n$ denotes the number of parties) only offers weak FaF security and takes much more than the optimal three rounds of communication.

In this paper, we describe two new constructions with GOD, both of which support $2t+h^{*} < n$. Our first construction, based on threshold FHE, is the first three-round construction that matches this optimal corruption bound (though it only offers weak FaF security). Our second construction, based on a variant of BGW, is the first such construction that offers strong FaF security (though it requires more than three rounds, as well as correlated randomness).

Our final contribution is further exploration of the relationship between FaF security and similar security notions. In particular, we show that FaF security does not imply mixed adversary security (where the adversary can make $t$ active and $h^{*}$ passive corruptions), and that Best of Both Worlds security (where the adversary can make $t$ active or $t+h^{*}$ passive corruptions, but not both) is orthogonal to both FaF and mixed adversary security.

The notion of Endemic Oblivious Transfer (EOT) was introduced by Masny and Rindal (CCS'19). EOT offers a weaker security guarantee than the conventional random OT; namely, the malicious parties can fix their outputs arbitrarily. The authors presented a 1-round UC-secure EOT protocol under a tailor-made and non-standard assumption, Choose-and-Open DDH, in the RO model.

In this work, we systematically study EOT in the UC/GUC framework. We present the first UC-secure 1-round EOT protocol in the RO model under the DDH assumption in both the static and the adaptive security setting. Under the GUC framework, we propose the first 1-round EOT construction under the CDH assumption in the Global Restricted Observable RO (GroRO) model proposed by Canetti et al. (CCS'14). We also provide an impossibility result, showing there exists no 1-round GUC-secure EOT protocols in the Global Restricted Programmable RO (GrpRO) model proposed by Camenisch et al. (Eurocrypt'18). Subsequently, we provide the first round-optimal (2-round) EOT protocol with adaptive security under the DDH assumption in the GrpRO model. Finally, we investigate the relations between EOT and other cryptographic primitives.

As side products, we present the first 2-round GUC-secure commitment in the GroRO model as well as a separation between the GroRO and the GrpRO model, which may be of independent interest.

Probabilistically Checkable Proofs (PCPs) allow a randomized verifier, with oracle access to a purported proof, to probabilistically verify an input statement of the form ``$x\in\mathcal{L}$'' by querying only few proof bits. Zero-Knowledge PCPs (ZK-PCPs) enhance standard PCPs to additionally guarantee that the view of any (possibly malicious) verifier querying a bounded number of proof bits can be efficiently simulated up to a small statistical distance.

The first ZK-PCP construction of Kilian, Petrank and Tardos (STOC 1997), and following constructions employing similar techniques, necessitate that the honest verifier make several rounds of queries to the proof. This undesirable property, which is inherent to their technique, translates into increased round complexity in cryptographic applications of ZK-PCPs.

We survey two recent ZK-PCP constructions -- due to Ishai, Yang and Weiss (TCC 2016-A), and Hazay, Venkitasubramaniam, and Weiss (ITC 2021) -- in which the honest verifier makes a single round of queries to the proof. Both constructions use entirely different techniques compared to previous ZK-PCP constructions, by showing connections to the seemingly-unrelated notion of leakage resilience. These constructions are incomparable to previous ZK-PCP constructions: while on the one hand the honest verifier only makes a single round of queries to the proof, these ZK-PCPs either obtain a smaller (polynomial) ratio between the query complexity of the honest and malicious verifiers, or obtain a weaker ZK guarantee in which the ZK simulator is not necessarily efficient.

Distributed Zero-Knowledge (dZK) proofs, recently introduced by Boneh et al. (CYPTO`19), allow a prover $P$ to prove NP statements on an input $x$ which is distributed between $k$ verifiers $V_1,\ldots,V_k$, where each $V_i$ holds only a piece of $x$. As in standard ZK proofs, dZK proofs guarantee Completeness when all parties are honest; Soundness against a malicious prover colluding with $t$ verifiers; and Zero Knowledge against a subset of $t$ malicious verifiers, in the sense that they learn nothing about the NP witness and the input pieces of the honest verifiers.

Unfortunately, dZK proofs provide no correctness guarantee for an honest prover against a subset of maliciously corrupted verifiers. In particular, such verifiers might be able to ``frame'' the prover, causing honest verifiers to reject a true claim. This is a significant limitation, since such scenarios arise naturally in dZK applications, e.g., for proving honest behavior, and such attacks are indeed possible in existing dZKs.

We put forth and study the notion of strong completeness for dZKs, guaranteeing that true claims are accepted even when $t$ verifiers are maliciously corrupted. We then design strongly-complete dZK proofs using the ``MPC-in-the-head'' paradigm of Ishai et al. (STOC`07), providing a novel analysis that exploits the unique properties of the distributed setting.

To demonstrate the usefulness of strong completeness, we present several applications in which it is instrumental in obtaining security. First, we construct a certifiable version of Verifiable Secret Sharing (VSS), which is a VSS in which the dealer additionally proves that the shared secret satisfies a given NP relation. Our construction withstands a constant fraction of corruptions, whereas a previous construction of Ishat et al. (TCC`14) could only handle $k^{\varepsilon}$ corruptions for a small $\varepsilon<1$. We also design a reusable version of certifiable VSS that we introduce, in which the dealer can prove an unlimited number of predicates on the same shared secret. Finally, we extend a compiler of Boneh et al. (CRYPTO`19), who used dZKs to transform a class of ``natural'' semi-honest protocols in the honest-majority setting into maliciously secure ones with abort. Our compiler uses strongly-complete dZKs to obtain identifiable abort.

We present two infinite families of APN functions in triviariate form over finite fields of the form $\mathbb{F}_{2^{3m}}$. We show that the functions from both families are permutations when $m$ is odd, and are 3-to-1 functions when $m$ is even. In particular, our functions are AB permutations for $m$ odd. Furthermore, we observe that for $m = 3$, i.e. for $\mathbb{F}_{2^9}$, the functions from our families are CCZ-equivalent to the two bijective sporadic APN instances discovered by Beierle and Leander.

Since the introduction of differential-neural cryptanalysis, as the machine learning assisted differential cryptanalysis proposed in [Goh19] is coined by now, a lot of followup works have been published, showing the applicability for a wide variety of ciphers. In this work, we set out to vet a multitude of differential-neural distinguishers presented so far, and additionally provide general insights. Firstly, we show for a selection of different ciphers how differential-neural distinguishers for those ciphers can be (automatically) optimized, also providing guidance to do so for other ciphers as well. Secondly, we explore a correlation between a differential-neural distinguisher's accuracy and a standard notion of difference between the two underlying distributions. Furthermore, we show that for a whole (practically relevant) class of ciphers, the differential-neural distinguisher can use differential features only. At last, we also rectify a common mistake in current literature, and show that, making use of an idea already presented in the foundational work[Goh19], the claimed improvements from using multiple ciphertext-pairs at once are at most marginal, if not non-existent.

Permissionless blockchains are too slow for applications like point-of-sale payments. While several techniques have been proposed to speed up blockchain payments, none of them are satisfactory for application scenarios like retail shopping. In particular, existing solutions like payment channels require users to lock up significant funds and schemes based on pre-defined validators enable easy transaction censoring. In this paper, we develop Quicksilver, the first blockchain payment scheme that works with practical collaterals and is fast, censorship-resilient, and confidential at the same time.We implement Quicksilver for EVM-compatible chains and show that censoring-resilient payments are fast and affordable on currently popular blockchains platforms like Ethereum and Polygon.

Public key broadcast encryption enables computations of ciphertexts, in which a single ciphertext is encrypted with regard to a set of recipients, and only the intended recipients can decrypt that ciphertext independently of each other and without interactions. A significant shortcoming of existing broadcast encryption schemes are long decryption keys comprising the public keys of pertaining recipients. Decryption therefore necessitates access to public keys, which requires key management and impacts computational and transmission overhead, accessibility, and storage. Moreover, a user description list referencing the pertaining recipients and their public keys must be appended to each ciphertext, which leads to the privacy implication of disclosing user/content-relations. Predominantly all broadcast encryption schemes are based on bilinear pairings. In this paper, we propose a collusion-resistant broadcast encryption scheme that is the first broadcast encryption scheme based on the factorization problem and hidden RSA subgroups. A novel feature is that the decryption key consists of a single element only, which leads to significantly reduced key management, improved computational efficiency, and elimination of the mentioned privacy issue.

The cube attack is one of the most important cryptanalytic techniques against Trivium. As the method of recovering superpolies becomes more and more effective, another problem of cube attacks, i.e., how to select cubes corresponding to balanced superpolies, is attracting more and more attention. It is well-known that a balanced superpoly could be used in both theoretical and practical analyses. In this paper, we present a novel framework to search for valuable cubes whose superpolies have an independent secret variable each, i.e., a linear variable not appearing in any nonlinear term. To control online complexity, valuable cubes are selected from very few large cubes. New ideas are given on the large cube construction and the subcube sieve.

For the verification of this new algorithm, we apply it to Trivium. For 815-round Trivium, using one cube of size 47, we obtain more than 200 balanced superpolies containing 68 different independent secret variables. To make a trade-off between the number of cubes and computation complexity, we choose 35 balanced superpolies and mount a key-recovery attack on 815-round Trivium with a complexity of $2^{47.32}$. For 820-round Trivium, using two cubes of size 52, we obtain more than 100 balanced superpolies, which contain 54 different independent secret variables. With 30 balanced superpolies, we mount a key-recovery attack on 820-round Trivium with a complexity of $2^{53.17}$. Strong experimental evidence shows that the full key-recovery attacks on 815- and 820-round Trivium could be completed within six hours and two weeks on a PC with two RTX3090 GPUs, respectively.

We construct the first secure multiparty quantum computation with public verifiable identifiable abort (MPQC-PVIA) protocol, where PVIA security enables outside observers with only classical computational power to agree on the identity of a malicious party in case of an abort. Moreover, our MPQC is the first quantum setting to provide Best-of-Both-Worlds (BoBW) security, which attains full security with an honest majority and is secure with abort if the majority is dishonest. At the heart of our construction is a generic transformation called Auditable Quantum Authentication (AQA) that publicly identifies the malicious sender with overwhelming probability. Our approach comes with several advantages over the traditional way of building MPQC protocols. First, instead of following the Clifford code paradigm, our protocol can be based on a variety of authentication codes. Second, the online phase of our MPQC requires only classical communications. Third, our construction can achieve distributed computation via a carefully crafted protocol design, which can be adjusted to an MPQC that conditionally guarantees output delivery.

Canetti, Rothblum, and Varia showed how to obfuscate membership testing in a hyperplane over a finite field of exponentially large prime order, assuming the membership predicate is evasive and the under a modified DDH assumption. Barak, Bitansky, Canetti, Kalai, Paneth, and Sahai extended their work from hyperplanes to hypersurfaces (of bounded degree), assuming multi-linear maps.

In this paper we give much more general obfuscation tools that allow to obfuscate evasive membership testing in arbitrary algebraic sets (including projective sets) over finite fields of arbitrary (prime power) order. We give two schemes and prove input-hiding security based on relatively standard assumptions. The first scheme is based on the preimage resistance property of cryptographic hash functions; and the second scheme is based on the hardness assumptions required for small superset obfuscation. We also introduce a new security notion called span-hiding, and prove that the second scheme achieves span-hiding assuming small superset obfuscation.

One special case of algebraic sets over finite fields is boolean polynomials, which means our methods can be applied to obfuscate any evasive function defined by a polynomial-size collection of boolean polynomials. As a corollary, we obtain an input-hiding obfuscator for evasive functions defined by circuits in NC^0.

Vector commitment schemes allow a user to commit to a vector of values $\mathbf{x} \in \{0,1\}^\ell$ and later, open up the commitment to a specific set of positions. Both the size of the commitment and the size of the opening should be succinct (i.e., polylogarithmic in the length $\ell$ of the vector). Vector commitments and their generalizations to polynomial commitments and functional commitments are key building blocks for many cryptographic protocols.

We introduce a new framework for constructing lattice-based vector commitments and their generalizations. A simple instantiation of our framework yields a new vector commitment scheme from the standard short integer solution (SIS) assumption that supports private openings and large messages. We then show how to use our framework to obtain the first succinct functional commitment scheme that supports openings with respect to arbitrary Boolean circuits of bounded depth. In this scheme, a user can commit to a vector $\mathbf{x} \in \{0,1\}^\ell$, and later on, open the commitment to any function $f(\mathbf{x})$. Both the commitment and the opening are succinct: namely, they have size $\textsf{poly}(\lambda, d, \log \ell)$, where $\lambda$ is the security parameter and $d$ is the depth of the Boolean circuit computing $f$. Previous constructions of functional commitments could only support constant-degree polynomials, or require a trusted online authority, or rely on non-falsifiable assumptions. The security of our functional commitment scheme is based on a new (and falsifiable) family of "basis-augmented" SIS assumptions BASIS we introduce in this work.

We also show how to use our vector commitment framework to obtain (1) a polynomial commitment scheme where the user can commit to a polynomial $f \in \mathbb{Z}_q[x]$ and subsequently open the commitment to an evaluation $f(x) \in \mathbb{Z}_q$; and (2) an aggregatable vector (resp., functional) commitment where a user can take a set of openings to multiple indices (resp., function evaluations) and aggregate them into a single short opening. Both of these extensions rely on the same BASIS assumption we use to obtain our succinct functional commitment scheme.

Pseudorandom quantum states (PRS) are efficiently constructible states that are computationally indistinguishable from being Haar-random, and have recently found cryptographic applications. We explore new definitions, new properties and applications of pseudorandom states, and present the following contributions:

1. New Definitions: We study variants of pseudorandom function-like state (PRFS) generators, introduced by Ananth, Qian, and Yuen (CRYPTO'22), where the pseudorandomness property holds even when the generator can be queried adaptively or in superposition. We show the feasibility of these variants assuming the existence of post-quantum one-way functions. 2. Classical Communication: We show that PRS generators with logarithmic output length imply commitment and encryption schemes with classical communication. Previous constructions of such schemes from PRS generators required quantum communication. 3. Simplified Proof: We give a simpler proof of the Brakerski-Shmueli (TCC'19) result that polynomially-many copies of uniform superposition states with random binary phases are indistinguishable from Haar-random states. 4. Necessity of Computational Assumptions: We also show that a secure PRS with output length logarithmic, or larger, in the key length necessarily requires computational assumptions.

Player-replaceability is a property of a blockchain protocol that ensures every step of the protocol is executed by an unpredictably random (small) set of players; this guarantees security against a fully adaptive adversary and is a crucial property in building permissionless blockchains. Forensic Support is a property of a blockchain protocol that provides the ability, with cryptographic integrity, to identify malicious parties when there is a safety violation; this provides the ability to enforce punishments for adversarial behavior and is a crucial component of incentive mechanism designs for blockchains. Player-replaceability and strong forensic support are both desirable properties, yet, none of the existing blockchain protocols have both properties. Our main result is to construct a new BFT protocol that is player-replaceable and has maximum forensic support. The key invention is the notion of a ``transition certificate'', without which we show that natural adaptations of extant BFT and longest chain protocols do not lead to the desired goal of simultaneous player-replaceability and forensic support.

The MPC-in-the-Head paradigm is a useful tool to build practical signature schemes. Many such schemes have been already proposed, relying on different assumptions. Some are relying on existing symmetric primitives like AES, some are relying on MPC-friendly primitives like LowMC or Rain, and some are relying on well-known hard problems like the syndrome decoding problem.

This work focus on the third type of MPCitH-based signatures. Following the same methodology as the work of Feneuil, Joux and Rivain (CRYPTO'22), we apply the MPC-in-the-Head paradigm to several problems: the multivariate quadratic problem, the MinRank problem, the rank syndrome decoding problem and the permuted kernel problem. Our goal is to study how this paradigm behaves for each of those problems.

For the multivariate quadratic problem, our scheme outperforms slightly the existing schemes when considering large fields (as $\mathbb{F}_{256}$), and for the permuted kernel problem, we obtain larger sizes. Even if both schemes do not outperform the existing ones according to the communication cost, they are highly parallelizable and compatible with some MPC-in-the-Head techniques (like fast signature verification) while the former proposals were not.

Moreover, we propose two efficient MPC protocols to check that the rank of a matrix over a field $\mathbb{F}_q$ is upper bounded by a public constant. The first one relies on the rank decomposition while the second one relies on $q$-polynomials. We then use them to build signature schemes relying on the MinRank problem and the rank syndrome decoding problem. Those schemes outperform the former schemes, achieving sizes below $6$ KB (while using only 256 parties for the MPC protocol).