Handwritten assembly is a widely used tool in the development of high-performance cryptography: By providing full control over instruction selection, instruction scheduling, and register allocation, highest performance can be unlocked. On the flip side, developing handwritten assembly is not only time-consuming, but the artifacts produced also tend to be difficult to review and maintain – threatening their suitability for use in practice. In this work, we present SLOTHY (Super (Lazy) Optimization of Tricky Handwritten assemblY), a framework for the automated superoptimization of assembly with respect to instruction scheduling, register allocation, and loop optimization (software pipelining): With SLOTHY, the developer controls and focuses on algorithm and instruction selection, providing a readable “base” implementation in assembly, while SLOTHY automatically finds optimal and traceable instruction scheduling and register allocation strategies with respect to a model of the target (micro)architecture. We demonstrate the flexibility of SLOTHY by instantiating it with models of the Cortex-M55, Cortex-M85, Cortex-A55 and Cortex-A72 microarchitectures, implementing the Armv8.1-M+Helium and AArch64+Neon architectures. We use the resulting tools to optimize three workloads: First, for Cortex-M55 and Cortex-M85, a radix-4 complex Fast Fourier Transform (FFT) in fixed-point and floating-point arithmetic, fundamental in Digital Signal Processing. Second, on Cortex-M55, Cortex-M85, Cortex-A55 and Cortex-A72, the instances of the Number Theoretic Transform (NTT) underlying CRYSTALS-Kyber and CRYSTALS-Dilithium, two recently announced winners of the NIST Post-Quantum Cryptography standardization project. Third, for Cortex-A55, the scalar multiplication for the elliptic curve key exchange X25519. The SLOTHY-optimized code matches or beats the performance of prior art in all cases, while maintaining compactness and readability.

In this paper, we observe that it is possible to solve partially-synchronous BFT and simultaneously achieves $O(n^2)$ worst-case communication, optimistically linear communication, a two-phase commit regime within a view, and optimistic responsiveness. Prior work falls short in achieving one or more of these properties, e.g., the most closely related work, HotStuff, requires a three-phase view while achieving all other properties. We demonstrate that these properties are achievable through a two-phase HotStuff variant named HotStuff-2. The quest for two-phase HotStuff variants that achieve all the above desirable properties has been long, producing a series of results that are yet sub-optimal and, at the same time, are based on somewhat heavy hammers. HotStuff-2 demonstrates that none of these are necessary: HotStuff-2 is remarkably simple, adding no substantive complexity to the original HotStuff protocol. The main takeaway is that two phases are enough for BFT after all.

Post-quantum signature schemes based on the MPC-in-the-Head (MPCitH) paradigm are recently attracting significant attention as their security solely depends on the one-wayness of the underlying primitive, providing diversity for the hardness assumption in post-quantum cryptography. Recent MPCitH-friendly ciphers have been designed using simple algebraic S-boxes operating on a large field in order to improve the performance of the resulting signature schemes. Due to their simple algebraic structures, their security against algebraic attacks should be comprehensively studied. In this paper, we refine algebraic cryptanalysis of power mapping based S-boxes over binary extension fields, and cryptographic primitives based on such S-boxes. In particular, for the Gröbner basis attack over $\mathbb{F}_2$, we experimentally show that the exact number of Boolean quadratic equations obtained from the underlying S-boxes is critical to correctly estimate the theoretic complexity based on the degree of regularity. Similarly, it turns out that the XL attack might be faster when all possible quadratic equations are found and used from the S-boxes. This refined cryptanalysis leads to more precise algebraic analysis of cryptographic primitives based on algebraic S-boxes. Considering the refined algebraic cryptanalysis, we propose a new one-way function, dubbed $\mathsf{AIM}$, as an MPCitH-friendly symmetric primitive with high resistance to algebraic attacks. The security of $\mathsf{AIM}$ is comprehensively analyzed with respect to algebraic, statistical, quantum, and generic attacks. $\mathsf{AIM}$ is combined with the BN++ proof system, yielding a new signature scheme, dubbed $\mathsf{AIMer}$. Our implementation shows that $\mathsf{AIMer}$ outperforms existing signature schemes based on symmetric primitives in terms of signature size and signing time.

We conduct a security analysis of the e-voting protocol used for the largest political election using e-voting in the world, the 2022 French legislative election for the citizens overseas. Due to a lack of system and threat model specifications, we built and contributed such specifications by studying the French legal framework and by reverse-engineering the code base accessible to the voters. Our analysis reveals that this protocol is affected by two design-level and implementation-level vulnerabilities. We show how those allow a standard voting server attacker and even more so a channel attacker to defeat the election integrity and ballot privacy due to 6 attack variants. We propose and discuss 5 fixes to prevent those attacks. Our specifications, the attacks, and the fixes were acknowledged by the relevant stakeholders during our responsible disclosure. Our attacks are in the process of being prevented with our fixes for future elections. Beyond this specific protocol, we draw general conclusions and lessons from this instructive experience where an e-voting protocol meets the real-world constraints of a large-scale and political election.

Numerous security vulnerability assessment techniques urge precise and fast finite state machines (FSMs) extraction from the design under evaluation. Sequential logic locking, watermark insertion, fault-injection assessment of a System-ona- Chip (SoC) control flow, information leakage assessment, and reverse engineering at gate-level abstraction, to name a few, require precise FSM extraction from the synthesized netlist of the design. Unfortunately, no reliable solutions are currently available for fast and precise extraction of FSMs from the highly unstructured gate-level netlist for effective security evaluation. The major challenge in developing such a solution is precise recognition of FSM state flip-flops in a netlist having a massive collection of flip-flops. In this paper, we propose FSMx-Ultra, a framework for extracting FSMs from extremely unstructured gate-level netlists. FSMx-Ultra utilizes state-of-the-art graph theory concepts and algorithms to distinguish FSM state registers from other registers and then constructs gate-level state transition graphs (STGs) for each identified FSM state register using automatic test pattern generation (ATPG) techniques. The results of our experiments on 14 open-source benchmark designs illustrate that FSMx-Ultra can recover all FSMs quickly and precisely from synthesized gate-level netlists of diverse complexity and size utilizing various state encoding schemes.

Incompressible encryption, recently proposed by Guan, Wichs and Zhandry (EUROCRYPT'22), is a novel encryption paradigm geared towards providing strong long-term security guarantees against adversaries with bounded long-term memory. Given that the adversary forgets just a small fraction of a ciphertext, this notion provides strong security for the message encrypted therein, even if, at some point in the future, the entire secret key is exposed. This comes at the price of having potentially very large ciphertexts. Thus, an important efficiency measure for incompressible encryption is the message-to-ciphertext ratio (also called the rate). Guan et al. provided a low-rate instantiation of this notion from standard assumptions and a rate-1 instantiation from indistinguishability obfuscation (iO). In this work, we propose a simple framework to build rate-1 incompressible encryption from standard assumptions. Our construction can be realized from, e.g. the DDH and additionally the DCR or the LWE assumptions.

The rising issues of harassment, exploitation, corruption, and other forms of abuse have led victims to seek comfort by acting in unison against common perpetrators (e.g., #MeToo movement). One way to curb these issues is to install allegation escrow systems that allow victims to report such incidents. The escrows are responsible for identifying victims of a common perpetrator and taking the necessary action to bring justice to them. However, users hesitate to participate in these systems due to the fear of such sensitive reports being leaked to perpetrators, who may further misuse them. Thus, to increase trust in the system, cryptographic solutions are being designed to realize secure allegation escrow (SAE) systems. In the work of Arun et al. (NDSS'20), which presents the state-of-the-art solution, we identify attacks that can leak sensitive information and compromise victim privacy. We also report issues present in prior works that were left unidentified. To arrest all these breaches, we put forth an SAE system that prevents the identified attacks and retains the salient features from all prior works. The cryptographic technique of secure multi-party computation (MPC) serves as the primary underlying tool in designing our system. At the heart of our system lies a new duplicity check protocol and an improved matching protocol. We also provide additional features such as allegation modification and deletion, which were absent in the state of the art. To demonstrate feasibility, we benchmark the proposed system with state-of-the-art MPC protocols and report the cost of processing an allegation. Different settings that affect system performance are analyzed, and the reported values showcase the practicality of our solution.

FPGA-SoCs are a popular platform for accelerating a wide range of applications due to their performance and flexibility. From a security point of view, these systems have been shown to be vulnerable to various attacks, especially side-channel attacks where an attacker can obtain the secret key of a cryptographic algorithm via laboratory mea- surement equipment or even remotely with sensors implemented inside the FPGA logic itself. Fortunately, a variety of countermeasures on the algorithmic level have been proposed to mitigate this threat. Beyond side- channel attacks, covert channels constitute another threat which enables communication through a hidden channel. In this work, we demonstrate the possibility of implementing a covert channel between the CPU and an FPGA by modulating the usage of the Power Distribution Network. We show that this resource is especially vulnerable since it can be easily controlled and observed, resulting in a stealthy communication and a high transmission data rate. The power usage is modulated using simple and inconspicuous instructions executed on the CPU. Additionally, we use Time-to-Digital Converter sensors to observe these power variations. The sensor circuits are programmed into the FPGA fabric using only standard logic components. Our covert channel achieves a transmission rate of up to 16.7 kbit/s combined with an error rate of 2.3%. Besides a good transmission quality, our covert channel is also stealthy and can be used as an activation function for a hardware trojan.

With the advancement of NIST PQC standardization, three of the four candidates in Round 4 are code-based schemes, namely Classic McEliece, HQC and BIKE. Currently, one of the most important tasks is to further analyze their security levels for the suggested parameter sets. At PKC 2022 Esser and Bellini restated the major information set decoding (ISD) algorithms by using nearest neighbor search and then applied these ISD algorithms to estimate the bit security of Classic McEliece, HQC and BIKE under the suggested parameter sets. However, all major ISD algorithms consume a large amount of memory, which in turn affects their time complexities. In this paper, we reestimate the bit-security levels of the parameter sets suggested by these three schemes in low memory by applying $K$-list sum algorithms to ISD algorithms. Compared with Esser-Bellini's results, our results achieve the best gains for Classic McEliece, HQC, and BIKE, with reductions in bit-security levels of $11.09$, $12.64$, and $12.19$ bits, respectively.

We describe high-throughput threshold protocols with guaranteed output delivery for generating Schnorr-type signatures. The protocols run a single message-independent interactive ephemeral randomness generation procedure (e.g., DKG) followed by a \emph{non-interactive} multi-message signature generation procedure. The protocols offer significant increase in throughput already for as few as ten parties while remaining highly-efficient for many hundreds of parties with thousands of signatures generated per minute (and over 10,000 in normal optimistic case). These protocols extend seamlessly to the dynamic/proactive setting, where each run of the protocol uses a new committee, and they support sub-sampling the committees from among an effectively unbounded number of nodes. The protocols work over a broadcast channel in both synchronous and asynchronous networks. The combination of these features makes our protocols a good match for implementing a signature service over an (asynchronous) public blockchain with many validators, where guaranteed output delivery is an absolute must. In that setting, there is a system-wide public key, where the corresponding secret signature key is distributed among the validators. Clients can submit messages (under suitable controls, e.g. smart contracts), and authorized messages are signed relative to the global public key. Asymptotically, when running with committees of $n$ parties, our protocols can generate $\Omega(n^2)$ signatures per run, while providing resilience against $\Omega(n)$ corrupted nodes, and using broadcast bandwidth of only $O(n^2)$ group elements and scalars. For example, we can sign about $n^2/16$ messages using just under $2n^2$ total bandwidth while supporting resilience against $n/4$ corrupted parties, or sign $n^2/8$ messages using just over $2n^2$ total bandwidth with resilience against $n/5$ corrupted parties. We prove security of our protocols by reduction to the hardness of the discrete logarithm problem in the random-oracle model.

We present a tightly secure identity-based signature (IBS) scheme based on the supersingular isogeny problems. Although Shaw and Dutta proposed an isogeny-based IBS scheme with provable security, the security reduction is non-tight. For an IBS scheme with concrete security, the tightness of its security reduction affects the key size and signature size. Hence, it is reasonable to focus on a tight security proof for an isogeny-based IBS scheme. In this paper, we propose an isogeny-based IBS scheme based on the lossy CSI-FiSh signature scheme and give a tight security reduction for this scheme. While the existing isogeny-based IBS has the square-root advantage loss in the security proof, the security proof for our IBS scheme avoids such advantage loss, due to the properties of lossy CSI-FiSh.

Chen et al. (IEEE Transactions on Cloud Computing 2022) introduced dual-server public key authenticated encryption with keyword search (DS-PAEKS), and proposed a DS-PAEKS scheme under the decisional Diffie-Hellman assumption. In this paper, we propose a generic construction of DS-PAEKS from PAEKS, public key encryption, and signatures. By providing a concrete attack, we show that the DS-PAEKS scheme of Chen et al. is vulnerable. That is, the proposed generic construction yields the first DS-PAEKS schemes. Our attack with a slight modification works against the Chen et al. dual-server public key encryption with keyword search (DS-PEKS) scheme (IEEE Transactions on Information Forensics and Security 2016). Moreover, we demonstrate that the Tso et al. generic construction of DS-PEKS from public key encryption (IEEE Access 2020) is also vulnerable. We also analyze other pairing-free PAEKS schemes (Du et al., Wireless Communications and Mobile Computing 2022 and Lu and Li, IEEE Transactions on Mobile Computing 2022). Though we did not find any attack against these schemes, we show that at least their security proofs are wrong.

Symmetry of Information (SoI) is a fundamental property of Kolmogorov complexity that relates the complexity of a pair of strings and their conditional complexities. Understanding if this property holds in the time-bounded setting is a longstanding open problem. In the nineties, Longpré and Mocas (1993) and Longpré and Watanabe (1995) established that if SoI holds for time-bounded Kolmogorov complexity then cryptographic one-way functions do not exist, and asked if a converse holds. We show that one-way functions exist if and only if (probabilistic) time-bounded SoI fails on average, i.e., if there is a samplable distribution of pairs (x,y) of strings such that SoI for pK$^t$ complexity fails for many of these pairs. Our techniques rely on recent perspectives offered by probabilistic Kolmogorov complexity and meta-complexity, and reveal further equivalences between inverting one-way functions and the validity of key properties of Kolmogorov complexity in the time-bounded setting: (average-case) language compression and (average-case) conditional coding. Motivated by these results, we investigate correspondences of this form for the worst-case hardness of NP (i.e., NP ⊄ BPP) and for the average-case hardness of NP (i.e., DistNP ⊄ HeurBPP), respectively. Our results establish the existence of similar dualities between these computational assumptions and the failure of results from Kolmogorov complexity in the time-bounded setting. In particular, these characterizations offer a novel way to investigate the main hardness conjectures of complexity theory (and the relationships among them) through the lens of Kolmogorov complexity and its properties.

This draft presents work-in-progress concerning hybrid/composite signature schemes. More concretely, we give several tailored combinations of Fiat-Shamir based signature schemes (such as Dilithium) or Falcon with RSA or DSA. We observe that there are a number of signature hybridization goals, few of which are not achieved through parallel signing or concatenation approaches. These include proof composability (that the post-quantum hybrid signature security can easily be linked to the component algorithms), weak separability, strong separability, backwards compatibility, hybrid generality (i.e., hybrid compositions that can be instantiated with different algorithms once proven to be secure), and simultaneous verification. We do not consider backwards compatibility in this work, but aim in our constructions to show the feasibility of achieving all other properties. As a work-in-progress, the constructions are presented without the accompanying formal security analysis, to be included in an update.

This paper presents Poplar, a new system for solving the private heavy-hitters problem. In this problem, there are many clients and a small set of data-collection servers. Each client holds a private bitstring. The servers want to recover the set of all popular strings, without learning anything else about any client’s string. A web-browser vendor, for instance, can use Poplar to figure out which homepages are popular, without learning any user’s homepage. We also consider the simpler private subset-histogram problem, in which the servers want to count how many clients hold strings in a particular set without revealing this set to the clients. Poplar uses two data-collection servers and, in a protocol run, each client send sends only a single message to the servers. Poplar protects client privacy against arbitrary misbehavior by one of the servers and our approach requires no public-key cryptography (except for secure channels), nor general-purpose multiparty computation. Instead, we rely on incremental distributed point functions, a new cryptographic tool that allows a client to succinctly secret-share the labels on the nodes of an exponentially large binary tree, provided that the tree has a single non-zero path. Along the way, we develop new general tools for providing malicious security in applications of distributed point functions. A limitation of Poplar is that it reveals to the servers slightly more information than the set of popular strings itself. We precisely define and quantify this leakage and explain how to ameliorate its effects. In an experimental evaluation with two servers on opposite sides of the U.S., the servers can find the 200 most popular strings among a set of 400,000 client-held 256-bit strings in 54 minutes. Our protocols are highly parallelizable. We estimate that with 20 physical machines per logical server, Poplar could compute heavy hitters over ten million clients in just over one hour of computation.

We describe a fault attack against the deterministic variant of the Falcon signature scheme. It is the first fault attack that exploits specific properties of deterministic Falcon. The attack works under a very liberal and realistic single fault random model. The main idea is to inject a fault into the pseudo-random generator of the pre-image trapdoor sampler, generate different signatures for the same input, find reasonably short lattice vectors this way, and finally use lattice reduction techniques to obtain the private key. We investigate the relationship between fault location, the number of faults, computational effort for a possibly remaining exhaustive search step and success probability.

This work is motivated by the following question: can an untrusted quantum server convince a classical verifier of the answer to an efficient quantum computation using only polylogarithmic communication? We show how to achieve this in the quantum random oracle model (QROM), after a non-succinct instance-independent setup phase. We introduce and formalize the notion of post-quantum interactive oracle arguments for languages in QMA, a generalization of interactive oracle proofs (Ben-Sasson-Chiesa-Spooner). We then show how to compile any non-adaptive public-coin interactive oracle argument (with private setup) into a succinct argument (with setup) in the QROM. To conditionally answer our motivating question via this framework under the post-quantum hardness assumption of LWE, we show that the XZ local Hamiltonian problem with at least inverse-polylogarithmic relative promise gap has an interactive oracle argument with instance-independent setup, which we can then compile. Assuming a variant of the quantum PCP conjecture that we introduce called the weak XZ quantum PCP conjecture, we obtain a succinct argument for QMA (and consequently the verification of quantum computation) in the QROM (with non-succinct instance-independent setup) which makes only black-box use of the underlying cryptographic primitives.

The Bitcoin architecture heavily relies on the ECDSA signature scheme which is broken by quantum adversaries as the secret key can be computed from the public key in quantum polynomial time. To mitigate this attack, bitcoins can be paid to the hash of a public key (P2PKH). However, the first payment reveals the public key so all bitcoins attached to it must be spent at the same time (i.e. the remaining amount must be transferred to a new wallet). Some problems remain with this approach: the owners are vulnerable against rushing adversaries between the time the signature is made public and the time it is committed to the blockchain. Additionally, there is no equivalent mechanism for threshold signatures. Finally, no formal analysis of P2PKH has been done. In this paper, we formalize the security notion of a digital signature with a hidden public key and we propose and prove the security of a generic transformation that converts a classical signature to a post-quantum one that can be used only once. We compare it with P2PKH. Namely, our proposal relies on pre-image resistance instead of collision resistance as for P2PKH, so allows for shorter hashes. Additionally, we propose the notion of a delay signature to address the problem of the rushing adversary when used with a public ledger and discuss the advantages and disadvantages of our approach. We further extend our results to threshold signatures.

As for any cryptographic algorithm, the deployment of post-quantum CCA-secure public-key encryption schemes may come with the need to be protected against side-channel attacks. For existing post-quantum schemes that have not been developed with leakage in mind, recent results showed that the cost of these protections can make their implementations more expensive by orders of magnitude. In this paper, we describe a new design, coined \(\texttt{POLKA}\), that is specifically tailored for this purpose. It leverages various ingredients in order to enable efficient side-channel protected implementations such as: (i) the rigidity property (which intuitively means that de-randomized encryption and decryption are injective functions) to avoid the very leaky re-encryption step of the Fujisaki-Okamoto transform, (ii) the randomization of the decryption thanks to the incorporation of a dummy ciphertext, removing the adversary’s control of its intermediate computations and making these computations ephemeral, (iii) key-homomorphic computations that can be masked against side-channel attacks with overheads that scale linearly in the number of shares, (iv) hard physical learning problem to argue about the security of some critical unmasked operations. Furthermore, we use an explicit rejection mechanism (returning an error symbol for invalid ciphertexts) to avoid the additional leakage caused by implicit rejection. As a result, all the operations of \(\texttt{POLKA}\) can be protected against leakage in a much cheaper way than state-of-the-art designs, opening the way towards schemes that are both quantum-safe and leakage-resistant.

Asynchronous Remote Key Generation (ARKG), introduced by Frymann et al. at CCS 2020, allows for the generation of unlinkable public keys by third parties, for which corresponding private keys may be later learned only by the key pair's legitimate owner. These key pairs can then be used in common public-key cryptosystems, including signatures, PKE, KEMs, and schemes supporting delegation, such as proxy signatures. The only known instance of ARKG generates discrete-log-based keys. In this paper, we introduce new ARKG constructions for lattice-based cryptosystems. The key pairs generated using our ARKG scheme can be applied to lattice-based signatures and KEMs, which have recently been selected for standardisation in the NIST PQ process, or as alternative candidates. In particular, we address challenges associated with the noisiness of lattice hardness assumptions, which requires a new generalised definition of ARKG correctness, whilst preserving the security and privacy properties of the former instantiation. Our ARKG construction uses key encapsulation techniques by Brendel et al. (SAC 2020) coined Split KEMs. As an additional contribution, we also show that Kyber (Bos et al., EuroS&P 2018) can be used to construct a Split KEM. The security of our protocol is based on standard LWE assumptions. We also discuss its use with selected candidates from the NIST process and provide an implementation and benchmarks.

In STOC 1989, Rabin and Ben-Or (RB) established an important milestone in the fields of cryptography and distributed computing by showing that every functionality can be computed with statistical (information-theoretic) security in the presence of an active (aka Byzantine) rushing adversary that controls up to half of the parties. We study the round complexity of general secure multiparty computation and several related tasks in the RB model. Our main result shows that every functionality can be realized in only four rounds of interaction which is known to be optimal. This completely settles the round complexity of statistical actively-secure optimally-resilient MPC, resolving a long line of research. Along the way, we construct the first round-optimal statistically-secure verifiable secret sharing protocol (Chor, Goldwasser, Micali, and Awerbuch; STOC 1985), show that every single-input functionality (e.g., multi-verifier zero-knowledge) can be realized in 3 rounds, and prove that the latter bound is optimal. The complexity of all our protocols is exponential in the number of parties, and the question of deriving polynomially-efficient protocols is left for future research. Our main technical contribution is a construction of a new type of statistically-secure signature scheme whose existence was open even for smaller resiliency thresholds. We also describe a new statistical compiler that lifts up passively-secure protocols to actively-secure protocols in a round-efficient way via the aid of protocols for single-input functionalities. This compiler can be viewed as a statistical variant of the GMW compiler (Goldreich, Micali, Wigderson; STOC, 1987) that originally employed zero-knowledge proofs and public-key encryption.

Cryptanalysis of modern symmetric ciphers may be done by using linear equation systems with multiple right hand sides, which describe the encryption process. The tool was introduced by Raddum and Semaev where several solving methods were developed. In this work, the probabilities are ascribed to the right hand sides and a statistical attack is then applied. The new approach is a multivariate generalisation of the correlation attack by Siegenthaler. A fast version of the attack is provided too. It may be viewed as an extension of the fast correlation attack by Meier and Staffelbach, based on exploiting so called parity-checks for linear recurrences. Parity-checks are a particular case of the relations that we introduce in the present work. The notion of a relation is irrelevant to linear recurrences. We show how to apply the method to some LFSR-based stream ciphers including those from the Grain family. The new method generally requires a lower number of the keystream bits to recover the initial states than other techniques reported in the literature.

A treasury system is a community controlled and decentralized collaborative decision-making mechanism for sustainable funding of the blockchain development and maintenance. During each treasury period, project proposals are submitted, discussed, and voted for; top-ranked projects are funded from the treasury. The Dash governance system is a real-world example of such kind of systems. In this work, we, for the first time, provide a rigorous study of the treasury system. We modeled, designed, and implemented a provably secure treasury system that is compatible with most existing blockchain infrastructures, such as Bitcoin, Ethereum, etc. More specifically, the proposed treasury system supports liquid democracy/delegative voting for better collaborative intelligence. Namely, the stake holders can either vote directly on the proposed projects or delegate their votes to experts. Its core component is a distributed universally composable secure end-to-end verifiable voting protocol. The integrity of the treasury voting decisions is guaranteed even when all the voting committee members are corrupted. To further improve efficiency, we proposed the world’s first honest verifier zero-knowledge proof for unit vector encryption with logarithmic size communication. This partial result may be of independent interest to other cryptographic protocols. A pilot system is implemented in Scala over the Scorex 2.0 framework, and its benchmark results indicate that the proposed system can support tens of thousands of treasury participants with high efficiency.

Self-masking allows the masking of success criteria, part of a problem instance (such as the sum in a subset-sum instance) that restricts the number of solutions. Self-masking is used to prevent the leakage of helpful information to attackers; while keeping the original solution valid and, at the same time, not increasing the number of unplanned solutions. Self-masking can be achieved by xoring the sums of two (or more) independent subset sum instances \cite{DD20, CDM22}, and by doing so, eliminate all known attacks that use the value of the sum of the subset to find the subset fast, namely, in a polynomial time; much faster than the naive exponential exhaustive search. We demonstrate that the concept of self-masking can be applied to a single instance of the subset sum and a single instance of the permuted secret-sharing polynomials. We further introduce the benefit of permuting the bits of the success criteria, avoiding leakage of information on the value of the $i$'th bit of the success criteria, in the case of a single instance, or the parity of the $i$'th bit of the success criteria in the case of several instances. In the case of several instances, we permute the success criteria bits of each instance prior to xoring them with each other. One basic permutation and its nesting versions (e.g., $\pi^i$) are used, keeping the solution space small and at the same time, attempting to create an ``all or nothing'' effect, where the result of a wrong $\pi$ trials does not imply much.

To overcome the limitations of traditional secure multi-party computation (MPC) protocols that consider a static set of participants, in a recent work, Choudhuri et al. [CRYPTO 2021] introduced a new model called Fluid MPC, which supports {\em dynamic} participants. Protocols in this model allow parties to join and leave the computation as they wish. Unfortunately, known fluid MPC protocols (even with strong honest-majority), either only achieve security with abort, or require strong computational and trusted setup assumptions. In this work, we also consider the "hardest" setting --- called the maximally-fluid model --- where each party can leave the computation after participating in a single round. We study the problem of designing information-theoretic maximally-fluid MPC protocols that achieve security with guaranteed output delivery (without relying on trusted setup), and obtain the following main results: (1) We design a perfectly secure maximally-fluid MPC protocol, that achieves guaranteed output delivery against unbounded adversaries who are allowed to corrupt less than a third of the parties in every round/committee. (2) We show that the corruption threshold in the above protocol is optimal. In particular, we prove that in fluid MPC, when the adversary can corrupt a third (or more) of the parties in any round, it is impossible to achieve information-theoretic security and guaranteed output delivery simultaneously --- even assuming a common random string (CRS) setup. Additionally, for the case where the adversary is allowed to corrupt up to half of the parties in each committee, we present a new computationally secure maximally-fluid MPC protocol with guaranteed output delivery. Unlike prior works that require correlated setup and NIZKs, our construction only uses a common random string setup and is based on linearly-homomorphic equivocal commitments.

It is known that one can generically construct a post-quantum anonymous credential scheme, supporting the showing of arbitrary predicates on its attributes using general-purpose zero-knowledge proofs secure against quantum adversaries [Fischlin, CRYPTO 2006]. Traditionally, such a generic instantiation is thought to come with impractical sizes and performance. We show that with careful choices and optimizations, such a scheme can perform surprisingly well. In fact, it performs competitively against state-of-the-art post-quantum blind signatures, for the simpler problem of post-quantum unlinkable tokens, required for a post-quantum version of Privacy Pass. To wit, a post-quantum Privacy Pass constructed in this way using zkDilithium, our proposal for a STARK-friendly variation on Dilithium2, allows for a trade-off between token size (85–175KB) and generation time (0.3–5s) with a proof security level of 115 bits. Verification of these tokens can be done in 20–30ms. We argue that these tokens are reasonably practical, adding less than a second upload time over traditional tokens, supported by a measurement study. Finally, we point out a clear advantage of our approach: the flexibility afforded by the general purpose zero-knowledge proofs. We demonstrate this by showing how we can construct a rate-limited variant of Privacy Pass that doesn't not rely on non-collusion for privacy.

Lattice-based homomorphic encryption (HE) schemes are based on the noisy encryption technique, where plaintexts are masked with some random noise for security. Recent advanced HE schemes rely on a decomposition technique to manage the growth of noise, which involves a conversion of a ciphertext entry into a short vector followed by multiplication with an evaluation key. Prior to this work, the decomposition procedure turns out to be the most time-consuming part, as it requires discrete Fourier transforms (DFTs) over the base ring for efficient polynomial arithmetic. In this paper, an expensive decomposition operation over a large modulus is replaced with relatively cheap operations over a ring of integers with a small bound. Notably, the cost of DFTs is reduced from quadratic to linear with the level of a ciphertext without any extra noise growth. We demonstrate the implication of our approach by applying it to the key-switching procedure. Our experiments show that the new key-switching method achieves a speedup of 1.2--2.3 or 2.1--3.3 times over the previous method, when the dimension of a base ring is $2^{15}$ or $2^{16}$, respectively.

We propose and implement a multiparty homomorphic encryption (MHE) scheme with a $t$-out-of-$N$-threshold access-structure that is efficient and does not require a trusted dealer in the common random-string model. We construct this scheme from the ring-learning-with-error (RLWE) assumptions, and as an extension of the MHE scheme of Mouchet et al. (PETS 21). By means of a specially adapted share re-sharing procedure, this extension can be used to relax the $N$-out-of-$N$-threshold access structure of the original scheme into a $t$-out-of-$N$-threshold one. This procedure introduces only a single round of communication during the setup phase, after which any set of at least $t$ parties can compute a $t$-out-of-$t$ additive sharing of the secret key with no interaction; this new sharing can be used directly in the scheme of Mouchet et al. We show that, by performing Shamir re-sharing over the MHE ciphertext-space ring with a carefully chosen exceptional set, this reconstruction procedure can be made secure and has negligible overhead. Moreover, it only requires the parties to store a constant-size state after its setup phase. Hence, in addition to fault tolerance, lowering the corruption threshold also yields considerable efficiency benefits, by enabling the distribution of batched secret-key operations among the online parties. We implemented and open-sourced our scheme in the Lattigo library.

Forward security is a fundamental requirement in searchable encryption, where a newly generated ciphertext is not allowed to be searched by previously generated trapdoors. However, forward security is somewhat overlooked in the public key encryption with keyword search (PEKS) context and there are few proposals, whereas forward security has been stated as a default security notion in the (dynamic) symmetric searchable encryption (SSE) context. In the PEKS context, forward secure PEKS (FS-PEKS) is essentially the same as public key encryption with temporary keyword search (PETKS) proposed by Abdalla et al. (JoC 2016) which can be constructed generically from hierarchical identity-based encryption (HIBE) with level-1 anonymity. Alternatively, Zeng et al. (IEEE Transactions on Cloud Computing 2022) also proposed a generic construction of FS-PEKS from attribute-based searchable encryption supporting OR gates. In the public key authenticated encryption with keyword search (PAEKS) context, a concrete forward secure PAEKS (FS-PAEKS) construction has been proposed by Jiang et al. (The Computer Journal 2022), and no generic construction has been proposed to date. In this paper, we propose a generic construction of FS-PAEKS from PAEKS. In addition to PAEKS, we employ 0/1 encodings proposed by Lin et al. (ACNS 2005). We also show that the Jiang et al. FS-PAEKS scheme does not provide forward security, and thus our generic construction yields the first secure FS-PAEKS schemes. Our generic construction is quite simple, and it can also be applied to construct FS-PEKS. Our generic construction yields a comparably efficient FS-PEKS scheme compared to the previous scheme. Moreover, it eliminates the hierarchical structure or attribute-based feature of the previous generic constructions which is meaningful from a feasibility perspective.

Digital signatures are one of the most basic cryptographic building blocks which are utilized to provide attractive security features like authenticity, unforgeability, and undeniability. The security of existing state of the art digital signatures is based on hardness of number theoretic hardness assumptions like discrete logarithm and integer factorization. However, these hard problems are insecure and face a threat in the quantum world. In particular, quantum algorithms like Shor’s algorithm can be used to solve the above mentioned hardness problem in polynomial time. As an alternative, a new direction of research called post-quantum cryptography (PQC) is supposed to provide a new generation of quantum-resistant digital signatures. Hash based signature is one such candidate to provide post quantum secure digital signatures. Hash based signature schemes are a type of digital signature scheme that use hash functions as their central building block. They are efficient, flexible, and can be used in a variety of applications. In this document, we provide an overview of the hash based signatures. Our presentation of the topic covers a wide range of aspects that are not only comprehensible for readers without expertise in the subject matter, but also serve as a valuable resource for experts seeking reference material.

Side-channel attacks, which aim to leak side information on secret system components, are ubiquitous. Even simple attacks, such as measuring time elapsed or radiation emitted during encryption and decryption procedures, completely break textbook versions of many cryptographic schemes. This has prompted the study of leakage-resilient cryptography, which remains secure in the presence of side-channel attacks. Classical leakage-resilient cryptography must necessarily impose restrictions on the type of leakage one aims to protect against. As a notable example, the most well-studied leakage model is that of bounded leakage, where it is assumed that an adversary learns at most $\ell$ bits of leakage on secret components, for some leakage bound $\ell$. Although this leakage bound is necessary, it is unclear if such a bound is realistic in practice since many practical side-channel attacks cannot be captured by bounded leakage. In this work, we investigate the possibility of designing cryptographic schemes that provide guarantees against arbitrary side-channel attacks: - Using techniques from uncloneable quantum cryptography, we design several basic leakage-resilient primitives, such as secret sharing, (weak) pseudorandom functions, digital signatures, and public- and private-key encryption, which remain secure under (polynomially) unbounded classical leakage. In particular, this leakage can be much longer than the (quantum) secret being leaked upon. In our view, leakage is the result of observations of quantities such as power consumption and hence is most naturally viewed as classical information. - In the even stronger adversarial setting where the adversary is allowed to obtain unbounded quantum leakage (and thus leakage-resilience is impossible), we design schemes for many cryptographic tasks which support leakage-detection. This means that we can efficiently check whether the security of such a scheme has been compromised by a side-channel attack. These schemes are based on techniques from cryptography with certified deletion. - We also initiate a study of classical cryptographic schemes with (bounded) post-quantum leakage-resilience. These schemes resist side-channel attacks performed by adversaries with quantum capabilities which may even share arbitrary entangled quantum states. That is, even if such adversaries are non-communicating, they can still have "spooky" communication via entangled states.

Function Secret Sharing (FSS; Eurocrypt 2015) allows a dealer to share a function f with two or more evaluators. Given secret shares of a function f, the evaluators can locally compute secret shares of f(x) on an input x, without learning information about f. In this paper, we initiate the study of access control for FSS. Given the shares of f, the evaluators can ensure that the dealer is authorized to share the provided function. For a function family F and an access control list defined over the family, the evaluators receiving the shares of f ∈ F can efficiently check that the dealer knows the access key for f. This model enables new applications of FSS, such as: – anonymous authentication in a multi-party setting, – access control in private databases, and – authentication and spam prevention in anonymous communication systems. Our definitions and constructions abstract and improve the concrete efficiency of several re- cent systems that implement ad-hoc mechanisms for access control over FSS. The main building block behind our efficiency improvement is a discrete-logarithm zero-knowledge proof-of-knowledge over secret-shared elements, which may be of independent interest. We evaluate our constructions and show a 50–70× reduction in computational overhead com- pared to existing access control techniques used in anonymous communication. In other applications, such as private databases, the processing cost of introducing access control is only 1.5–3× when amortized over databases with 500,000 or more items.

It is known that the agreement property of the Byzantine consensus problem among $n$ processes can be violated in a non-synchronous system if the number of faulty processes exceeds $t_0 = n / 3 - 1$. In this paper, we investigate the accountable Byzantine consensus problem in non-synchronous systems: the problem of solving Byzantine consensus whenever possible (e.g., when the number of faulty processes does not exceed $t_0$) and allowing correct processes to obtain proof of culpability of (at least) $t_0 + 1$ faulty processes whenever correct processes disagree. We present four complementary contributions: 1) We introduce $ABC$: a simple yet efficient transformation of any Byzantine consensus protocol to an accountable one. $ABC$ introduces an overhead of (1) only two all-to-all communication rounds and $O(n^2)$ additional bits in executions with up to $t_0$ faults (i.e., in the common case). 2) We define the accountability complexity, a complexity metric representing the number of accountability-specific messages that correct processes must send. Furthermore, we prove a tight lower bound. In particular, we show that any accountable Byzantine consensus algorithm incurs cubic accountability complexity. Moreover, we illustrate that the bound is tight by applying the $ABC$ transformation to any Byzantine consensus protocol. 3) We demonstrate that, when applied to an optimal Byzantine consensus protocol, $ABC$ constructs an accountable Byzantine consensus protocol that is (1) optimal in solving consensus whenever consensus is solvable with respect to the communication complexity, and (2) optimal in obtaining accountability whenever disagreement occurs with respect to the accountability complexity. 4) We generalize $ABC$ to other distributed computing problems besides the classic consensus problem. We characterize a class of agreement tasks, including reliable and consistent broadcast, that $ABC$ renders accountable.

Consider a state-level adversary who observes and stores large amounts of encrypted data from all users on the Internet, but does not have the capacity to store it all. Later, it may target certain "persons of interest" in order to obtain their decryption keys. We would like to guarantee that, if the adversary's storage capacity is only (say) $1\%$ of the total encrypted data size, then even if it can later obtain the decryption keys of arbitrary users, it can only learn something about the contents of (roughly) $1\%$ of the ciphertexts, while the rest will maintain full security. This can be seen as an extension of incompressible cryptography (Dziembowski CRYPTO '06, Guan, Wichs and Zhandry EUROCRYPT '22) to the multi-user setting. We provide solutions in both the symmetric key and public key setting with various trade-offs in terms of computational assumptions and efficiency. As the core technical tool, we study an information-theoretic problem which we refer to as "somewhere randomness extraction". Suppose $X_1, \ldots, X_t$ are correlated random variables whose total joint min-entropy rate is $\alpha$, but we know nothing else about their individual entropies. We choose $t$ random and independent seeds $S_1, \ldots, S_t$ and attempt to individually extract some small amount of randomness $Y_i = \mathsf{Ext}(X_i;S_i)$ from each $X_i$. We'd like to say that roughly an $\alpha$-fraction of the extracted outputs $Y_i$ should be indistinguishable from uniform even given all the remaining extracted outputs and all the seeds. We show that this indeed holds for specific extractors based on Hadamard and Reed-Muller codes.

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.

This work presents a novel machine-checked tight security proof for $\mathrm{XMSS}$ — a stateful hash-based signature scheme that is (1) standardized in RFC 8391 and NIST SP 800-208, and (2) employed as a primary building block of $\mathrm{SPHINCS}^{+}$, one of the signature schemes recently selected for standardization as a result of NIST’s post-quantum competition. In 2020, Kudinov, Kiktenko, and Fedoro pointed out a flaw affecting the tight security proofs of $\mathrm{SPHINCS}^{+}$ and $\mathrm{XMSS}$. For the case of $\mathrm{SPHINCS}^{+}$, this flaw was fixed in a subsequent tight security proof by Hülsing and Kudinov. Unfortunately, employing the fix from this proof to construct an analogous tight security proof for XMSS would merely demonstrate security with respect to an insufficient notion. At the cost of modeling the message-hashing function as a random oracle, we complete the tight security proof for $\mathrm{XMSS}$ and formally verify it using the EasyCrypt proof assistant. As part of this endeavor, we formally verify the crucial step common to (the security proofs of) $\mathrm{SPHINCS}^{+}$ and $\mathrm{XMSS}$ that was found to be flawed before, thereby confirming that the core of the aforementioned security proof by Hülsing and Kudinov is correct. As this is the first work to formally verify proofs for hash-based signature schemes in EasyCrypt, we develop several novel libraries for the fundamental cryptographic concepts underlying such schemes — e.g., hash functions and digital signature schemes — establishing a common starting point for future formal verification efforts. These libraries will be particularly helpful in formally verifying proofs of other hash-based signature schemes such as $\mathrm{LMS}$ or $\mathrm{SPHINCS}^{+}$.

We study the rational behaviors of participants in $DAG$-Based Distributed Ledgers. We analyze generic algorithms that encapsulate the main actions of participants in a $DAG$-based distributed ledger: voting for a block, and checking its validity. Knowing that those actions have costs, and validating a block gives rewards to users who participated in the validation procedure, we study using game theory how strategic participants behave while trying to maximize their gains. We consider scenarios with different type of participants and investigate if there exist equilibria where the properties of the protocols are guaranteed. The analysis is focused on the study of equilibria with trembling participants (i.e. rational participants that can do unintended actions with a low probability). We found that in presence of trembling participants, there exist equilibria where protocols properties may be violated.

The implementation of cryptographic algorithms must be protected against physical attacks. Side-channel and fault injection analyses are two prominent such implem\-entation-level attacks. Protections against either do exist; they are characterized by security orders: the higher the order, the more difficult the attack. In this paper, we leverage fast discrete Fourier transform to reduce the complexity of high-order masking, and extend it to allow for fault detection and/or correction. The security paradigm is that of code-based masking. Coding theory is amenable both to mix the information and masking material at a prescribed order, and to detect and/or correct errors purposely injected by an attacker. For the first time, we show that quasi-linear masking (pioneered by Goudarzi, Joux and Rivain at ASIACRYPT 2018) can be achieved alongside with cost amortisation. This technique consists in masking several symbols/bytes with the same masking material, therefore improving the efficiency of the masking. Similarly, it allows to optimize the detection capability of codes as linear codes are all the more efficient as the information to protect is longer. Namely, we prove mathematically that our scheme features side-channel security order of $d+1-t$, detects $d$ faults and corrects $\lfloor(d-1)/2\rfloor$ faults, where $2d+1$ is the encoding length and $t$ is the information size ($t\geq1$). Applied to AES, one can get side-channel protection of order $d=7$ when masking one column/line ($t=4$ bytes) at once. In addition to the theory, that makes use of the Frobenius Additive Fast Fourier Transform, we show performance results, both in software and hardware.

We present a novel code-based digital signature scheme, called enhanced pqsigRM for post-quantum cryptography (PQC). This scheme is based on a modified Reed--Muller (RM) code, which reduces the signature size and verification time compared with existing code-based signature schemes. In fact, it strengthens pqsigRM submitted to NIST for post-quantum cryptography standardization. The proposed scheme has the advantage of the short signature size and fast verification and uses public codes that are more difficult to distinguish from random codes. We use $(U,U+V)$-codes with the high-dimensional hull to overcome the disadvantages of code-based schemes. The proposed decoder samples from coset elements with small Hamming weight for any given syndrome and efficiently finds such an element. Using a modified RM code, the proposed signature scheme resists various known attacks on RM-code-based cryptography. It has advantages on signature size, verification time, and proven security. For 128 bits of classical security, the signature size of the proposed signature scheme is 512 bytes, which corresponds to 1/4.7 of that of CRYSTALS-DILITHIUM, and the number of median verification cycles is 1,717,336, which corresponds to the five times of that of CRYSTALS-DILITHIUM.

Time-based cryptographic primitives such as Time-Lock Puzzles (TLPs) and Verifiable Delay Functions (VDFs) have recently found many applications to the efficient design of secure protocols such as randomness beacons or multiparty computation with partial fairness. However, current TLP and VDF candidate constructions rely on the average hardness of sequential computational problems. Unfortunately, obtaining concrete parameters for these is notoriously hard, as there cannot be a large gap between the honest parties’ and the adversary’s runtime when solving the same problem. Moreover, even a constant improvement in algorithms for solving these problems can render parameter choices, and thus deployed systems, insecure - unless very conservative and therefore highly inefficient parameters are chosen. In this work, we investigate how to construct time-based cryptographic primitives from communication delay, which has a known lower bound given the physical distance between devices: the speed of light. In order to obtain high delays, we explore the sequential communication delay that arises when sending a message through a constellation of satellites. This has the advantage that distances between protocol participants are guaranteed as positions of satellites are observable, so delay lower bounds can be easily computed. At the same time, building cryptographic primitives for this setting is challenging due to the constrained resources of satellites and possible corruptions of parties within the constellation. We address these challenges by constructing efficient proofs of sequential communication delay to convince a verifier that a message has accrued delay by traversing a path among satellites. As part of this construction, we propose the first ordered multisignature scheme with security under a version of the the discrete logarithm assumption, which enjoys constant-size signatures and, modulo preprocessing, computational complexity independent of the number of signers. Building on our proofs of sequential communication delay, we show new constructions of Publicly Verifiable TLPs and VDFs whose delay guarantees are rooted on physical communication delay lower bounds. Our protocols as well as the ordered multisignature are analysed in the Universal Composability framework using novel models for sequential communication delays and (ordered) multisignatures. A direct application of our results is a randomness beacon that only accesses expensive communication resources in case of cheating.

Laconic cryptography is an emerging paradigm that enables cryptographic primitives with sublinear communication complexity in just two messages. In particular, a two-message protocol between Alice and Bob is called laconic if its communication and computation complexity are essentially independent of the size of Alice's input. This can be thought of as a dual notion of fully-homomorphic encryption, as it enables "Bob-optimized" protocols. This paradigm has led to tremendous progress in recent years. However, all existing constructions of laconic primitives are considered only of theoretical interest: They all rely on non-black-box cryptographic techniques, which are highly impractical. This work shows that non-black-box techniques are not necessary for basic laconic cryptography primitives. We propose a completely algebraic construction of laconic encryption, a notion that we introduce in this work, which serves as the cornerstone of our framework. We prove that the scheme is secure under the standard Learning With Errors assumption (with polynomial modulus-to-noise ratio). We provide proof-of-concept implementations for the first time for laconic primitives, demonstrating the construction is indeed practical: For a database size of $2^{50}$, encryption and decryption are in the order of single digit milliseconds. Laconic encryption can be used as a black box to construct other laconic primitives. Specifically, we show how to construct: - Laconic oblivious transfer - Registration-based encryption scheme - Laconic private-set intersection protocol All of the above have essentially optimal parameters and similar practical efficiency. Furthermore, our laconic encryption can be preprocessed such that the online encryption step is entirely combinatorial and therefore much more efficient. Using similar techniques, we also obtain identity-based encryption with an unbounded identity space and tight security proof (in the standard model).

This work discusses real world deniability in messaging. We highlight how the different models for cryptographic deniability do not ensure practical deniability. To overcome this situation, we propose a model for real world deniability that takes into account the entire messaging system. We then discuss how deniability is (not) used in practice and the challenges arising from the design of a deniable system. We propose a simple, yet powerful solution for deniability: applications should enable direct modification of local messages; we discuss the impacts of this strong deniability property.

In recent history of fully homomorphic encryption, bootstrapping has been actively studied throughout many HE schemes. As bootstrapping is an essential process to transform somewhat homomorphic encryption schemes into fully homomorphic, enhancing its performance is one of the key factors of improving the utility of homomorphic encryption. In this paper, we propose an extended bootstrapping for TFHE, which we name it by EBS. One of the main drawback of TFHE bootstrapping was that the precision of bootstrapping is mainly decided by the polynomial dimension $N$. Thus if one wants to bootstrap with high precision, one must enlarge $N$, or take alternative method. Our EBS enables to use small $N$ for parameter selection, but to bootstrap in higher dimension to keep high precision. Moreover, it can be easily parallelized for faster computation. Also, the EBS can be easily adapted to other known variants of TFHE bootstrappings based on the original bootstrapping algorithm. We implement our EBS along with the full domain bootstrapping methods known ($\mathsf{FDFB}$, $\mathsf{TOTA}$, $\mathsf{Comp}$), and show how much our EBS can improve the precision for those bootstrapping methods. We provide experimental results and thorough analysis with our EBS, and show that EBS is capable of bootstrapping with high precision even with small $N$, thus small key size, and small complexity than selecting large $N$ by birth.

As a multi-receiver variant of public key authenticated encryption with keyword search (PAEKS), broadcast authenticated encryption with keyword search (BAEKS) was proposed by Liu et al. (ACISP 2021). BAEKS focuses on receiver anonymity, where no information about the receiver is leaked from ciphertexts, which is reminiscent of the anonymous broadcast encryption. Here, there are rooms for improving their security definitions, e.g., two challenge sets of receivers are selected before the setup phase, and an adversary is not allowed to corrupt any receiver. In this paper, we propose a generic construction of BAEKS derived from PAEKS that provides ciphertext anonymity and consistency in a multi-receiver setting. The proposed construction is an extension of the generic construction proposed by Libert et al. (PKC 2012) for the anonymous broadcast encryption and provides adaptive corruptions. We also demonstrate that the Qin et al. PAEKS scheme (ProvSec 2021) provides ciphertext anonymity and consistency in a multi-receiver setting.

Inventory matching is a standard mechanism for trading financial stocks by which buyers and sellers can be paired. In the financial world, banks often undertake the task of finding such matches between their clients. The related stocks can be traded without adversely impacting the market price for either client. If matches between clients are found, the bank can offer the trade at advantageous rates. If no match is found, the parties have to buy or sell the stock in the public market, which introduces additional costs. A problem with the process as it is presently conducted is that the involved parties must share their order to buy or sell a particular stock, along with the intended quantity (number of shares), to the bank. Clients worry that if this information were to “leak” somehow, then other market participants would become aware of their intentions and thus cause the price to move adversely against them before their transaction finalizes. We provide a solution, Prime Match, that enables clients to match their orders efficiently with reduced market impact while maintaining privacy. In the case where there are no matches, no information is revealed. Our main cryptographic innovation is a two-round secure linear comparison protocol for computing the minimum between two quantities without preprocessing and with malicious security, which can be of independent interest. We report benchmarks of our Prime Match system, which runs in production and is adopted by a large bank in the US -- J.P. Morgan. The system is designed utilizing a star topology network, which provides clients with a centralized node (the bank) as an alternative to the idealized assumption of point-to-point connections, which would be impractical and undesired for the clients to implement in reality. Prime Match is the first secure multiparty computation solution running live in the traditional financial world.

The US National Institute of Standards and Technology initiated a standardization process for post-quantum cryptography in 2017, with the aim of selecting key encapsulation mechanisms and signature schemes that can withstand the threat from emerging quantum computers. In 2022, Falcon was selected as one of the standard signature schemes, eventually attracting effort to optimize the implementation of Falcon on various hardware architectures for practical applications. Recently, Mitaka was proposed as an alternative to Falcon, allowing parallel execution of most of its operations. These recent advancements motivate us to develop high throughput implementations of Falcon and Mitaka signature schemes on Graphics Processing Units (GPUs), a massively parallel architecture widely available on cloud service platforms. In this paper, we propose the first parallel implementation of Falcon on various GPUs. An iterative version of the sampling process in Falcon, which is also the most time-consuming Falcon operation, was developed. This allows us to implement Falcon signature generation without relying on expensive recursive function calls on GPUs. In addition, we propose a parallel random samples generation approach to accelerate the performance of Mitaka on GPUs. We evaluate our implementation techniques on state-of-the-art GPU architectures (RTX 3080, A100, T4 and V100). Experimental results show that our Falcon-512 implementation achieves 58, 595 signatures/second and 2, 721, 562 verifications/second on an A100 GPU, which is 20.03× and 29.51× faster than the highly optimized AVX2 implementation on CPU. Our Mitaka implementation achieves 161, 985 signatures/second and 1, 421, 046 verifications/second on the same GPU. Due to the adoption of a parallelizable sampling process, Mitaka signature generation enjoys ≈ 2 – 20× higher throughput than Falcon on various GPUs. The high throughput signature generation and verification achieved by this work can be very useful in various emerging applications, including the Internet of Things.

We introduce BICYCL an Open Source C++ library that implements arithmetic in the ideal class groups of imaginary quadratic fields, together with a set of cryptographic primitives based on class groups. It is available at https://gite.lirmm.fr/crypto/bicycl under GNU General Public License version 3 or any later version. BICYCL provides significant speed-ups on the implementation of the arithmetic of class groups. Concerning cryptographic applications, BICYCL is orders of magnitude faster than any previous pilot implementation of the CL linearly encryption scheme, making it faster than Paillier’s encryption scheme at any security level. Linearly homomorphic encryption is the core of many multi-party computation protocols, sometimes involving a huge number of encryptions and homomorphic evaluations: class group-based protocols become the best solution in terms of bandwidth and computational efficiency to rely upon.

In SAC’14, Biham and Carmeli presented a novel attack on DES, involving a variation of Partitioning Cryptanalysis. This was further extended in ToSC’18 by Biham and Perle into the Conditional Linear Cryptanalysis in the context of Feistel ciphers. In this work, we formalize this cryptanalytic technique for block ciphers in general and derive several properties. This conditional approximation is then used to approximate the inv : GF(2^8) → GF(2^8) : x → x^254 function which forms the only source of non-linearity in the AES. By extending the approximation to encompass the full AES round function, a linear distinguisher for four-round AES in the known-plaintext model is constructed; the existence of which is often understood to be impossible. We furthermore demonstrate a key-recovery attack capable of extracting 32 bits of information in 4-round AES using 2^125.62 data and time. In addition to suggesting a new approach to advancing the cryptanalysis of the AES, this result moreover demonstrates a caveat in the standard interpretation of the Wide Trail Strategy — the design framework underlying many SPN-based ciphers published in recent years.

Biometric databases collect people’s information and allow users to perform proximity searches (finding all records within a bounded distance of the query point) with few cryptographic protections. This work studies proximity searchable encryption applied to the iris biometric. Prior work proposed inner product functional encryption as a technique to build proximity biometric databases (Kim et al., SCN 2018). This is because binary Hamming distance is computable using an inner product. This work identifies and closes two gaps in using inner product encryption for biometric search: 1. Biometrics naturally use long vectors often with thousands of bits. Many inner product encryption schemes generate a random matrix whose dimension scales with vector size and have to invert this matrix. As a result, setup is not feasible on commodity hardware unless we reduce the dimension of the vectors. We explore state-of-the-art techniques to reduce the dimension of the iris biometric and show that all known techniques harm the accuracy of the resulting system. That is, for small vector sizes multiple unrelated biometrics are returned in the search. For length 64 vectors, at a 90% probability of the searched biometric being returned, 10% of stored records are erroneously returned on average. Rather than changing the feature extractor, we introduce a new cryptographic technique that allows one to generate several smaller matrices. For vectors of length 1024 this reduces the time to run setup from 23 days to 4 minutes. At this vector length, for the same 90% probability of the searched biometric being returned, .02% of stored records are erroneously returned on average. 2. Prior inner product approaches leak distance between the query and all stored records. We refer to these as distance-revealing. We show a natural construction from function hiding, secret-key, predicate, inner product encryption (Shen, Shi, and Waters, TCC 2009). Our construction only leaks access patterns and which returned records are the same distance from the query. We refer to this scheme as distance-hiding. We implement and benchmark one distance-revealing and one distance-hiding scheme. The distance-revealing scheme can search a small (hundreds) database in 4 minutes while the distance-hiding scheme is not yet practical, requiring 3.5 hours. As a technical contribution of independent interest, we show that our scheme can be instantiated using symmetric pairing groups reducing the cost of search by roughly a factor of three. We believe this analysis extends to other schemes based on projections to a random linear map and its inverse analyzed in the generic group model.

DMTF is a standards organization by major industry players in IT infrastructure including AMD, Alibaba, Broadcom, Cisco, Dell, Google, Huawei, IBM, Intel, Lenovo, and NVIDIA, which aims to enable interoperability, e.g., including cloud, virtualization, network, servers and storage. It is currently standardizing a security protocol called SPDM, which aims to secure communication over the wire and to enable device attestation, notably also explicitly catering for communicating hardware components. The SPDM protocol inherits requirements and design ideas from IETF’s TLS 1.3. However, its state machines and transcript handling are substantially different and more complex. While architecture, specification, and open-source libraries of the current versions of SPDM are publicly available, these include no significant security analysis of any kind. In this work we develop the first formal models of the three modes of the SPDM protocol version 1.2.1, and formally analyze their main security properties.

Differential obliviousness (DO) access pattern privacy is a privacy notion which guarantees that the access patterns of a program satisfy differential privacy. Differential obliviousness was studied in a sequence of recent works as a relaxation of full obliviousness. Earlier works showed that DO not only allows us to circumvent the logarithmic-overhead barrier of fully oblivious algorithms, in many cases, it also allows us to achieve polynomial speedup over full obliviousness, since it avoids "padding to the worst-case" behavior of fully oblivious algorithms. Despite the promises of differential obliviousness (DO), a significant barrier that hinders its broad application is the lack of composability. In particular, when we apply one DO algorithm to the output of another DO algorithm, the composed algorithm may no longer be DO (with reasonable parameters). More specifically, the outputs of the first DO algorithm on two neighboring inputs may no longer be neighboring, and thus we cannot directly benefit from the DO guarantee of the second algorithm. In this work, we are the first to explore a theory of composition for differentially oblivious algorithms. We propose a refinement of the DO notion called $(\epsilon, \delta)$-neighbor-preserving-DO, or $(\epsilon, \delta)$-NPDO for short, and we prove that our new notion indeed provides nice compositional guarantees. In this way, the algorithm designer can easily track the privacy loss when composing multiple DO algorithms. We give several example applications to showcase the power and expressiveness of our new NPDO notion. One of these examples is a result of independent interest: we use the compositional framework to prove an optimal privacy amplification theorem for the differentially oblivious shuffle model. In other words, we show that for a class of distributed differentially private mechanisms in the shuffle-model, one can replace the perfectly secure shuffler with a DO shuffler, and nonetheless enjoy almost the same privacy amplification enabled by a shuffler.

Starting from the problem of $d$-Tensor Isomorphism ($d$-TI), we study the relation between various Code Equivalence problems in different metrics. In particular, we show a reduction from the sum-rank metric (CE${}_{sr}$) to the rank metric (CE${}_{rk}$). To obtain this result, we investigate reductions between tensor problems. We define the Monomial Isomorphism problem for $d$-tensors ($d$-TI${}^*$ ), where, given two $d$-tensors, we ask if there are $d-1$ invertible matrices and a monomial matrix sending one tensor into the other. We link this problem to the well-studied $d$-TI and the TI-completeness of $d$-TI${}^*$ is shown. Due to this result, we obtain a reduction from CE${}_{sr}$ to CE${}_{rk}$. In the literature, a similar result was known, but it needs an additional assumption on the automorphisms of matrix codes. Since many constructions based on the hardness of Code Equivalence problems are emerging in cryptography, we analyze how such reductions can be taken into account in the design of cryptosystems based on CE${}_{sr}$.

Registered encryption (Garg {\em et al.}, TCC'18) is an emerging paradigm that tackles the key-escrow problem associated with identity-based encryption by replacing the private-key generator with a much weaker entity known as the key curator. The key curator holds no secret information, and is responsible to: (i) update the master public key whenever a new user registers its own public key to the system; (ii) provide helper decryption keys to the users already in the system, in order to make them still able to decrypt. For practical purposes, tasks (i) and (ii) need to be efficient, in the sense that the size of the public parameters, of the master public key, and of the helper decryption keys, as well as the running time for key generation and user registration, and the number of updates, must be small. In this paper, we generalize the notion of registered encryption to the setting of functional encryption (FE). Our contributions are twofold: On the one hand, we show that registered FE exists assuming indistinguishability obfuscation and somewhere statistically binding hash functions. On the other hand, we show an efficient construction of registered FE for the special case of inner-product predicates, over asymmetric bilinear groups of prime order, with provable security in the generic group model.

In this paper, we perform a systematic study of functions $f: \mathbb{Z}_{p^e} \to \mathbb{Z}_{p^e}$ and categorize those functions that can be represented by a polynomial with integer coefficients. More specifically, we cover the following properties: necessary and sufficient conditions for the existence of an integer polynomial representation; computation of such a representation; and the complete set of equivalent polynomials that represent a given function. As an application, we use the newly developed theory to speed up bootstrapping for the BGV and BFV homomorphic encryption schemes. The crucial ingredient underlying our improvements is the existence of null polynomials, i.e. non-zero polynomials that evaluate to zero in every point. We exploit the rich algebraic structure of these null polynomials to find better representations of the digit extraction function, which is the main bottleneck in bootstrapping. As such, we obtain sparse polynomials that have 50% fewer coefficients than the original ones. In addition, we propose a new method to decompose digit extraction as a series of polynomial evaluations. This lowers the time complexity from $\mathcal{O}(\sqrt{pe})$ to $\mathcal{O}(\sqrt{p}\sqrt[^4]{e})$ for digit extraction modulo $p^e$, at the cost of a slight increase in multiplicative depth. Overall, our implementation in HElib shows a significant speedup of a factor up to 2.6 over the state-of-the-art.

We unify the state-of-the-art bootstrapping algorithms for BGV and BFV in a single framework, and show that both schemes can be bootstrapped with identical complexity. This result corrects a claim by Chen and Han (Eurocrypt 2018) that BFV is more efficient to bootstrap than BGV. We also fix an error in their optimized procedure for power-of-two cyclotomics, which occurs for some parameter sets. Our analysis is simpler, yet more general than earlier work, in that it simultaneously covers both BGV and BFV. Furthermore, we also design and implement a high-level open source software library for bootstrapping in the Magma Computer Algebra System. It is the first library to support both BGV and BFV bootstrapping in full generality, with all recent techniques (including the above fixes) and trade-offs.

We introduce a new class of efficient transparent interactive zero knowledge argument system based on the input transformation concept. The idea of the input transformation concept is converting circuit inputs in Pedersen commitment form to linear polynomials in integer form so that verifiers can use standard integer operations to compute and verify the circuit output. While the verifier runtime of our protocol is linear to the size of the circuit, its practical performance compares favorably against state-of-the-art transparent zero-knowledge protocols with sub-linear verifier work. We therefore claim that our protocol achieves practical succinctness. The input transformation concept replaces the constraint system often required in zero knowledge protocols. Once inputs are transformed, they can be used as inputs to a circuit that computes the output directly from inputs. This direct computation mechanism eliminates the need of a front end encoder to translate NP relation $R$ to some zero-knowledge friendly representation $\hat{R}$ (such as R1CS constraint system) before the relation can be converted to a proof system, making our protocol relatively easy to implement and likely easier to use compared to constraint system based protocols. The asymptotic cost of our protocol is $O (m_p \text{ log } m_p)$ for prover work, $O (n)$ for verifier work, and $ O({m_p}^{1/2})$ for communication cost, where $n$ stands for the total number of all operations in a circuit and $m_p$ stands for the total number of multiplications performed on the path that leads to the circuit output (e.g. for a circuit with $n=2^{20}$ sequential multiplications and one output, $m_p = n$). Specifically, when running a circuit with $2^{20}$ sequential multiplication gates with 640 input bits on a single thread, the prover runtime of our protocol is $6$ seconds, the verifier runtime is $23$ ms and the communication cost is approximately $59$ kbs, which shows significant improvement over the current approaches in verifier runtime while keeping the prover runtime and communication cost competitive with current state of art. In this paper, we will first introduce a base version of our protocol in which the prover work is dominated by $O ({m_p}^2)$ field operations. Although field operations are significantly faster than group operations, they become increasingly expensive as $m_p$ value gets large. So in the follow up sections, we will introduce a mechanism to apply number theoretic transformation (NTT) to bring down the prover runtime to $O (m_p \text{ log } m_p)$.

Continuous Group Key Agreement (CGKA) lets a evolving group of clients agree on a sequence of group keys. An important application of CGKA is scalable asynchronous end-to-end (E2E) encrypted group messaging. A major problem preventing the use of CGKA over unreliable infrastructure are so-called forks. A fork occurs when group members have diverging views of the group's history (and thus its current state); e.g. due to network or server failures. Once communication channels are restored, members resolve a fork by agreeing on the state of the group again. Today's CGKA protocols make fork resolution challenging, as natural resolution strategies seem to conflict with the way the protocols enforce group state agreement and forward secrecy. Meanwhile, secure group messaging protocols which do support fork resolution do not scale nearly as well as CGKA does. In this work, we pave the way to practical scalable E2E messaging over unreliable infrastructure. To that end, we generalize CGKA to Fork Resilient-CGKA which allows clients to process significantly more types of out-of-order network traffic. This is important for many natural fork resolution procedures as they are based, in part, on replaying missed traffic. Next, we give two FR-CGKA constructions: a practical one based on the CGKA underlying the MLS messaging standard and an optimally secure one (albeit with only theoretical efficiency). To further assist with fork resolution, we introduce a simple new abstraction to describe a client's local protocol state. The abstraction describes all and only the information relevant to natural fork resolution, making it easier for higher-level fork resolution procedures to work with and reason about. We define a black-box extension of an FR-CGKA which maintains such a description of a client's internal state. Finally, as a proof of concept, we give a basic fork resolution protocol.

Given two KZG-committed polynomials $f(X),g(X)\in \mathbb{F}_{<n}[X]$, a matrix $M\in \mathbb{F}^{n\times n}$, and subgroup $H\subset \mathbb{F}^*$ of order $n$, we present a protocol for checking that $f|_{H}\cdot M = g|_{H}$. After preprocessing, the prover makes $O(n)$ field and group operations. This presents a significant improvement over the lincheck protocols in [CHMMVW, COS], where the prover's run-time (also after preprocessing) was quasilinear in the number of non-zeroes of $M$, which could be $n^2$.

The goal of a covert learning algorithm is to learn a function $f$ by querying it, while ensuring that an adversary, who sees all queries and their responses, is unable to (efficiently) learn any more about $f$ than they could learn from random input-output pairs. We focus on a relaxation that we call local covertness, in which queries are distributed across $k$ servers and we only limit what is learnable by $k - 1$ colluding servers. For any constant $k$, we give a locally covert algorithm for efficiently learning any Fourier-sparse function (technically, our notion of learning is improper, agnostic, and with respect to the uniform distribution). Our result holds unconditionally and for computationally unbounded adversaries. Prior to our work, such an algorithm was known only for the special case of $O(\log n)$-juntas, and only with $k = 2$ servers, Ishai et al. (Crypto 2019). Our main technical observation is that the original Goldreich-Levin algorithm only utilizes i.i.d. pairs of correlated queries, where each half of every pair is uniformly random. We give a simple generalization of this algorithm in which pairs are replaced by $k$-tuples in which any $k - 1$ components are jointly uniform. The cost of this generalization is that the number of queries needed grows exponentially with $k$.

In this paper, we design secure multi-party computation (MPC) protocols in the asynchronous communication setting with optimal resilience. Our protocols are secure against a computationally-unbounded malicious adversary, characterized by an adversary structure $\mathcal{Z}$, which enumerates all possible subsets of potentially corrupt parties. Our protocols incur a communication of $\mathcal{O}(|\mathcal{Z}|^2)$ and $\mathcal{O}(|\mathcal{Z}|)$ bits per multiplication for perfect and statistical security respectively. These are the first protocols with this communication complexity, as such protocols were known only in the synchronous communication setting (Hirt and Tschudi, ASIACRYPT 2013).

NIST selected the A SCON family of cryptographic primitives for standardization in February 2023 as the final step in the Lightweight Cryptography Competition. The ASCON submission to the competition provided Authenticated Encryption with Associated Data (AEAD), hashing, and Extensible Output Function (XOF) modes. Real world cryptography systems often need more than packet encryption and simple hashing. Keyed message authentication, key derivation, cryptographically secure pseudo-random number generation (CSPRNG), password hashing, and encryption of sensitive values in memory are also important. This paper defines additional modes that can be deployed on top of ASCON based on proven designs from the literature.

The present article provides a novel hash function $\mathcal{H}$ to any elliptic curve of $j$-invariant $\neq 0, 1728$ over a finite field $\mathbb{F}_{\!q}$ of large characteristic. The unique bottleneck of $\mathcal{H}$ consists in extracting a square root in $\mathbb{F}_{\!q}$ as well as for most hash functions. However, $\mathcal{H}$ is designed in such a way that the root can be found by (Cipolla-Lehmer-)Müller's algorithm in constant time. Violation of this security condition is known to be the only obstacle to applying the given algorithm in the cryptographic context. When the field $\mathbb{F}_{\!q}$ is highly $2$-adic and $q \equiv 1 \ (\mathrm{mod} \ 3)$, the new batching technique is the state-of-the-art hashing solution except for some sporadic curves. Indeed, Müller's algorithm costs $\approx 2\log_2(q)$ multiplications in $\mathbb{F}_{\!q}$. In turn, (constant-time) Tonelli-Shanks's square root algorithm has asymptotic complexity $O(\log(q) + \nu^2)$, where $\nu$ is the $2$-adicity of $\mathbb{F}_{\!q}$. As an example, Müller's algorithm needs $\approx 4561$ fewer multiplications in the field $\mathbb{F}_{\!q}$ (whose $\nu = 96$) of the standardized curve NIST P-224. In other words, there is an acceleration of about $11$ times.

Mass surveillance can be more easily achieved leveraging fear and desire of the population to feel protected while affected by devastating events. Indeed, in such scenarios, governments can adopt exceptional measures that limit civil rights, usually receiving large support from citizens. The COVID-19 pandemic is currently affecting daily life of many citizens in the world. People are forced to stay home for several weeks, unemployment rates quickly increase, uncertainty and sadness generate an impelling desire to join any government effort in order to stop as soon as possible the spread of the virus. Following recommendations of epidemiologists, governments are proposing the use of smartphone applications to allow automatic contact tracing of citizens.Such systems can be an effective way to defeat the spread of the SARS-CoV-2 virus since they allow to gain time in identifying potentially new infected persons that should therefore be in quarantine. This raises the natural question of whether this form of automatic contact tracing can be a subtle weapon for governments to violate privacy inside new and more sophisticated mass surveillance programs. In order to preserve privacy and at the same time to contribute to the containment of the pandemic, several research partnerships are proposing privacy-preserving contact tracing systems where pseudonyms are updated periodically to avoid linkability attacks. A core component of such systems is Bluetooth low energy (BLE, for short) a technology that allows two smartphones to detect that they are in close proximity. Among such systems there are some proposals like DP-3T, MIT-PACT, UW-PACT and the Apple&Google exposure notification system that through a decentralized approach claim to guarantee better privacy properties compared to other centralized approaches (e.g., PEPP-PT-NTK, PEPP-PT-ROBERT). On the other hand, advocates of centralized approaches claim that centralization gives to epidemiologists more useful data, therefore allowing to take more effective actions to defeat the virus. Motivated by Snowden's revelations about previous attempts of governments to realize mass surveillance programs, in this paper we first analyze mass surveillance attacks that leverage weaknesses of automatic contact tracing systems. We focus in particular on the DP-3T system (still our analysis is significant also for MIT-PACT and Apple&Google systems). Based on recent literature and new findings, we discuss how a government can exploit the use of the DP-3T system to successfully mount privacy attacks as part of a mass surveillance program. Interestingly, we show that privacy issues in the DP-3T system are not inherent in BLE-based contact tracing systems. Indeed, we propose two systems named and $\textsf{Pronto-C2}$ that, in our view, enjoy a much better resilience with respect to mass surveillance attacks still relying on BLE. Both systems are based on a paradigm shift: instead of asking smartphones to send keys to the Big Brother (this corresponds to the approach of the DP-3T system), we construct a decentralized BLE-based ACT system where smartphones anonymously and confidentially talk to each other in the presence of the Big Brother. Unlike $\textsf{Pronto-B2}$, $\textsf{Pronto-C2}$ relies on Diffie-Hellman key exchange providing better privacy but also requiring a bulletin board to translate a BLE beacon identifier into a group element. Both systems can optionally be implemented using Blockchain technology, offering complete transparency and resilience through full decentralization, therefore being more appealing for citizens. Only through a large participation of citizens contact tracing systems can be really useful to defeat COVID-19, and our proposal goes straight in this direction.

An important tool that has contributed to collision search on Keccak/SHA3 is the Target Difference Algorithm (TDA) and its inter- nal differential counterpart Target Internal Difference Algorithm (TIDA), which were introduced by Dinur et al. in separate works in FSE 2012 and 2013 respectively. These algorithms provide an ingenious way of extend- ing the differential trails by one round and exploiting the affine subspaces generated due to the low algebraic degree of the Keccak S-box. The cur- rent work introduces TIDAL, which can extend TIDA by one more round capitalizing on linearization techniques introduced by Guo et al. in JoC. This approach requires increment consistency checks, which is also im- proved in this work. The TIDAL strategy, in conjunction with a determin- istic internal differential trail, has been applied to Keccak variants up to 400-bit state-size and leads to practical collision attacks for most of them up to 5 rounds. In particular collisions have been confirmed for 4-round Keccak[136, 64] with a complexity of 220 and on 6-round of Keccak[84,16] with a complexity of 25 . Further, this work completely characterizes all collision attacks on state-reduced variants, showcasing that TIDAL covers most space up to 5 rounds. As state and round-reduced Keccak variants are used to realize the internal states of many crypto primitives, the re- sults presented here generate a significant impact. Finally, it shows new directions for the long-standing problem of state-reduced variants being difficult to be attacked.

In this paper we revise the ideas of our previous work `Lin2-Xor lemma and Log-size Linkable Threshold Ring Signature' and introduce another lemma called Lin2-Choice, which extends the Lin2-Xor lemma. Using the Lin2-Choice lemma we create a compact general-purpose trusted-setup-free log-size linkable threshold ring signature with strong security model. The signature size is 2log(n+1)+3l+1, where n is the ring size and l is the threshold. It is composed of several public coin arguments that are special honest verifier zero-knowledge and have computational witness-extended emulation. We use an arbitrary vector commitment argument as the base building block, providing the possibility to use any of its specific implementations that have the above properties. Also, we present an extended version of our signature of size 2log(n+l+1)+7l+4, which simultaneously proves balance and allows for easy multipary signing. All this is constructed in a prime order group without bilinear parings under the decisional Diffie-Hellman assumption in the random oracle model.

Secret sharing is an essential tool for many distributed applications, including distributed key generation and multiparty computation. For many practical applications, we would like to tolerate network churn, meaning participants can dynamically enter and leave the pool of protocol participants as they please. Such protocols, called Dynamic-committee Proactive Secret Sharing (DPSS), have recently been studied; however, existing DPSS protocols do not gracefully handle faults: the presence of even one unexpectedly slow node can often slow down the whole protocol by a factor of $O(n)$. In this work, we explore optimally fault-tolerant asynchronous DPSS that is not slowed down by crash faults and even handles byzantine faults while maintaining the same performance. We first introduce the first high-threshold DPSS, which offers favorable characteristics relative to prior non-synchronous works in the presence of faults while simultaneously supporting higher privacy thresholds. We then batch-amortize this scheme along with a parallel non-high-threshold scheme which achieves optimal bandwidth characteristics. We implement our schemes and demonstrate that they can compete with prior work in best-case performance while outperforming it in non-optimal settings.

The FX construction provides a way to increase the effective key length of a block cipher E. We prove security of a tweakable version of the FX construction in the post-quantum setting, i.e., against a quantum attacker given only classical access to the secretly keyed construction while retaining quantum access to E, a setting that seems to be the most relevant one for real-world applications. We then use our results to prove post-quantum security—in the same model—of the (plain) FX construction, Elephant (a finalist of NIST's lightweight cryptography standardization effort), and Chaskey (an ISO-standardized lightweight MAC).

Blind signatures allow a signer to issue signatures on messages chosen by the signature recipient. The main property is that the recipient's message is hidden from the signer. There are many applications, including Chaum's e-cash system and Privacy Pass, where no special distribution of the signed message is required, and the message can be random. Interestingly, existing notions do not consider this practical use case separately. In this paper, we show that constraining the recipient's choice over the message distribution spawns a surprising new primitive that improves the well-established state-of-the-art. We formalize this concept by introducing the notion of non-interactive blind signatures (${\sf NIBS}$). Informally, the signer can create a presignature with a specific recipient in mind, identifiable via a public key. The recipient can use her secret key to finalize it and receive a blind signature on a random message determined by the finalization process. The key idea is that online interaction between the signer and recipient is unnecessary. We show an efficient instantiation of ${\sf NIBS}$ in the random oracle model from signatures on equivalence classes. The exciting part is that, in this case, for the recipient's public key, we can use preexisting keys for Schnorr, ECDSA signatures, El-Gamal encryption scheme, or even the Diffie-Hellman key exchange. Reusing preexisting public keys allows us to distribute anonymous tokens similarly to cryptocurrency airdropping. Additional contributions include tagged non-interactive blind signatures (${\sf TNIBS}$) and their efficient instantiation. A generic construction in the random oracle or common reference string model based on verifiable random functions, standard signatures, and non-interactive proof systems.

In recent years, lattice-based secure multi-party computation (MPC) has seen a rise in popularity and is used more and more in large scale applications like privacy-preserving cloud computing, electronic voting, or auctions. Many of these applications come with the following high security requirements: a computation result should be publicly verifiable, with everyone being able to identify a malicious party and hold it accountable, and a malicious party should not be able to corrupt the computation, force a protocol restart, or block honest parties or an honest third-party (client) that provided private inputs from receiving a correct result. The protocol should guarantee verifiability and accountability even if all protocol parties are malicious. While some protocols address one or two of these often essential security features, we present the first publicly verifiable and accountable, and (up to a threshold) robust SPDZ-like MPC protocol without restart. We propose protocols for accountable and robust online, offline, and setup computations. We adapt and partly extend the lattice-based commitment scheme by Baum et al. (SCN 2018) as well as other primitives like ZKPs. For the underlying commitment scheme and the underlying BGV encryption scheme we determine ideal parameters. We give a performance evaluation of our protocols and compare them to state-of-the-art protocols both with and without our target security features: public accountability, public verifiability and robustness.

Typical lattice-based cryptosystems are commonly believed to resist multi-target attacks. For example, the New Hope proposal stated that it avoids "all-for-the-price-of-one attacks". An ACM CCS 2021 paper from Duman–Hövelmanns–Kiltz–Lyubashevsky–Seiler stated that "we can show that Adv_{PKE}^{IND-CPA} ≈ Adv_{PKE}^{(n,q_C)-IND-CPA} for "lattice-based schemes" such as Kyber, i.e. that one-out-of-many-target IND-CPA is as difficult to break as single-target IND-CPA, assuming "the hardness of MLWE as originally defined for the purpose of worst-case to average-case reductions". Meanwhile NIST expressed concern regarding multi-target attacks against non-lattice cryptosystems. This paper quantifies the asymptotic impact of multiple ciphertexts per public key upon standard analyses of known primal lattice attacks, assuming existing heuristics. The qualitative conclusions are that typical lattice PKEs asymptotically degrade in heuristic multi-ciphertext IND-CPA security as the number of ciphertexts increases. These PKE attacks also imply multi-ciphertext IND-CCA2 attacks against typical constructions of lattice KEMs. Quantitatively, the asymptotic heuristic security degradation is exponential in Θ(n) for decrypting many ciphertexts, cutting a constant fraction out of the total number of bits of security, and exponential in Θ(n/log n) for decrypting one out of many ciphertexts, for conservative cryptosystem parameters. This shows a contradiction between the existing heuristics and the idea that multi-target security matches single-target security. Also, whether or not the existing heuristics are correct, (1) there are flaws in the claim of an MLWE-based proof of tight multi-target security, and (2) there is a 2^{88}-guess attack breaking one out of 2^{40} ciphertexts for a FrodoKEM-640 public key, disproving FrodoKEM's claim that "the FrodoKEM parameter sets comfortably match their target security levels with a large margin".

We propose and analyze a simple strategy for constructing 1-key constrained pseudorandom functions (CPRFs) from homomorphic secret sharing. In the process, we obtain the following contributions. First, we identify desirable properties for the underlying HSS scheme for our strategy to work. Second, we show that (most) recent existing HSS schemes satisfy these properties, leading to instantiations of CPRFs for various constraints and from various assumptions. Notably, we obtain the first (1-key selectively secure, private) CPRFs for inner-product and (1-key selectively secure) CPRFs for NC 1 from the DCR assumption, and more. Lastly, we revisit two applications of HSS, equipped with these additional properties, to secure computation: we obtain secure computation in the silent preprocessing model with one party being able to precompute its whole preprocessing material before even knowing the other party, and we construct one-sided statistically secure computation with sublinear communication for restricted forms of computation.

The Digital Markets Act (DMA) is a nascent European Union regulation adopted in May 2022. One of its most controversial provisions is a requirement that so-called “gatekeepers” offering end-to-end encrypted messaging apps, such as WhatsApp, implement “interoperability” with other messaging apps: in essence, encrypted messaging across service providers. This requirement represents a fundamental shift in the design assumptions of existing encrypted messaging systems, most of which are designed to be centralized. Technologists have not really begun thinking about the myriad security, privacy, and functionality questions raised by the interoperability requirement; given that the DMA’s interoperability mandate may take effect as soon as mid-2024, it is critical for researchers to begin understanding the challenges and offering solutions. In this paper, we take an initial step in this direction. We break down the DMA’s effects on the design of encrypted messaging systems into three main areas: identity, or how to resolve identities across service providers; protocols, or how to establish a secure connection between clients on different platforms; and abuse prevention, or how service providers can detect and take action against users engaging in abuse or spam. For each area, we identify key security and privacy requirements, summarize existing proposals, and examine whether proposals meet our security and privacy requirements. Finally, we propose our own design for an interoperable encrypted messaging system, and point out open problems.

Private Information Retrieval (PIR) addresses the cryptographic problem of hiding sensitive database queries from database operators. In practice, PIR schemes face the challenges of either high computational costs or restrictive security assumptions, resulting in a barrier to deployment. In this work, we introduce Assisted Private Information Retrieval (APIR), a new PIR framework for keyword-value databases generalizing multi-server PIR and relaxing its database consistency assumption. We propose the construction of Synchronized APIR, an efficient hybrid APIR scheme combining black-box single-server PIR and non-black-box multi-server PIR. To evaluate the scheme, we apply it to a proof-of-concept privacy-preserving DNS application. The experiment results demonstrate that Synchronized APIR outperforms the baseline single-server PIR protocol in communication and computational cost after the initial one-time cost.

We propose Flashproofs, a new type of efficient special honest verifier zero-knowledge arguments with a transparent setup in the discrete logarithm (DL) setting. First, we put forth gas-efficient range arguments that achieve $O(N^{\frac{2}{3}})$ communication cost, and involve $O(N^{\frac{2}{3}})$ group exponentiations for verification and a slightly sub-linear number of group exponentiations for proving with respect to the range $[0, 2^N-1]$, where $N$ is the bit length of the range. For typical confidential transactions on blockchain platforms supporting smart contracts, verifying our range arguments consumes only 234K and 315K gas for 32-bit and 64-bit ranges, which are comparable to 220K gas incurred by verifying the most efficient zkSNARK with a trusted setup (EUROCRYPT 16) at present. Besides, the aggregation of multiple arguments can yield further efficiency improvement. Second, we present polynomial evaluation arguments based on the techniques of Bayer & Groth (EUROCRYPT 13). We provide two zero-knowledge arguments, which are optimised for lower-degree ($D \in [3, 2^9]$) and higher-degree ($D > 2^9$) polynomials, where $D$ is the polynomial degree. Our arguments yield a non-trivial improvement in the overall efficiency. Notably, the number of group exponentiations for proving drops from $8\log D$ to $3(\log D+\sqrt{\log D})$. The communication cost and the number of group exponentiations for verification decrease from $7\log D$ to $(\log D + 3\sqrt{\log D})$. To the best of our knowledge, our arguments instantiate the most communication-efficient arguments of membership and non-membership in the DL setting among those not requiring trusted setups. More importantly, our techniques enable a significantly asymptotic improvement in the efficiency of communication and verification (group exponentiations) from $O(\log D)$ to $O(\sqrt{\log D})$ when multiple arguments satisfying different polynomials with the same degree and inputs are aggregated.

The Restricted Syndrome Decoding Problem (R-SDP) cor- responds to the Syndrome Decoding Problem (SDP) with the additional constraint that entries of the solution vector must live in a desired sub- set of a finite field. In this paper we study how this problem can be applied to the construction of signatures derived from Zero-Knowledge (ZK) proofs. First, we show that R-SDP appears to be well suited for this type of applications: almost all ZK protocols relying on SDP can be modified to use R-SDP, with important reductions in the communication cost. Then, we describe how R-SDP can be further specialized, so that solutions can be represented with a number of bits that is slightly larger than the security parameter (which clearly provides an ultimate lower bound), thus enabling the design of ZK protocols with tighter and rather competitive parameters. Finally, we show that existing ZK protocols can greatly benefit from the use of R-SDP, achieving signature sizes in the order of 7 kB, which are smaller than those of several other schemes ob- tained from ZK protocols. For instance, this beats all schemes based on the Permuted Kernel Problem (PKP), almost all schemes based on SDP and several schemes based on rank metric problems.

We present Origami verifiable delay function, build from the MinRoot hash and our dedicated plonk proof system that utilizes a tai- lored custom gate and a folding scheme. MinRoot VDF is the leading candidate for Ethereum adoption. For N iterations of MinRoot hash func- tion, the overall cost of Origami is N +o(N ) group operations; improving the previous best known result of 6N from a Nova based solution. The proof size is 128k + 224 bytes if we fold the proofs for k times; and may be further reduce to around 960 bytes, regardless of k, via a standard recursive prover.

Sharding is a promising approach to scale permissionless blockchains. In a sharded blockchain, participants are split into groups, called shards, and each shard only executes part of the workloads. Despite its wide adoption in permissioned systems, transferring such success to permissionless blockchains is still an open problem. In permissionless networks, participants may join and leave the system at any time, making load balancing challenging. In addition, the adversary in such networks can launch the single-shard takeover attack by compromising a single shard’s consensus. To address these issues, participants should be securely and dynamically allocated into different shards. However, the protocol capturing such functionality – which we call shard allocation – is overlooked. In this paper, we study shard allocation protocols for permissionless blockchains. We formally define the shard allocation protocol and propose an evaluation framework. We apply the framework to evaluate the shard allocation subprotocols of seven state-of-the-art sharded blockchains, and show that none of them is fully correct or achieves satisfactory performance. We attribute these deficiencies to their extreme choices between two performance metrics: self-balance and operability. We observe and prove the fundamental trade-off between these two metrics, and identify a new property memory-dependency that enables parameterisation over this trade-off. Based on these insights, we propose Wormhole, a correct and efficient shard allocation protocol with minimal security assumptions and parameterisable self-balance and operability. We implement Wormhole and evaluate its overhead and performance metrics in a network with 128 shards and 32768 nodes. The results show that Wormhole introduces little overhead, achieves consistent self-balance and operability with our theoretical analysis, and allows the system to recover quickly from load imbalance.

Randomness cannot be compressed, hence expanded randomness is ‘contaminated randomness’ where hidden pattern is used. Current cryptography uses little randomness (the key) to generate large randomness (the ciphertext). The pattern used for this expansion is subject to cryptanalysis. By contrast, Vernam and the new breed of Trans-Vernam ciphers project security with sufficient supply of genuine randomness. Having no hidden pattern in their process, they expose no vulnerability to cryptanalysis, other than brute force, the efficacy of which, is well gauged by using enough randomness to brute-force through. Unlike the original genuine randomness cipher (the Vernam cipher; US patent: 1,310,719), the new breed of Trans-Vernam ciphers (US patents: 10,541,802, 10,911,215, 11,159,317 to name a few) projects security with shared randomness (between transmitter and recipient) as well as with unilateral randomness determined ad hoc by the transmitter, thereby controlling the vulnerability of the transmitted message, including eliminating it all together, rising to Vernam grade. The new Trans-Vernam ciphers exploit new technologies for generating high-grade randomness, storing it and communicating it in large quantities. Their security is mathematically established and barring faulty implementation these ciphers are unbreakable. We are looking at a flat cyberspace, no more hierarchy based on math skills: Vernam grade security delivered through modern Trans-Vernam ciphers. Robust privacy of communication will be claimed by all – for good and for ill; law-enforcement and national security will have to adjust. It's a new cryptography, and a new society.

Homomorphic secret sharing (HSS) is a form of secret sharing that supports the local evaluation of functions on the shares, with applications to multi-server private information retrieval, secure computation, and more. Insisting on additive reconstruction, all known instantiations of HSS from "Learning with Error (LWE)"-type assumptions either have to rely on LWE with superpolynomial modulus, come with non-negligible error probability, and/or have to perform expensive ciphertext multiplications, resulting in bad concrete efficiency. In this work, we present a new 2-party local share conversion procedure, which allows to locally convert noise encoded shares to non-noise plaintext shares such that the parties can detect whenever a (potential) error occurs and in that case resort to an alternative conversion procedure. Building on this technique, we present the first HSS for branching programs from (Ring-)LWE with polynomial input share size which can make use of the efficient multiplication procedure of Boyle et al.~(Eurocrypt 2019) and has no correctness error. Our construction comes at the cost of a -- on expectation -- slightly increased output share size (which is insignificant compared to the input share size) and a more involved reconstruction procedure. More concretely, we show that in the setting of 2-server private counting queries we can choose ciphertext sizes of only a quarter of the size of the scheme of Boyle et al. at essentially no extra cost.

The discrete logarithm problem forms the basis of security of many practical schemes. When the number of bases is more than one, the problem of finding out the exponents is known as the multi- dimensional discrete logarithm problem. We focus on solving this problem in groups modulo some prime p. Gaudry and Schost proposed a low-memory algorithm for this problem which performs a pseudo-random walk in the group. We have proposed an improvement to the Gaudry-Schost algorithm. Our modification is valid for any dimension and does not put any additional restrictions. To the best of our knowledge, experimentation of such a technique was not done before for dimension D > 1. We implemented the new algorithm in subgroups of Z ∗ p , relevant in the context of electronic voting and cash schemes. Our algorithm showed a substantial decrease in run-time. For example, on a single core of Intel Xeon E7-8890 @ 2.50 GHz our algorithm required 12 times less time than the Gaudry-Schost algorithm when implemented on 2076 bit-sized groups. Moreover, experiments indicate that the factor by which the time requirement reduces when compared with the Gaudry- Schost algorithm is directly proportional to the size of the group. This leads to better practical behavior of the algorithm over such cryptographically important groups. We also point out a few more optimizations that can be adopted along with future applications for other scenarios. One of the main aspects of our work is the listing of the improvements in multi-dimensional log computation that may happen in such prime-ordered groups.

Given a network of nodes with certain communication and computation capacities, what is the maximum rate at which a blockchain can run securely? We study this question for proof-of-work (PoW) and proof-of-stake (PoS) longest chain protocols under a ‘bounded bandwidth’ model which captures queuing and processing delays due to high block rate relative to capacity, bursty release of adversarial blocks, and in PoS, spamming due to equivocations. We demonstrate that security of both PoW and PoS longest chain, when operating at capacity, requires carefully designed scheduling policies that correctly prioritize which blocks are processed first, as we show attack strategies tailored to such policies. In PoS, we show an attack exploiting equivocations, which highlights that the throughput of the PoS longest chain protocol with a broad class of scheduling policies must decrease as the desired security error probability decreases. At the same time, through an improved analysis method, our work is the first to identify block production rates under which PoW longest chain is secure in the bounded bandwidth setting. We also present the first PoS longest chain protocol, SaPoS, which is secure with a block production rate independent of the security error probability, by using an ‘equivocation removal’ policy to prevent equivocation spamming.

In this paper, we present an AES-based authenticated-encryption with associated-data scheme called Rocca, with the purpose to reach the requirements on the speed and security in 6G systems. To achieve ultrafast software implementations, the basic design strategy is to take full advantage of the AES-NI and SIMD instructions as that of the AEGIS family and Tiaoxin-346. Although Jean and Nikolić have generalized the way to construct efficient round functions using only one round of AES (aesenc) and 128-bit XOR operation and have found several efficient candidates, there still seems to exist potential to further improve it regarding speed and state size. In order to minimize the critical path of one round, we remove the case of applying both aesenc and XOR in a cascade way for one round. By introducing a cost-free block permutation in the round function, we are able to search for candidates in a larger space without sacrificing the performance. Consequently, we obtain more efficient constructions with a smaller state size than candidates by Jean and Nikolić. Based on the newly-discovered round function, we carefully design the corresponding AEAD scheme with 256-bit security by taking several reported attacks on the AEGIS family and Tiaxion-346 into account. Our AEAD scheme can reach 178 Gbps which is almost 5 times faster than the AEAD scheme of SNOW-V. Rocca is also much faster than other efficient schemes with 256-bit key length, e.g. AEGIS-256 and AES-256-GCM. As far as we know, Rocca is the first dedicated cryptographic algorithm targeting 6G systems, i.e., 256-bit key length and the speed of more than 100 Gbps.

Digital signatures are fundamental components of public key cryptography. They allow a signer to generate verifiable and unforgeable proofs---signatures---over arbitrary messages with a private key, and allow recipients to verify the proofs against the corresponding and expected public key. These properties are used in practice for a variety of use cases, ranging from identity or data authenticity to non-repudiation. Unsurprisingly, signature schemes are widely used in security protocols deployed on the Internet today. In recent years, some protocols have extended the basic syntax of signature schemes to support key blinding, a.k.a., key randomization. Roughly speaking, key blinding is the process by which a private signing key or public verification key is blinded (randomized) to hide information about the key pair. This is generally done for privacy reasons and has found applications in Tor and Privacy Pass. Recently, Denis, Eaton, Lepoint, and Wood proposed a technical specification for signature schemes with key blinding in an IETF draft. In this work, we analyze the constructions in this emerging specification. We demonstrate that the constructions provided satisfy the desired security properties for signature schemes with key blinding. We experimentally evaluate the constructions and find that they introduce a very reasonable 2-3x performance overhead compared to the base signature scheme. Our results complement the ongoing standardization efforts for this primitive.

Secure multi-party computation (SMPC) protocols allow several parties that distrust each other to collectively compute a function on their inputs. In this paper, we introduce a protocol that lifts classical SMPC to quantum SMPC in a composably and statistically secure way, even for a single honest party. Unlike previous quantum SMPC protocols, our proposal only requires very limited quantum resources from all but one party; it suffices that the weak parties, i.e. the clients, are able to prepare single-qubit states in the X-Y plane. The novel quantum SMPC protocol is constructed in a naturally modular way, and relies on a new technique for quantum verification that is of independent interest. This verification technique requires the remote preparation of states only in a single plane of the Bloch sphere. In the course of proving the security of the new verification protocol, we also uncover a fundamental invariance that is inherent to measurement-based quantum computing.

TEE-based smart contracts are an emerging blockchain architecture, offering fully programmable privacy with better performance than alternatives like secure multiparty computation. They can also support compatibility with existing smart contract languages, such that existing (plaintext) applications can be readily ported, picking up privacy enhancements automatically. While previous analysis of TEE-based smart contracts have focused on failures of TEE itself, we asked whether other aspects might be understudied. We focused on state consistency, a concern area highlighted by Li et al., as well as new concerns including access pattern leakage and software upgrade mechanisms. We carried out a code review of a cohort of four TEE-based smart contract platforms. These include Secret Network, the first to market with in-use applications, as well as Oasis, Phala, and Obscuro, which have at least released public test networks. The first and most broadly applicable result is that access pattern leakage occurs when handling persistent contract storage. On Secret Network, its fine-grained access pattern is catastrophic for the transaction privacy of SNIP-20 tokens. If ERC-20 tokens were naively ported to Oasis they would be similarly vulnerable; the others in the cohort leak coarse-grained information at approximately the page level (4 kilobytes). Improving and characterizing this will require adopting techniques from ORAMs or encrypted databases. Second, the importance of state consistency has been underappreciated, in part because exploiting such vulnerabilities is thought to be impractical. We show they are fully practical by building a proof-of-concept tool that breaks all advertised privacy properties of SNIP-20 tokens, able to query the balance of individual accounts and the token amount of each transfer. We additionally demonstrate MEV attacks against the Sienna Swap application. As a final consequence of lacking state consistency, the developers have inadvertently introduced a decryption backdoor through their software upgrade process. We have helped the Secret developers mitigate this through a coordinated vulnerability disclosure, after which their transaction replay defense is roughly on par with the rest.

In this work we introduce a new code-based signature scheme, called FuLeeca, based on the NP-hard problem of finding low Lee-weight codewords. The scheme follows the Hash-and-Sign approach applied to quasi-cyclic codes of small Lee-weight density. Similar approaches in the Hamming metric have suffered statistical attacks, which reveal the small support of the secret basis. Using the Lee metric we are able to thwart such attacks. We use existing hardness results on the underlying problem and study adapted statistical attacks. We propose parameters for FuLeeca and compare them to the best known post-quantum signature schemes. This comparison reveals that FuLeeca is extremely competitive. For example, for NIST category I, i.e., 160 bit of classical security, we obtain an average signature size of 276 bytes and public key sizes of 389 bytes. This not only outperforms all known code-based signature schemes, but also the signature schemes Dilithium, Falcon and SPHINCS+ selected by NIST for standardization.

The goal of this research is to raise technical doubts regarding the usefulness of the repeated attempts by governments to curb Cryptography (aka the ``Crypto Wars''), and argue that they, in fact, cause more damage than adding effective control. The notion of {\em Anamorphic Encryption} was presented in Eurocrypt'22 for a similar aim. There, despite the presence of a Dictator who possesses all keys and knows all messages, parties can arrange a hidden ``{\it anamorphic}'' message in an otherwise indistinguishable from regular ciphertexts (wrt the Dictator). In this work, we postulate a stronger cryptographic control setting where encryption does not exist (or is neutralized) since all communication is passed through the Dictator in, essentially, cleartext mode (or otherwise, when secure channels to and from the Dictator are the only confidentiality mechanism). Messages are only authenticated to assure recipients of the identity of the sender. We ask whether security against the Dictator still exists, even under such a~strict regime which allows only authentication (i.e., authenticated/ signed messages) to pass end-to-end, and where received messages are determined by/ known to the Dictator, and the Dictator also eventually gets all keys to verify compliance of past signing. To frustrate the Dictator, this authenticated message setting gives rise to the possible notion of anamorphic channels inside signature and authentication schemes, where parties attempt to send undetectable secure messages (or other values) using signature tags which are indistinguishable from regular tags. We define and present implementation of schemes for anamorphic signature and authentication; these are applicable to existing and standardized signature and authentication schemes which were designed independently of the notion of anamorphic messages. Further, some cornerstone constructions of the foundations of signatures, in fact, introduce anamorphism.

Encryption alone is not enough for secure end-to-end encrypted messaging: a server must also honestly serve public keys to users. Key transparency has been presented as an efficient solution for detecting (and hence deterring) a server that attempts to dishonestly serve keys. Key transparency involves two major components: (1) a username to public key mapping, stored and cryptographically committed to by the server, and, (2) an out-of-band consistency protocol for serving short commitments to users. In the setting of real-world deployments and supporting production scale, new challenges must be considered for both of these components. We enumerate these challenges and provide solutions to address them. In particular, we design and implement a memory-optimized and privacy-preserving verifiable data structure for committing to the username to public key store. To make this implementation viable for production, we also integrate support for persistent and distributed storage. We also propose a future-facing solution, termed ''compaction'', as a mechanism for mitigating practical issues that arise from dealing with infinitely growing server data structures. Finally, we implement a consensusless solution that achieves the minimum requirements for a service that consistently distributes commitments for a transparency application, providing a much more efficient protocol for distributing small and consistent commitments to users. This culminates in our production-grade implementation of a key transparency system (Parakeet) which we have open-sourced, along with a demonstration of feasibility through our benchmarks.

We investigate a new class of fault-injection attacks against the CSIDH family of cryptographic group actions. Our disorientation attacks effectively flip the direction of some isogeny steps. We achieve this by faulting a specific subroutine, connected to the Legendre symbol or Elligator computations performed during the evaluation of the group action. These subroutines are present in almost all known CSIDH implementations. Post-processing a set of faulty samples allows us to infer constraints on the secret key. The details are implementation specific, but we show that in many cases, it is possible to recover the full secret key with only a modest number of successful fault injections and modest computational resources. We provide full details for attacking the original CSIDH proof-of-concept software as well as the CTIDH constant-time implementation. Finally, we present a set of lightweight countermeasures against the attack and discuss their security.

The parametrization of $(3,3)$-isogenies by Bruin, Flynn and Testa requires over 37.500 multiplications if one wants to evaluate a single isogeny in a point. We simplify their formulae and reduce the amount of required multiplications by 94%. Further we deduce explicit formulae for evaluating $(3,3)$-splitting and gluing maps in the framework of the parametrization by Bröker, Howe, Lauter and Stevenhagen. We provide implementations to compute $(3^n,3^n)$-isogenies between principally polarized abelian surfaces with a focus on cryptographic application. Our implementation can retrieve Alice's secret isogeny in 11 seconds for the SIKEp751 parameters, which were aimed at NIST level 5 security.

Finite field multiplication is widely used for masking countermeasures against side-channel attacks. The execution time of finite field multiplication implementation is critical as it greatly impacts the overhead of the countermeasure. In this context, the use of exp-log tables is popular for the implementation of finite field multiplication. Yet, its performance is affected by the need for particular code to handle the case where one of the operands equals zero, as log is undefined for zero. As noticed by two recent papers, the zero case can be managed without any extra code by extending the exp table and setting $log[0]$ to a large-enough value. The multiplication of $a$ and $b$ then becomes as simple as: $exp[log[a]+log[b]]$. In this paper, we compare this approach with other implementations of finite field multiplication and show that it provides a good trade-off between memory use and execution time.

The block cipher GOST 28147-89 was the Russian Federation encryption standard for over 20 years, and is still one of its two standard block ciphers. GOST is a 32-round Feistel construction, whose security benefits from the fact that the S-boxes used in the design are kept secret. In the last 10 years, several attacks on the full 32-round GOST were presented. However, they all assume that the S-boxes are known. When the S-boxes are secret, all published attacks either target a small number of rounds, or apply for small sets of weak keys. In this paper we present the first practical-time attack on GOST with secret S-boxes. The attack works in the related-key model and is faster than all previous attacks in this model which assume that the S-boxes are known. The complexity of the attack is less than $2^{27}$ encryptions. It was fully verified, and runs in a few seconds on a PC. The attack is based on a novel type of related-key differentials of GOST, inspired by local collisions. Our new technique may be applicable to certain GOST-based hash functions as well. To demonstrate this, we show how to find a collision on a Davies-Meyer construction based on GOST with an arbitrary initial value, in less than $2^{10}$ hash function evaluations.

Blockchain consensus algorithms for cryptocurrency consist of the proof of work and proof of stake. However, current algorithms have problems, such as huge power consumption and equality issues. We propose a new consensus algorithm that uses transaction history. This algorithm ensures equality by randomly assigning approval votes based on past transaction records. We also incorporate a mechanism for adjusting issuance volume to measure the stability of the currency's value.

Public-key encryption with keyword search (PEKS) does not provide trapdoor privacy, i.e., keyword information is leaked through trapdoors. To prevent this information leakage, public key authenticated encryption with keyword search (PAEKS) has been proposed, where a sender's secret key is required for encryption, and a trapdoor is associated with not only a keyword but also the sender. Liu et al. (ASIACCS 2022) proposed a generic construction of PAEKS based on word-independent smooth projective hash functions (SPHFs) and PEKS. In this paper, we propose a new generic construction of PAEKS. The basic construction methodology is the same as that of the Liu et al. construction, where each keyword is converted into an extended keyword using SPHFs, and PEKS is used for extended keywords. Nevertheless, our construction is more efficient than Liu et al.'s in the sense that we only use one SPHF, but Liu et al. used two SPHFs. In addition, for consistency we considered a security model that is stronger than Liu et al.'s. Briefly, Liu et al. considered only keywords even though a trapdoor is associated with not only a keyword but also a sender. Thus, a trapdoor associated with a sender should not work against ciphertexts generated by the secret key of another sender, even if the same keyword is associated. Our consistency definition considers a multi-sender setting and captures this case. In addition, for indistinguishability against chosen keyword attack (IND-CKA) and indistinguishability against inside keyword guessing attack (IND-IKGA), we use a stronger security model defined by Qin et al. (ProvSec 2021), where an adversary is allowed to query challenge keywords to the encryption and trapdoor oracles. We also highlight several issues associated with the Liu et al. construction in terms of hash functions, e.g., their construction does not satisfy the consistency that they claimed to hold.

We conduct a systematic study of solving the learning parity with noise problem (LPN) using neural networks. Our main contribution is designing families of two-layer neural networks that practically outperform classical algorithms in high-noise, low-dimension regimes. We consider three settings where the numbers of LPN samples are abundant, very limited, and in between. In each setting we provide neural network models that solve LPN as fast as possible. For some settings we are also able to provide theories that explain the rationale of the design of our models. Comparing with the previous experiments of Esser, Kübler, and May (CRYPTO 2017), for dimension $n=26$, noise rate $\tau = 0.498$, the "Guess-then-Gaussian-elimination'' algorithm takes 3.12 days on 64 CPU cores, whereas our neural network algorithm takes 66 minutes on 8 GPUs. Our algorithm can also be plugged into the hybrid algorithms for solving middle or large dimension LPN instances.

It has been a long-standing viewpoint that doubling the length of key seeds in symmetric cipher can resist the quantum search attacks. This paper establishes a quantum key search model to deal with the post-quantum security of symmetric ciphers. The quantum search is performed in the punctured keystream/ciphertext space instead of the key space. On inputting the punctured keystreams/ciphertexts, we rule out the fake keys and find out the real key via the iterative use of the quantum singular value search algorithm. We find out several parameters, such as the length and min-entropy of the punctured keystream, the iterations, and the error in the search algorithm, and all of them can influence the resulting complexity. When these parameters are chosen properly, a better complexity can be obtained than Grover algorithm. Our search model can apply to any typical symmetric cipher. To demonstrate the power, we apply our model to analyze block cipher AES family, stream ciphers Grain-128 and ZUC-like. The resulting complexity of AES-128 is $\tilde{\mathcal O}(2^{30.8})$, $\tilde{\mathcal O}(2^{32.0})$ of AES-192, $\tilde{\mathcal O}(2^{32.7})$ of AES-256, $\tilde{\mathcal O}(2^{27.5})$ of Grain-128, $\tilde{\mathcal O}(2^{39.8})$ of ZUC-128, and $\tilde{\mathcal O}(2^{44.6})$ of ZUC-256. Our results show that increasing the length of key seeds is not an effective way anymore to resist the quantum search attacks, and it is necessary to propose new measures to ensure the post-quantum security of symmetric ciphers.

To be useful and widely accepted, automated contact tracing / expo- sure notification schemes need to solve two problems at the same time: they need to protect the privacy of users while also protecting the users’ from the behavior of a malicious adversary who may potentially cause a false alarm. In this paper, we provide, for the first time, an exposure notification construction that guarantees the same levels of privacy as ex- isting schemes (notably, the same as CleverParrot of [CKL+20]), which also provides the following integrity guarantees: no malicious user can cause exposure warnings in two locations at the same time; and any up- loaded exposure notifications must be recent, and not previously used. We provide these integrity guarantees while staying efficient by only re- quiring a single broadcast message to complete multiple contacts. Also, a user’s upload remains linear in the number of contacts, similar to other schemes. Linear upload complexity is achieved with a new primitive: zero knowledge subset proofs over commitments. Our integrity guarantees are achieved with a new primitive as well: set commitments on equivalence classes. Both of which are of independent interest.

We build quantum cryptosystems that support publicly-verifiable deletion from standard cryptographic assumptions. We introduce target-collapsing as a weakening of collapsing for hash functions, analogous to how second preimage resistance weakens collision resistance; that is, target-collapsing requires indistinguishability between superpositions and mixtures of preimages of an honestly sampled image. We show that target-collapsing hashes enable publicly-verifiable deletion (PVD), proving conjectures from [Poremba, ITCS'23] and demonstrating that the Dual-Regev encryption (and corresponding fully homomorphic encryption) schemes support PVD under the LWE assumption. We further build on this framework to obtain a variety of primitives supporting publicly-verifiable deletion from weak cryptographic assumptions, including: - Commitments with PVD assuming the existence of injective one-way functions, or more generally, almost-regular one-way functions. Along the way, we demonstrate that (variants of) target-collapsing hashes can be built from almost-regular one-way functions. - Public-key encryption with PVD assuming trapdoored variants of injective (or almost-regular) one-way functions. We also demonstrate that the encryption scheme of [Hhan, Morimae, and Yamakawa, Eurocrypt'23] based on pseudorandom group actions has PVD. - $X$ with PVD for $X \in \{$attribute-based encryption, quantum fully-homomorphic encryption, witness encryption, time-revocable encryption$\}$, assuming $X$ and trapdoored variants of injective (or almost-regular) one-way functions.

We introduce Lurk, a new LISP-based programming language for zk-SNARKs. Traditional approaches to programming over zero-knowledge proofs require compiling the desired computation into a flat circuit, imposing serious constraints on the size and complexity of computations that can be achieved in practice. Lurk programs are instead provided as data to the universal Lurk interpreter circuit, allowing the resulting language to be Turing-complete without compromising the size of the resulting proof artifacts. Our work describes the design and theory behind Lurk, along with detailing how its implementation of content addressing can be used to sidestep many of the usual concerns of programming zero-knowledge proofs.

During the last decade, there has been a stunning progress in the domain of AI with adoption in both safety-critical and security-critical applications. A key requirement for this is highly trained Machine Learning (ML) models, which are valuable Intellectual Property (IP) of the respective organizations. Naturally, these models have become targets for model recovery attacks through side-channel leakage. However, majority of the attacks reported in literature are either on simple embedded devices or assume a custom Vivado HLS based FPGA accelerator. On the other hand, for commercial neural network accelerators, such as Google TPU, Intel Compute Stick and NVDLA, there are relatively fewer successful attacks. Focussing on that direction, in this work, we study the vulnerabilities of commercial open-source accelerator NVDLA and present the first successful model recovery attack. For this purpose, we use power and timing side-channel leakage information from Convolutional Neural Network (CNN) models to train CNN based attack models. Utilizing these attack models, we demonstrate that even with a highly pipelined architecture, multiple parallel execution in the accelerator along with Linux OS running tasks in the background, recovery of number of layers, kernel sizes, output neurons and distinguishing different layers, is possible with very high accuracy. Our solution is fully automated, and portable to other hardware neural networks, thus presenting a greater threat towards IP protection.