International Association
for Cryptologic Research

Starting from links between coding theory and secret sharing we develop an extensible and decentralized version of Shamir Secret Sharing, that allows the addition of new users after the initial shares distribution.

On top of it we design a totally decentralized $(t,n)$-threshld Schnorr signature scheme that needs only $t$ users online during the key generation phase, while the others join later. Under standard assumptions we prove our scheme secure against adaptive malicious adversaries. Furthermore, we show how our security notion can be strengthen when considering a rushing adversary. Using a classical game-based argument, we prove that if there is an adversary capable of forging the scheme with non-negligible probability, then we can build a forger for the centralized Schnorr scheme with non-negligible probability.

Various systematic modifications of vectorial Boolean functions have been used for finding new previously unknown classes of S-boxes with good or even optimal differential uniformity and nonlinearity. In this paper, a new general modification method is given that preserves the bijectivity property of the function in case the inverse of the function admits a linear structure. A previously known construction of such a modification based on bijective Gold functions in odd dimension is a special case of the new method.

In this paper, we show that it is inaccurate to apply the hypothesis of independent round keys to search for differential characteristics of a block cipher with a simple key schedule. Therefore, the derived differential characteristics may be valid. We develop a SAT-based algorithm to verify the validity of differential characteristics. Furthermore, we take the key schedule into account and thus put forward an algorithm to directly find the valid differential characteristics. All experiments are performed on Midori64 and we find some interesting results.

Trellis is a mix-net based anonymous broadcast system with cryptographic security guarantees. Trellis can be used to anonymously publish documents or communicate with other users, all while assuming full network surveillance. In Trellis, users send messages through a set of servers in successive rounds. The servers mix and post the messages to a public bulletin board, hiding which users sent which messages.

Trellis hides all network metadata, remains robust to changing network conditions, guarantees availability to honest users, and scales with the number of mix servers. Trellis provides three to five orders of magnitude faster performance and better network robustness compared to Atom, the state-of-the-art anonymous broadcast system with a comparable threat model.

In achieving these guarantees, Trellis contributes: (1) a simpler theoretical mixing analysis for a routing mix network constructed with a fraction of malicious servers, (2) anonymous routing tokens for verifiable random paths, and (3) lightweight blame protocols built on top of onion routing to identify and eliminate malicious parties.

We implement and evaluate Trellis in a networked deployment. With 128 servers, Trellis achieves a throughput of 320 bits per second. Trellis’s throughput is only 100 to 1000× slower compared to Tor (which has 6,000 servers and 2 million daily users) and is potentially deployable at a smaller “enterprise” scale. Our implementation is open-source.

Security against side-channel assisted attacks remains a focus and concern in the ongoing standardization process of quantum-computer-resistant cryptography algorithms. Hiding and masking techniques are currently under investigation to protect the Post-Quantum Cryptography (PQC) algorithms in the NIST PQC standardization process against sophisticated side-channel attacks. Between hiding and masking, masking is emerging as a popular option due to its simplicity and minimized cost of implementation compared with hiding, which often requires duplication of hardware resources and advanced analysis and design techniques to implement correctly. This work presents a pure hardware implementation of masked CCA2-secure Kyber-512, a candidate chosen by NIST to be standardized. A novel hiding technique that leverages the advantages of FPGAs over micro-controllers and is demonstrably secure against Simple Power Analysis (SPA) and Differential Power Analysis (DPA) side-channel attacks is presented. Finally, a novel hybrid hiding-masking approach is presented that achieves a reduced hardware resource and clock-cycle penalty compared with previously reported figures for similar PQC candidates. The Test Vector Leakage Assessment (TVLA) is adopted to demonstrate the absence of side-channel leakage.

This paper provides necessary properties to algorithmically secure first-order maskings in scalar micro-architectures. The security notions of threshold implementations are adapted following micro-processor leakage effects which are known to the literature. The resulting notions, which are based on the placement of shares, are applied to a two-share randomness-free PRESENT cipher and Keccak-f. The assembly implementations are put on a RISC-V and an ARM Cortex-M4 core. All designs are validated in the glitch and transition extended probing model and their implementations via practical lab analysis.

The Groth-Sahai proof system is a highly efficient pairing-based proof system for a specific class of group-based languages. Cryptographic primitives that are compatible with these languages (such that we can express, e.g., that a ciphertext contains a valid signature for a given message) are called "structure-preserving". The combination of structure-preserving primitives with Groth-Sahai proofs allows to prove complex statements that involve encryptions and signatures, and has proved useful in a variety of applications. However, so far, the concept of structure-preserving cryptography has been confined to the pairing setting.

In this work, we propose the first framework for structure-preserving cryptography in the lattice setting. Concretely, we - define "structure-preserving sets" as an abstraction of (typically noisy) lattice-based languages, - formalize a notion of generalized structure-preserving encryption and signature schemes capturing a number of existing lattice-based encryption and signature schemes), - construct a compatible zero-knowledge argument system that allows to argue about lattice-based structure-preserving primitives, - offer a lattice-based construction of verifiably encrypted signatures in our framework. Along the way, we also discover a new and efficient strongly secure lattice-based signature scheme. This scheme combines Rückert's lattice-based signature scheme with the lattice delegation strategy of Agrawal et al., which yields more compact and efficient signatures.

We hope that our framework provides a first step towards a modular and versatile treatment of cryptographic primitives in the lattice setting.

We focus on the problem of efficiently deploying a federated learning training task in a decentralized setting with multiple aggregators. To that end, we introduce a number of improvements and modifications to the recently proposed IPLS protocol. In particular, we relax its assumption for direct communication across participants, using instead indirect communication over a decentralized storage system, effectively turning it into a partially asynchronous protocol. Moreover, we secure it against malicious aggregators (that drop or alter data) by relying on homomorphic cryptographic commitments for efficient verification of aggregation. We implement the modified IPLS protocol and report on its performance and potential bottlenecks. Finally, we identify important next steps for this line of research.

We construct the first four-round non-malleable commitment scheme based solely on the black-box use of one-to-one one-way functions. Prior to our work, all non-malleable commitment schemes based on black-box use of polynomial-time cryptographic primitives require more than $16$ rounds of interaction. A key tool for our construction is a proof system that satisfies a new definition of security that we call non-malleable zero-knowledge with respect to commitments. In a nutshell, such a proof system can be safely run in parallel with a (potentially interactive) commitment scheme. We provide an instantiation of this tool using the MPC-in-the-Head approach in combination with BMR.

Concretely efficient interactive oracle proofs (IOPs) are of interest due to their applications to scaling blockchains, their minimal security assumptions, and their potential future-proof resistance to quantum attacks.

Scalable IOPs, in which prover time scales quasilinearly with the computation size and verifier time scales poly-logarithmically with it, have been known to exist thus far only over a set of finite fields of negligible density, namely, over "FFT-friendly" fields that contain a sub-group of size $2^k$.

Our main result is to show that scalable IOPs can be constructed over any sufficiently large finite field, of size that is at least quadratic in the length of computation whose integrity is proved by the IOP. This result has practical applications as well, because it reduces the proving and verification complexity of cryptographic statements that are naturally stated over pre-defined finite fields which are not "FFT-friendly".

Prior state-of-the-art scalable IOPs relied heavily on arithmetization via univariate polynomials and Reed--Solomon codes over FFT-friendly fields. To prove our main result and extend scalability to all large finite fields, we generalize the prior techniques and use new algebraic geometry codes evaluated on sub-groups of elliptic curves (elliptic curve codes). We also show a new arithmetization scheme that uses the rich and well-understood group structure of elliptic curves to reduce statements of computational integrity to other statements about the proximity of functions evaluated on the elliptic curve to the new family of elliptic curve codes.

This paper continues our recent work that used elliptic curves and their subgroups to create FFT-based algorithms for polynomial manipulation over generic finite fields. However, our new IOP constructions force us to use new codes (ones that are not based on polynomials), and this poses a new set of challenges involving the more restricted automorphism group of these codes, and the constraints of Riemann-Roch spaces of strictly positive genus.

Sealed bid auctions are used to allocate a resource among a set of interested parties. Traditionally, auctions need the presence of a trusted auctioneer to whom the bidders provide their private bid values. Existence of such a trusted party is not an assumption easily realized in practice. Generic secure computation protocols can be used to remove a trusted party. However, generic techniques result in inefficient protocols, and typically do not provide fairness - that is, a corrupt party can learn the output and abort the protocol thereby preventing other parties from learning the output.

At CRYPTO 2009, Miltersen, Nielsen and Triandopoulos [MNT09], introduced the problem of building auctions that are secure against rational bidders. Such parties are modelled as self-interested agents who care more about maximizing their utility than about learning information about bids of other agents. To realize this, they put forth a novel notion of information utility and introduce a game-theoretic framework that helps analyse protocols while taking into account both information utility as well as monetary utility. Unfortunately, their construction makes use a of generic MPC protocol and, consequently, the authors do not analyze the concrete efficiency of their protocol.

In this work, we construct the first concretely efficient and provably secure protocol for First Price Auctions in the rational setting. Our protocol guarantees privacy, public verifiability and fairness. Inspired by [MNT09], we put forth a solution concept that we call Privacy Enhanced Computational Weakly Dominant Strategy Equilibrium that captures parties' privacy and monetary concerns in the game theoretic context, and show that our protocol realizes this. We believe this notion to be of independent interest. Our protocol is crafted specifically for the use case of auctions, is simple, using off-the-shelf cryptographic components.

Executing our auction protocol on commodity hardware with 30 bidders, with bids of length 10, our protocol runs to completion in 0.429s and has total communication of 82KB.

The so-called $\omega$-encoding, introduced by Goudarzi, Joux and Rivain (Asiacrypt 2018), generalizes the commonly used arithmetic encoding. By using the additionnal structure of this encoding, they proposed a masked multiplication gadget (GJR) with quasilinear (randomness and operations) complexity. A second contribution by Goudarzi, Prest, Rivain and Vergnaud in this line of research appeared in TCHES 2021. The authors revisited the aforementioned multiplication gadget (GPRV), and brought the IOS security notion for refresh gadgets to allow secure composition between probing secure gadgets.

In this paper, we propose a follow up on GPRV. Our contribution stems from a single Lemma, linking algebra and probing security for a wide class of circuits, further exploiting the algebraic structure of $\omega$-encoding. On the theoretical side, we weaken the IOS notion into the KIOS notion, and we weaken the usual $t$-probing security into the RTIK security. The composition Theorem that we obtain by plugging together KIOS, RTIK still achieves region-probing security for composition of circuits.

To substantiate our weaker definitions, we also provide examples of competitively efficient gadgets verifying our weaker security notions. Explicitly, we give 1) a refresh gadget that uses $d-1$ random field elements to refresh a length $d$ encoding that is KIOS but not IOS, and 2) multiplication gadgets asymptotically subquadratic in both randomness and complexity. While our algorithms outperform the ISW masked compiler asymptotically, their security proofs require a bounded number of shares for a fixed base field.

In p-noisy coin-tossing, Alice and Bob obtain fair coins which are of opposite values with probability p. Its Oblivious-Transfer (OT) complexity refers to the least number of OTs required by a semi-honest perfectly secure 2-party protocol for this task. We show a tight bound of Θ(log 1/p) for the OT complexity of p-noisy coin-tossing. This is the first instance of a lower bound for OT complexity that is independent of the input/output length of the function.

We obtain our result by providing a general connection between the OT complexity of randomized functions and the complexity of Secure Zero Communication Reductions (SZCR), as recently de- fined by Narayanan et al. (TCC 2020), and then showing a lower bound for the complexity of an SZCR from noisy coin-tossing to (a predicate corresponding to) OT.

DME is a multivariate public key cryptosystem based on the composition of linear and exponential maps that allow the polynomials of the public key to be of a very high degree. A previous version of DME was presented to the NIST call for post quantum cryptosystems (in the KEM category), but it did not qualify to the second round. This new version of DME adds two extra rounds of exponentials to the first version, and only needs arithmetic in the finite fields Fq and Fq^2.

Multivariate rule x_i -> f_i, i = 1, 2, ..., n, f_i from K[x_1, x_2, ..., x_n] over commutative ring K defines endomorphism σ_n of K[x_1, x_2, ..., x_n] into itself given by its values on variables x_i. Degree of σ_n can be defined as maximum of degrees of polynomials f_i. We say that family σ_n, n = 2, 3, .... has trapdoor accelerator ^nT if the knowledge of the piece of information ^nT allows to compute reimage x of y = σ_n(x) in time O(n^2). We use extremal algebraic graphs for the constructions of families of automorphisms σ_n with trapdoor accelerators and (σ_n)^{−1} of large order. We use these families for the constructions of new multivariate public keys and protocol based cryptosystems of El Gamal type of Postquantum Cryptography. Some of these cryptosystems use as encryption tools families of endomorphisms σn of unbounded degree such that their restriction on the varieties (K^∗)^n are injective. As usual K^∗ stands for the multiplicative group of commutative ring K with the unity. Spaces of plaintexts and ciphertexts are (K^∗)^n and K^n. Security of such cryptosystem of El Gamal type rests on the complexity of word decomposition problem in the semigroup of Eulerian endomorphisms of K[x_1, x_2; ... , x_n].

In a world where everyone uses anonymous credentials for all access control needs, it is impossible to trace wrongdoers, by design. This makes legitimate controls, such as tracing illicit trade and terror suspects, impossible to carry out. Here, we propose a privacy-preserving blueprint capability that allows an auditor to publish an encoding $pk_A$ of the function $f(x,\cdot)$ for a publicly known function $f$ and a secret input $x$. For example, $x$ may be a secret watchlist, and $f(x,y)$ may return $y$ if $y\in x$. On input her data $y$ and the auditor's $pk_A$, a user can compute an escrow $Z$ such that anyone can verify that $Z$ was computed correctly from the user's credential attributes, and moreover, the auditor can recover $f(x,y)$ from $Z$. Our contributions are:

* We define secure $f$-blueprint systems; our definition is designed to provide a modular extension to anonymous credential systems.

* We show that secure $f$-blueprint systems can be constructed for all functions $f$ from fully homomorphic encryption and NIZK proof systems. This result is of theoretical interest but is not efficient enough for practical use.

* We realize an optimal blueprint system under the DDH assumption in the random-oracle model for the watchlist function.

In the setting of subversion, an adversary tampers with the machines of the honest parties thus leaking the honest parties' secrets through the protocol transcript. The work of Mironov and Stephens-Davidowitz (EUROCRYPT’15) introduced the idea of reverse firewalls (RF) to protect against tampering of honest parties' machines. All known constructions in the RF framework rely on the malleability of the underlying operations in order for the RF to rerandomize/sanitize the transcript. RFs are thus limited to protocols that offer some structure, and hence based on public-key operations. In this work, we initiate the study of $efficient$ Multiparty Computation (MPC) protocols in the presence of tampering. In this regard,

- We construct the $first$ Oblivious Transfer (OT) extension protocol in the RF setting. We obtain $poly(\kappa)$ maliciously-secure OTs using $O(\kappa)$ public key operations and $O(1)$ inexpensive symmetric key operations, where $\kappa$ is the security parameter.

- We construct the $first$ Zero-knowledge protocol in the RF setting where each multiplication gate can be proven using $O(1)$ symmetric key operations. We achieve this using our OT extension protocol and by extending the ZK protocol of Quicksilver (Yang, Sarkar, Weng and Wang, CCS'21) to the RF setting. - Along the way, we introduce new ideas for malleable interactive proofs that could be of independent interest. We define a notion of $full$ $malleability$ for Sigma protocols that unlike prior notions allow modifying the instance as well, in addition to the transcript. We construct new protocols that satisfy this notion, construct RFs for such protocols and use them in constructing our OT extension. The key idea of our work is to demonstrate that correlated randomness may be obtained in an RF-friendly way $without$ having to rerandomize the entire transcript. This enables us to avoid expensive public-key operations that grow with the circuit-size.

Many modes of operations for block ciphers or tweakable block ciphers do not require invertibility from their underlying primitive. In this work, we study fixed-length Tweakable Pseudorandom Function (TPRF) with large domain extension, a novel primitive that can bring high security and significant performance optimizations in symmetric schemes, such as (authenticated) encryption. Our first contribution is to introduce a new design paradigm, derived from the Iterate-Fork-Iterate construction, in order to build $n$-to-$\alpha n$-bit ($\alpha\geq2$), $n$-bit secure, domain expanding TPRF. We dub this new generic composition masked Iterate-Fork-Iterate (mIFI). We then propose a concrete TPRF instantiation ButterKnife that expands an $n$-bit input to $8n$-bit output via a public tweak and secret key. ButterKnife is built with high efficiency and security in mind. It is fully parallelizable and based on Deoxys-BC, the AES-based tweakable block cipher used in the authenticated encryption winner algorithm in the defense-in-depth category of the recent CAESAR competition. We analyze the resistance of ButterKnife to differential, linear, meet-in-the-middle, impossible differentials and rectangle attacks. A special care is taken to the attack scenarios made possible by the multiple branches. Our next contribution is to design and provably analyze two new TPRF-based deterministic authenticated encryption (DAE) schemes called SAFE and ZAFE that are highly efficient, parallelizable, and offer $(n+\min(n,t))/2$ bits of security, where $n,t$ denote respectively the input block and the tweak sizes of the underlying primitives. We further implement SAFE with ButterKnife to show that it achieves an encryption performance of 1.06 c/B for long messages on Skylake, which is 33-38% faster than the comparable Crypto'17 TBC-based ZAE DAE. Our second candidate ZAFE, which uses the same authentication pass as ZAE, is estimated to offer a similar level of speedup. Besides, we show that ButterKnife, when used in Counter Mode, is slightly faster than AES (0.50 c/B vs 0.56 c/B on Skylake).

Secure group messaging (SGM) protocols allow large groups of users to communicate in a secure and asynchronous manner. In recent years, continuous group key agreements (CGKAs) have provided a powerful abstraction to reason on the security properties we expect from SGM protocols. While robust techniques have been developed to protect the contents of conversations in this context, it is in general more challenging to protect metadata (e.g. the identity and social relationships of group members), since their knowledge is often needed by the server in order to ensure the proper function of the SGM protocol.

In this work, we provide a simple and generic wrapper protocol that upgrades non-metadata-hiding CGKAs into metadata-hiding CGKAs. Our key insight is to leverage the existence of a unique continuously evolving group secret key shared among the group members. We use this key to perform a group membership authentication protocol that convinces the server in an \textit{anonymous} manner that a user is a legitimate group member. Our technique only uses a standard signature scheme, and thus, the wrapper protocol can be instantiated from a wide range of assumptions, including post-quantum ones. It is also very efficient, as it increases the bandwidth cost of the underlying CGKA operations by at most a factor of two.

To formally prove the security of our protocol, we use the universal composability (UC) framework and model a new ideal functionality ${\mathcal{F}_{\text{CGKA}}^{\sf mh}}$ capturing the correctness and security guarantee of metadata-hiding CGKA. To capture the above intuition of a ``wrapper'' protocol, we also define a restricted ideal functionality $\mathcal{F}_{\text{CGKA}}^{\sf ctxt}$, which roughly captures a non-metadata-hiding CGKA. We then show that our wrapper protocol UC-realizes ${\mathcal{F}_{\text{CGKA}}^{\sf mh}}$ in the $\mathcal{F}_{\text{CGKA}}^{\sf ctxt}$-hybrid model, which in particular formalizes the intuition that any non-metadata-hiding CGKA can be modularly bootstrapped into metadata-hiding CGKA.

Decentralized Multi-Client Functional Encryption (DMCFE) extends the basic functional encryption to multiple clients that do not trust each other. They can independently encrypt the multiple inputs to be given for evaluation to the function embedded in the functional decryption key. And they keep control on these functions as they all have to contribute to the generation of the functional decryption keys. As any encryption scheme, all the FE schemes provide privacy of the plaintexts. But the functions associated to the functional decryption keys might be sensitive too (e.g. a model in machine learning). The function-hiding property has thus been introduced to additionally protect the function evaluated during the decryption process. But it was not properly defined for previous definitions of DMCFE. In this paper, we provide a formal definition of DMCFE with complete function-hiding security game. We thereafter propose a concrete construction of function-hiding DMCFE for inner products, with strong security guarantees: the adversary is allowed to adaptively query multiple challenge ciphertexts and multiple challenge keys. Previous constructions were proven secure for a single challenge ciphertext only, in the selective setting (i.e. provided before the setup).