highlighting a looming cyber threat emanating from fast developing artificial intelligence. This strategic threat is further magnified with the advent of quantum computers. AI and quantum-AI (QAI) represent a totally new and effective vector of cryptanalytic attack. Much as modern AI successfully completes browser search phrases, so it is increasingly capable of guessing a rather narrow a-priori list of plausible plaintexts. This guessing is most effective over device cryptography where the message space is limited. Matching these guesses with the captured ciphertext will greatly accelerate the code breaking process. We never faced such a plaintext-originated attack on a strategic level, and never had to prepare for it. Now we do. Proposing to apply a well-known martial art tactics: using the opponent's strength against them: constructing ciphertexts that would provide false answers to the AI attacker and lead them astray. We are achieving this defensive measure by pivoting away from the norm of small, known-size key and pattern-loaded ciphers. Using instead large keys of secret size, augmented with ad-hoc unilateral randomness of unbound limits, and deploying a pattern-devoid algorithm with a remarkably low computational burden, so it can easily handle very large keys. Thereby we achieve large as desired unicity distances. This strategy has become feasible just when the AI threat looms. It exploits three new technologies coming together: (i) non-algorithmic randomness, (ii) very large and inexpensive memory chips, and (iii) high throughout communication networks. These pattern-devoid, randomness rich ciphers also turn up to be an important option in the toolbox NIST prepares to meet the quantum challenge. Avoiding the computational load of mainstay ciphers, AIR-cryptography presents itself as the ciphers of choice for medical, military and other battery-limited devices for which data security is paramount. In summary: we are pointing out a fast emerging cyber challenges, and laying out a matching cryptographic answer.

While the round function of the AEGIS authenticated encryption algorithms is highly parallelizable, their mode of operation is not. We introduce two new modes to overcome that limitation: AEGIS-128X and AEGIS-256X, that require minimal changes to existing implementations and retain the security properties of AEGIS-128L and AEGIS-256.

From hashing and commitment schemes to Fiat-Shamir and encryption, hash functions are everywhere in zero-knowledge proofsystems (ZKPs), and minor performance changes in ``vanilla'' implementations can translate in major discrepancies when the hash is processed as a circuit within the proofsystem. Protocol designers have resorted to a number of techniques and custom modes to optimize hash functions for ZKPs settings, but so far without a single established, well-studied construction. To address this need, we define the Sponge API for Field Elements (SAFE), a unified framework for permutation-based schemes (including AEAD, Sigma, PRNGs, and so on). SAFE eliminates the performance overhead, is pluggable in any field-oriented protocol, and is suitable for any permutation algorithm. SAFE is implemented in Filecoin's Neptune hash framework, {which is} our reference implementation (in Rust). SAFE is also being integrated in other prominent ZKP projects. This report specifies SAFE and describes some use cases. Among other improvements, our construction is among the first to store the protocol metadata in the sponge inner part in a provably secure way, which may be of independent interest to the sponge use cases outside of ZKP.

Secure computation is of critical importance to not only the DoD, but across financial institutions, healthcare, and anywhere personally identifiable information (PII) is accessed. Traditional security techniques require data to be decrypted before performing any computation. When processed on untrusted systems the decrypted data is vulnerable to attacks to extract the sensitive information. To address these vulnerabilities Fully Homomorphic Encryption (FHE) keeps the data encrypted during computation and secures the results, even in these untrusted environments. However, FHE requires a significant amount of computation to perform equivalent unencrypted operations. To be useful, FHE must significantly close the computation gap (within 10x) to make encrypted processing practical. To accomplish this ambitious goal the TREBUCHET project is leading research and development in FHE processing hardware to accelerate deep computations on encrypted data, as part of the DARPA MTO Data Privacy for Virtual Environments (DPRIVE) program. We accelerate the major secure standardized FHE schemes (BGV, BFV, CKKS, FHEW, etc.) at >=128-bit security while integrating with the open-source PALISADE and OpenFHE libraries currently used in the DoD and in industry. We utilize a novel tile-based chip design with highly parallel ALUs optimized for vectorized 128b modulo arithmetic. The TREBUCHET coprocessor design provides a highly modular, flexible, and extensible FHE accelerator for easy reconfiguration, deployment, integration and application on other hardware form factors, such as System-on-Chip or alternate chip areas

We provide security foundations for SAFE, a recently introduced API framework for sponge-based hash functions tailored to prime-field-based protocols. SAFE aims to provide a robust and foolproof interface, has been implemented in the Neptune hash framework and some zero-knowledge proof projects, but currently lacks any security proof. In this work we identify the SAFECore as versatile variant sponge construction underlying SAFE, we prove indifferentiability of SAFECore for all (binary and prime) fields up to around $|\mathbb{F}_p|^{c/2}$ queries, where $\mathbb{F}_p$ is the underlying field and $c$ the capacity, and we apply this security result to various use cases. We show that the SAFE-based protocols of plain hashing, authenticated encryption, verifiable computation, non-interactive proofs, and commitment schemes are secure against a wide class of adversaries, including those dealing with multiple invocations of a sponge in a single application. Our results pave the way of using SAFE with the full taxonomy of hash functions, including SNARK-, lattice-, and x86-friendly hashes.

The generalized inverses of systematic non-square binary matrices have applications in mathematics, channel coding and decoding, navigation signals, machine learning, data storage, and cryptography, such as the McEliece and Niederreiter public-key cryptosystems. A systematic non-square (n−k)×n matrix H, n > k, has 2 power k×(n−k) different generalized inverse matrices. This paper presents an algorithm for generating these matrices and compares it with two well-known methods, i.e. Gauss-Jordan elimination and Moore-Penrose. A random generalized inverse matrix construction method is given, which has a lower execution time than the Gauss-Jordan elimination and Moore-Penrose approaches. This paper also expands the novel idea to non-systematic non-square binary matrices and provides an application in public-key cryptosystems.

Besides the U.S. NIST standard SHA-3(Keccak), another sponge-based primitive Ascon was selected as the NIST standard for lightweight applications, recently. Exploring the security against attacks on the sponge-based hash functions is very important. At EUROCRYPT 2023, Qin et al. introduced the MitM preimage attack framework and the automatic tools for Keccak, Ascon, and Xoodyak. In this paper, we extend Qin et al.'s MitM attack framework into collision attack and also develop various techniques to improve the automatic tools for both preimage and collision attacks. We introduce a novel initial structure called weak-diffusion structure that enjoys many more degrees of freedom to build the blue/red neutral sets than Qin et al.'s. In addition, a more flexible condition scheme is introduced to reduce the diffusion of variables. To further accelerate the solving of automatic model, we propose a heuristic two-stage searching strategy, which first finds many blue neutral sets with naturally weak-diffusion properties, and then solves different automatic models with different blue neutral sets prefixed. Also symmetry property of Keccak is applied to speed up the search. At last, we introduce the first collision attack on 4-round Keccak-512. Besides, the first MitM-based preimage attack on 4-round Keccak-384 is found that outperforms all previous attacks, while Qin et al. only found attack on Keccak-512. Moreover, we find collision attacks on reduced Xoodyak and Ascon with 1-2 rounds improvements than before. The complexities of preimage attacks on reduced Xoodyak and Ascon are also improved.

Lattice-based cryptography has laid the foundation of various modern-day cryptosystems that cater to several applications, including post-quantum cryptography. For structured lattice-based schemes, polynomial arithmetic is a fundamental part. In several instances, the performance optimizations come from implementing compact multipliers due to the small range of the secret polynomial coefficients. However, this optimization does not easily translate to side-channel protected implementations since masking requires secret polynomial coefficients to be distributed over a large range. In this work, we address this problem and propose two novel generalized techniques, one for the number theoretic transform (NTT) based and another for the non-NTT-based polynomial arithmetic. Both these proposals enable masked polynomial multiplication while utilizing and retaining the small secret property. For demonstration, we used the proposed technique and instantiated masked multipliers for schoolbook as well as NTT-based polynomial multiplication. Both of these can utilize the compact multipliers used in the unmasked implementations. The schoolbook multiplication requires an extra polynomial accumulation along with the two polynomial multiplications for a first-order protected implementation. However, this cost is nothing compared to the area saved by utilizing the existing cheap multiplication units. We also extensively test the side-channel resistance of the proposed design through TVLA to guarantee its first-order security.

A distributed oblivious RAM (DORAM) is a method for accessing a secret-shared memory while hiding the accessed locations. DORAMs are the key tool for secure multiparty computation (MPC) for RAM programs that avoids expensive RAM-to-circuit transformations. We present new and improved 3-party DORAM protocols. For a logical memory of size $N$ and for each logical operation, our DORAM requires $O(\log N)$ local CPU computation steps. This is known to be asymptotically optimal. Our DORAM satisfies passive security in the honest majority setting. Our technique results with concretely-efficient protocols and does not use expensive cryptography (such as re-randomizable or homomorphic encryption). Specifically, our DORAM is 25X faster than the known most efficient DORAM in the same setting. Lastly, we extend our technique to handle malicious attackers at the expense of using slightly larger blocks (i.e., $\omega(\log^2 N)$ vs. $\Omega(\log N)$). To the best of our knowledge, this is the first concretely-efficient maliciously secure DORAM. Technically, our construction relies on a novel concretely-efficient 3-party oblivious permutation protocol. We combine it with efficient non-oblivious hashing techniques (i.e., Cuckoo hashing) to get a distributed oblivious hash table. From this, we build a full-fledged DORAM using a distributed variant of the hierarchical approach of Goldreich and Ostrovsky (J. ACM '96). These ideas, and especially the permutation protocol, are of independent interest.

Proof of Storage-time (PoSt) is a cryptographic primitive that enables a server to demonstrate non-interactive continuous avail- ability of outsourced data in a publicly verifiable way. This notion was first introduced by Filecoin to secure their Blockchain-based decentral- ized storage marketplace, using expensive SNARKs to compact proofs. Recent work [2] employs the notion of trapdoor delay function to address the problem of compact PoSt without SNARKs. This approach however entails statefulness and non-transparency, while it requires an expensive pre-processing phase by the client. All of the above renders their solution impractical for decentralized storage marketplaces, leaving the stateless trapdoor-free PoSt with reduced setup costs as an open problem. In this work, we present stateless and transparent PoSt constructions using probabilistic sampling and a new Merkle variant commitment. In the process of enabling adjustable prover difficulty, we then propose a multi- prover construction to diminish the CPU work each prover is required to do. Both schemes feature a fast setup phase and logarithmic verification time and bandwidth with the end-to-end setup, prove, and verification costs lower than the existing solutions

We revisit the problem of {\em reusable} non-interactive secure computation (NISC). A standard NISC protocol for a sender-receiver functionality $f$ enables the receiver to encrypt its input $x$ such that any sender, on input $y$, can send back a message revealing only $f(x,y)$. Security should hold even when either party can be malicious. A {\em reusable} NISC protocol has the additional feature that the receiver's message can be safely reused for computing multiple outputs $f(x,y_i)$. Here security should hold even when a malicious sender can learn partial information about the honest receiver's outputs in each session. We present the first reusable NISC protocol for general functions $f$ that only makes a {\em black-box} use of any two-message oblivious transfer protocol, along with a random oracle. All previous reusable NISC protocols either made a non-black-box use of cryptographic primitives (Cachin et al., ICALP 2002) or alternatively required a stronger arithmetic variant of oblivious transfer and were restricted to $f$ in $\mathsf{NC}^1$ or similar classes (Chase et al., Crypto 2019). Our result is obtained via a general compiler from standard NISC to reusable NISC that makes use of special type of honest-majority protocols for secure multiparty computation. Finally, we extend the above main result to reusable {\em two-sided} NISC, in which two parties can encrypt their inputs in the first round and then reveal different functions of their inputs in multiple sessions. This extension either requires an additional (black-box) use of additively homomorphic commitment or alternatively requires the parties to maintain a state between sessions.

Secure computation enables mutually distrusting parties to jointly compute a function on their secret inputs, while revealing nothing beyond the function output. A long-running challenge is understanding the required communication complexity of such protocols---in particular, when communication can be sublinear in the circuit representation size of the desired function. For certain functions, such as Private Information Retrieval (PIR), this question extends to even sublinearity in the input size. We develop new techniques expanding the set of computational assumptions for sublinear communication in both settings: 1) [Circuit size] We present sublinear-communication protocols for secure evaluation of general layered circuits, given any 2-round rate-1 batch oblivious transfer (OT) protocol with a particular ``decomposability'' property. In particular, this condition can be shown to hold for the recent batch OT protocols of (Brakerski et al. Eurocrypt 2022), in turn yielding a new sublinear secure computation feasibility result: from Quadratic Residuosity (QR) together with polynomial-noise-rate Learning Parity with Noise (LPN). Our approach constitutes a departure from existing paths toward sublinear secure computation, all based on fully homomorphic encryption or homomorphic secret sharing. 2) [Input size.] We construct single-server PIR based on the Computational Diffie-Hellman (CDH) assumption, with polylogarithmic communication in the database input size $n$. Previous constructions from CDH required communication $\Omega(n)$. In hindsight, our construction comprises of a relatively simple combination of existing tools from the literature.

As zero-knowledge proofs gain increasing adoption, the cryptography community has designed domain-specific languages (DSLs) that facilitate the construction of zero-knowledge proofs (ZKPs). Many of these DSLs, such as Circom, facilitate the construction of arithmetic circuits, which are essentially polynomial equations over a finite field. In particular, given a program in a zero-knowledge proof DSL, the compiler automatically produces the corresponding arithmetic circuit. However, a common and serious problem is that the generated circuit may be underconstrained, either due to a bug in the program or a bug in the compiler itself. Underconstrained circuits admit multiple witnesses for a given input, so a malicious party can generate bogus witnesses, thereby causing the verifier to accept a proof that it should not. Because of the increasing prevalence of such arithmetic circuits in blockchain applications, several million dollars worth of cryptocurrency have been stolen due to underconstrained arithmetic circuits. Motivated by this problem, we propose a new technique for finding ZKP bugs caused by underconstrained polynomial equations over finite fields. Our method performs semantic reasoning over the finite field equations generated by the compiler to prove whether or not each signal is uniquely determined by the input. Our proposed approach combines SMT solving with lightweight uniqueness inference to effectively reason about underconstrained circuits. We have implemented our proposed approach in a tool called $\mathbf{\mathsf{QED}^2}$ and evaluate it on 163 Circom circuits. Our evaluation shows that $\mathbf{\mathsf{QED}^2}$ can successfully solve 70\% of these benchmarks, meaning that it either verifies the uniqueness of the output signals or finds a pair of witnesses that demonstrate non-uniqueness of the circuit. Furthermore, $\mathbf{\mathsf{QED}^2}$ has found 8 previously unknown vulnerabilities in widely-used circuits.

The global supply chain involves multiple independent entities, and potential adversaries can exploit different attack vectors to steal proprietary designs and information. As a result, intellectual property (IP) owners and consumers have reasons to keep their designs private. Without a trusted third party, this mutual mistrust can lead to a deadlock where IP owners are unwilling to disclose their IP core before a financial agreement is reached, while consumers need assurance that the proprietary design will meet their integration needs without compromising the confidentiality of their test vectors. To address this challenge, we introduce an efficient framework called MPloC that resolves this deadlock by allowing owners and consumers to jointly evaluate the target design with consumer-supplied test vectors while preserving the privacy of both the IP core and the inputs. MPloC is the first work that combines secure multiparty computation (MPC) and logic-locking techniques to accomplish these goals. Our approach supports both semi-honest and malicious security models to allow users to balance stronger security guarantees with performance. We compare our approach to existing state-of-the-art works that utilize homomorphic encryption across several benchmarks and report runtime improvements of more than two orders of magnitude.

Tampering attack is the act of deliberately modifying the codeword to produce another codeword of a related message. The main application is to find out the original message from the codeword. Non-malleable codes are introduced to protect the message from such attack. Any tampering attack performed on the message encoded by non-malleable codes, guarantee that output is either completely unrelated or original message. It is useful mainly in the situation when privacy and integrity of the message is important rather than correctness. Unfortunately, standard version of non-malleable codes are used for one-time tampering attack. In literature, it is shown that non-malleable codes can be designed from authenticated encryption. But, such construction does not provide security when an adversary tampers the codeword more than once. Later, continuously non-malleable codes are constructed where an attacker can tamper the message for polynomial number of times. In this work, we propose a construction of continuously non-malleable code from authenticated encryption in 2-split-state model. Our construction provides security against polynomial number of tampering attacks and non-malleability property is preserved. The security of proposed continuously non-malleable code reduces to the security of underlying leakage resilient storage when tampering experiment triggers self-destruct.

The secret key of any encryption scheme that are stored in secure memory of the hardwired devices can be tampered using fault attacks. The usefulness of tampering attack is to recover the key by altering some regions of the memory. Such attack may also appear when the device is stolen or viruses has been introduced. Non-malleable codes are used to protect the secret information from tampering attacks. The secret key can be encoded using non-malleable codes rather than storing it in plain form. An adversary can apply some arbitrary tampering function on the encoded message but it guarantees that output is either completely unrelated or original message. In this work, we propose a computationally secure non-malleable code from leakage resilient authenticated encryption along with 1-more extractable hash function in split-state model with no common reference string (CRS) based trusted setup. Earlier constructions of non-malleable code cannot handle the situation when an adversary has access to some arbitrary decryption leakage (i.e., during decoding of the codeword) function to get partial information about the codeword. In this scenario, the proposed construction is capable of handling such decryption leakages along with tampering attacks.

The wave of attacks by Castryck and Decru (Eurocrypt, 2023), Maino, Martindale, Panny, Pope and Wesolowski (Eurocrypt, 2023) and Robert (Eurocrypt, 2023), highlight the destructive facet of calculating power-smooth degree isogenies between higher-dimensional abelian varieties in isogeny-based cryptography. Despite those recent attacks, there is still interest in using isogenies but for building protocols on top of higher-dimensional abelian varieties. Examples of such protocols are Public-Key Encryption, Key Encapsulation Mechanism, Verifiable Delay Function, Verifiable Random Function, and Digital Signatures. This work abstracts and proposes a generalization of the strategy technique by Jao, De Feo and Plût (Journal of Mathematical Cryptology, 2014) to give an efficient generic algorithm for computing isogenies between higher-dimensional abelian varieties with kernels being maximal isotropic of power-smooth degree. To illustrate the impact of using such strategy technique, we draft our experiments on the computation of isogenies over two-dimensional abelian varieties determined by a maximal isotropic subgroup of torsion with a power of two or three. Our experiments illustrate a speed-up of 1.25x faster than the state-of-the-art (about 20% of savings).

Despite recent breakthrough results in attacking SIDH, the CSIDH protocol remains a secure post-quantum key exchange protocol with appealing properties. However, for obtaining efficient CSIDH instantiations one has to resort to small secret keys. In this work, we provide novel methods to analyze small key CSIDH, thereby introducing the representation method ---that has been successfully applied for attacking small secret keys in code- and lattice-based schemes--- also to the isogeny-based world. We use the recently introduced Restricted Effective Group Actions ($\mathsf{REGA}$) to illustrate the analogy between CSIDH and Diffie-Hellman key exchange. This framework allows us to introduce a $\mathsf{REGA}\text{-}\mathsf{DLOG}$ problem as a level of abstraction to computing isogenies between elliptic curves, analogous to the classic discrete logarithm problem. This in turn allows us to study $\mathsf{REGA}\text{-}\mathsf{DLOG}$ with ternary key spaces such as $\{-1, 0, 1\}^n, \{0,1,2\}^n$ and $\{-2,0,2\}^n$, which lead to especially efficient, recently proposed CSIDH instantiations. The best classic attack on these key spaces is a Meet-in-the-Middle algorithm that runs in time $3^{0.5 n}$, using also $3^{0.5 n}$ memory. We first show that $\mathsf{REGA}\text{-}\mathsf{DLOG}$ with ternary key spaces $\{0,1,2\}^n$ or $\{-2,0,2\}^n$ can be reduced to the ternary key space $\{-1,0,1\}^n$. We further provide a heuristic time-memory tradeoff for $\mathsf{REGA}\text{-}\mathsf{DLOG}$ with keyspace $\{-1,0,1\}^n$ based on Parallel Collision Search with memory requirement $M$ that under standard heuristics runs in time $3^{0.75 n}/M^{0.5}$ for all $M \leq 3^{n/2}$. We then use the representation technique to heuristically improve to $3^{0.675n}/M^{0.5}$ for all $M \leq 3^{0.22 n}$, and further provide more efficient time-memory tradeoffs for all $M \leq 3^{n/2}$. Although we focus in this work on $\mathsf{REGA}\text{-}\mathsf{DLOG}$ with ternary key spaces for showing its efficacy in providing attractive time-memory tradeoffs, we also show how to use our framework to analyze larger key spaces $\{-m, \ldots, m\}^n$ with $m = 2,3$.

Post-Quantum cryptography (PQC), in the past few years, constitutes the main driving force of the quantum resistance transition for security primitives, protocols and tools. TLS is one of the widely used security protocols that needs to be made quantum safe. However, PQC algorithms integration into TLS introduce various implementation overheads compared to traditional TLS that in battery powered embedded devices with constrained resources, cannot be overlooked. While there exist several works, evaluating the PQ TLS execution time overhead in embedded systems there are only a few that explore the PQ TLS energy consumption cost. In this paper, a thorough power/energy consumption evaluation and analysis of PQ TLS 1.3 on embedded systems has been made. A WolfSSL PQ TLS 1.3 custom implementation is used that integrates all the NIST PQC algorithms selected for standardisation as well as 2 out of 3 of those evaluated in NIST Round 4. Also 1 out of 2 of the BSI recommendations have been included. The PQ TLS 1.3 with the various PQC algorithms is deployed in a STM Nucleo evaluation board under a mutual and a unilateral client-server authentication scenario. The power and energy consumption collected results are analyzed in detail. The performed comparisons and overall analysis provide very interesting results indicating that the choice of the PQC algorithms in TLS 1.3 to be deployed on an embedded system may be very different depending on the device use as an authenticated or not authenticated, client or server. Also, the results indicate that in some cases, PQ TLS 1.3 implementations can be equally or more energy consumption efficient compared to traditional TLS 1.3.

Spiking neural networks gain attention due to low power properties and event-based operation, making them suitable for usage in resource constrained embedded devices. Such edge devices allow physical access opening the door for side-channel analysis. In this work, we reverse engineer the parameters of a feed-forward spiking neural network implementation with correlation power analysis. Localized measurements of electro-magnetic emanations enable our attack, despite inherent parallelism and the resulting algorithmic noise of the network. We provide a methodology to extract valuable parameters of integrate-and-fire neurons in all layers, as well as the layer sizes.

Privacy computing is a collection of a series of technical systems that intersect and integrate many disciplines such as cryptography, statistics, artificial intelligence, and computer hardware. On the premise of not exposing the original data, it can realize the fusion, sharing, circulation and calculation of data and its value in a manageable, controllable and measurable way. In the case of ensuring that the data is not leaked, it can achieve the purpose of making the data available and invisible, as well as the conversion and release of data value. We propose a privacy computing algorithm based on polynomial operations based on the unsolvable problem of high-degree polynomial modulo n. Encryptors can encrypt their own private information to generate ciphertext that can be calculated. This ciphertext can support any integer calculation including addition, multiplication, power calculation, etc. Different ciphertexts generated by the same key are fully homomorphic, and addition and multiplication operations can be performed between these ciphertexts. All calculations in our encryption system are carried out with polynomials as the medium, so the calculation efficiency is guaranteed. Our ciphertext can be provided to a third party for processing without revealing the encryption party's key and secret information.

Homomorphic encryption (HE) enables calculating on encrypted data, which makes it possible to perform privacy- preserving neural network inference. One disadvantage of this technique is that it is several orders of magnitudes slower than calculation on unencrypted data. Neural networks are commonly trained using floating-point, while most homomorphic encryption libraries calculate on integers, thus requiring a quantisation of the neural network. A straightforward approach would be to quantise to large integer sizes (e.g., 32 bit) to avoid large quantisation errors. In this work, we reduce the integer sizes of the networks, using quantisation-aware training, to allow more efficient computations. For the targeted MNIST architecture proposed by Badawi et al., we reduce the integer sizes by 33% without significant loss of accuracy, while for the CIFAR architecture, we can reduce the integer sizes by 43%. Implementing the resulting networks under the BFV homomorphic encryption scheme using SEAL, we could reduce the execution time of an MNIST neural network by 80% and by 40% for a CIFAR neural network.

Laconic function evaluation (LFE) allows Alice to compress a large circuit $\mathbf{C}$ into a small digest $\mathsf{d}$. Given Alice's digest, Bob can encrypt some input $x$ under $\mathsf{d}$ in a way that enables Alice to recover $\mathbf{C}(x)$, without learning anything beyond that. The scheme is said to be $laconic$ if the size of $\mathsf{d}$, the runtime of the encryption algorithm, and the size of the ciphertext are all sublinear in the size of $\mathbf{C}$. Until now, all known LFE constructions have ciphertexts whose size depends on the $depth$ of the circuit $\mathbf{C}$, akin to the limitation of $levelled$ homomorphic encryption. In this work we close this gap and present the first LFE scheme (for Turing machines) with asymptotically optimal parameters. Our scheme assumes the existence of indistinguishability obfuscation and somewhere statistically binding hash functions. As further contributions, we show how our scheme enables a wide range of new applications, including two previously unknown constructions: • Non-interactive zero-knowledge (NIZK) proofs with optimal prover complexity. • Witness encryption and attribute-based encryption (ABE) for Turing machines from falsifiable assumptions.

The beautiful work of Applebaum, Ishai, and Kushilevitz [FOCS'11] initiated the study of arithmetic variants of Yao's garbled circuits. An arithmetic garbling scheme is an efficient transformation that converts an arithmetic circuit $C: \mathcal{R}^n \rightarrow \mathcal{R}^m$ over a ring $\mathcal{R}$ into a garbled circuit $\widehat C$ and $n$ affine functions $L_i$ for $i \in [n]$, such that $\widehat C$ and $L_i(x_i)$ reveals only the output $C(x)$ and no other information of $x$. AIK presented the first arithmetic garbling scheme supporting computation over integers from a bounded (possibly exponentially large) range, based on Learning With Errors (LWE). In contrast, converting $C$ into a Boolean circuit and applying Yao's garbled circuit treats the inputs as bit strings instead of ring elements, and hence is not "arithmetic". In this work, we present new ways to garble arithmetic circuits, which improve the state-of-the-art on efficiency, modularity, and functionality. To measure efficiency, we define the rate of a garbling scheme as the maximal ratio between the bit-length of the garbled circuit $|\widehat C|$ and that of the computation tableau $|C|\ell$ in the clear, where $\ell$ is the bit length of wire values (e.g., Yao's garbled circuit has rate $O(\lambda)$). $\bullet$ We present the first constant-rate arithmetic garbled circuit for computation over large integers based on the Decisional Composite Residuosity (DCR) assumption, significantly improving the efficiency of the schemes of Applebaum, Ishai, and Kushilevitz. $\bullet$ We construct an arithmetic garbling scheme for modular computation over $\mathcal{R} = \mathbb{Z}_p$ for any integer modulus $p$, based on either DCR or LWE. The DCR-based instantiation achieves rate $O(\lambda)$ for large $p$. Furthermore, our construction is modular and makes black-box use of the underlying ring and a simple key extension gadget. $\bullet$ We describe a variant of the first scheme supporting arithmetic circuits over bounded integers that are augmented with Boolean computation (e.g., truncation of an integer value, and comparison between two values), while keeping the constant rate when garbling the arithmetic part. To the best of our knowledge, constant-rate (Boolean or arithmetic) garbling was only achieved before using the powerful primitive of indistinguishability obfuscation, or for restricted circuits with small depth.

Quantum key distribution (QKD) allows Alice and Bob to agree on a shared secret key, while communicating over a public (untrusted) quantum channel. Compared to classical key exchange, it has two main advantages: (i) The key is unconditionally hidden to the eyes of any attacker, and (ii) its security assumes only the existence of authenticated classical channels which, in practice, can be realized using Minicrypt assumptions, such as the existence of digital signatures. On the flip side, QKD protocols typically require multiple rounds of interactions, whereas classical key exchange can be realized with the minimal amount of two messages using public-key encryption. A long-standing open question is whether QKD requires more rounds of interaction than classical key exchange. In this work, we propose a two-message QKD protocol that satisfies everlasting security, assuming only the existence of quantum-secure one-way functions. That is, the shared key is unconditionally hidden, provided computational assumptions hold during the protocol execution. Our result follows from a new construction of quantum public-key encryption (QPKE) whose security, much like its classical counterpart, only relies on authenticated classical channels.

The concept of using Lookup Tables (LUTs) instead of Boolean circuits is well-known and been widely applied in a variety of applications, including FPGAs, image processing, and database management systems. In cryptography, using such LUTs instead of conventional gates like AND and XOR results in more compact circuits and has been shown to substantially improve online performance when evaluated with secure multi-party computation. Several recent works on secure floating-point computations and privacy-preserving machine learning inference rely heavily on existing LUT techniques. However, they suffer from either large overhead in the setup phase or subpar online performance. We propose FLUTE, a novel protocol for secure LUT evaluation with good setup and online performance. In a two-party setting, we show that FLUTE matches or even outperforms the online performance of all prior approaches, while being competitive in terms of overall performance with the best prior LUT protocols. In addition, we provide an open-source implementation of FLUTE written in the Rust programming language, and implementations of the Boolean secure two-party computation protocols of ABY2.0 and silent OT. We find that FLUTE outperforms the state of the art by two orders of magnitude in the online phase while retaining similar overall communication.

We propose a variant of the original Boneh, Drijvers, and Neven (Asiacrypt '18) BLS multi-signature aggregation scheme best suited to applications where the full set of potential signers is fixed and known and any subset $I$ of this group can create a multi-signature over a message $m$. This setup is very common in proof-of-stake blockchains where a $2f+1$ majority of $3f$ validators sign transactions and/or blocks and is secure against $\textit{rogue-key}$ attacks without requiring a proof of key possession mechanism. In our scheme, instead of randomizing the aggregated signatures, we have a one-time randomization phase of the public keys: each public key is replaced by a sticky randomized version (for which each participant can still compute the derived private key). The main benefit compared to the original Boneh at al. approach is that since our randomization process happens only once and not per signature we can have significant savings during aggregation and verification. Specifically, for a subset $I$ of $t$ signers, we save $t$ exponentiations in $\mathbb{G}_2$ at aggregation and $t$ exponentiations in $\mathbb{G}_1$ at verification or vice versa, depending on which BLS mode we prefer: $\textit{minPK}$ (public keys in $\mathbb{G}_1$) or $\textit{minSig}$ (signatures in $\mathbb{G}_1$). Interestingly, our security proof requires a significant departure from the co-CDH based proof of Boneh at al. When $n$ (size of the universal set of signers) is small, we prove our protocol secure in the Algebraic Group and Random Oracle models based on the hardness of the Discrete Log problem. For larger $n$, our proof also requires the Random Modular Subset Sum (RMSS) problem.

Using the representation of bent functions by bent rectangles, that is, special matrices with restrictions on columns and rows, we obtain an upper bound on the number of bent functions that improves previously known bounds in a practical range of dimensions. The core of our method is the following fact based on the recent observation by Potapov (arXiv:2107.14583): a 2-row bent rectangle is completely determined by one of its rows and the remaining values in slightly more than half of the columns.

Zero-correlation linear attack is a powerful attack of block ciphers, the lower number of rounds (LNR) which no its distinguisher (named zero-correlation linear approximation, ZCLA) exists reflects the ability of a block cipher against the zero-correlation linear attack. However, due to the large search space, showing there are no ZCLAs exist for a given block cipher under a certain number of rounds is a very hard task. Thus, present works can only prove there no ZCLAs exist in a small search space, such as 1-bit/nibble/word input and output active ZCLAs, which still exist very large gaps to show no ZCLAs exist in the whole search space. In this paper, we propose the meet-in-the-middle method and double-collision method to show there no ZCLAs exist in the whole search space. The basic ideas of those two methods are very simple, but they work very effectively. As a result, we apply those two methods to AES, Midori64, and ARIA, and show that there no ZCLAs exist for $5$-round AES without the last Mix-Column layer, $7$-round Midori64 without the last Mix-Column layer, and $5$-round ARIA without the last linear layer. As far as we know, our method is the first automatic method that can be used to show there no ZCLAs exist in the whole search space, which can provide sufficient evidence to show the security of a block cipher against the zero-correlation linear attack in the distinguishers aspect, this feature is very useful for designing block ciphers.

In this article we study the Algebraic Immunity (AI) of Weightwise Perfectly Balanced (WPB) functions. After showing a lower bound on the AI of two classes of WPB functions from the previous literature, we prove that the minimal AI of a WPB $n$-variables function is constant, equal to $2$ for $n\ge 4$ . Then, we compute the distribution of the AI of WPB function in $4$ variables, and estimate the one in $8$ and $16$ variables. For these values of $n$ we observe that a large majority of WPB functions have optimal AI, and that we could not obtain an AI-$2$ WPB function by sampling at random. Finally, we address the problem of constructing WPB functions with bounded algebraic immunity, exploiting a construction from 2022 by Gini and Méaux. In particular, we present a method to generate multiple WPB functions with minimal AI, and we prove that the WPB functions with high nonlinearity exhibited by Gini and Méaux also have minimal AI. We conclude with a construction giving WPB functions with lower bounded AI, and give as example a family with all elements with AI at least $n/2-\log(n)+1$.

Increasing deployment of advanced zero-knowledge proof systems, especially zkSNARKs, has raised critical questions about their security against real-world attacks. Two classes of attacks of concern in practice are adaptive soundness attacks, where an attacker can prove false statements by choosing its public input after generating a proof, and malleability attacks, where an attacker can use a valid proof to create another valid proof it could not have created itself. Prior work has shown that simulation-extractability (SIM-EXT), a strong notion of security for proof systems, rules out these attacks. In this paper, we prove that two transparent, discrete-log-based zkSNARKs, Spartan and Bulletproofs, are simulation-extractable (SIM-EXT) in the random oracle model if the discrete logarithm assumption holds in the underlying group. Since these assumptions are required to prove standard security properties for Spartan and Bulletproofs, our results show that SIM-EXT is, surprisingly, "for free" with these schemes. Our result is the first SIM-EXT proof for Spartan and encompasses both linear- and sublinear-verifier variants. Our result for Bulletproofs encompasses both the aggregate range proof and arithmetic circuit variants, and is the first to not rely on the algebraic group model (AGM), resolving an open question posed by Ganesh et al. (EUROCRYPT '22). As part of our analysis, we develop a generalization of the tree-builder extraction theorem of Attema et al. (TCC '22), which may be of independent interest.

Tremendous efforts have been made to improve the efficiency of secure Multi-Party Computation (MPC), which allows n ≥ 2 parties to jointly evaluate a target function without leaking their own private inputs. It has been confirmed by previous research that Three-Party Computation (3PC) and outsourcing computations to GPUs can lead to huge performance improvement of MPC in computationally intensive tasks such as Privacy-Preserving Machine Learning (PPML). A natural question to ask is whether super-linear performance gain is possible for a linear increase in resources. In this paper, we give an affirmative answer to this question. We propose Force, an extremely efficient Four-Party Computation (4PC) system for PPML. To the best of our knowledge, each party in Force enjoys the least number of local computations, smallest graphic memory consumption and lowest data exchanges between parties. This is achieved by introducing a new sharing type X-share along with MPC protocols in privacy-preserving training and inference that are semi-honest secure in the honest-majority setting. By comparing the results with state-of-the-art research, we showcase that Force is sound and extremely efficient, as it can improve the PPML performance by a factor of 2 to 38 compared with other latest GPU-based semi-honest secure systems, such as Piranha (including SecureML, Falcon, FantasticFour), CryptGPU and CrypTen.

We revisit batch signatures (previously considered in a draft RFC, and used in multiple recent works), where a single, potentially expensive, "inner" digital signature authenticates a Merkle tree constructed from many messages. We formalise a construction and prove its unforgeability and privacy properties. We also show that batch signing allows us to scale slow signing algorithms, such as those recently selected for standardisation as part of NIST's post-quantum project, to high throughput, with a mild increase in latency. For the example of Falcon-512 in TLS, we can increase the amount of connections per second by a factor 3.2x, at the cost of an increase in the signature size by ~14% and the median latency by ~25%, where both are ran on the same 30 core server. We also discuss applications where batch signatures allow us to increase throughput and to save bandwidth. For example, again for Falcon-512, once one batch signature is available, the additional bandwidth for each of the remaining N-1 is only 82 bytes.

Blind signatures were originally introduced by Chaum (CRYPTO ’82) in the context of privacy-preserving electronic payment systems. Nowadays, the cryptographic primitive has also found applications in anonymous credentials and voting systems. However, many practical blind signature schemes have only been analysed in the game-based setting where a single signer is present. This is somewhat unsatisfactory as blind signatures are intended to be deployed in a setting with many signers. We address this in the following ways: – We formalise two variants of one-more-unforgeability of blind signatures in the Multi-Signer Setting. – We show that one-more-unforgeability in the Single-Signer Setting translates straightforwardly to the Multi-Signer Setting with a reduction loss proportional to the number of signers. – We identify a class of blind signature schemes which we call Key-Convertible where this reduction loss can be traded for an increased number of signing sessions in the Single-Signer Setting and show that many practical blind signature schemes such as blind BLS, blind Schnorr, blind Okamoto-Schnorr as well as two pairing-free, ROS immune schemes by Tessaro and Zhu (Eurocrypt’22) fulfil this property. – We further describe how the notion of key substitution attacks (Menezes and Smart, DCC’04) can be translated to blind signatures and provide a generic transformation of how they can be avoided.

We construct quantum public-key encryption from one-way functions. In our construction, public keys are quantum, but ciphertexts are classical. Quantum public-key encryption from one-way functions (or weaker primitives such as pseudorandom function-like states) are also proposed in some recent works [Morimae-Yamakawa, eprint:2022/1336; Coladangelo, eprint:2023/282; Barooti-Grilo-Malavolta-Sattath-Vu-Walter, eprint:2023/877]. However, they have a huge drawback: they are secure only when quantum public keys can be transmitted to the sender (who runs the encryption algorithm) without being tampered with by the adversary, which seems to require unsatisfactory physical setup assumptions such as secure quantum channels. Our construction is free from such a drawback: it guarantees the secrecy of the encrypted messages even if we assume only unauthenticated quantum channels. Thus, the encryption is done with adversarially tampered quantum public keys. Our construction is the first quantum public-key encryption that achieves the goal of classical public-key encryption, namely, to establish secure communication over insecure channels, based only on one-way functions. Moreover, we show a generic compiler to upgrade security against chosen plaintext attacks (CPA security) into security against chosen ciphertext attacks (CCA security) only using one-way functions. As a result, we obtain CCA secure quantum public-key encryption based only on one-way functions.

We provide identity-based signature (IBS) schemes with tight security against adaptive adversaries, in the (classical or quantum) random oracle model (ROM or QROM), in both unstructured and structured lattices, based on the SIS or RSIS assumption. These signatures are short (of size independent of the message length). Our schemes build upon a work from Pan and Wagner (PQCrypto’21) and improve on it in several ways. First, we prove their transformation from non-adaptive to adaptive IBS in the QROM. Then, we simplify the parameters used and give concrete values. Finally, we simplify the signature scheme by using a non-homogeneous relation, which helps us reduce the size of the signature and get rid of one costly trapdoor delegation. On the whole, we get better security bounds, shorter signatures and faster algorithms.

In the average-case $k$-SUM problem, given $r$ integers chosen uniformly at random from $\{0,\ldots,M-1\}$, the objective is to find a "solution" set of $k$ numbers that sum to $0$ modulo $M$. In the dense regime of $M \leq r^k$, where solutions exist with high probability, the complexity of these problems is well understood. Much less is known in the sparse regime of $M\gg r^k$, where solutions are unlikely to exist. In this work, we initiate the study of the sparse regime for $k$-SUM and its variant $k$-XOR, especially their planted versions, where a random solution is planted in a randomly generated instance and has to be recovered. We provide evidence for the hardness of these problems and suggest new applications to cryptography. Our contributions are summarized below. Complexity. First we study the complexity of these problems in the sparse regime and show: - Conditional Lower Bounds. Assuming established conjectures about the hardness of average-case (non-planted) $k$-SUM/$k$-XOR when $M = r^k$, we provide non-trivial lower bounds on the running time of algorithms for planted $k$-SUM when $r^k\leq M\leq r^{2k}$. - Hardness Amplification. We show that for any $M \geq r^k$, if an algorithm running in time $T$ solves planted $k$-SUM/$k$-XOR with success probability $\Omega(1/\text{polylog}(r))$, then there is an algorithm running in time $\tilde{O}(T)$ that solves it with probability $(1-o(1))$. This in particular implies hardness amplification for 3-SUM over the integers, which was not previously known. Technically, our approach departs significantly from existing approaches to hardness amplification, and relies on the locality of the solution together with the group structure inherent in the problem. Additionally, it enables us to assume only mild hardness of these problems for use in applications. - New Reductions and Algorithms. We provide reductions for $k$-SUM/$k$-XOR from search to decision, as well as worst-case and average-case reductions to the Subset Sum problem from $k$-SUM. Additionally, we present a new algorithm for average-case $k$-XOR that is faster than known worst-case algorithms at low densities. Cryptography. We show that by additionally assuming mild hardness of $k$-XOR, we can construct Public Key Encryption (PKE) from a weaker variant of the Learning Parity with Noise (LPN) problem than was known before. In particular, such LPN hardness does not appear to imply PKE on its own -- this suggests that $k$-XOR/$k$-SUM can be used to bridge "minicrypt" and "cryptomania" in some cases, and may be applicable in other settings in cryptography.

The demand for crypto-agility, although dating back for more than two decades, recently started to increase in the light of the expected post-quantum cryptography (PQC) migration. Nevertheless, it started to evolve into a science on its own. Therefore, it is important to establish a unified definition of the notion, as well as its related aspects, scope, and practical applications. This paper presents a literature survey on crypto-agility and discusses respective development efforts categorized into different areas, including requirements, characteristics, and possible challenges. We explore the need for crypto-agility beyond PQC algorithms and security protocols and shed some light on current solutions, existing automation mechanisms, and best practices in this field. We evaluate the state of readiness for crypto-agility, and offer a discussion on the identified open issues. The results of our survey indicate a need for a comprehensive understanding. Further, more agile design paradigms are required in developing new IT systems, and in refactoring existing ones, in order to realize crypto-agility on a broad scale.

This paper introduces Flamingo, a system for secure aggregation of data across a large set of clients. In secure aggregation, a server sums up the private inputs of clients and obtains the result without learning anything about the individual inputs beyond what is implied by the final sum. Flamingo focuses on the multi-round setting found in federated learning in which many consecutive summations (averages) of model weights are performed to derive a good model. Previous protocols, such as Bell et al. (CCS ’20), have been designed for a single round and are adapted to the federated learning setting by repeating the protocol multiple times. Flamingo eliminates the need for the per-round setup of previous protocols, and has a new lightweight dropout resilience protocol to ensure that if clients leave in the middle of a sum the server can still obtain a meaningful result. Furthermore, Flamingo introduces a new way to locally choose the so-called client neighborhood introduced by Bell et al. These techniques help Flamingo reduce the number of interactions between clients and the server, resulting in a significant reduction in the end-to-end runtime for a full training session over prior work. We implement and evaluate Flamingo and show that it can securely train a neural network on the (Extended) MNIST and CIFAR-100 datasets, and the model converges without a loss in accuracy, compared to a non-private federated learning system.

We report several practically-exploitable cryptographic vulnerabilities in the Matrix standard for federated real-time communication and its flagship client and prototype implementation, Element. These, together, invalidate the confidentiality and authentication guarantees claimed by Matrix against a malicious server. This is despite Matrix’ cryptographic routines being constructed from well-known and -studied cryptographic building blocks. The vulnerabilities we exploit differ in their nature (insecure by design, protocol confusion, lack of domain separation, implementation bugs) and are distributed broadly across the different subprotocols and libraries that make up the cryptographic core of Matrix and Element. Together, these vulnerabilities highlight the need for a systematic and formal analysis of the cryptography in the Matrix standard.

Side-channel resistance is one of the primary criteria identified by NIST for use in evaluating candidates in the Lightweight Cryptography (LWC) Standardization process. In Rounds 1 and 2 of this process, when the number of candidates was still substantial (56 and 32, respectively), evaluating this feature was close to impossible. With ten finalists remaining, side-channel resistance and its effect on the performance and cost of practical implementations became of utmost importance. In this paper, we describe a general framework for evaluating the side-channel resistance of LWC candidates using resources, experience, and general practices of the cryptographic engineering community developed over the last two decades. The primary features of our approach are a) self-identification and self-characterization of side-channel security evaluation labs, b) distributed development of protected hardware and software implementations, matching certain high-level requirements and deliverable formats, and c) dynamic and transparent matching of evaluators with implementers in order to achieve the most meaningful and fair evaluation report. After the classes of hardware implementations with similar resistance to side-channel attacks are established, these implementations are comprehensively benchmarked using Xilinx Artix-7 FPGAs. All implementations belonging to the same class are then ranked according to several performance and cost metrics. Four candidates - Ascon, Xoodyak, TinyJAMBU, and ISAP - are selected as offering unique advantages over other finalists in terms of the throughput, area, throughput-to-area ratio, or randomness requirements of their protected hardware implementations.

Predicate inner product functional encryption (P-IPFE) is essentially attribute-based IPFE (AB-IPFE) which additionally hides attributes associated to ciphertexts. In a P-IPFE, a message x is encrypted under an attribute w and a secret key is generated for a pair (y, v) such that recovery of ⟨x, y⟩ requires the vectors w, v to satisfy a linear relation. We call a P-IPFE unbounded if it can encrypt unbounded length attributes and message vectors. • zero predicate IPFE. We construct the first unbounded zero predicate IPFE (UZP-IPFE) which recovers ⟨x,y⟩ if ⟨w,v⟩ = 0. This construction is inspired by the unbounded IPFE of Tomida and Takashima (ASIACRYPT 2018) and the unbounded zero inner product encryption of Okamoto and Takashima (ASIACRYPT 2012). The UZP-IPFE stands secure against general attackers capable of decrypting the challenge ciphertext. Concretely, it provides full attribute-hiding security in the indistinguishability-based semi-adaptive model under the standard symmetric external Diffie-Hellman assumption. • non-zero predicate IPFE. We present the first unbounded non-zero predicate IPFE (UNP-IPFE) that successfully recovers ⟨x, y⟩ if ⟨w, v⟩ ≠ 0. We generically transform an unbounded quadratic FE (UQFE) scheme to weak attribute-hiding UNP-IPFE in both public and secret key settings. Interestingly, our secret key simulation secure UNP-IPFE has succinct secret keys and is constructed from a novel succinct UQFE that we build in the random oracle model. We leave the problem of constructing a succinct public key UNP-IPFE or UQFE in the standard model as an important open problem.

Group signature (GS) schemes are an important primitive in cryptography that provides anonymity and traceability for a group of users. In this paper, we propose a new approach to constructing GS schemes using the homomorphic trapdoor function (HTDF). We focus on constructing an identity-based homomorphic signature (IBHS) scheme using the trapdoor, providing a simpler scheme that has no zero-knowledge proofs. Our scheme allows packing more data into the signatures by elevating the existing homomorphic trapdoor from the SIS assumption to the MSIS assumption to enable packing techniques. Compared to the existing group signature schemes, we provide a straightforward and alternate construction that is efficient and secure under the standard model. Overall, our proposed scheme provides an efficient and secure solution for GS schemes using HTDF.

Despite its popularity, password based authentication is susceptible to various kinds of attacks, such as online or offline dictionary attacks. Employing biometric credentials in the authentication process can strengthen the provided security guarantees, but raises significant privacy concerns. This is mainly due to the inherent variability of biometric readings that prevents us from simply applying a standard hash function to them. In this paper we first propose an ideal functionality for modeling secure, privacy preserving biometric based two-factor authentication in the framework of universal composability (UC). The functionality is of independent interest and can be used to analyze other two-factor authentication protocols. We then present a generic protocol for biometric based two-factor authentication and prove its security (relative to our proposed functionality) in the UC framework. The first factor in our protocol is the possession of a device that stores the required secret keys and the second factor is the user's biometric template. Our construction can be instantiated with function hiding functional encryption, which computes for example the distance of the encrypted templates or the predicate indicating whether the templates are close enough. Our contribution can be split into three parts: - We model privacy preserving biometric based two-factor authentication as an ideal functionality in the UC framework. To the best of our knowledge, this is the first description of an ideal functionality for biometric based two-factor authentication in the UC framework. - We propose a general protocol that uses functional encryption and prove that it UC-realizes our ideal functionality. - We show how to instantiate our framework with efficient, state of the art inner-product functional encryption. This allows the computation of the Euclidean distance, Hamming distance or cosine similarity between encrypted biometric templates. In order to show its practicality, we implemented our protocol and evaluated its performance.

Fully homomorphic encryption (FHE) is a powerful cryptographic technique allowing to perform computation directly over encrypted data. Motivated by the overhead induced by the homomorphic ciphertexts during encryption and transmission, the transciphering technique, consisting in switching from a symmetric encryption to FHE encrypted data was investigated in several papers. Different stream and block ciphers were evaluated in terms of their "FHE-friendliness", meaning practical implementations costs while maintaining sufficient security levels. In this work, we present a first evaluation of hash functions in the homomorphic domain, based on well-chosen block ciphers. More precisely, we investigate the cost of transforming PRINCE, SIMON, SPECK, and LowMC, a set of lightweight block-ciphers into secure hash primitives using well-established hash functions constructions based on block-ciphers, and provide evaluation under bootstrappable FHE schemes. We also motivate the necessity of practical homomorphic evaluation of hash functions by providing several use cases in which the integrity of private data is also required. In particular, our hash constructions can be of significant use in a threshold-homomorphic based protocol for the single secret leader election problem occurring in blockchains with Proof-of-stake consensus. Our experiments showed that using a TFHE implementation of a hash function, we are able to achieve practical runtime, and appropriate security levels (e.g., for PRINCE it takes 1.28 minutes to obtain a 128 bits of hash).

Agrawal et al. (Asiacrypt 2013) proved the discrete Gaussian leftover hash lemma, which states that the linear transformation of the discrete spherical Gaussian is statistically close to the discrete ellipsoid Gaussian. Showing that it is statistically close to the discrete spherical Gaussian, which we call the discrete spherical Gaussian leftover hash lemma (SGLHL), is an open problem posed by Agrawal et al. In this paper, we solve the problem in a weak sense: we show that the distribution of the linear transformation of the discrete spherical Gaussian and the discrete spherical Gaussian are close with respect to the Rényi divergence (RD), which we call the weak SGLHL (wSGLHL). As an application of wSGLHL, we construct a sharper self-reduction of the learning with errors problem (LWE) problem. Applebaum et al. (CRYPTO 2009) showed that linear sums of LWE samples are statistically close to (plain) LWE samples with some unknown error parameter. In contrast, we show that linear sums of LWE samples and (plain) LWE samples with a known error parameter are close with respect to RD. As another application, we weaken the independence heuristic required for the fully homomorphic encryption scheme TFHE.

We propose a new inner product argument (IPA), called TENET, which features sublogarithmic proof size and sublinear verifier without a trusted setup. IPA is a core primitive for various advanced proof systems including range proofs, circuit satisfiability, and polynomial commitment, particularly where a trusted setup is hard to apply. At ASIACRYPT 2022, Kim, Lee, and Seo showed that pairings can be utilized to exceed the complexity barrier of the previous discrete logarithm-based IPA without a trusted setup. More precisely, they proposed two pairing-based IPAs, one with sublogarithmic proof size and the other one with sublinear verifier cost, but they left achieving both complexities simultaneously as an open problem. We investigate the obstacles for this open problem and then provide our solution TENET, which achieves both sublogarithmic proof size and sublinear verifier. We prove the soundness of TENET under the discrete logarithm assumption and double pairing assumption.

Simulation-based formulation of security enables us to naturally capture our intuition for security. However, since the simulation-based formulation is rather complicated, it is convenient to consider alternative simulation-free formulations which are easy to manipulate but can be employed to give the same security as the simulation-based one. So far the indistinguishability-based and comparison-based formulations have been introduced as such ones. Regarding the security for public key encryption, while these three formulations are shown equivalent in most settings, some relations among these formulations of non-malleability under the valid ciphertext condition, in which an adversary fails if it outputs an invalid ciphertext, remain open. This work aims to help to consider the appropriateness of the formulations of security by clarifying the above open relations among the formulations of non-malleable encryption.

Private set intersection (PSI) is a cryptographic primitive that allows two or more parties to learn the intersection of their input sets and nothing else. In this paper, we present a private set intersection protocol based on a new secure multi-party quantum protocol for greatest common divisor (GCD). The protocol is mainly inspired by the recent quantum private set union protocol based on least common multiple by Liu, Yang, and Li. Performance analysis guarantees the correctness and it also shows that the proposed protocols are completely secure in semi-honest model. Moreover, the complexity is proven to be efficient (poly logarithmic) in the size of the input sets.

The hardness of solving the quadratic residuosity problem is the basis for establishing the security of many cryptographic schemes. Two of these are the public key encryption scheme and the identity-based encryption scheme proposed by Cocks. In this paper, we introduce a new computational problem: the problem of distinguishing between the Jacobi symbols of the solutions of a quadratic congruence modulo an RSA integer. We show that the security of the two encryption schemes is equivalent to the hardness of this problem, while the quadratic residuosity problem reduces to this new problem. We then specialize the problem to roots of quadratic residues and establish several computational indistinguishability relationships.

STARK is a widely used transparent proof system that uses low-degree tests for proving the correctness of a computer program. STARK consumes an intermediate representation known as AIR that is more appropriate for programs with a relatively short and structured description. However, an AIR is not able to succinctly express non-equality constraints, leading to the incorporation of unwanted polynomials. We present the eSTARK protocol, a new probabilistic proof that generalizes the STARK family through the introduction of a more generic intermediate representa- tion called eAIR. We describe eSTARK in the polynomial IOP model, which com- bines the optimized version of the STARK protocol with the incorporation of three arguments into the protocol. We also explain various techniques that enhance the vanilla STARK complexity, including optimizations applied to polynomial computa- tions, and analyze the tradeoffs between controlling the constraint degree either at the representation of the AIR or inside the eSTARK itself.

Computationally sound protocol verification tools promise to deliver full-strength cryptographic proofs for security protocols. Unfortunately, current tools lack either modularity or automation. We propose a new approach based on a novel use of information flow and refinement types for sound cryptographic proofs. Our framework, Owl, allows type-based modular descriptions of security protocols, wherein disjoint subprotocols can be programmed and automatically proved secure separately. We give a formal security proof for Owl via a core language which supports standard symmetric and asymmetric primitives, Diffie-Hellman operations, and hashing via random oracles. We also implement a type checker for Owl along with a prototype extraction mechanism to Rust, and evaluate it on 14 case studies, including (simplified forms of) SSH key exchange and Kerberos.

Blockchain security relies on incentives to ensure participants, called miners, cooperate and behave as the protocol dictates. Such protocols have a security threshold – a miner whose relative computational power is larger than the threshold can deviate to improve her revenue. Moreover, blockchain participants can behave in a petty compliant manner: usually follow the protocol, but deviate to increase revenue when deviation cannot be distinguished externally from the prescribed behavior. The effect of petty compliant miners on the security threshold of blockchains is not well understood. Due to the complexity of the analysis, it remained an open question since Carlsten et al. identified it in 2016. In this work, we use deep Reinforcement Learning (RL) to analyze how a rational miner performs selfish mining by deviating from the protocol to maximize revenue when petty compliant miners are present. We find that a selfish miner can exploit petty compliant miners to increase her revenue by bribing them. Our method reveals that the security threshold is lower when petty compliant miners are present. In particular, with parameters estimated from the Bitcoin blockchain, we find the threshold drops from the known value of 25% to only 21% (or 19%) when 50% (or 75%) of the other miners are petty compliant. Hence, our deep RL analysis puts the open question to rest; the presence of petty compliant miners exacerbates a blockchain’s vulnerability to selfish mining and is a major security threat.

We propose the first aggregate signature scheme such that: (1) its security is based on the standard lattice assumptions in the random oracle model; (2) the aggregate signature size is logarithmic; (3) it is not one-time; and (4) it supports non-interactive aggregation. To obtain such a scheme, we combine the most compact SNARK (Succinct Non-interactive ARgument of Knowledge) system and a SNARK-friendly signature scheme. As a result, our aggregated signature size is sufficiently compact. For example, the size required to aggregate $2^{20}$ signatures is only a few hundred kilobytes. This result shows that our scheme is superior to the existing lattice-based schemes in compressing many signatures.

Password Authenticated Key Exchange (PAKE) have become a key building block in many security products as they provide interesting efficiency/security trade-offs. Indeed, a PAKE allows to dispense with the heavy public key infrastructures and its efficiency and portability make it well suited for applications such as Internet of Things or e-passports. With the emerging quantum threat and the effervescent development of post-quantum public key algorithms in the last five years, one would wonder how to modify existing password authenticated key exchange protocols that currently rely on Diffie-Hellman problems in order to include newly introduced and soon-to-be-standardized post-quantum key encapsulation mechanisms (KEM). A generic solution is desirable for maintaining modularity and adaptability with the many post-quantum KEM that have been introduced. In this paper, we propose two new generic and natural constructions proven in the Universal Composability (UC) model to transform, in a black-box manner, a KEM into a PAKE with very limited performance overhead: one or two extra symmetric encryptions. Behind the simplicity of the designs, establishing security proofs in the UC model is actually non-trivial and requires some additional properties on the underlying KEM like fuzziness and anonymity. Luckily, post-quantum KEM protocols often enjoy these two extra properties. As a demonstration, we prove that it is possible to apply our transformations to Crystals-Kyber, a lattice-based post-quantum KEM that will soon be standardized by the National Institute of Standards and Technology (NIST). In a nutshell, this work opens up the possibility to securely include post-quantum cryptography in PAKE-based real-world protocols.

We study the use of symmetric cryptography in the MTProto 2.0 protocol, Telegram's equivalent of the TLS protocol. We give positive and negative results. On the one hand, we formally and in detail specify a slight variant of Telegram's "record protocol" and prove that it achieves security in a suitable bidirectional secure channel model, albeit under unstudied assumptions; this model itself advances the state-of-the-art for secure channels. On the other hand, we first motivate our slight deviation from MTProto as deployed by giving two attacks on the original protocol specification: one of practical, one of theoretical interest. Then, we give two attacks on the implementation, which are outside of our formal model: one targeting the client, one targeting the server. The client-side attack enables plaintext recovery by exploiting timing side channels, of varying strength, in three official Telegram clients. On its own this attack is thwarted by the secrecy of header fields that are established by Telegram's key exchange protocol. We thus chain this attack with an attack against the implementation of the key exchange protocol on Telegram's servers. This final attack breaks the authentication properties of Telegram's key exchange, allowing a MitM attack. More mundanely, it also reduces the cost of the client-side plaintext recovery attack. In totality, our results provide the first comprehensive study of MTProto's use of symmetric cryptography, as well as highlight weaknesses in its key exchange.

Internet of Things (IoT) has become an established part of our daily lives by interconnecting billions of devices in diverse areas such as health care, smart home technologies, agriculture, etc. However, IoT devices are limited in memory, energy and computational capabilities. This creates a great potential for security issues, since being constrained prevents producers from implementing mostly complex cryptographic algorithms in IoT devices. In this study, we propose a novel method to provide a low-cost and secure communication for constrained IoT devices. The proposed method is based on an $n$-out-of-$n$ secret sharing scheme and mimicks the idea of visual cryptography in a digital setup. Whenever an IoT device communicates with an outer party, it establishes the communication by itself or through a mediary such as a central hub or gateway; in which the latter mostly leads to a single point of failure. Our proposed method aims for a distributed environment in which IoT devices within a secure network collaborate with each other in order to send a message to a master device over an insecure channel.

Secure 2-party computation (2PC) of floating-point arithmetic is improving in performance and recent work runs deep learning algorithms with it, while being as numerically precise as commonly used machine learning (ML) frameworks like PyTorch. We find that the existing 2PC libraries for floating-point support generic computations and lack specialized support for ML training. Hence, their latency and communication costs for compound operations (e.g., dot products) are high. We provide novel specialized 2PC protocols for compound operations and prove their precision using numerical analysis. Our implementation BEACON outperforms state-of-the-art libraries for 2PC of floating-point by over $6\times$.

In this paper, we introduce $\mathsf{SparsePIR}$, a single-server keyword private information retrieval (PIR) construction that enables querying over sparse databases. At its core, $\mathsf{SparsePIR}$ is based on a novel encoding algorithm that encodes sparse database entries as linear combinations while being compatible with important PIR optimizations including recursion. $\mathsf{SparsePIR}$ achieves response overhead that is half of state-of-the art keyword PIR schemes without requiring long term client storage of linear sized mappings. We also introduce two variants, $\mathsf{SparsePIR}^g$ and $\mathsf{SparsePIR}^c$, that further reduces the size of the serving database at the cost of increased encoding time and small additional client storage, respectively. Our frameworks enable performing keyword PIR with, essentially, the same costs as standard PIR. Finally, we also show that $\mathsf{SparsePIR}$ may be used to build batch keyword PIR with halved response overhead without any client mappings.

Ring-Learning-with-Errors (RLWE) has emerged as the foundation of many important techniques for improving security and privacy, including homomorphic encryption and post-quantum cryptography. While promising, these techniques have received limited use due to their extreme overheads of running on general-purpose machines. In this paper, we present a novel vector Instruction Set Architecture (ISA) and microarchitecture for accelerating the ring-based computations of RLWE. The ISA, named B512, is developed to meet the needs of ring processing workloads while balancing high-performance and general-purpose programming support. Having an ISA rather than fixed hardware facilitates continued software improvement post-fabrication and the ability to support the evolving workloads. We then propose the ring processing unit (RPU), a high-performance, modular implementation of B512. The RPU has native large word modular arithmetic support, capabilities for very wide parallel processing, and a large capacity high-bandwidth scratchpad to meet the needs of ring processing. We address the challenges of programming the RPU using a newly developed SPIRAL backend. A configurable simulator is built to characterize design tradeoffs and quantify performance. The best performing design was implemented in RTL and used to validate simulator performance. In addition to our characterization, we show that a RPU using 20.5mm2 of GF 12nm can provide a speedup of 1485x over a CPU running a 64k, 128-bit NTT, a core RLWE workload

With an anonymous reputation system one can realize the process of rating sellers anonymously in an online shop. While raters can stay anonymous, sellers still have the guarantee that they can be only be reviewed by raters who bought their product. We present the first generic construction of a reputation system from basic building blocks, namely digital signatures, encryption schemes, non-interactive zero-knowledge proofs, and linking indistinguishable tags. We then show the security of the reputation system in a strong security model. Among others, we instantiate the generic construction with building blocks based on lattice problems, leading to the first module lattice-based reputation system in the random oracle model.

We present a theoretical framework for analyzing the efficiency of consensus protocols, and apply it to analyze the optimistic and pessimistic confirmation times of state-of-the-art partially-synchronous protocols in the so-called "rotating leader/random leader" model of consensus (recently popularized in the blockchain setting). We next present a new and simple consensus protocol in the partially synchronous setting, tolerating $f < n/3$ byzantine faults; in our eyes, this protocol is essentially as simple to describe as the simplest known protocols, but it also enjoys an even simpler security proof, while matching and, even improving, the efficiency of the state-of-the-art (according to our theoretical framework). As with the state-of-the-art protocols, our protocol assumes a (bare) PKI, a digital signature scheme, collision-resistant hash functions, and a random leader election oracle, which may be instantiated with a random oracle (or a CRS).

Some of the most efficient protocols for Multi-Party Computation (MPC) follow a two-phase approach where correlated randomness, in particular Beaver triples, is generated in the offline phase and then used to speed up the online phase. Recently, more complex correlations have been introduced to optimize certain operations even further, such as matrix triples for matrix multiplications. In this paper, our goal is to improve the efficiency of the triple generation in general and in particular for classical field values as well as matrix operations. To this end, we modify the Overdrive LowGear protocol to remove the costly sacrificing step and therewith reduce the round complexity and the bandwidth. We extend the state-of-the-art MP-SPDZ implementation with our new protocols and show that the new offline phase outperforms state-of-the-art protocols for the generation of Beaver triples and matrix triples. For example, we save 33 % in bandwidth compared to Overdrive LowGear.

Deep learning-based cryptanalysis is one of the emerging trends in recent times. Differential cryptanalysis is one of the most po- tent approaches to classical cryptanalysis. Researchers are now modeling classical differential cryptanalysis by applying deep learning-based tech- niques. In this paper, we report deep learning-based differential distin- guishers for block cipher PRIDE and RC5, utilizing deep learning models: CNN, LGBM and LSTM. We found distinguishers up to 23 rounds for PRIDE and nine rounds for RC5. To the best of our knowledge this is the first deep learning based differential classifier for cipher PRIDE and RC5.

At Eurocrypt 2016, Méaux et al. presented FLIP, a new family of stream ciphers {that aimed to enhance the efficiency of homomorphic encryption frameworks. Motivated by FLIP, recent research has focused on the study of Boolean functions with good cryptographic properties when restricted to subsets of the space $\mathbb{F}_2^n$. If an $n$-variable Boolean function has the property of balancedness when restricted to each set of vectors with fixed Hamming weight between $1$ and $n-1$, it is a weightwise perfectly balanced (WPB) Boolean function. In the literature, a few algebraic constructions of WPB functions are known, in which there are some constructions that use iterative method based on functions with low degrees of 1, 2, or 4. In this paper, we generalize the iterative method and contribute a unified construction of WPB functions based on functions with algebraic degrees that can} be any power of 2. For any given positive integer $d$ not larger than $m$, we first provide a class of $2^m$-variable Boolean functions with a degree of $2^{d-1}$. Utilizing these functions, we then present a construction of $2^m$-variable WPB functions $g_{m;d}$. In particular, $g_{m;d}$ includes four former classes of WPB functions as special cases when $d=1,2,3,m$. When $d$ takes other integer values, $g_{m;d}$ has never appeared before. In addition, we prove the algebraic degree of the constructed WPB functions and compare the weightwise nonlinearity of WPB functions known so far in 8 and 16 variables.

Side-channel analysis (SCA) attacks manifest a significant challenge to the security of cryptographic devices. In turn, it is generally quite expensive to protect from SCAs (energy, area, performance etc.). In this work we exhibit a significant change in paradigm for SCA attacks: our proposed attack is quite different from conventional SCA attacks and is able to filter out physical measurement noise, algorithmic noise, as well as thwart various countermeasures, and extract information from the entire leakage waveform as a whole and not only points-of-interest. We demonstrate on measured devices break of masking schemes of orders 2 and 3, supported by a model and also shuffling and dual-rail based countermeasures model; all performed efficiently with the same methodology, and with orders of magnitude less measurements and smaller computation time; underpinning the importance of this form of attack. In essence, in our attack we assume nothing different than a standard side-channel attack, i.e., a known plaintext scenario. However, we further group and classify leakages associated with specific subsets of plaintexts bits. The fact that we group specific (sub-)plaintexts associated leakages, and than in the next stage group or concatenate the associated leakages of these large groups in a predefined ordered sequence (modulation), enables far stronger attacks against SCA protected and unprotected designs. The evaluation-domain or the modulation-domain is the frequency domain in which per frequency it is possible to build a two feature constellation diagrams (amplitude and phase) and construct distinguishers over these diagrams. On top of the methodological contribution of this new SCA, the main observation we push forward is that practically such an attack is devastating for many countermeasures we were used to consider as secure to some level, such as masking or shuffling with large permutation size. As an example, leakage from a third order masked design can be detected with merely 100 leakage traces from the first statistical moment of the leakage as compared to $15\cdot10^6$ traces with conventional SCA leakage detection test from the third statistical order.

In 2002, Barak and Goldreich introduced the notion of a universal argument and constructed an interactive universal argument for non-deterministic computations based on polynomially hard collision-resistant hash functions. Since then, and especially in recent years, there have been tremendous developments in the construction of non-interactive succinct arguments for deterministic computations under standard hardness assumptions. However, the constructed succinct arguments can be proven universal only under sub-exponential assumptions. Assuming polynomially hard fully homomorphic encryption and a widely believed worst-case complexity assumption, we prove a general lifting theorem showing that all existing non-interactive succinct arguments can be made universal. The required complexity assumption is that non-uniformity does not allow arbitrary polynomial speedup. In the setting of uniform adversaries, this extra assumption is not needed.

This paper introduces the first registered functional encryption RFE scheme tailored for linear functions. Distinctly different from classical functional encryption (FE), RFE addresses the key-escrow issue and negates the master key exfiltration attack. Instead of relying on a centralized trusted authority, it introduces a “key curator” - a fully transparent entity that does not retain secrets. In an RFE framework, users independently generate secret keys and subsequently register their respective public keys, along with their authorized functions, with the key curator. This curator consolidates public keys from various users into a unified, concise master public key. For decryption, users occasionally secure helper decryption keys from the key curator, which they use in conjunction way with their private keys. It is imperative that the aggregate public key, helper decryption keys, ciphertexts, and the times for encryption/decryption are polylogarithmic in the number of registered users. All existing RFE designs were confined to predicates where given the correct credentials a user can retrieve the entire payload from a ciphertext or gain no information about it otherwise. Contrarily, our RFE scheme facilitates the computation of linear functions on encrypted content and extraction of only the computation results. Recognizing potential leaks from linear functions, we further enhance our RFE by incorporating an attribute-based access control mechanism. The outcome is the first registered attribute-based linear FE (RABIPFE), which supports access policies depicted as linear secret sharing schemes LSSS. Our proposed schemes are realized in the common reference string (CRS) model as introduced by Hohenberger et al.[EUROCRYPT 2023], employ simple tools and black-box methods. Specifically, our constructs operate in asymmetric prime-order bilinear group regime setting and are proven secure in the generic bilinear group model. Aligning with all pre-existing black-box RFE designs within the CRS model, our schemes cater to a predetermined maximum user count. A notable variant of our RABIPFE scheme also yields the first efficient register ABE (RABE) system for LSSS access policies in asymmetric prime-order bilinear groups. Conclusively, demonstrating feasibility, we formulated an RFE blueprint that supports general functionalities and an infinite user base, leveraging indistinguishability obfuscation and one-way functions.

Asynchronous Remote Key Generation (ARKG, introduced in ACM CCS 2020) allows for a party to create public keys for which corresponding private keys may be later computed by another intended party only. ARKG can be composed with standard public-key cryptosystems and has been used to construct a new class of privacy-preserving proxy signatures. The original construction of ARKG, however, generates discrete logarithm key pairs of the form $(x, g^x)$. In this paper we define a generic approach for building ARKG schemes which can be applied to a wide range of pairing-based cryptosystems. This construction is based on a new building block which we introduce and call Asymmetric Key Generation (AKG) along with its extension $\phi$-AKG where $\phi$ is a suitable mapping for capturing different key structures and types of pairings. We show that appropriate choice of $\phi$ allows us to create a secure ARKG scheme compatible with any key pair that is secure under the Uber assumption (EUROCRYPT 2004). To demonstrate the extensive range of our general approach, we construct ARKG schemes for a number of popular pairing-based primitives: Boneh-Lynn-Shacham (JoC 2004), Camenisch-Lysyanskaya (CRYPTO 2004), Pointcheval-Sanders (CT-RSA 2016), Waters (EUROCRYPT 2005) signatures and structure-preserving signatures on equivalence classes (ASIACRYPT 2014). For each scheme we give an implementation and provide benchmarks that show the feasibility of our techniques.

We introduce tri-state circuits (TSCs). TSCs form a natural model of computation that, to our knowledge, has not been considered by theorists. The model captures a surprising combination of simplicity and power. TSCs are simple in that they allow only three wire values ($0,1,$ and undefined - $\mathcal{Z}$) and three types of fan-in two gates; they are powerful in that their statically placed gates fire (execute) eagerly as their inputs become defined, implying orders of execution that depend on input. This behavior is sufficient to efficiently evaluate RAM programs. We construct a TSC that emulates $T$ steps of any RAM program and that has only $O(T \cdot \log^3 T \cdot \log \log T)$ gates. Contrast this with the reduction from RAM to Boolean circuits, where the best approach scans all of memory on each access, incurring quadratic cost. We connect TSCs with cryptography by using them to improve Yao's Garbled Circuit (GC) technique. TSCs capture the power of garbling far better than Boolean Circuits, offering a more expressive model of computation that leaves per-gate cost essentially unchanged. As an important application, we construct authenticated Garbled RAM (GRAM), enabling constant-round maliciously-secure 2PC of RAM programs. Let $\lambda$ denote the security parameter. We extend authenticated garbling to TSCs; by simply plugging in our TSC-based RAM, we obtain authenticated GRAM running at cost $O(T \cdot \log^3 T \cdot \log \log T \cdot \lambda)$, outperforming all prior work, including prior semi-honest GRAM. We also give semi-honest garbling of TSCs from a one-way function (OWF). This yields OWF-based GRAM at cost $O(T \cdot \log^3 T \cdot \log \log T \cdot \lambda)$, outperforming the best prior OWF-based GRAM by more than factor $\lambda$.

Wireless-channel key exchange (WiKE) protocols that leverage Physical Layer Security (PLS) techniques could become an alternative solution for secure communication establishment, such as vehicular ad-hoc networks, wireless IoT networks, or cross-layer protocols. In this paper, we provide a novel abstraction of WiKE protocols and present the first game-based security model for WiKE. Our result enables the analysis of security guarantees offered by these cross-layer protocols and allows the study of WiKE's compositional aspects. Further, we address the potential problem of the slow-rate secret-key generation in WiKE due to inadequate environmental conditions that might render WiKE protocols impractical or undesirably slow. We explore a solution to such a problem by bootstrapping a low-entropy key coming as the output of WiKE using a Password Authenticated Key Exchange (PAKE). On top of the new security definition for WiKE and those which are well-established for PAKE, we build a compositional WiKE-then-PAKE model and define the minimum security requirements for the safe sequential composition of the two primitives in a black-box manner. Finally, we show the pitfalls of previous ad-hoc attempts to combine WiKE and PAKE.

We give an algebraic attack to forge the signature of a scheme called MPPK/DS, which can be achieved by solving a linear system in 5 variables with coefficients on $\mathbb{Z}/2^x q \mathbb{Z}$ for some odd prime $q$ and $x ≥ 1$.

We construct a sublinear-time single-server pre-processing Private Information Retrieval (PIR) scheme with optimal client storage and server computation (up to poly-logarithmic factors), only relying on the assumption of the existence of One Way Functions (OWF). Our scheme achieves amortized $\tilde{O}(\sqrt{n})$ online server computation and client computation and $O(\sqrt{n})$ online communication per query, and requires $\widetilde{O}_\lambda(\sqrt{n})$ client storage. Unlike prior single-server PIR schemes that rely on heavy cryptographic machinery such as Homomorphic Encryption, our scheme only utilizes lightweight cryptography such as PRFs, which is easily instantiated in practice. To our knowledge, this is the first practical implementation of a single-server sublinear-time PIR scheme. Compared to existing linear time single-server solutions, our schemes are faster by $40-900\times$ and are comparable to the fastest two-server schemes. In particular, for a 100GB database of 1.6 billion entries, our experiments show that our scheme has 12ms online computation time on a single core.

We put forward a non-interactive verifiable secret sharing (NI-VSS) scheme using class groups – we call it cgVSS. Our construction follows the standard framework of encrypting the shares to a set of recipients and generating a non-interactive proof of correct sharing. However, as opposed to prior works, such as Groth’s [Eprint 2021], or Gentry et al.’s [Eurocrypt 2022], we do not require any range proof - this is possible due to the unique structure of class groups, that enables efficient encryption/decryption of large field elements in the exponent of an ElGamal-style encryption scheme. Importantly, this is possible without destroying the additive holomorphic structure, which is required to make the proof-of-correctness highly efficient. This approach not only substantially simplifies the NI-VSS process, but also outperforms the state-of-art schemes significantly. For example, our implementation shows that for a 150 node system cgVSS outperforms (a simplified implementation of) Groth’s protocol in overall communication complexity by 5.6x, about 9.3 − 9.7x in the dealer time and 2.4 − 2.7x in the receiver time per node. Additionally, we formalize the notion of public verifiability, which enables anyone, possibly outside the participants, to verify the correctness of the dealing. In fact, we re-interpret the notion of public verifiability and extend it to the setting when potentially all recipients may be corrupt and yet can not defy public verifiability – to distinguish from state-of-art, we call this strong public verifiability. Our formalization uses the universal composability framework. Finally, through a generic transformation, we obtain a non-interactive distributed key generation (NI-DKG) scheme for threshold systems, where the secret key is the discrete log of the public key. Our security analysis in the VSS-hybrid model uses a formalization that considers a (strong) public verifiability notion for DKG, even when more than threshold parties are corrupt. Instantiating with cgVSS we obtain a NI-DKG scheme from class groups – we call it cgDKG.

HID Global is a major vendor of physical access control systems. In 2012, it introduced Seos, its newest and most secure contactless RFID credential technology, successfully remediating known flaws in predecessors iCLASS and Prox. Seos has been widely deployed to secure sensitive assets and facilities. To date, no published research has demonstrated a security flaw in Seos. We present a relay attack developed with inexpensive COTS hardware, including the Proxmark 3 RDV4. Our attack is capable of operating over extremely long ranges as it uses the Internet as a communications backbone. We have tested multiple real-world attack scenarios and are able to unlock a door in our lab with a card approximately 1960 km away. Our attack is covert and does not require long-term access to the card. Further, our attack is generic and is potentially applicable to other protocols that, like Seos, use ISO/IEC 14443A to communicate. We discuss several mitigations capable of thwarting our attack that could be introduced in future credential systems or as an update to Seos-compatible readers' firmware; these rely on rejecting cards that take too long to reply.

Multidimensional Approximate Agreement considers a setting of $n$ parties, where each party holds a vector in $\mathbb{R}^D$ as input. The honest parties are required to obtain very close outputs in $\mathbb{R}^D$ that lie inside the convex hull of their inputs. Existing Multidimensional Approximate Agreement protocols achieve resilience against $t_s < n / (D + 1)$ corruptions under a synchronous network where messages are delivered within some time $\Delta$, but become completely insecure as soon as a single message is further delayed. On the other hand, asynchronous solutions do not rely on any delay upper bound, but only achieve resilience up to $t_a < n / (D + 2)$ corruptions. We investigate the feasibility of achieving Multidimensional Approximate Agreement protocols that achieve simultaneously guarantees in both network settings: We want to tolerate $t_s$ corruptions when the network is synchronous, and also tolerate $t_a \leq t_s$ corruptions when the network is asynchronous. We provide a protocol that works as long as $(D + 1) \cdot t_s + t_a < n$, and matches several existing lower bounds.

The generalized inverses of systematic non-square binary matrices have applications in mathematics, channel coding and decoding, navigation signals, machine learning, data storage and cryptography such as the McEliece and Niederreiter public-key cryptosystems. A systematic non-square $(n-k) \times n$ matrix $H$, $n > k$, has $2^{k\times(n-k)}$ different generalized inverse matrices. This paper presents an algorithm for generating these matrices and compares it with two well-known methods, i.e. Gauss-Jordan elimination and Moore-Penrose methods. A random generalized inverse matrix construction method is given which has a lower execution time than the Gauss-Jordan elimination and Moore-Penrose approaches.

The Lattice Isomorphism Problem (LIP) is the computational task of recovering, assuming it exists, a orthogonal linear transformation sending one lattice to another. For cryptographic purposes, the case of the trivial lattice $\mathbb Z^n$ is of particular interest ($\mathbb Z$LIP). Heuristic analysis suggests that the BKZ algorithm with blocksize $\beta = n/2 + o(n)$ solves such instances (Ducas, Postlethwaite, Pulles, van Woerden, ASIACRYPT 2022). In this work, I propose a provable version of this statement, namely, that $\mathbb Z$LIP can indeed be solved by making polynomially many calls to a Shortest Vector Problem (SVP) oracle in dimension at most $n/2 + 1$.

Preimage sampling is a fundamental tool in lattice-based cryptography, and its performance directly impacts that of the cryptographic mechanisms relying on it. In 2012, Micciancio and Peikert proposed a new way of generating trapdoors (and an associated preimage sampling procedure) with very interesting features. Unfortunately, in some applications such as digital signatures, the performance may not be as competitive as other approaches like Fiat-Shamir with Aborts. In an effort to improve preimage sampling for Micciancio-Peikert (MP) trapdoors, Lyubashevsky and Wichs (LW) introduced a new sampler which leverages rejection sampling but suffers from strong parameter requirements that hampered performance. As a consequence it seemed to be restricted to theoretical applications and has not been, to our knowledge, considered for real-world applications. Our first contribution is to revisit the LW sampler by proposing an improved analysis which yields much more compact parameters. This leads to gains on the preimage size of about 60% over the LW sampler, and up to 25% compared to the original MP sampling technique. It thus sheds a new light on the LW sampler, opening promising perspectives for the efficiency of advanced lattice-based constructions relying on such mechanisms. To provide further improvements, we show that it perfectly combines with the approximate trapdoors approach by Chen, Genise and Mukherjee, but with a smaller preimage error. Building upon those results, we introduce a hash-and-sign signature scheme called Phoenix. The scheme is based on the M-LWE and M-SIS assumptions and features attractive public key and signature sizes which are even smaller than those of the most recent gadget-based construction Eagle of Yu, Jia and Wang (Crypto’23). Moreover, Phoenix is designed to be implementation-friendly, avoiding in particular complex Gaussian samplers that are often hard to protect.

We prove adaptive security of a simple three-round threshold Schnorr signature scheme, which we call Sparkle+. The standard notion of security for threshold signatures considers a static adversary – one who must declare which parties are corrupt at the beginning of the protocol. The stronger adaptive adversary can at any time corrupt parties and learn their state. This notion is natural and practical, yet not proven to be met by most schemes in the literature. In this paper, we demonstrate that Sparkle+ achieves several levels of security based on different corruption models and assumptions. To begin with, Sparkle+ is statically secure under minimal assumptions: the discrete logarithm assumption (DL) and the random oracle model (ROM). If an adaptive adversary corrupts fewer than t/2 out of a threshold of t+1 signers, then Sparkle+ is adaptively secure under a weaker variant of the one-more discrete logarithm assumption (AOMDL) in the ROM. Finally, we prove that Sparkle+ achieves full adaptive security, with a corruption threshold of t, under AOMDL in the algebraic group model (AGM) with random oracles. Importantly, we show adaptive security without requiring secure erasures. Ours is the first proof achieving full adaptive security without exponential tightness loss for any threshold Schnorr signature scheme.

Bounded-collusion identity-based encryption (BC-IBE) is a variant of identity-based encryption, where an adversary obtains user secrete keys corresponding to at most $d$ identities. From results of existing work, it is proven that BC-IBE can be constructed from public key encryption (PKE) with several properties. In particular, we focus on post-quantum PKE schemes submitted to the NIST PQC competition, as the underlying PKE of BC-IBE schemes. This is because post-quantum cryptography is one of active research areas, due to recent advancement of developing quantum computers. Hence, it is reasonable to consider converting such PKE schemes into encryption schemes with additional functionalities. By using existing generic constructions of BC-IBE, those post-quantum PKE schemes are transformed into BC-IBE with non-compact public parameter. In this paper, we propose generic constructions of BC-IBE whose public parameter-size is more compact, and it is possible to apply many post-quantum PKE schemes secure against chosen plaintext attacks, into our generic constructions. To this end, we construct BC-IBE schemes from a group testing perspective, while existing ones are constructed by employing error-correcting codes or cover-free families. As a result, we can obtain BC-IBE schemes with more compact public parameter, which are constructed from the NIST PQC PKE schemes.

A thread of physical attacks that try to obtain secret information from cryptographic modules has been of academic and practical interest. One of the concerns is determining its efficiency, e.g., the number of attack trials to recover the secret key. However, the accurate estimation of the attack efficiency is generally expensive because of the complexity of the physical attack on a cryptographic algorithm. Based on this background, in this study, we propose a new abstraction model for evaluating the attack efficiency of the probing and DFA attacks. The proposed model includes an abstracted attack target and attacker to determine the amount of leaked information obtained in a single attack trial. We can adapt the model flexibly to various attack scenarios and can get the attack efficiency quickly and precisely. In the probing attack on AES, the difference in the attack efficiency is only approximately 0.3% between the model and experimental values, whereas that of a previous model is approximately 16%. We also apply the probing attack on DES, and the results show that DES has a high resistance to the probing attack. Moreover, the proposed model works accurately also for the DFA attack on AES.

In this paper, we propose a non-interactive privacy-preserving naive Bayes classifier from leveled fully homomorphic encryption schemes. The classifier runs on a server that is also the model’s owner (modeler), whose input is the encrypted data from a client. The classifier produces encrypted classification results, which can only be decrypted by the client, while the modelers model is only accessible to the server. Therefore, the classifier does not leak any privacy on either the servers model or the clients data and results. More importantly, the classifier does not require any interactions between the server and the client during the classification phase. The main technical ingredient is an algorithm that computes the maximum index of an encrypted array homomorphically without any interactions. The proposed classifier is implemented using HElib. Experiments show the accuracy and efficiency of our classifier. For instance, the average cost can achieve about 34ms per sample for a real data set in UCI Machine Learning Repository with the security parameter about 100 and accuracy about 97%.

We consider the problem of constructing an unconditionally secure cipher with a short key for the case where the probability distribution of encrypted messages is unknown. Note that unconditional security means that an adversary with no computational constraints can obtain only a negligible amount of information ("leakage") about an encrypted message (without knowing the key). Here we consider the case of a priori (partially) unknown message source statistics. More specifically, the message source probability distribution belongs to a given family of distributions. We propose an unconditionally secure cipher for this case. As an example, one can consider constructing a single cipher for texts written in any of the languages of the European Union. That is, the message to be encrypted could be written in any of these languages.

In this paper, we study both the implications and potential impact of backdoored parameters for two RSA-based pseudorandom number generators: the ISO-standardized Micali-Schnorr generator and a closely related design, the RSA PRG. We observe, contrary to common understanding, that the security of the Micali-Schnorr PRG is not tightly bound to the difficulty of inverting RSA. We show that the Micali-Schnorr construction remains secure even if one replaces RSA with a publicly evaluatable PRG, or a function modeled as an efficiently invertible random permutation. This implies that any cryptographic backdoor must somehow exploit the algebraic structure of RSA, rather than an attacker's ability to invert RSA or the presence of secret keys. We exhibit two such backdoors in related constructions: a family of exploitable parameters for the RSA PRG, and a second vulnerable construction for a finite-field variant of Micali-Schnorr. We also observe that the parameters allowed by the ISO standard are incompletely specified, and allow insecure choices of exponent. Several of our backdoor constructions make use of lattice techniques, in particular multivariate versions of Coppersmith's method for finding small solutions to polynomials modulo integers.

The introduction of time-lock puzzles initiated the study of publicly “sending information into the future.” For time-lock puzzles, the underlying security-enabling mechanism is the computational complexity of the operations needed to solve the puzzle, which must be tunable to reveal the solution after a predetermined time, and not before that time. Time-lock puzzles are typically constructed via a commitment to a secret, paired with a reveal algorithm that sequentially iterates a basic function over such commitment. One then shows that short-cutting the iterative process violates cryptographic hardness of an underlying problem. To date, and for more than twenty-five years, research on time-lock puzzles relied heavily on iteratively applying well-structured algebraic functions. However, despite the tradition of cryptography to reason about primitives in a realistic model with standard hardness assumptions (often after initial idealized assumptions), most analysis of time-lock puzzles to date still relies on cryptography modeled (in an ideal manner) as a random oracle function or a generic group function. Moreover, Mahmoody et al. showed that time-lock puzzles with superpolynomial gap cannot be constructed from random-oracles; yet still, current treatments generally use an algebraic trapdoor to efficiently construct a puzzle with a large time gap, and then apply the inconsistent (with respect to Mahmoody et al.) random-oracle idealizations to analyze the solving process. Finally, little attention has been paid to the nuances of composing multi-party computation with timed puzzles that are solved as part of the protocol. In this work, we initiate a study of time-lock puzzles in a model built upon a realistic (and falsifiable) computational framework. We present a new formal definition of residual complexity to characterize a realistic, gradual time-release for time-lock puzzles. We also present a general definition of timed multi-party computation (MPC) and both sequential and concurrent composition theorems for MPC in our model.

In this article, we propose several generic methods for constructing minimal linear codes over the field $\mathbb{F}_p$. The first construction uses the method of direct sum of an arbitrary function $f:\mathbb{F}_{p^r}\to \mathbb{F}_{p}$ and a bent function $g:\mathbb{F}_{p^s}\to \mathbb{F}_p$ to induce minimal codes with parameters $[p^{r+s}-1,r+s+1]$ and minimum distance larger than $p^r(p-1)(p^{s-1}-p^{s/2-1})$. For the first time, we provide a general construction of linear codes from a subclass of non-weakly regular plateaued functions, which partially answers an open problem posed in [22]. The second construction deals with a bent function $g:\mathbb{F}_{p^m}\to \mathbb{F}_p$ and a subspace of suitable derivatives $U$ of $g$, i.e., functions of the form $g(y+a)-g(y)$ for some $a\in \mathbb{F}_{p^m}^*$. We also provide a sound generalization of the recently introduced concept of non-covering permutations [45]. Some important structural properties of this class of permutations are derived in this context. The most remarkable observation is that the class of non-covering permutations contains the class of APN power permutations (characterized by having two-to-one derivatives). Finally, the last general construction combines the previous two methods (direct sum, non-covering permutations and subspaces of derivatives), using a bent function in the Maiorana-McFarland class to construct minimal codes (even those violating the Ashikhmin-Barg bound) with larger dimensions. This last method proves to be highly flexible since it can lead to several non-equivalent codes, depending to a great extent on the choice of the underlying non-covering permutation.

Measuring people’s interactions that span multiple websites can provide unique insight that enables better products and improves people’s experiences, but directly observing people’s individual journeys creates privacy risks that conflict with the newly emerging privacy model for the web. We propose a protocol that uses the combination of multi-party computation and differential privacy that enables the processing of peoples’ data such that only aggregate measurements are revealed, strictly limiting the information leakage about individual people. Our primary application of this protocol is measuring, in aggregate, the effectiveness of digital advertising without enabling cross-site tracking of individuals. In this paper we formalize our protocol, Interoperable Private Attribution (IPA), and analyze its security. IPA is proposed in the W3C’s Private Advertising Technology Community Group (PATCG) [8]. We have implemented our protocol in the malicious honest majority MPC setting for three parties where network costs dominate compute costs. For processing a query with 1M records it uses around 18GB of network which at \$0.08 per GB leads to a network cost of \$1.44.

We introduce SQIsignHD, a new post-quantum digital signature scheme inspired by SQIsign. SQIsignHD exploits the recent algorithmic breakthrough underlying the attack on SIDH, which allows to efficiently represent isogenies of arbitrary degrees as components of a higher dimensional isogeny. SQIsignHD overcomes the main drawbacks of SQIsign. First, it scales well to high security levels, since the public parameters for SQIsignHD are easy to generate: the characteristic of the underlying field needs only be of the form $2^{f}3^{f'}-1$. Second, the signing procedure is simpler and more efficient. Our signing procedure implemented in C runs in 28 ms, which is a significant improvement compared to SQISign. Third, the scheme is easier to analyse, allowing for a much more compelling security reduction. Finally, the signature sizes are even more compact than (the already record-breaking) SQIsign, with compressed signatures as small as 109 bytes for the post-quantum NIST-1 level of security. These advantages may come at the expense of the verification, which now requires the computation of an isogeny in dimension $4$, a task whose optimised cost is still uncertain, as it has been the focus of very little attention. Our experimental sagemath implementation of the verification runs in around 600 ms, indicating the potential cryptographic interest of dimension $4$ isogenies after optimisations and low level implementation.

Research on (Decentralized) Multi-Client Functional Encryption (or (D)MCFE) is very active, with interesting constructions, especially for the class of inner products. However, the security notions have been evolving over the time. While the target of the adversary in distinguishing ciphertexts is clear, legitimate scenarios that do not consist of trivial attacks on the functionality are less obvious. In this paper, we wonder whether only trivial attacks are excluded from previous security games. And, unfortunately, this was not the case. We then propose a stronger security notion, with a large definition of admissible attacks, and prove it is optimal: any extension of the set of admissible attacks is actually a trivial attack on the functionality, and not against the specific scheme. In addition, we show that all the previous constructions are insecure w.r.t. this new security notion. Eventually, we propose new DMCFE schemes for the class of inner products that provide the new features and achieve this stronger security notion.

As part of the responses to the ongoing ``crypto wars,'' the notion of {\em Anamorphic Encryption} was put forth [Persiano-Phan-Yung Eurocrypt '22]. The notion allows private communication in spite of a dictator who (in violation of the usual normative conditions under which Cryptography is developed) is engaged in an extreme form of surveillance and/or censorship, where it asks for all private keys and knows and may even dictate all messages. The original work pointed out efficient ways to use two known schemes in the anamorphic mode, bypassing the draconian censorship and hiding information from the all-powerful dictator. A question left open was whether these examples are outlier results or whether anamorphic mode is pervasive in existing systems. Here we answer the above question: we develop new techniques, expand the notion, and show that the notion of Anamorphic Cryptography is, in fact, very much prevalent. We first refine the notion of Anamorphic Encryption with respect to the nature of covert communication. Specifically, we distinguish {\em Single-Receiver Encryption} for many to one communication, and {\em Multiple-Receiver Encryption} for many to many communication within the group of conspiring (against the dictator) users. We then show that Anamorphic Encryption can be embedded in the randomness used in the encryption, and give families of constructions that can be applied to numerous ciphers. In total the families cover classical encryption schemes, some of which in actual use (RSA-OAEP, Pailler, Goldwasser-Micali, ElGamal schemes, Cramer-Shoup, and Smooth Projective Hash based systems). Among our examples is an anamorphic channel with much higher capacity than the regular channel. In sum, the work shows the very large extent of the potential futility of control and censorship over the use of strong encryption by the dictator (typical for and even stronger than governments engaging in the ongoing ``crypto-wars''): While such limitations obviously hurt utility which encryption typically brings to safety in computing systems, they essentially, are not helping the dictator. The actual implications of what we show here and what does it mean in practice require further policy and legal analyses and perspectives.

In this note we assess the efficiency of a SIDH-based digital signature built on a weakened variant of a recent identification protocol proposed by Basso et al. Despite the devastating attacks against (the mathematical problem underlying) SIDH, this identification protocol remains secure, as its security is backed by a different (and more standard) isogeny-finding problem. We conduct our analysis by applying some known cryptographic techniques to decrease the signature size by about $70\%$ for all parameter sets (obtaining signatures of approximately 21 KB for SIKEp434). Moreover, we propose a minor optimisation to compute many isogenies in parallel from the same starting curve. Our assessment confirms that the problem of designing a practical isogeny-based signature scheme remains largely open. However, concretely determine the current state of the art which future optimisations can compare to appears to be of relevance for a problem which has witnessed only small steps towards a solution.

In this paper we describe attacks on the UOV-based signature scheme called MQ-Sign. MQ-Sign was submitted by Shim, Kim, and An as a a first-round candidate for standardization in the (South) Korean post-quantum cryptography competition (KpqC). The scheme makes use of sparseness of the secret central polynomials and equivalent key construction to reduce the size of the private key. The authors propose four variants exploiting different levels of sparsity, MQ-Sign-SS, MQ-Sign-RS, MQ-Sign-SR, and MQ-Sign-RR with the last one being the standard UOV signature scheme. We show that apart from the MQ-Sign-RR variant, all the others are insecure. Namely, we present a polynomial-time key-recovery attack on the variants MQ-Sign-SS and MQ-Sign-RS and a forgery attack on the variant MQ-Sign-SR below the claimed security level. Our attack exploits exactly the techniques used for reduction of keys - the sparsity of the central polynomials in combination with the specific structure of the secret linear map $\mathbf{S}$. We provide a verification script for the polynomial-time key-recovery attack, that recovers the secret key in less than seven seconds for security level V. Furthermore, we provide an implementation of the non-guessing part of the forgery attack, confirming our complexity estimates.

Secure shuffle is an important primitive that finds use in several applications such as secure electronic voting, oblivious RAMs, secure sorting, to name a few. For time-sensitive shuffle-based applications that demand a fast response time, it is essential to design a fast and efficient shuffle protocol. In this work, we design secure and fast shuffle protocols relying on the techniques of secure multiparty computation. We make several design choices that aid in achieving highly efficient protocols. Specifically, we consider malicious 3-party computation setting with an honest majority and design robust ring-based protocols. Our shuffle protocols provide a fast online (i.e., input-dependent) phase compared to the state-of-the-art for the considered setting. To showcase the efficiency improvements brought in by our shuffle protocols, we consider two distinct applications of anonymous broadcast and secure graph computation via the GraphSC paradigm. In both cases, multiple shuffle invocations are required. Hence, going beyond standalone shuffle invocation, we identify two distinct scenarios of multiple invocations and provide customised protocols for the same. Further, we showcase that our customized protocols not only provide a fast response time, but also provide improved overall run time for multiple shuffle invocations. With respect to the applications, we not only improve in terms of efficiency, but also work towards providing improved security guarantees, thereby outperforming the respective state-of-the-art works. We benchmark our shuffle protocols and the considered applications to analyze the efficiency improvements with respect to various parameters.

ISO 15118 enables charging and billing of Electric Vehicles (EVs) without user interaction by using locally installed cryptographic credentials that must be secure over the long lifetime of vehicles. In the dawn of quantum computers, Post-Quantum Cryptography (PQC) needs to be integrated into the EV charging infrastructure. In this paper, we propose QuantumCharge, a PQC extension for ISO 15118, which includes concepts for migration, crypto-agility, verifiable security, and the use of PQC-enabled hardware security modules. Our prototypical implementation and the practical evaluation demonstrate the feasibility, and our formal analysis shows the security of QuantumCharge, which thus paves the way for secure EV charging infrastructures of the future.

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.