Since the proposal of Bitcoin in 2008, the world has seen accelerated growth in the field of blockchain and discovered its potential to immensely transform most industries, one of the first and most important being finance. The blockchain trilemma states that blockchains can have security, scalability, and decentralization, but never all three at the same time, in the same amount. At the moment, the most successful blockchains have a lack of scalability that researchers and developers try to alleviate by solutions like layer 2s. Most of these solutions rely on cryptographic primitives and technologies, like collision-free hash function or zero-knowledge proofs. In this paper we explore a few of the most popular solutions available now, their improvements to scalability, their drawbacks and security risks.

Back in the 90s when the notion of malware first appeared, it was clear that the behaviour and purpose of such software should be closely analysed, such that systems all over the world should be patched, secured and ready to prevent other malicious activities to be happening in the future. Thus, malware analysis was born. In recent years, the rise of malware of all types, for example trojan, ransowmare, adware, spyware and so on, implies that deeper understanding of operating systems, attention to the details and perseverance are just some of the traits any malware analyst should have in their bag. With Windows being the worldwide go-to operating system, Windows' executable files represent the perfect way in which malware can be disguised to later be loaded and produce damage. In this paper we highlight how ciphers like Vigen\`ere cipher or Caesar cipher can be extended to more complex classes, such that, when later broken, ways of decrypting malware payloads, that are disguised in Windows executable files, are found. Alongside the theoretical information present in this paper, based on a dataset provided by our team at Bitdefender, we describe our implementation on how the key to decryption of such payloads can be found, what techniques are present in our approach, how optimization can be done, what are the pitfalls of this implementation and, lastly, open a discussion on how to tackle these pitfalls.

Recent years have seen the emergence of practical advanced cryptographic tools that not only protect data privacy and authenticity, but also allow for jointly processing data from different institutions without sacrificing privacy. The ability to do so has enabled implementations a number of traditional and decentralized financial applications that would have required sacrificing privacy or trusting a third party. The main catalyst of this revolution was the advent of decentralized cryptocurrencies that use public ledgers to register financial transactions, which must be verifiable by any third party, while keeping sensitive data private. Zero Knowledge (ZK) proofs rose to prominence as a solution to this challenge, allowing for the owner of sensitive data (e.g. the identities of users involved in an operation) to convince a third party verifier that a certain operation has been correctly executed without revealing said data. It quickly became clear that performing arbitrary computation on private data from multiple sources by means of secure Multiparty Computation (MPC) and related techniques allows for more powerful financial applications, also in traditional finance. In this SoK, we categorize the main traditional and decentralized financial applications that can benefit from state-of-the-art Privacy-Enhancing Technologies (PETs) and identify design patterns commonly used when applying PETs in the context of these applications. In particular, we consider the following classes of applications: 1. Identity Management, KYC & AML; and 2. Markets & Settlement; 3. Legal; and 4. Digital Asset Custody. We examine how ZK proofs, MPC and related PETs have been used to tackle the main security challenges in each of these applications. Moreover, we provide an assessment of the technological readiness of each PET in the context of different financial applications according to the availability of: theoretical feasibility results, preliminary benchmarks (in scientific papers) or benchmarks achieving real-world performance (in commercially deployed solutions). Finally, we propose future applications of PETs as Fintech solutions to currently unsolved issues. While we systematize financial applications of PETs at large, we focus mainly on those applications that require privacy preserving computation on data from multiple parties.

The current article provides a new deterministic hash function $\mathcal{H}$ to almost any elliptic curve $E$ over a finite field $\mathbb{F}_{\!q}$, having an $\mathbb{F}_{\!q}$-isogeny of degree $3$. Since $\mathcal{H}$ just has to compute a certain Lucas sequence element, its complexity always equals $O(\log(q))$ operations in $\mathbb{F}_{\!q}$ with a small constant hidden in $O$. In comparison, whenever $q \equiv 1 \ (\mathrm{mod} \ 3)$, almost all previous hash functions need to extract at least one square root in $\mathbb{F}_{\!q}$. Over the field $\mathbb{F}_{\!q}$ of $2$-adicity $\nu$ this amounts to $O(\log(q) + \nu^2)$ operations in $\mathbb{F}_{\!q}$ for the Tonelli--Shanks algorithm and $O(\log(q) + \nu^{3/2})$ ones for the recent Sarkar algorithm. A detailed analysis shows that $\mathcal{H}$ is several times faster than earlier state-of-the-art hash functions to the curve NIST P-224 (for which $\nu = 96$) from the American standard NIST SP 800-186.

Homomorphic encryption (HE) allows for computations over ciphertexts while they are encrypted. Because of this, HE supports the outsourcing of computation on private data. Due to the additional risks caused by data outsourcing, the ability to recover from losses is essential, but doing so on data encrypted under an HE scheme introduces additional challenges for recovery and usability. This work introduces X-Cipher, which aims to make HE ciphertexts resilient by ensuring they are private and recoverable simultaneously at all stages during data outsourcing. X-Cipher allows data recovery without requiring the decryption of HE ciphertexts and maintains its ability to recover and keep data private when a cluster server has been compromised. X-Cipher allows for reduced ciphertext storage overhead by introducing novel encoding and leveraging previously introduced ciphertext packing. X-Cipher's capabilities were evaluated on a synthetic dataset to demonstrate that X-Cipher enables secure availability capabilities while enabling privacy-preserving outsourced computations.

In this work, we will give new attacks on the pseudorandomness of algebraic pseudorandom number generators (PRGs) of polynomial stretch. Our algorithms apply to a broad class of PRGs, while at the same time, in contrast to most algebraic attacks, subexponential time and space bounds will be proven for our attacks without making any assumptions of the PRGs or assuming any further conjectures. Therefore, we yield in this text the first subexponential distinguishing attacks on PRGs from constant-degree polynomials and close current gaps in the subexponential cryptoanalysis of lightweight PRGs. Concretely, against PRGs $F : \mathbb{Z}_q^{n} \rightarrow \mathbb{Z}_q^{m}$ that are computed by polynomials of degree $d$ over a field $\mathbb{Z}_q$ and have a stretch of $m = n^{1+e}$ we give an attack with space and time complexities $n^{O(n^{1 - \frac{e}{d-1}})}$ and noticeable advantage $1 - {O(n^{1 - \frac{e}{d-1}}/{q})}$, if $q$ is large. If $F$ is of constant locality $d$ and $q$ is constant, we construct a second attack that has a space and time complexity of $n^{O(\log(n)^{\frac{1}{(q-1)d-1}} \cdot n^{1 - \frac{e}{(q-1)d-1}})}$ and noticeable advantage $1-O((\log(n)/n^e)^{\frac{1}{(q-1)d-1}})$.

One of the main security challenges white-box cryptography needs to address is side-channel security. To this end, designers aim to eliminate the dependence between variables and sensitive data. Classical countermeasures to do so are masking schemes. Nevertheless, most masking schemes are not designed to thwart the other main security threat : fault attacks. Thus, we aimed to build a masking scheme that could combine resistance to both of these types of attacks. In this paper, we present our new generic fault resistant masking scheme using BCH error-correcting codes, as well as the design choices behind it.

The lightweight block ciphers ULC and LICID are introduced by Sliman et al. (2021) and Omrani et al. (2019) respectively. These ciphers are based on substitution permutation network structure. ULC is designed using the ULM method to increase efficiency, memory usage, and security. On the other hand, LICID is specifically designed for image data. In the ULC paper, the authors have given a full-round differential characteristic with a probability of $2^{-80}$. In the LICID paper, the authors have presented an 8-round differential characteristic with a probability of $2^{-112.66}$. In this paper, we present the 15-round ULC and the 14-round LICID differential characteristics of probabilities $2^{-45}$ and $2^{-40}$ respectively using the MILP model.

Cryptocurrencies are used in several, distinct use cases, thereby sustaining the existence of many ledgers that are heterogeneous in terms of design and purpose. In addition, the interest of central banks in deploying Central Bank Digital Currency (CBDC) has spurred a blooming number of conceptually different proposals from central banks and academia. As a result of the diversity of cryptocurrency and CBDC ledgers, interoperability, i.e., the seamless transfer of value between users that operate on different ledgers, has become an interesting research problem. In fact, interoperability has been explored both in CBDC and cryptocurrencies, and numerous proposals exist. However, these proposals are tailored to the characteristics of the ledgers for which they are designed. For instance, some rely on trusted hardware, others rely on the scripting capabilities of the underlying ledger or on specific cryptographic assumptions of the transaction authorization mechanism (e.g., adaptor signatures), while others rely on a trusted entity. This fragmentation results in the repetitive development of interoperablity protocols that address the same applications across the various ledgers. In this work, we propose an alternative approach: decouple the transaction authorization details of each ledger from the definition of cross-ledger applications. To do so, we define a middle layer that abstracts the core functionality for authorizing transactions in any ledger and the security notions of interest. This middle layer serves two purposes: (i) it becomes the main cryptographic building block to (re)define cross-ledger applications in a ledger agnostic manner; (ii) for any ledger that exists (and the new to come), it suffices to prove that it is a secure instance of the middle layer to be compatible with cross-ledger protocols. We define two new primitives for our middle layer, the basic payment ledger (BL) and the conditional payment ledger (CL). We prove that the two most common transaction authorization mechanism (digital signatures and zero knowledge proofs) are secure constructions for BL. We also prove that common smart contracts (e.g., HTLC and PTLC) and the combination of adaptor signatures with verifiable timelock puzzles are also secure constructions for CL. Finally, we discuss how to design some popular applications (e.g. atomic swaps between ledgers) using our middle layer.

We introduce CorrGapCDH, the Gap Computational Diffie-Hellman problem in the multi-user setting with Corruptions. In the random oracle model, our assumption tightly implies the security of the authenticated key exchange protocols NAXOS in the eCK model and (a simplified version of) X3DH without ephemeral key reveal. We prove hardness of CorrGapCDH in the generic group model, with optimal bounds matching the one of the discrete logarithm problem. We also introduce CorrCRGapCDH, a stronger Challenge-Response variant of our assumption. Unlike standard GapCDH, CorrCRGapCDH implies the security of the popular AKE protocol HMQV in the eCK model, tightly and without rewinding. Again, we prove hardness of CorrCRGapCDH in the generic group model, with (almost) optimal bounds. Our new results allow implementations of NAXOS, X3DH, and HMQV without having to adapt the group sizes to account for the tightness loss of previous reductions. As a side result of independent interest, we also obtain modular and simple security proofs from standard GapCDH with tightness loss, improving previously known bounds.

Akbarpour and Li (2020) formalized credibility as an auction desideratum where the auctioneer cannot benefit by implementing undetectable deviations from the promised auction and showed that, in the plain model, the ascending price auction with reserves is the only credible, strategyproof, revenue-optimal auction. Ferreira and Weinberg (2020) proposed the Deferred Revelation Auction (DRA) as a communication efficient auction that avoids the uniqueness results from (2020) assuming the existence of cryptographic commitments and as long as bidder valuations are MHR. They also showed DRA is not credible in settings where bidder valuations are $\alpha$-strongly regular unless $\alpha$ > 1. In this paper, we ask if blockchains allow us to design a larger class of credible auctions. We answer this question positively, by showing that DRA is credible even for $\alpha$-strongly regular distributions for all $\alpha$ > 0 if implemented over a secure and censorship-resistant blockchain. We argue ledgers provide two properties that limit deviations from a self-interested auctioneer. First, the existence of smart contracts allows one to extend the concept of credibility to settings where the auctioneer does not have a reputation — one of the main limitations for the definition of credibility from Akbarpour and Li (2020). Second, blockchains allow us to implement mechanisms over a public broadcast channel, removing the adaptive undetectable deviations driving the negative results of Ferreira and Weinberg (2020).

In a single secret leader election protocol (SSLE), one of the system participants is chosen and, unless it decides to reveal itself, no other participant can identify it. SSLE has a great potential in protecting blockchain consensus protocols against denial of service (DoS) attacks. However, all existing solutions either make strong synchrony assumptions or have expiring registration, meaning that they require elected processes to re-register themselves before they can be re-elected again. This, in turn, prohibits the use of these SSLE protocols to elect leaders in partially-synchronous consensus protocols as there may be long periods of network instability when no new blocks are decided and, thus, no new registrations (or re-registrations) are possible. In this paper, we propose Homomorphic Sortition -- the first asynchronous SSLE protocol with non-expiring registration, making it the first solution compatible with partially-synchronous leader-based consensus protocols. Homomorphic Sortition relies on Threshold Fully Homomorphic Encryption (ThFHE) and is tailored to proof-of-stake (PoS) blockchains, with several important optimizations with respect to prior proposals. In particular, unlike most existing SSLE protocols, it works with arbitrary stake distributions and does not require a user with multiple coins to be registered multiple times. Our protocol is highly parallelizable and can be run completely off-chain after setup. Some blockchains require a sequence of rounds to have non-repeating leaders. We define a generalization of SSLE, called Secret Leader Permutation (SLP) in which the application can choose how many non-repeating leaders should be output in a sequence of rounds and we show how Homomorphic Sortition also solves this problem.

Amortized bootstrapping offers a way to simultaneously refresh many ciphertexts of a fully homomorphic encryption scheme, at a total cost comparable to that of refreshing a single ciphertext. An amortization method for FHEW-style cryptosystems was first proposed by (Micciancio and Sorrell, ICALP 2018), who showed that the amortized cost of bootstrapping n FHEW-style ciphertexts can be reduced from $O(n)$ basic cryptographic operations to just $O(n^{\epsilon})$, for any constant $\epsilon>0$. However, despite the promising asymptotic saving, the algorithm was rather inpractical due to a large constant (exponential in $1/\epsilon$) hidden in the asymptotic notation. In this work, we propose an alternative amortized boostrapping method with much smaller overhead, still achieving $O(n^\epsilon)$ asymptotic amortized cost, but with a hidden constant that is only linear in $1/\epsilon$, and with reduced noise growth. This is achieved following the general strategy of (Micciancio and Sorrell), but replacing their use of the Nussbaumer transform, with a much more practical Number Theoretic Transform, with multiplication by twiddle factors implemented using ring automorphisms. A key technical ingredient to do this is a new "scheme switching" technique proposed in this paper which may be of independent interest.

A few small-state stream ciphers (SSCs) were proposed for constrained environments. All of the SSCs before the LILLE stream cipher suffered from distinguishing attacks and fast correlation attacks. The designers of LILLE claimed that it is based on the well-studied two-key Even-Mansour scheme and so is resistant to various types of attacks. This paper proposes a distinguishing attack on LILLE, the first attack since 2018. The data and time complexities to attack LILLE-40 are 2^(50.7) and 2^(41.2), respectively. We verified practically our attack on a halved version of LILLE-40. A countermeasure is suggested to strengthen LILLE against the proposed attack. We hope our attack opens the door to more cryptanalyses of LILLE.

In this paper, we propose a variable-sized, one-way, and randomized secure hash algorithm, VORSHA for short. We present six variants of VORSHA, which are able to generate a randomized secure hash value. VORSHA is the first secure hash algorithm to randomize the secure hash value fully. The key embodiment of our proposed algorithm is to generate a pool of pseudo-random bits using the primary hash functions and selects a few bits from the pool of bits to form the final randomized secure hash value. Each hash value of the primary hash function produces a single bit (either 0 or 1) for the pool of pseudo-random bits. Thus, VORSHA randomized the generated bit string to produce the secure hash value, and we term it as a randomized secure hash value. Moreover, the randomized secure hash value is tested using NIST-SP 800-22 statistical test suite, and the generated randomized secure hash value of VORSHA has passed all 15 statistical tests of NIST-SP 800-22. It proves that the VORSHA is able to generate a highly unpredictable yet consistent secure hash value. Moreover, VORSHA features a memory-hardness property to restrict a high degree of parallelism, which features a tiny memory footprint for legal users but massive memory requirements for adversaries. Furthermore, we demonstrate how to prevent Rainbow Table as a Service (RTaaS) attack using VORSHA. The source code is available at https://github.com/patgiri/VORSHA.

Automatic methods for differential and linear characteristic search are well-established at the moment. Typically, the designers of novel ciphers also give preliminary analytical findings for analysing the differential and linear properties using automatic techniques. However, neither MILP-based nor SAT/SMT-based approaches have fully resolved the problem of searching for actual differential and linear characteristics of ciphers with large S-boxes. To tackle the issue, we present three strategies for developing SAT models for 8-bit S-boxes that are geared toward differential probabilities and linear correlations. While these approaches cannot guarantee a minimum model size, the time needed to obtain models is drastically reduced. The newly proposed SAT model for large S-boxes enables us to establish that the upper bound on the differential probability for 14 rounds of SKINNY-128 is 2^{-131}, thereby completing the unsuccessful work of Abdelkhalek et al. We also analyse the seven AES-based constructions C1 - C7 designed by Jean and Nikolic and compute the minimum number of active S-boxes necessary to cause an internal collision using the SAT method. For two constructions C3 and C5, the current lower bound on the number of active S-boxes is increased, resulting in a more precise security analysis for these two structures.

We introduce Grotto, a framework and C++ library for space- and time-efficient $(2+1)$-party piecewise polynomial (i.e., spline) evaluation on secrets additively shared over $\mathbb{Z}_{2^{n}}$. Grotto improves on the state-of-the-art approaches based on distributed comparison functions (DCFs) in almost every metric, offering asymptotically superior communication and computation costs with the same or lower round complexity. At the heart of Grotto is a novel observation about the structure of the ``tree'' representation underlying the most efficient distributed point functions (DPFs) from the literature, alongside an efficient algorithm that leverages this structure to do with a single DPF what state-of-the-art approaches require many DCFs to do. Our open-source Grotto implementation supports evaluating dozens of useful functions out of the box, including trigonometric and hyperbolic functions (and their inverses); various logarithms; roots, reciprocals, and reciprocal roots; sign testing and bit counting; and over two dozen of the most common (univariate) activation functions from the deep-learning literature.

This paper specifies a new arithmetization-oriented hash function called Tip5. It uses the SHARK design strategy with low-degree power maps in combination with lookup tables, and is tailored to the field with $p=2^{64}-2^{32}+1$ elements. The context motivating this design is the recursive verification of STARKs. This context imposes particular design constraints, and therefore the hash function's arithmetization is discussed at length.

Constructing a supersingular elliptic curve whose endomorphism ring is isomorphic to a given quaternion maximal order (one direction of the Deuring correspondence) is known to be polynomial-time assuming the generalized Riemann hypothesis [KLPT14; Wes21], but notoriously daunting in practice when not working over carefully selected base fields. In this work, we speed up the computation of the Deuring correspondence in general characteristic, i.e., without assuming any special form of the characteristic. Our algorithm follows the same overall strategy as earlier works, but we add simple (yet effective) optimizations to multiple subroutines to significantly improve the practical performance of the method. To demonstrate the impact of our improvements, we show that our implementation achieves highly practical running times even for examples of cryptographic size. One implication of these findings is that cryptographic security reductions based on KLPT-derived algorithms (such as [EHLMP18; Wes22]) have become tighter, and therefore more meaningful in practice. Another is the pure bliss of fast(er) computer algebra: We provide a Sage implementation which works for general primes and includes many necessary tools for computational number theorists' and cryptographers' needs when working with endomorphism rings of supersingular elliptic curves. This includes the KLPT algorithm, translation of ideals to isogenies, and finding supersingular elliptic curves with known endomorphism ring for general primes. Finally, the Deuring correspondence has recently received increased interest because of its role in the SQISign signature scheme [DeF+20]. We provide a short and self-contained summary of the state-of-the-art algorithms without going into any of the cryptographic intricacies of SQISign.

Streamlined NTRU Prime is a lattice-based Key Encapsulation Mechanism (KEM) that is, together with X25519, currently the default algorithm in OpenSSH 9. Being based on lattice assumptions, it is assumed to be secure also against attackers with access to large-scale quantum computers. While Post-Quantum Cryptography (PQC) schemes have been subject to extensive research in the recent years, challenges remain with respect to protection mechanisms against attackers that have additional side-channel information such as the power consumption of a device processing secret data. As a countermeasure to such attacks, masking has been shown to be a promising and effective approach. For public-key schemes, including any recent PQC schemes, usually a mixture of Boolean and arithmetic approaches are applied on an algorithmic level. Our generic hardware implementation of Streamlined NTRU Prime decapsulation, however, follows an idea that until now was assumed to be only applicable to symmetric cryptography: gate-level masking. There, a hardware design that consists of logic gates is transformed into a secure implementation by replacing each gate with a composably secure gadget that operates on uniform random shares of secret values. In our work, we show the feasibility of applying this approach also to PQC schemes and present the first Public-Key Cryptography (PKC) – pre- and post-quantum – implementation masked at gate level considering several trade-offs and design choices. We synthesize our implementation both for Artix-7 Field-Programmable Gate Arrays (FPGAs) and 45 nm Application-Specific Integrated Circuits (ASICs), yielding practically feasible results regarding area, randomness demand and latency. Finally, we also analyze the applicability of our concept to Kyber which will be standardized by the National Institute of Standards and Technology (NIST).

In this work, we investigate the BGV scheme as implemented in HElib. We begin by performing an implementation-specific noise analysis of BGV. This allows us to derive much tighter bounds than what was previously done. To confirm this, we compare our bounds against the state of the art. We find that, while our bounds are at most $1.8$ bits off the experimentally observed values, they are as much as $29$ bits tighter than previous work. Finally, to illustrate the importance of our results, we propose new and optimised parameters for HElib. In HElib, the special modulus is chosen to be $k$ times larger than the current ciphertext modulus $Q_i$. For a ratio of subsequent ciphertext moduli $\log\left( \frac{Q_i}{Qi−1}\right) = 54$ (a very common choice in HElib), we can optimise $k$ by up to $26$ bits. This means that we can either enable more multiplications without having to switch to larger parameters, or reduce the size of the evaluation keys, thus reducing on communication costs in relevant applications. We argue that our results are near-optimal.

Thesecurityofmanyprotocolssuchasvotingandblockchains relies on a secure source of randomness. Decentralised Randomness Beacon (DRB) has been considered as a promising approach, where a set of participants jointly generates a sequence of random outputs. While the DRBs have been extensively studied, they failed to capture the advantage that some participants learn random outputs earlier than other participants. In time-sensitive protocols whose execution depends on the randomness from a DRB, such an advantage allows the adversary to behave adaptively according to random outputs, compromising the fairness and/or security in these protocols. In this paper, we formalise a new property, delivery-fairness, to quantify the advantage. In particular, we distinguish two aspects of delivery-fairness, namely length-advantage, i.e., how many random outputs an adversary can learn earlier than correct participants, and time-advantage, i.e., how much time an adversary can learn a given random output earlier than correct participants. In addition, we prove the lower bound of delivery-fairness showing optimal guarantee. We further analyse the delivery-fairness guarantee of state-of-the-art DRBs and discuss insights, which, we show through case studies, could help improve delivery-fairness of existing systems to its optimal.

In this paper, we present the first chosen-ciphertext (CC) cache-timing attacks on the reference implementation of HQC. We build a cache-timing based distinguisher for implementing a plaintext-checking (PC) oracle. The PC oracle uses side-channel information to check if a given ciphertext decrypts to a given message. This is done by identifying a vulnerability during the generating process of two vectors in the reference implementation of HQC. We also propose a new method of using PC oracles for chosen-ciphertext side-channel attacks against HQC, which may have independent interest. We show a general proof-of-concept attack, where we use the Flush&Reload technique and also derive, in more detail, a practical attack on an HQC execution on Intel SGX, where the Prime&Probe technique is used. We show the exact path to do key recovery by explaining the detailed steps, using the PC oracle. In both scenarios, the new attack requires $53,857$ traces on average with much fewer PC oracle calls than the timing attack of Guo et al. CHES 2022 on an HQC implementation.

Recently, linear structures and algebraic attacks have been widely used in preimage attacks on round-reduced Keccak. Inherited by pioneers' work, we make some improvements for 3-round Keccak-256 and 4-round Keccak[r=640, c=160]. For 3-round Keccak-256, we introduce a three-stage model to deal with the unsatisfied restrictions while bringing more degrees of freedom at the same time. Besides, we show that guessing values for different variables will result in different complexity of solving time. With these techniques, the guessing times can be decreased to 2^{52}, and the solving time for each guess can be decreased to around 2^{5.2} 3-round Keccak calls. As a result, the complexity of finding a preimage for 3-round Keccak-256 can be decreased to around 2^{57.2}. For 4-round Keccak[r=640, c=160], an instance of the Crunchy Contest, we use some techniques to save degrees of freedom and make better linearization. Based on these techniques, we build an MILP model and obtain an attack with better complexity of around 2^{60.9}. The results of 3-round Keccak-256 and 4-round Keccak[r=640, c=160] are verified with real examples.

Secure neural network inference has been a promising solution to private Deep-Learning-as-a-Service, which enables the service provider and user to execute neural network inference without revealing their private inputs. However, the expensive overhead of current schemes is still an obstacle when applied in real applications. In this work, we present \textsc{Meteor}, an online communication-efficient and fast secure 3-party computation neural network inference system aginst semi-honest adversary in honest-majority. The main contributions of \textsc{Meteor} are two-fold: \romannumeral1) We propose a new and improved 3-party secret sharing scheme stemming from the \textit{linearity} of replicated secret sharing, and design efficient protocols for the basic cryptographic primitives, including linear operations, multiplication, most significant bit extraction, and multiplexer. \romannumeral2) Furthermore, we build efficient and secure blocks for the widely used neural network operators such as Matrix Multiplication, ReLU, and Maxpool, along with exploiting several specific optimizations for better efficiency. Our total communication with the setup phase is a little larger than SecureNN (PoPETs'19) and \textsc{Falcon} (PoPETs'21), two state-of-the-art solutions, but the gap is not significant when the online phase must be optimized as a priority. Using \textsc{Meteor}, we perform extensive evaluations on various neural networks. Compared to SecureNN and \textsc{Falcon}, we reduce the online communication costs by up to $25.6\times$ and $1.5\times$, and improve the running-time by at most $9.8\times$ (resp. $8.1\times$) and $1.5\times$ (resp. $2.1\times$) in LAN (resp. WAN) for the online inference.

Multiparty garbling is the most popular approach for constant-round secure multiparty computation (MPC). Despite being the focus of significant research effort, instantiating prior approaches to multiparty garbling results in constant-round MPC that can not realistically accommodate large numbers of parties. In this work we present the first global-scale multiparty garbling protocol. The per-party communication complexity of our protocol decreases as the number of parties participating in the protocol increases --- for the first time matching the asymptotic communication complexity of non-constant round MPC protocols. Our protocol achieves malicious security in the honest-majority setting and relies on the hardness of the Learning Party with Noise assumption.

In LWE-based KEMs, observed decryption errors leak information about the secret key in the form of equations or inequalities. Several practical fault attacks have already exploited such leakage by either directly applying a fault or enabling a chosen-ciphertext attack using a fault. When the leaked information is in the form of inequalities, the recovery of the secret key is not trivial. Recent methods use either statistical or algebraic methods (but not both), with some being able to handle incorrect information. Having in mind that integration of the side-channel information is a crucial part of several classes of implementation attacks on LWE-based schemes, it is an important question whether statistically processed information can be successfully integrated in lattice reduction algorithms. We answer this question positively by proposing an error-tolerant combination of statistical and algebraic methods that make use of the advantages of both approaches. The combination enables us to improve upon existing methods -- we use both fewer inequalities and are more resistant to errors. We further provide precise security estimates based on the number of available inequalities. Our recovery method applies to several types of implementation attacks in which decryption errors are used in a chosen-ciphertext attack. We practically demonstrate the improved performance of our approach in a key-recovery attack against Kyber with fault-induced decryption errors.

Non-interactive zero-knowledge proofs (NIZKs) and in particular succinct NIZK arguments of knowledge (zk-SNARKs) increasingly see real-world adoption in large and complex systems. Many zk-SNARKs require a trusted setup, i.e., a common reference string (CRS), and for practical use it is desirable to reduce the trust in the CRS generation. The latter can be achieved via the notions of subversion or updatable CRS. Another important property when deployed in large systems is the ability to securely compose them to obtain more complex protocols, e.g., via the Universal Composability (UC) framework. Relying on the UC framework allows arbitrary and secure composition of protocols in a modular way. In this work, we investigate whether zk-SNARKs can provide updatability and composability simultaneously. This is a challenging task as the UC framework rules out several natural techniques for such a construction. As our main result, we show that it is indeed possible to achieve these properties in a generic and modular way if we relax the succinctness properties of zk-SNARKs slightly to those of a circuit-succinct NIZK which is not witness-succinct, i.e., by increasing the proof size of the underlying zk-SNARK by the size of the witness $w$. We argue that for various practical applications of zk-SNARKs this overhead is acceptable. Our starting point is the Lamassu framework (ACM CCS'20), which we extend in several directions. Our new generic compiler adds only minimal overhead, which we demonstrate by benchmarking its application to the Sonic proof system (ACM CCS'19).

While the efficiency of secure multi-party computation protocols has greatly increased in the last few years, these improvements and protocols are often based on rather unrealistic, idealised, assumptions about how technology is deployed in the real world. In this work we examine multi-party computation protocols in the presence of two major constraints present in deployed systems. Firstly, we consider the situation where the parties are connected not by direct point-to-point connections, but by a star-like topology with a few central post-office style relays. Secondly, we consider MPC protocols with a strong honest majority ($n \gg t/2$) in which we have stragglers (some parties are progressing slower than others). We model stragglers by allowing the adversary to delay messages to and from some parties for a given length of time. We first show that having only a single honest rely is enough to ensure consensus of the messages sent within a protocol; secondly, we show that special care must be taken to describe multiplication protocols in the case of relays and stragglers and that some well known protocols do not guarantee privacy and correctness in this setting; thirdly, we present an efficient honest-majority MPC protocol which can be run on top of the relays and which provides active-security with abort in the case of a strong honest majority, even when run with stragglers. We back up our protocol presentation with both experimental evaluations and simulations of the effect of the relays and delays on our protocol.

The TLS (Transport Layer Security) protocol is the most important, most attacked, most analysed and most used cryptographic protocol in the world today. TLS is critical to the integrity of the Internet, and if it were to be broken e-commerce would become impossible, with very serious implications for the global economy. Furthermore TLS is likely to assume even greater significance in the near future with the rapid growth of an Internet of Things (IoT) -- a multiplicity of internet connected devices all engaged in secure inter-communication. However the impending invention of a Cryptographically Relevant Quantum Computer (CRQC) would represent an existential threat to TLS in its current form. As it stands the latest version TLS1.3, benefiting as it does from years of research and study, provides effective security, but it must soon be updated to resist this new threat. In this research we first undertake a new clean-room implementation of a small-footprint open source TLS1.3, written in C++ and Rust, and suitable for IoT applications. Our implementation is designed to be cryptographically agile, so that it can easily accomodate new post-quantum cryptographic primitives. Next we use this new implementation as a vehicle to study the impact of going post-quantum, with a particular emphasis on the impact on the Internet of Things. Finally we showcase the flexibility of our implementation by proposing an implementation of TLS that uses identity-based encryption to mitigate this impact.

TLS termination, which is essential to network and security infrastructure providers, is an extremely latency sensitive operation that benefits from access to sensitive key material close to the edge. However, increasing regulatory concerns prompt customers to demand sophisticated controls on where their keys may be accessed. While traditional access-control solutions rely on a highly available centralized process to enforce access, the round-trip latency and decreased fault tolerance make this approach unappealing. Furthermore, the desired level of customer control is at odds with customizing the distribution process for each key. To solve this dilemma, we have designed and implemented Portunus, a cryptographic storage and access control system built using a variant of public-key cryptography called attribute-based encryption (ABE). Using Portunus, TLS keys are protected using ABE under a policy chosen by the customer. Each server is issued unique ABE keys based on its attributes, allowing it to decrypt only the TLS keys for which it satisfies the policy. Thus, the encrypted keys can be stored at the edge, with access control enforced passively through ABE. If a server receives a TLS connection but is not authorized to decrypt the necessary TLS key, the request is forwarded directly to the nearest authorized server, further avoiding the need for a centralized coordinator. In comparison, a trivial instantiation of this system using standard public-key cryptography might wrap each TLS key with the key of every authorized data center. This strategy, however, multiplies the storage overhead by the number of data centers. We have deployed Portunus on Cloudflare's global network of over 400 data centers. Our measurements indicate that we can handle millions of requests per second globally, making it one of the largest deployments of ABE.

The usage of convolutional neural networks (CNNs) to break cryptographic systems through hardware side-channels has enabled fast and adaptable attacks on devices like smart cards and TPMs. Current literature proposes fixed CNN architectures designed by domain experts to break such systems, which is time-consuming and unsuitable for attacking a new system. Recently, an approach using neural architecture search (NAS), which is able to acquire a suitable architecture automatically, has been explored. These works use the secret key information in the attack dataset for optimization and only explore two different search strategies using one-dimensional CNNs. We propose a NAS approach that relies only on using the profiling dataset for optimization, making it fully black-box. Using a large-scale experimental parameter study, we explore which choices for NAS, such as 1-D or 2-D CNNs and search strategy, produce the best results on 10 state-of-the-art datasets for Hamming weight and identity leakage models. We show that applying the random search strategy on 1-D inputs results in a high success rate and retrieves the correct secret key using a single attack trace on two of the datasets. This combination matches the attack efficiency of fixed CNN architectures, outperforming them in 4 out of 10 datasets. Our experiments also point toward the need for repeated attack evaluations of machine learning-based solutions in order to avoid biased performance estimates.

Evaluating exact computational resources necessary for factoring large integers by Shor algorithm using an ideal quantum computer is difficult because simplified circuits were used in past experiments, in which qubits and gates were reduced as much as possible by using the features of the integers, though 15 and 21 were factored on quantum computers. In this paper, we implement Shor algorithm for general composite numbers, and factored 96 RSA-type composite numbers up to 9-bit using a quantum computer simulator. In the largest case, $N=511$ was factored within 2 hours. Then, based on these experiments, we estimate the number of gates and the depth of Shor's quantum circuits for factoring 1024-bit and 2048-bit integers. In our estimation, Shor's quantum circuit for factoring 1024-bit integers requires $2.78 \times 10^{11}$ gates, and with depth $2.24 \times 10^{11}$, while $2.23 \times 10^{12}$ gates, and with depth $1.80 \times 10^{12}$ for 2048-bit integers.

We study satisfiability modulo the theory of finite fields and give a decision procedure for this theory. We implement our procedure for prime fields inside the cvc5 SMT solver. Using this theory, we con- struct SMT queries that encode translation validation for various zero knowledge proof compilers applied to Boolean computations. We evalu- ate our procedure on these benchmarks. Our experiments show that our implementation is superior to previous approaches (which encode field arithmetic using integers or bit-vectors).

Because of the rapid growth of Internet of Things (IoT), embedded systems have become an interesting target for experienced attackers. ESP32~\cite{tech-ref-man} is a low-cost and low-power system on chip (SoC) series created by Espressif Systems. The firmware extraction of such embedded systems is a real threat to the manufacturer as it breaks its intellectual property and raises the risk of creating equivalent systems with less effort and resources. In 2019, LimitedResults~\cite{LimitedResultsPown} published power glitch attacks which resulted in dumping secure boot and flash encryption keys stored in the eFuses of ESP32. Therefore, Espressif patched this vulnerability and then advised its customers to use ESP32-V3, which is an updated SoC revision. This new version is hardened against fault injection attacks in hardware and software as announced by Espressif~\cite{ESPpatch}. In this paper, we present for the first time a deep hardware security evaluation for ESP32-V3. The main goal of this evaluation is to extract the firmware encryption key stored in the eFuses. This evaluation includes Fault Injection (FI) and Side-Channel (SC) attacks. First, we use Electromagnetic FI (EMFI) in order to show that ESP32-V3 doesn't resist EMFI. However, by experimental results, we show that this version contains a revised bootloader compared to ESP32-V1, which hardens dumping the eFuse keys by FI. Second, we perform a full SC analysis on the AES accelerator of ESP32-V3. We show that an attacker with a physical access to the device can extract all the keys of the hardware AES-256 after collecting 60K power measurements during the execution of the AES block. Third, we present another SC analysis for the firmware decryption mechanism, by targeting the decryption operation during the power up. Using this knowledge, we demonstrate that the full 256-bit AES firmware encryption key, which is stored in the eFuses, can be recovered by SC analysis using 300K power measurements. Finally, we apply practically the firmware encryption attack on Jade hardware wallet \cite{jade}.

Recent years have witnessed significant advances in programming technology for multi-party computation (MPC), bringing MPC closer to practice and wider applicability. Typical MPC programming frameworks focus on either front-end language design (e.g., Wysteria, Viaduct, SPDZ), or back-end protocol implementation (e.g., ABY, MOTION, SPDZ). We propose a methodology for an MPC compilation toolchain, which by mimicking the compilation methodology of classical compilers enables middle-end (i.e., machine-independent) optimizations, yielding significant improvements. We advance an intermediate language, which we call MPC-IR that can be viewed as the analogue of (enriched) Static Single Assignment (SSA) form. MPC-IR enables backend-independent optimizations in a close analogy to machine-independent optimizations in classical compilers. To demonstrate our approach, we focus on a specific backend-independent optimization, SIMD-vectorization: We devise a novel classical-compiler-inspired automatic SIMD vectorization on MPC-IR. To demonstrate backend independence and quality of our optimization, we evaluate our approach with two mainstream backend frameworks that support multiple types of MPC protocols, namely MOTION and MP-SPDZ, and show significant improvements across the board.

We initiate a formal study of individual cryptography. Informally speaking, an algorithm $\mathsf{Alg}$ is "individual" if, in every implementation of $\mathsf{Alg}$, there always exists an individual user with full knowledge of the cryptographic data $S$ used by $\mathsf{Alg}$. In particular, it should be infeasible to design implementations of this algorithm that would hide $S$ by distributing it between a group of parties using an MPC protocol or outsourcing it to a trusted execution environment. We define and construct two primitives in this model. The first one, called "proofs of individual knowledge", is a tool for proving that a given message is fully known to a single ("individual") machine on the Internet, i.e., it cannot be shared between a group of parties. The second one, dubbed "individual secret sharing", is a scheme for sharing a secret $S$ between a group of parties so that the parties have no knowledge of $S$ as long as they do not reconstruct it. The reconstruction ensures that if the shareholders attempt to collude, one of them will learn the secret entirely. Individual secret sharing has applications for preventing collusion in secret sharing. A central technique for constructing individual cryptographic primitives is the concept of MPC hardness. MPC hardness precludes an adversary from completing a cryptographic task in a distributed fashion within a specific time frame.

Since the post-quantum crypto system CRYSTALS-KYBER has been chosen for standardization by the National Institute for Standards and Technology (US), a formal verification of its correctness and security properties becomes even more relevant. Using the automated theorem prover Isabelle, we are able to formalize the algorithm specifications and parameter sets of Kyber's public key encryption scheme and verify the $\delta$-correctness and indistinguishability under chosen plaintext attack property. However, during the formalization process, several gaps in the pen-and-paper proofs were discovered. All but one gap concerning the error bound $\delta$ could be filled. Calculations in smaller dimensions give examples where the bound $\delta$ is less than the actual error term, violating the correctness property. Since the correctness proof could be formalized up to an application of the module-Learning-with-Errors assumption, we believe that the discrepancy of the original error bound and the formalized version is relatively small. Thus the correctness could be formalized up to a minimal change to the error bound.

As the number of blockchain projects grows, efficient cross-chain interoperability becomes more necessary. A common cross-chain protocol is the two-way peg, which is typically used to transfer assets between blockchains and their sidechains. The criticality of cross-chain protocols require that they are designed with strong security models, which can reduce usability in the form of long transfer times. In this paper, we present Flyover, a repayment protocol to speed up the transfer of bitcoins over federated pegs by allowing untrusted liquidity providers to advance funds for the users. Transfer times are reduced because liquidity providers do not have the same security requirements as the underlying cross-chain protocol. We illustrate the Flyover protocol on the cross-chain interoperability protocol that connects Bitcoin to the RSK sidechain and show how Flyover can reduce transfer times without reducing security. In addition to this, Flyover extends the cross-chain protocol by allowing liquidity providers to make smart contract calls on RSK on behalf of the user.

The ChaCha20-Poly1305 AEAD scheme is being increasingly widely deployed in practice. Practitioners need proven security bounds in order to set data limits and rekeying intervals for the scheme. But the formal security analysis of ChaCha20-Poly1305 currently lags behind that of AES-GCM. The only extant analysis (Procter, 2014) contains a flaw and is only for the single-user setting. We rectify this situation. We prove a multi-user security bound on the AEAD security of ChaCha20-Poly1305 and establish the tightness of each term in our bound through matching attacks. We show how our bound differs both qualitatively and quantitatively from the known bounds for AES-GCM, highlighting how subtle design choices lead to distinctive security properties. We translate our bound to the nonce-randomized setting employed in TLS 1.3 and elsewhere, and we additionally improve the corresponding security bounds for GCM. Finally, we provide a simple yet stronger variant of ChaCha20-Poly1305 that addresses the deficiencies highlighted by our analysis.

We propose a single-tiered hybrid Proof-of-Work consensus protocol to encourage decentralization in bitcoin. Our new mechanism comprises coupled puzzles of which properties differ from each other; the one is the extant outsourceable bitcoin puzzle while the other is non-outsourceable. Our new protocol enables miners to solve either puzzle as they want; therefore, blocks can be generated by either puzzle. Our hybrid consensus can be successfully implemented in bitcoin, because it is backward-compatible with existing bitcoin mining equipment(more precisely, existing bitcoin mining ASICs)

Oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (J. ACM `96), is a primitive that allows a client to perform RAM computations on an external database without revealing any information through the access pattern. For a database of size $N$, well-known lower bounds show that a multiplicative overhead of $\Omega(\log N)$ in the number of RAM queries is necessary assuming $O(1)$ client storage. A long sequence of works culminated in the asymptotically optimal construction of Asharov, Komargodski, Lin, and Shi (CRYPTO `21) with $O(\log N)$ worst-case overhead and $O(1)$ client storage. However, this optimal ORAM is known to be secure only in the honest-but-curious setting, where an adversary is allowed to observe the access patterns but not modify the contents of the database. In the malicious setting, where an adversary is additionally allowed to tamper with the database, this construction and many others in fact become insecure. In this work, we construct the first maliciously secure ORAM with worst-case $O(\log N)$ overhead and $O(1)$ client storage assuming one-way functions, which are also necessary. By the $\Omega(\log N)$ lower bound, our construction is asymptotically optimal. To attain this overhead, we develop techniques to intricately interleave online and offline memory checking for malicious security. Furthermore, we complement our positive result by showing the impossibility of a generic overhead-preserving compiler from honest-but-curious to malicious security, barring a breakthrough in memory checking.

Flow is a high-throughput blockchain with a dedicated step for executing the transactions in a block and a subsequent verification step performed by Verification Nodes. To enforce integrity of the blockchain, the protocol requires a component that prevents Verification Nodes from approving execution results without checking. In our preceding work, we have sketched out an approach called Specialized Proof of Confidential Knowledge (SPoCK). Using SPoCK, nodes can provide evidence to a third party that they both executed the same transaction sequence without revealing the resulting execution trace. The previous Flow white paper presented a basic implementation of such scheme. In this note, we introduce a new SPoCK implementation that is more concise and more efficient than the previous proposal. We first provide a formal generic description of a SPoCK scheme as well as its security definition. Then we propose a new construction of SPoCK based on the BLS signature scheme. We support the new scheme with its proof of security under the appropriate computation assumptions.

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

Private heavy-hitters is a data-collection task where multiple clients possess private bit strings, and data-collection servers aim to identify the most popular strings without learning anything about the clients' inputs. In this work, we introduce PLASMA: a private analytics framework in the three-server setting that protects the privacy of honest clients and the correctness of the protocol against a coalition of malicious clients and a malicious server. Our core primitives are a verifiable incremental distributed point function (VIDPF) and a batched consistency check, which are of independent interest. Our VIDPF introduces new methods to validate client inputs based on hashing. Meanwhile, our batched consistency check uses Merkle trees to validate multiple client sessions together in a batch. This drastically reduces server communication across multiple client sessions, resulting in significantly less communication compared to related works. Finally, we compare PLASMA with the recent works of Asharov et al. (CCS'22) and Poplar (S&P'21) and compare in terms of monetary cost for different input sizes.

The increasing popularity of blockchain technology has affected the way we view many fields related to computer science, with E-commerce being no exception. The distributed nature and transparency of blockchain-based systems is one of its main perks, but it also raises some issues when it comes to privacy. Zero-knowledge proofs are very powerful building blocks when it comes to building privacy-preserving protocols, so, naturally, they have attracted a lot of attention in the last years. Following the recent collapse of the very popular crypto exchange FTX, we believe it is important to analyse how such events can be prevented in the future. This paper aims to highlight solutions that use zero-knowledge to prove solvency.

Blockchain is a newly emerging technology, however, it has proven effective in many applications because it provides multiple advantages, mainly as it represents a trust system in which data is encrypted in a way that cannot be tampered with or forged. Because it contains many details such as smart contracts, consensus, authentication, etc. the blockchain is a fertile ground for researchers where they can continually improve previous versions of these concepts. This paper introduces a new multi-signature scheme based on RSA. This scheme is designed to reduce the blockchain's size and prevent known attacks and is also applicable in many other settings that require multi-signatures. Our scheme is in the plain public key model, which means nodes do not need to prove knowledge or possession of their private key. In which, whatever the number of signers, the final signature size is equal to $O(k)$ where $k$ is a security parameter and no interaction between signers is needed. To verify that a number of parties have signed a shared message $m$, a verifier needs the signature, list of signers, and the message $m$. The presented practical short accountable-subgroup multi-signature (ASM) scheme allows a valid signature to disclose which subset generated the signature. It is worth noting that our multi-signatures with public key aggregation is an interactive two-round protocol and a multi-signature model applied to the entire block and not to individual transactions.

We give a construction of a 2-round blind signature scheme based on the hardness of standard lattice problems (Ring/Module-SIS/LWE and NTRU) with a signature size of 22 KB. The protocol is round-optimal and has a transcript size that can be as small as 60 KB. This blind signature is around $4$ times shorter than the most compact lattice-based scheme based on standard assumptions of del Pino and Katsumata (Crypto 2022) and around $2$ times shorter than the scheme of Agrawal et al. (CCS 2022) based on their newly-proposed one-more-SIS assumption. We also give a construction of a ``keyed-verification'' blind signature scheme in which the verifier and the signer need to share a secret key. The signature size in this case is only $48$ bytes, but more work needs to be done to explore the efficiency of the protocol which generates the signature.

Masking has become one of the most effective approaches for securing hardware designs against side-channel attacks. Regardless of the effort put into correctly implementing masking schemes on a field-programmable gate array (FPGA), leakage can be unexpectedly observed. This is due to the fact that the assumption underlying all masked designs, i.e., the leakages of different shares are independent of each other, may no longer hold in practice. In this regard, extreme temperatures have been shown to be an important factor in inducing leakage, even in correctly masked designs. This has previously been verified using an external heat generator (i.e., a climate chamber). In this paper, we examine whether the leakage can be induced using the circuit components themselves without making any changes to the design. Specifically, we target masked neural networks (NNs) in FPGAs, one of the main building blocks of which is block random access memory (BRAM). In this respect, thanks to the inherent characteristics of NNs, our novel internal heat generators leverage solely the memories devoted to storing the user’s input, especially when frequently writing alternating patterns into BRAMs. The possibility of observing first-order leakage is evaluated by considering one of the most recent and successful first-order secure masked NNs, namely ModuloNET. ModuloNET is specifically designed for FPGAs, where BRAMs are used to store inputs and intermediate computations. Our experimental results demonstrate that undesirable first-order leakage can be observed and exploited by increasing the temperature when an alternating input is applied to the masked NN. To give a better understanding of the impact of extreme heat, we further perform a similar test on the design using an external heat generator, where a similar conclusion can be drawn.

The threat of chip-level tampering and its detection has been widely researched. Hardware Trojan insertions are prominent examples of such tamper events. Altering the placement and routing of a design or removing a part of a circuit for side-channel leakage/fault sensitivity amplification are other instances of such attacks. While semi- and fully-invasive physical verification methods can confidently detect such stealthy tamper events, they are costly, time-consuming, and destructive. On the other hand, virtually all proposed non-invasive side-channel methods suffer from noise and, therefore, have low confidence. Moreover, they require activating the tampered part of the circuit (e.g., the Trojan trigger) to compare and detect the modifications. In this work, we introduce a non-invasive post-silicon tamper detection technique applicable to different classes of tamper events at the chip level without requiring the activation of the malicious circuit. Our method relies on the fact that physical modifications (regardless of their physical, activation, or action characteristics) alter the impedance of the chip. Hence, characterizing the impedance can lead to the detection of the tamper events. To sense the changes in the impedance, we deploy known RF tools, namely, scattering parameters, in which we inject sine wave signals with high frequencies to the power distribution network (PDN) of the system and measure the “echo” of the signal. The reflected signals in various frequency bands reveal different tamper events based on their impact size on the die. To validate our claims, we performed measurements on several proof-of-concept tampered hardware implementations realized on FPGAs manufactured with a 28 nm technology. We further show that deploying the Dynamic Time Warping (DTW) distance can distinguish between tamper events and noise resulting from manufacturing process variation of different chips/boards. Based on the acquired results, we demonstrate that stealthy hardware Trojans, as well as sophisticated modifications of P&R, can be detected.

We consider multi-party information-theoretic private computation. Such computation inherently requires the use of local randomness by the parties, and the question of minimizing the total number of random bits used for given private computations has received considerable attention in the literature. In this work we are interested in another question: given a private computation, we ask how many of the players need to have access to a random source, and how many of them can be deterministic parties. We are further interested in the possible interplay between the number of random sources in the system and the total number of random bits necessary for the computation. We give a number of results. We first show that, perhaps surprisingly, $t$ players (rather than $t+1$) with access to a random source are sufficient for the information-theoretic $t$-private computation of any deterministic functionality over $n$ players for any $t<n/2$; by a result of (Kushilevitz and Mansour, PODC'96), this is best possible. This means that, counter intuitively, while private computation is impossible without randomness, it is possible to have a private computation even when the adversary can control all parties who can toss coins (and therefore sees all random coins). For randomized functionalities we show that $t+1$ random sources are necessary (and sufficient). We then turn to the question of the possible interplay between the number of random sources and the necessary number of random bits. Since for only very few settings in private computation meaningful bounds on the number of necessary random bits are known, we consider the AND function, for which some such bounds are known. We give a new protocol to $1$-privately compute the $n$-player AND function, which uses a single random source and $6$ random bits tossed by that source. This improves, upon the currently best known results (Kushilevitz et al., TCC'19), at the same time the number of sources and the number of random bits (KOPRT19 gives a $2$-source, $8$-bits protocol). This result gives maybe some evidence that for $1$-privacy, using the minimum necessary number of sources one can also achieve the necessary minimum number of random bits. We believe however that our protocol is of independent interest for the study of randomness in private computation.

Privacy-preserving neural network based on secure multi-party computation (MPC) enables multiple parties to jointly train neural network models without revealing sensitive data. In privacy-preserving neural network, the high communication costs of securely computing non-linear functions is the primary performance bottleneck. For commonly used non-linear functions, such as ReLU, existing work adopts an offline-online computation paradigm and utilizes distributed comparison function (DCF) to reduce communication costs. Specifically, these works prepare DCF keys in the offline phase and perform secure ReLU using these DCF keys in the online phase. However, the practicality of existing work is significantly limited due to the substantial size of DCF keys and the heavy reliance on a trusted third party in the offline phase. In this work, we introduce a communication-efficient secure two-party neural network framework called FssNN, which proposes a key-reduced DCF scheme without a trusted third party to enable practical secure training and inference. First, by analyzing the correlations between DCF keys to eliminate redundant parameters, we propose a key-reduced DCF scheme with a compact additive construction, which decreases the size of DCF keys by about $17.9\%$ and the offline communication costs by approximately $28.0\%$. Secondly, by leveraging an MPC-friendly pseudorandom number generator, we propose a secure two-party distributed key generation protocol for our key-reduced DCF, thereby eliminating the reliance on the trusted third party. Finally, we utilize the key-reduced DCF and additive secret sharing to compute non-linear and linear functions, respectively, and design secure computation protocols with constant online communication rounds for neural network operators, reducing the online communication costs by $28.9\% \sim 43.4\%$. We provide formal security proofs and evaluate the performance of FssNN on various models and datasets. Experimental results show that compared to the state-of-the-art framework AriaNN, our framework reduces the total communication costs of secure training and inference by approximately $25.4\%$ and $26.4\%$ respectively.

We put forth a new cryptographic primitive for securely computing inner-products in a scalable, non-interactive fashion: any party can broadcast a public (computationally hiding) encoding of its input, and store a secret state. Given their secret state and the other party's public encoding, any pair of parties can non-interactively compute additive shares of the inner-product between the encoded vectors. We give constructions of this primitive from a common template, which can be instantiated under either the LPN (with non-negligible correctness error) or the LWE (with negligible correctness error) assumptions. Our construction uses a novel twist on the standard non-interactive key exchange based on the Alekhnovich cryptosystem, which upgrades it to a non-interactive inner product protocol almost for free. In addition to being non-interactive, our constructions have linear communication (with constants smaller than all known alternatives) and small computation: using LPN or LWE with quasi-cyclic codes, we estimate that encoding a length-$2^{20}$ vector over a 32-bit field takes less that 2s on a standard laptop; decoding amounts to a single cheap inner-product. We show how to remove the non-negligible error in our LPN instantiation using a one-time, logarithmic-communication preprocessing. Eventually, we show to to upgrade its security to the malicious model using new sublinear-communication zero-knowledge proofs for low-noise LPN samples, which might be of independent interest.

This paper aims to provide a security analysis comparison between three popular instant messaging apps: Signal, WhatsApp and Telegram. The analysis will focus on the encryption protocols used by each app and the security features they offer. The paper will evaluate the strengths and weaknesses of each app, and provide a summary of their overall security posture. Additionally, this paper will discuss other considerations such as user base, data collection and usage policies, and other features which may impact the security of the apps. The results of this analysis will provide insights for individuals and organizations looking to choose a secure instant messaging app for their communication needs. In this paper we reviewed the main encryption standards and we compared the features, traffic analysis, protocols, performance and recent security breaches for WhatsApp, Signal and Telegram. The paper includes packet sniffing using Wireshark and Fiddler.

The purpose of this article is to present,illustrate and to put in evidence a new side- channel attack on RSA cryptosystem based on the generation of prime numbers. The vulnerability of the cryptosystem is spotted during the execution of the key generation step.The probability of success of the attack is around 10-15% in the case of realistic parameters

Public-key quantum money is a cryptographic proposal for using highly entangled quantum states as currency that is publicly verifiable yet resistant to counterfeiting due to the laws of physics. Despite significant interest, constructing provably-secure public-key quantum money schemes based on standard cryptographic assumptions has remained an elusive goal. Even proposing plausibly-secure candidate schemes has been a challenge. These difficulties call for a deeper and systematic study of the structure of public-key quantum money schemes and the assumptions they can be based on. Motivated by this, we present the first black-box separation of quantum money and cryptographic primitives. Specifically, we show that collision-resistant hash functions cannot be used as a black-box to construct public-key quantum money schemes where the banknote verification makes classical queries to the hash function. Our result involves a novel combination of state synthesis techniques from quantum complexity theory and simulation techniques, including Zhandry's compressed oracle technique.

We present a new encoder for hiding parameters in an interval membership function. As an application, we design a simple and efficient virtual black-box obfuscator for evasive decision trees. The security of our construction is proved in the random oracle model. Our goal is to increase the class of programs that have practical and cryptographically secure obfuscators.

We propose a novel methodology to obtain $B$lind signatures that is fundamentally based on the idea of hiding part of the underlying plain signatures under a $Z$ero-knowledge argument of knowledge of the whole signature (hence the shorthand, $BZ$). Our proposal is necessarily non-black-box and stated in the random oracle model. We illustrate the technique by describing two instantiations: a classical setting based on the traditional discrete logarithm assumption, and a post-quantum setting based on the commutative supersingular isogeny Diffie-Hellman (CSIDH) assumption.

There is a line of 'lookup' protocols to show that all elements of a sequence $f\in{\mathbb F}^n$ are contained in a table $t\in{\mathbb F}^d$, for some field ${\mathbb F}$. Lookup has become an important primitive in Zero Knowledge Virtual Machines, and is used for range checks and other parts of the proofs of a correct program execution. In this note we give several variants of the protocol. We adapt it to the situation when there are multiple lookups with the same table (as is usually the case with range checks), and handle also 'bounded lookup' that caps the number of repetitions.

Fully Homomorphic Encryption enables arbitrary computations over encrypted data and it has a multitude of applications, e.g., secure cloud computing in healthcare or finance. Multi-Key Homomorphic Encryption (MKHE) further allows to process encrypted data from multiple sources: the data can be encrypted with keys owned by different parties. In this paper, we propose a new variant of MKHE instantiated with the TFHE scheme. Compared to previous attempts by Chen et al. and by Kwak et al., our scheme achieves computation runtime that is linear in the number of involved parties and it outperforms the faster scheme by a factor of 4.5-6.9x, at the cost of a slightly extended pre-computation. In addition, for our scheme, we propose and practically evaluate parameters for up to 128 parties, which enjoy the same estimated security as parameters suggested for the previous schemes (100 bits). It is also worth noting that our scheme—unlike the previous schemes—did not experience any error in any of our nine experiments, each running 1 000 trials.

We present several new heuristic algorithms to compute class polynomials and modular polynomials modulo a prime $p$ by revisiting the idea of working with supersingular elliptic curves. The best known algorithms to this date are based on ordinary curves, due to the supposed inefficiency of the supersingular case. While this was true a decade ago, the recent advances in the study of supersingular curves through the Deuring correspondence motivated by isogeny-based cryptography has provided all the tools to perform the necessary tasks efficiently. Our main ingredients are two new heuristic algorithms to compute the $j$-invariants of supersingular curves having an endomorphism ring contained in some set of isomorphism class of maximal orders. The first one is derived easily from the existing tools of isogeny-based cryptography, while the second introduces new ideas to perform that task efficiently for a big number of maximal orders at the same time. For each of the polynomials (Hilbert and modular), we obtain two algorithms. The first one, that we will qualify as \textit{direct}, is based on the computation of a set of well-chosen supersingular $j$-invariants defined over $\FF_{p^2}$ and uses the aforementioned algorithm to translate maximal orders to $j$-invariants as its main building block. The second one is a CRT algorithm that applies the direct algorithm on a set of small primes and reconstruct the result modulo $p$ with the chinese remainder theorem. In both cases, the direct algorithm achieves the best known complexity for primes $p$ that are relatively small compared to the discriminant (for the Hilbert case) and to the level (for the modular case). Our CRT algorithms matches the complexities of the state-of-the-art CRT approach based on ordinary curves, while improving some of the steps, thus opening the possibility to a better practical efficiency. Second, we revisit the CRT method for both class and modular polynomials. We show that applying our second heuristic algorithm over supersingular curves to the CRT approach yields the same asymptotic complexity as the best known algorithms based on ordinary curves and we argue that our new approach might be more efficient in practice. The situation appears especially promising for modular polynomials, as our approach reduces the asymptotic cost of elliptic curve operations by a linear factor in the level $\ell$. We obtain an algorithm whose asymptotic complexity is now fully dominated by linear algebra and standard polynomial arithmetic over finite fields.

We introduce a new notion of {\em multiverse threshold signatures} (MTS). In an MTS scheme, multiple universes -- each defined by a set of (possibly overlapping) signers, their weights, and a specific security threshold -- can co-exist. A universe can be (adaptively) created via a non-interactive asynchronous setup. Crucially, each party in the multiverse holds constant-sized keys and releases compact signatures with size and computation time both independent of the number of universes. Given sufficient partial signatures over a message from the members of a specific universe, an aggregator can produce a short aggregate signature relative to that universe. We construct an MTS scheme building on BLS signatures. Our scheme is practical, and can be used to reduce bandwidth complexity and computational costs in decentralized oracle networks. As an example data point, consider a multiverse containing 2000 nodes and 100 universes (parameters inspired by Chainlink's use in the wild) each of which contains arbitrarily large subsets of nodes and arbitrary thresholds. Each node computes and outputs 1 group element as its partial signature; the aggregator performs under 0.7 seconds of work for each aggregate signature, and the final signature of size 192 bytes takes 6.4 ms (or 198K EVM gas units) to verify. For this setting, prior approaches when used to construct MTS, yield schemes that have one of the following drawbacks: (i) partial signatures that are 97$\times$ larger, (ii) have aggregation times 311$\times$ worse, or (iii) have signature size 39$\times$ and verification gas costs 3.38$\times$ larger. We also provide an open-source implementation and a detailed evaluation.

Since the invention of Bitcoin, cryptocurrencies have gained huge popularity. Crypto wallet, as the tool to store and manage the cryptographic keys, is the primary entrance for the public to access cryptocurrency funds. Deterministic wallet is an advanced wallet mech- anism that has been proposed to achieve some appealing virtues, such as low-maintenance, easy backup and recovery, supporting functionali- ties required by cryptocurrencies, and so on. But deterministic wallets still have a long way to be practical in quantum world, and there are also some gaps in the classic world, since there are the following prob- lems waiting to be solved. Firstly, the relying on the state, i.e., stateful. The stateful deterministic wallet scheme must internally maintain and keep refreshing synchronously a state which makes the implementation in practice become more complex. And once one of the states is leaked, thereafter the security notion of unlinkability is cannot be guaranteed (referred to as the weak security notion of forward unlinkability). The second problem is vulnerable. There are security shortfalls in previous works, they suffer a vulnerability when a minor fault happens (say, one derived key is compromised somehow), then the damage is not limited to the leaked derived key, instead, it spreads to the master key and the whole system collapses. Thirdly, the falling short in supporting hot/cold setting. The hot/cold setting is a widely adopted method to effectively reduce the exposure chance of secret keys and hence improving the se- curity of the deterministic wallet system. The last problem is the relying on the weak security notion of unforgeability, in which the adversary is only allowed to query and forge the signatures w.r.t. the public keys that were assigned by the challenger. In this work, we present a new deterministic wallet scheme in quantum world, which is stateless, supports hot/cold setting, satisfiies stronger security notions, and is more efficient. In particular, we reformalize the syntax and security models for deterministic wallets, capturing the func- tionality and security requirements imposed by the practice in cryptocur- rency. Then we propose a deterministic wallet construction and prove its security in the quantum random oracle model. Finally, we show our wal- let scheme is more practicable by analyzing an instantiation of our wallet scheme based on the signature scheme Falcon.

Multi-signature is a protocol where a set of signatures jointly sign a message so that the final signature is significantly shorter than concatenating individual signatures together. Recently, it finds applications in blockchain, where several users want to jointly authorize a payment through a multi-signature. However, in this setting, there is no centralized authority and it could suffer from a rogue key attack where the attacker can generate his own keys arbitrarily. Further, to minimize the storage on blockchain, it is desired that the aggregated public-key and the aggregated signature are both as short as possible. In this paper, we find a compiler that converts a kind of identification (ID) scheme (which we call a linear ID) to a multi-signature so that both the aggregated public-key and the aggregated signature have a size independent of the number of signers. Our compiler is provably secure. The advantage of our results is that we reduce a multi-party problem to a weakly secure two-party problem. We realize our compiler with two ID schemes. The first is Schnorr ID. The second is a new lattice-based ID scheme, which via our compiler gives the first regular lattice-based multi-signature scheme with key-and-signature compact without a restart during signing process.

Many applications in finance and healthcare need access to data from multiple organizations. While these organizations can benefit from computing on their joint datasets, they often cannot share data with each other due to regulatory constraints and business competition. One way mutually distrusting parties can collaborate without sharing their data in the clear is to use secure multiparty computation (MPC). However, MPC’s performance presents a serious obstacle for adoption as it is difficult for users who lack expertise in advanced cryptography to optimize. In this paper, we present Silph, a framework that can automatically compile a program written in a high-level language to an optimized, hybrid MPC protocol that mixes multiple MPC primitives securely and efficiently. Compared to prior works, our compilation speed is improved by up to 30000×. On various database analytics and machine learning workloads, the MPC protocols generated by Silph match or outperform prior work by up to 3.6×.

Two multivariate digital signature schemes, Rainbow and GeMSS, made it into the third round of the NIST PQC competition. However, either made its way to being a standard due to devastating attacks (in one case by Beullens, the other by Tao, Petzoldt, and Ding). How should multivariate cryptography recover from this blow? We propose that, rather than trying to fix Rainbow and HFEv- by introducing countermeasures, the better approach is to return to the classical Oil and Vinegar scheme. We show that, if parametrized appropriately, Oil and Vinegar still provides competitive performance compared to the new NIST standards by most measures (except for key size). At NIST security level 1, this results in either 128-byte signatures with 44 kB public keys or 96-byte signatures with 67 kB public keys. We revamp the state-of-the-art of Oil and Vinegar implementations for the Intel/AMD AVX2, the Arm Cortex-M4 microprocessor, the Xilinx Artix-7 FPGA, and the Armv8-A microarchitecture with the Neon vector instructions set.

We present SCALLOP: SCALable isogeny action based on Oriented supersingular curves with Prime conductor, a new group action based on isogenies of supersingular curves. Similarly to CSIDH and OSIDH, we use the group action of an imaginary quadratic order’s class group on the set of oriented supersingular curves. Compared to CSIDH, the main benefit of our construction is that it is easy to compute the class-group structure; this data is required to uniquely represent — and efficiently act by — arbitrary group elements, which is a requirement in, e.g., the CSI-FiSh signature scheme by Beullens, Kleinjung and Vercauteren. The index-calculus algorithm used in CSI-FiSh to compute the class-group structure has complexity L(1/2), ruling out class groups much larger than CSIDH-512, a limitation that is particularly problematic in light of the ongoing debate regarding the quantum security of cryptographic group actions. Hoping to solve this issue, we consider the class group of a quadratic order of large prime conductor inside an imaginary quadratic field of small discriminant. This family of quadratic orders lets us easily determine the size of the class group, and, by carefully choosing the conductor, even exercise significant control on it — in particular supporting highly smooth choices. Although evaluating the resulting group action still has subexponential asymptotic complexity, a careful choice of parameters leads to a practical speedup that we demonstrate in practice for a security level equivalent to CSIDH-1024, a parameter currently firmly out of reach of index-calculus-based methods. However, our implementation takes 35 seconds (resp. 12.5 minutes) for a single group-action evaluation at a CSIDH-512-equivalent (resp. CSIDH-1024-equivalent) security level, showing that, while feasible, the SCALLOP group action does not achieve realistically usable performance yet.

Critical and widely used cryptographic protocols have repeatedly been found to contain flaws in their design and their implementation. A prominent class of such vulnerabilities is logical attacks, e.g. attacks that exploit flawed protocol logic. Automated formal verification methods, based on the Dolev-Yao (DY) attacker, formally define and excel at finding such flaws, but operate only on abstract specification models. Fully automated verification of existing protocol implementations is today still out of reach. This leaves open whether such implementations are secure. Unfortunately, this blind spot hides numerous attacks, such as recent logical attacks on widely used TLS implementations introduced by implementation bugs. We answer by proposing a novel and effective technique that we call DY model-guided fuzzing, which precludes logical attacks against protocol implementations. The main idea is to consider as possible test cases the set of abstract DY executions of the DY attacker, and use a novel mutation-based fuzzer to explore this set. The DY fuzzer concretizes each abstract execution to test it on the program under test. This approach enables reasoning at a more structural and security-related level of messages represented as formal terms (e.g. decrypt a message and re-encrypt it with a different key) as opposed to random bit-level modifications that are much less likely to produce relevant logical adversarial behaviors. We implement a full-fledged and modular DY protocol fuzzer. We demonstrate its effectiveness by fuzzing three popular TLS implementations, resulting in the discovery of four novel vulnerabilities.

In recent works of Li the noisy subset product problem (also known as subset product with errors) was invented and applied to cryptography. To better understand its hardness, we give a quantum annealing algorithm for it. Our algorithm is the first algorithm for the problem. We also give the first quantum annealing algorithm for the subset product problem. The efficiencies of both algorithms rely on the fundamental efficiency of quantum annealing. At the end we give two lattice algorithms for both problems via solving the closest vector problem. The complexities of the lattice algorithms depend on the complexities of solving the closest vector problem in two special lattices. They are efficient when the special closest vector problems fall into the regime of bounded distance decoding problems that can be efficiently solved using existing methods based on the LLL algorithm or Babai's nearest plane algorithm.

Voting mechanisms allow the expression of the elections by a democratic approach. Any voting scheme must ensure, preferably in an efficient way, a series of safety measures such as confidentiality, integrity and anonymity. Since the 1980s, the concept of electronic voting became more and more of interest, being an advantageous or even necessary alternative for the organization of secure elections. In this paper, we give an overview for the e-voting mechanisms together with the security features they must fulfill. Then we focus on the blind signature paradigm, specifically on the Pairing Free Identity-Based Blind Signature Scheme with Message Recovery (PF-IDBS-MR). Our goal is to give a better understanding on the PF-IDBS-MR scheme by offering an adaptation on the standard voting protocol’s phases. More important, we analyze if the general security requirements and the recommendations proposed by the Council of Europe are met by the scheme.

We introduce incoercible digital signature schemes, a variant of a standard digital signature. Incoercible signatures enable signers, when coerced to produce a signature for a message chosen by an attacker, to generate fake signatures that are indistinguishable from real signatures, even if the signer is compelled to reveal their full history (including their secret signing keys and any randomness used to produce keys/signatures) to the attacker. Additionally, we introduce an authenticator that can detect fake signatures, which ensures that coercion is identified. We present a formal security model for incoercible signature schemes that comprises an established definition of unforgeability and captures new notions of weak receipt-freeness, strong receipt-freeness and coercion-resistance. We demonstrate that an incoercible signature scheme can be viewed as a transformation of any generic signature scheme. Indeed, we present two incoercible signature scheme constructions that are built from a standard signature scheme and a sender-deniable encryption scheme. We prove that our first construction satisfies coercion-resistance, and our second satisfies strong receipt-freeness. We conclude by presenting an extension to our security model: we show that our security model can be extended to the designated verifier signature scheme setting in an intuitive way as the designated verifier can assume the role of the authenticator and detect coercion during the verification process.

In practical operational networks, it is essential to validate path integrity, especially when untrusted intermediate nodes are from numerous network infrastructures operated by several network authorities. Current solutions often reveal the entire path to all parties involved, which may potentially expose the network structures to malicious intermediate attackers. Additionally, there is no prior work done to provide a systematic approach combining the complete lifecycle of packet delivery, i.e., path slicing, path validation and path rerouting, leaving these highly-intertwined modules completely separated. In this work, we present a decentralized privacy-preserving path validation system 𝑃3𝑉 that integrates our novel path validation protocol with an efficient path slicing algorithm and a malice-resilient path rerouting mechanism. Specifically, leveraging Non-Interactive Zero-Knowledge proofs, our path validation protocol XOR-Hash-NIZK protects the packet delivery tasks against information leakage about multi-hop paths and potentially the underlying network infrastructures. We implemented and evaluated our system on a state-of-the-art 5G Dispersed Computing Testbed simulating a multi-authority network. Our results show that while preserving the privacy of paths and nodes and enhancing the security of network service, our system optimizes the performance trade-off between network service quality and security/privacy.

An important research direction in secure multi-party computation (MPC) is to improve the efficiency of the protocol. One idea that has recently received attention is to consider a slightly weaker security model than full malicious security -- the so-called setting of $\textit{covert security}$. In covert security, the adversary may cheat but only is detected with certain probability. Several works in covert security consider the offline/online approach, where during a costly offline phase correlated randomness is computed, which is consumed in a fast online phase. State-of-the-art protocols focus on improving the efficiency by using a covert offline phase, but ignore the online phase. In particular, the online phase is usually assumed to guarantee security against malicious adversaries. In this work, we take a fresh look at the offline/online paradigm in the covert security setting. Our main insight is that by weakening the security of the online phase from malicious to covert, we can gain significant efficiency improvements during the offline phase. Concretely, we demonstrate our technique by applying it to the online phase of the well-known TinyOT protocol (Nielsen et al., CRYPTO '12). The main observation is that by reducing the MAC length in the online phase of TinyOT to $t$ bits, we can guarantee covert security with a detection probability of $1- \frac{1}{2^t}$. Since the computation carried out by the offline phase depends on the MAC length, shorter MACs result in a more efficient offline phase and thus speed up the overall computation. Our evaluation shows that our approach reduces the communication complexity of the offline protocol by at least 35% for a detection rate up to $\frac{7}{8}$. In addition, we present a new generic composition result for analyzing the security of online/offline protocols in terms of concrete security.

Applying the pothole method on the factors of numbers of the form $2^n-1$, we prove the stronger inequality $$\iota(2^n-1)\leq n+1-\sum \limits_{j=1}^{\lfloor \frac{\log n}{\log 2}\rfloor}\xi(n,j)+3\lfloor\frac{\log n}{\log 2}\rfloor$$ for all $n\in \mathbb{N}$ with $n\geq 64$ for $0\leq \xi(n,j)<1$, where $\iota(\cdot)$ denotes the length of the shortest addition chain producing $\cdot$. This inequality is stronger than $$\iota(r)<\frac{\log r}{\log 2}(1+\frac{1}{\log \log r}+\frac{2\log 2}{(\log r)^{1-\log 2}})$$ in the case $r=2^n-1$ but slightly weaker than the conjectured inequality $$\iota(2^n-1)\leq n-1+\iota(n).$$

This paper presents a new profiling side-channel attack on CRYSTALS-Dilithium, the new NIST primary standard for quantum-safe digital signatures. An open source implementation of CRYSTALS-Dilithium is already available, with constant-time property as a consideration for side-channel resilience. However, this implementation does not protect against attacks that exploit intermediate data leakage. We show how to exploit a new leakage on a vector generated during the signing process, for which the costly protection by masking is still a matter of debate. With a corpus of 700000 messages, we design a template attack that enables us to efficiently predict whether a given coefficient in one coordinate of this vector is zero or not. By gathering signatures and being able to make the correct predictions for each index, and then using linear algebra methods, this paper demonstrates that one can recover part of the secret key that is sufficient to produce universal forgeries. While our paper deeply discusses the theoretical attack path, it also demonstrates the validity of the assumption regarding the required leakage model from practical experiments with the reference implementation on an ARM Cortex-M4. We need approximately a day to collect enough representatives and one more day to perform the traces acquisition on our target.

Homomorphic encryption (HE) is a promising technique for privacy-preserving computations, especially the word-wise HE schemes that allow batching. However, the high computational overhead hinders the deployment of HE in real-word applications. GPUs are often used to accelerate execution, but a comprehensive performance comparison of different schemes on the same platform is still missing. In this work, we fill this gap by implementing three word-wise HE schemes BGV, BFV, and CKKS on GPU, with both theoretical and engineering optimizations. We enhance the hybrid key-switching technique, significantly reducing the computational and memory overhead. We explore several kernel fusing strategies to reuse data, resulting in reduced memory access and IO latency, and enhancing the overall performance. By comparing with the state-of-the-art works, we demonstrate the effectiveness of our implementation. Meanwhile, we introduce a unified framework that finely integrates our implementation of the three schemes, covering almost all scheme functions and homomorphic operations. We optimize the management of pre-computation, RNS bases, and memory in the framework, to provide efficient and lowlatency data access and transfer. Based on this framework, we provide a thorough benchmark of the three schemes, which can serve as a reference for scheme selection and implementation in constructing privacy-preserving applications. Our library is available for access at https://github.com/encryptorion-lab/phantom-fhe. It is released under the GPLv3 license.

On-line/off-line encryption schemes enable the fast encryption of a message from a pre-computed coupon. The paradigm was put forward in the case of digital signatures. This work introduces a compact public-key additively homomorphic encryption scheme. The scheme is semantically secure under the decisional composite residuosity (DCR) assumption. Compared to Paillier cryptosystem, it merely requires one or two integer additions in the on-line phase and no increase in the ciphertext size. This work also introduces a compact on-line/off-line trapdoor commitment scheme featuring the same fast on-line phase. Finally, applications to chameleon signatures are presented.

The goals of cryptography are achieved using mathematically strong crypto-algorithms, which are adopted for securing data and communication. Even though the algorithms are mathematically secure, the implementation of these algorithms may be vulnerable to side-channel attacks such as timing and power analysis attacks. One of the effective countermeasures against such attacks is Threshold Implementation(TI). However, TI realization in crypto-device introduces hardware complexity, so it shall not be suitable for resource-constrained devices. Therefore, there is a need for efficient and effective countermeasure techniques for resource-constrained devices. In this work, we propose a lightweight countermeasure using an Arbiter Physical Unclonable Function (A-PUF) to obfuscate intermediate values in the register for rolled and unrolled implementation of Advanced Encryption Standard (AES). The countermeasure is realized in rolled (iterative) implementation of AES in a 65nm Field Programmable Gate Array (FPGA). We have analyzed the security strength and area of the obfuscated AES using A-PUF and compared it with conventional (rolled AES) and masked TI of AES. Further, we have illustrated the effectiveness of pre-charge and neutralizing countermeasures to strengthen the side channel resistance. We have discussed the complexity of mounting a side channel and modeling attacks on obfuscated AES using A-PUF.

This study presents a proof-of-concept for a cognitive-based authentication system that uses an individual's writing style as a unique identifier to grant access to a system. A machine learning SVM model was trained on these features to distinguish between texts generated by each user. The stylometric feature vector was then used as an input to a key derivation function to generate a unique key for each user. The experiment results showed that the developed system achieved up to 87.42\% accuracy in classifying texts as written, and the generated keys were found to be secure and unique. We explore the intersection between natural intelligence, cognitive science, and cryptography, intending to develop a cognitive cryptography system. The proposed system utilizes behavioral features from linguistic-biometric data to detect and classify users through stylometry. This information is then used to generate a cryptographic key for authentication, providing a new level of security in access control. The field of cognitive cryptography is relatively new and has yet to be fully explored, making this research particularly relevant and essential. Through our study, we aim to contribute to understanding the potential of cognitive cryptography and its potential applications in securing access to sensitive information.

Ransomware is a malware that employs encryption to hold a victim's data, causing irreparable loss and monetary incentives to individuals or business organizations. The occurrence of ransomware attacks has been increasing significantly and as the attackers are investing more creativity and inventiveness into their threats, the struggle of fighting against ill-themed activities has become more difficult and even time and energy-draining. Therefore, recent researches try to shed some light on combining machine learning with defense mechanisms for detecting this type of malware. Machine learning allows anti-ransomware systems to become more accurate at predicting outcomes or behaviors of the attacks and is vastly used in the advanced research of cybersecurity. In this paper we analyze how machine learning can improve malware recognition in order to stand against critical security issues, giving a brief, yet comprehensive overview of this thriving topic in order to facilitate future research. We also briefly present the most important events of 2022 in terms of ransomware attacks, providing details about the ransoms demanded.

Most cryptographic protocols model a player’s knowledge of secrets in a simple way. Informally, the player knows a secret in the sense that she can directly furnish it as a (private) input to a protocol, e.g., to digitally sign a message. The growing availability of Trusted Execution Environments (TEEs) and secure multiparty computation, however, undermines this model of knowledge. Such tools can encumber a secret sk and permit a chosen player to access sk conditionally, without actually knowing sk. By permitting selective access to sk by an adversary, encumbrance of secrets can enable vote-selling in cryptographic voting schemes, illegal sale of credentials for online services, and erosion of deniability in anonymous messaging systems. Unfortunately, existing proof-of-knowledge protocols fail to demonstrate that a secret is unencumbered. We therefore introduce and formalize a new notion called complete knowledge (CK). A proof (or argument) of CK shows that a prover does not just know a secret, but also has fully unencumbered knowledge, i.e., unrestricted ability to use the secret. We introduce two practical CK schemes that use special-purpose hardware, specifically TEEs and off-the-shelf mining ASICs. We prove the security of these schemes and explore their practical deployment with a complete, end-to-end prototype with smart-contract verification that supports both. We show how CK can address encumbrance attacks identified in previous work. Finally, we introduce two new applications enabled by CK that involve proving ownership of blockchain assets.

State-of-the-art sensors for measuring FPGA voltage fluctuations are time-to-digital converters (TDCs). They allow detecting voltage fluctuations in the order of a few nanoseconds. The key building component of a TDC is a delay line, typically implemented as a chain of fast carry propagation multiplexers. In FPGAs, the fast carry chains are constrained to dedicated logic and routing, and need to be routed strictly vertically. In this work, we present an alternative approach to designing on-chip voltage sensors, in which the FPGA routing resources replace the carry logic. We present three variants of what we name a routing delay sensor (RDS): one vertically constrained, one horizontally constrained, and one free of any constraints. We perform a thorough experimental evaluation on both the Sakura-X side-channel evaluation board and the Alveo U200 datacenter card, to evaluate the performance of the RDS sensors in the context of a remote power side-channel analysis attack. The results show that our best RDS implementation in most cases outperforms the TDC. On average, for breaking the full 128-bit key of an AES-128 cryptographic core, an adversary requires 35% fewer side-channel traces when using the RDS than when using the TDC. Besides making the attack more effective, given the absence of the placement and routing constraint, the RDS sensor is also easier to deploy.

SPHINCS+ is a hash-based digital signature scheme that was selected by NIST in their post-quantum cryptography standardization process. The establishment of a universal forgery on the seminal scheme SPHINCS was shown to be feasible in practice by injecting a fault when the signing device constructs any non-top subtree. Ever since the attack has been made public, little effort was spent to protect the SPHINCS family against attacks by faults. This paper works in this direction in the context of SPHINCS+ and analyzes the current algorithms that aim to prevent fault-based forgeries. First, the paper adapts the original attack to SPHINCS+ reinforced with randomized signing and extends the applicability of the attack to any combination of faulty and valid signatures. Considering the adaptation, the paper then presents a thorough analysis of the attack. In particular, the analysis shows that, with high probability, the security guarantees of SPHINCS+ significantly drop when a single random bit flip occurs anywhere in the signing procedure and that the resulting faulty signature cannot be detected with the verification procedure. The paper shows both in theory and experimentally that the countermeasures based on caching the intermediate W-OTS+s offer a marginally greater protection against unintentional faults, and that such countermeasures are circumvented with a tolerable number of queries in an active attack. Based on these results, the paper recommends real-world deployments of SPHINCS+ to implement redundancy checks.

The use of traditional cryptography based on symmetric keys has been replaced with the revolutionary idea discovered by Diffie and Hellman in 1976 that fundamentally changed communication systems by ensuring a secure transmission of information over an insecure channel. Nowadays public key cryptography is frequently used for authentication in e-commerce, digital signatures and encrypted communication. Most of the public key cryptosystems used in practice are based on integer factorization (the famous RSA cryptosystem proposed by Rivest, Shamir and Adlemann), respectively on the discrete logarithm (in finite curves or elliptic curves). However these systems suffer from two potential drawbacks like efficiency because they must use large keys to maintain security and of course security breach with the advent of the quantum computer as a result of Peter Shor's discovery in 1999 of the polynomial algorithm for solving problems such factorization of integers and discrete logarithm.

TRNG is an essential component for security applications. A vulnerable TRNG could be exploited to facilitate potential attacks or be related to a reduced key space, and eventually results in a compromised cryptographic system. A digital FIRO-/GARO-based TRNG with high throughput and high entropy rate was introduced by Jovan Dj. Golić (TC’06). However, the fact that periodic oscillation is a main failure of FIRO-/GARO-based TRNGs is noticed in the paper (Markus Dichtl, ePrint’15). We verify this problem and estimate the consequential entropy loss using Lyapunov exponents and the test suite of the NIST SP 800-90B standard. To address the problem of periodic oscillations, we propose several implementation guidelines based on a gate-level model, a design methodology to build a reliable GARO-based TRNG, and an online test to improve the robustness of FIRO-/GARO-based TRNGs. The gate-level implementation guidelines illustrate the causes of periodic oscillations, which are verified by actual implementation and bifurcation diagram. Based on the design methodology, a suitable feedback polynomial can be selected by evaluating the feedback polynomials. The analysis and understanding of periodic oscillation and FIRO-/GARO-based TRNGs are deepened by delay adjustment. A TRNG with the selected feedback polynomial may occasionally enter periodic oscillations, due to active attacks and the delay inconstancy of implementations. This inconstancy might be caused by self-heating, temperature and voltage fluctuation, and the process variation among different silicon chips. Thus, an online test module, as one indispensable component of TRNGs, is proposed to detect periodic oscillations. The detected periodic oscillation can be eliminated by adjusting feedback polynomial or delays to improve the robustness. The online test module is composed of a lightweight and responsive detector with a high detection rate, outperforming the existing detector design and statistical tests. The areas, power consumptions and frequencies are evaluated based on the ASIC implementations of a GARO, the sampling circuit and the online test module. The gate-level implementation guidelines promote the future establishment of the stochastic model of FIRO-/GARO-based TRNGs with a deeper understanding.

We propose a threshold encryption scheme with two-party decryption, where one of the keyshares may be stored and used in a device that is able to provide only weak security for it. We state the security properties the scheme needs to have to support such use-cases, and construct a scheme with these properties.

Designing an efficient solution for Byzantine broadcast is an important problem for many distributed computing and cryptographic tasks. There have been many attempts to achieve sub-quadratic communication complexity in several directions, both in theory and practice, all with pros and cons. This paper initiates the study of another attempt: improving the amortized communication complexity of multi-shot Byzantine broadcast. Namely, we try to improve the average cost when we have sequential multiple broadcast instances. We present a protocol that achieves optimal amortized linear complexity under an honest majority. Our core technique is to efficiently form a network for disseminating the sender's message by keeping track of dishonest behaviors over multiple instances. We also generalize the technique for the dishonest majority to achieve amortized quadratic communication complexity.

Generating supersingular elliptic curves of unknown endomorphism ring has been a problem vexing isogeny-based cryptographers for several years. A recent development has proposed a trusted setup protocol to generate such a curve, where each participant generates and proves knowledge of an isogeny. Thus, the construction of efficient proofs of knowledge of isogeny has developed new interest. Historically, the isogeny community has assumed that obtaining isogeny proofs of knowledge from generic proof systems, such as zkSNARKs, was not a practical approach. We contribute the first concrete result in this area by applying Aurora (EUROCRYPT'19), Ligero (CCS'17) and Limbo (CCS'21) to an isogeny path relation, and comparing their performance to a state-of-the-art, tailor-made protocol for the same relation. In doing so, we show that modern generic proof systems are competitive when applied to isogeny assumptions, and provide an order of magnitude ($3\textrm{-}10\times$) improvement to proof and verification times, with similar proof sizes. In addition, these proofs provide a stronger notion of soundness, and statistical zero-knowledge; a property that has only recently been achieved in isogeny PoKs. Independently, this technique shows promise as a component in the design of future isogeny-based or other post-quantum protocols.

Troika is a sponge-based hash function designed by Kölbl, Tischhauser, Bogdanov and Derbez in 2019. Its specificity is that it is defined over $\mathbb{F}_3$ in order to be used inside IOTA’s distributed ledger but could also serve in all settings requiring the generation of ternary randomness. To be used in practice, Troika needs to be proven secure against state-of-the-art cryptanalysis. However, there are today almost no analysis tools for ternary designs. In this article we take a step in this direction by analyzing the propagation of differential trails of Troika and by providing bounds on the weight of its trails. For this, we adapt a well-known framework for trail search designed for KECCAK and provide new advanced techniques to handle the search on $\mathbb{F}_3$. Our work demonstrates that providing analysis tools for non-binary designs is a highly non-trivial research direction that needs to be enhanced in order to better understand the real security offered by such non-conventional primitives.

In the context of masking, which is the dominant technique for protecting cryptographic hardware designs against SCA attacks, the focus has long been on the design of masking schemes that guarantee provable security in the presence of glitches. Unfortunately, achieving this comes at the cost of increased latency, since registers are required to stop glitch propagation. Previous work has attempted to reduce latency by eliminating registers, but the exponential increase in area makes such approaches impractical. Some relatively new attempts have used DRP logic styles to avoid glitches in algorithmically masked circuits. Promising approaches in this area include LMDPL and SESYM, presented at CHES 2020 and CHES 2022 respectively. Both schemes allow masking of arbitrary functions with only one cycle latency. However, even if glitches no longer occur, there are other physical defaults that may violate the security of a glitch-free masked circuit. The imbalanced delay of dual rails is a known security problem for DRP logic styles such as WDDL, but is not covered by the known security models, e.g., robust probing model. In this work, we illustrate that imbalanced signal delays pose a threat to the security of algorithmically masked circuits implemented with DRP logic, both in theory and practice. Notably, we underscore the security of LMDPL even when delays are taken into account, contrasting with the vulnerability observed in SESYM under similar conditions. Consequently, our findings highlight the critical importance of addressing imbalanced delays in the design of masked circuits using DRP logic. In particular, our findings motivate the need for an appropriate security model, and imply that relying solely on the probing security model and avoiding glitches may be insufficient to construct secure circuits.

A decisive contribution to the all-embracing protection of cryptographic software, especially on embedded devices, is the protection against SCA attacks. Masking countermeasures can usually be integrated into the software during the design phase. In theory, this should provide reliable protection against such physical attacks. However, the correct application of masking is a non-trivial task that often causes even experts to make mistakes. In addition to human-caused errors, micro-architectural CPU effects can lead even a seemingly theoretically correct implementation to fail to satisfy the desired level of security in practice. This originates from different components of the underlying CPU which complicates the tracing of leakage back to a particular source and hence avoids making general and device-independent statements about its security. PROLEAD has recently been presented at CHES 2022 and has originally been developed as a simulation-based tool to evaluate masked hardware designs. In this work, we adapt PROLEAD for the evaluation of masked software, and enable the transfer of the already known benefits of PROLEAD into the software world. These include (1) evaluation of larger designs compared to the state of the art, e.g. a full AES masked implementation, and (2) formal verification under our new generic leakage model for CPUs. Concretely, we formalize leakages, observed across different CPU architectures, into a generic abstraction model that includes all these leakages and is therefore independent of a specific CPU design. Our resulting tool PROLEAD_SW allows to provide a formal statement on the security based on the derived generic model. As a concrete result, using PROLEAD_SW we evaluated the security of several publicly available masked software implementations in our new generic leakage model and reveal multiple vulnerabilities.

In this note we explain how to compute $n$ KZG proofs for a polynomial of degree $d$ in time superlinear of $(n+d)$. Our technique is used in lookup arguments and vector commitment schemes.

The applicability of lattice reduction to a wide variety of cryptographic situations makes it an important part of the cryptanalyst's toolbox. Despite this, the construction of lattices and use of lattice reduction algorithms for cryptanalysis continue to be somewhat difficult to understand for beginners. This tutorial aims to be a gentle but detailed introduction to lattice-based cryptanalysis targeted towards the novice cryptanalyst with little to no background in lattices. We explain some popular attacks through a conceptual model that simplifies the various components of a lattice attack.

In a single secret leader election (SSLE), a set of participants elect exactly one leader, who remains anonymous until they announce themselves by providing a proof. SSLE protocols are used in proof-of-stake blockchains to elect the leader who publishes the next block. Anonymity of the leader is an important security property, as the leader makes for an attractive target and may be subject to denial-of-service (DOS) attacks. In this work, we propose a novel single leader election protocol, called Sassafras. We depart from the common approach of shuffling for constructing SSLE and instead employ a ring verifiable random function, which hides the identity of the leader within a ring of participants. Moreover, Sassafras is designed for batch leader elections, in which a single leader is selected for several elections at once. This allows the rate of leader election to match the rate of block production, an often-sought property not met by most SSLE protocols in the literature. We characterize single leader election with batching in the form of an ideal functionality in the Universal Composability (UC) framework and prove that Sassafras realizes this functionality. Sassafras is secure against an adaptive adversary, while achieving a slightly relaxed notion of anonymity for leaders. Sassafras features exceptionally low communication and computational complexity, outperforming other SSLE protocols by an order of magnitude or more.

In Private Set Intersection protocols (PSIs), a non-empty result always reveals something about the private input sets of the parties. Moreover, in various variants of PSI, not all parties necessarily receive or are interested in the result. Nevertheless, to date, the literature has assumed that those parties who do not receive or are not interested in the result still contribute their private input sets to the PSI for free, although doing so would cost them their privacy. In this work, for the first time, we propose a multi-party PSI, called “Anesidora”, that rewards parties who contribute their private input sets to the protocol. Anesidora is efficient; it mainly relies on symmetric key primitives and its computation and communication complexities are linear with the number of parties and set cardinality. It remains secure even if the majority of parties are corrupted by active colluding adversaries.

End-to-end encryption (E2EE) prevents online services from accessing user content. This important security property is also an obstacle for content moderation methods that involve content analysis. The tension between E2EE and efforts to combat child sexual abuse material (CSAM) has become a global flashpoint in encryption policy, because the predominant method of detecting harmful content---server-side perceptual hash matching on plaintext images---is unavailable. Recent applied cryptography advances enable private hash matching (PHM), where a service can match user content against a set of known CSAM images without revealing the hash set to users or nonmatching content to the service. These designs, especially a 2021 proposal for identifying CSAM in Apple's iCloud Photos service, have attracted widespread criticism for creating risks to security, privacy, and free expression. In this work, we aim to advance scholarship and dialogue about PHM by contributing new cryptographic methods for system verification by the general public. We begin with motivation, describing the rationale for PHM to detect CSAM and the serious societal and technical issues with its deployment. Verification could partially address shortcomings of PHM, and we systematize critiques into two areas for auditing: trust in the hash set and trust in the implementation. We explain how, while these two issues cannot be fully resolved by technology alone, there are possible cryptographic trust improvements. The central contributions of this paper are novel cryptographic protocols that enable three types of public verification for PHM systems: (1) certification that external groups approve the hash set, (2) proof that particular lawful content is not in the hash set, and (3) eventual notification to users of false positive matches. The protocols that we describe are practical, efficient, and compatible with existing PHM constructions.

A distributed point function (DPF) (Gilboa-Ishai, Eurocrypt 2014) is a cryptographic primitive that enables compressed additive secret-sharing of a secret weight-1 vector across two or more servers. DPFs support a wide range of cryptographic applications, including efficient private information retrieval, secure aggregation, and more. Up to now, the study of DPFs was restricted to the computational security setting, relying on one-way functions. This assumption is necessary in the case of a dishonest majority. We present the first statistically private 3-server DPF for domain size $N$ with subpolynomial key size $N^{o(1)}$. We also present a similar perfectly private 4-server DPF. Our constructions offer benefits over their computationally secure counterparts, beyond the superior security guarantee, including better computational complexity and better protocols for distributed key generation, all while having comparable communication complexity for moderate-sized parameters.

This paper describes a formalization of the specification and the algorithm of the cryptographic scheme CRYSTALS-KYBER as well as the verification of its (1 − δ)-correctness proof. During the formalization, a problem in the correctness proof was uncovered. In order to amend this issue, a necessary property on the modulus parameter of the CRYSTALS-KYBER algorithm was introduced. This property is already implicitly fulfilled by the structure of the modulus prime used in the number theoretic transform (NTT). The NTT and its convolution theorem in the case of CRYSTALS-KYBER was formalized as well. The formalization was realized in the theorem prover Isabelle.

We are applying Fermat’s factorization algorithm to sets of public RSA keys. Fermat’s factorization allows efficiently calculating the prime factors of a composite number if the difference between the two primes is small. Knowledge of the prime factors of an RSA public key allows efficiently calculating the private key. A flawed RSA key generation function that produces close primes can therefore be attacked with Fermat’s factorization. We discovered a small number of vulnerable devices that generate such flawed RSA keys in the wild. These affect devices from two printer vendors - Canon and Fuji Xerox. Both use an underlying cryptographic module by Rambus.

In this paper, we investigate the security of several recent MAC constructions with provable security beyond the birthday bound (called BBB MACs) in the quantum setting. On the one hand, we give periodic functions corresponding to targeted MACs (including PMACX, PMAC with parity, HPxHP, and HPxNP), and we can recover secret states using Simon algorithm, leading to forgery attacks with complexity $O(n)$. This implies our results realize an exponential speedup compared with the classical algorithm. Note that our attacks can even break some optimally secure MACs, such as mPMAC+-f, mPMAC+-p1, mPMAC+-p2, mLightMAC+-f, etc. On the other hand, we construct new hidden periodic functions based on SUM-ECBC-like MACs: SUM-ECBC, PolyMAC, GCM-SIV2, and 2K-ECBC$_{-}$Plus, where periods reveal the information of the secret key. Then, by applying Grover-meets-Simon algorithm to specially constructed functions, we can recover full keys with $O(2^{n/2}n)$ or $O(2^{m/2}n)$ quantum queries, where $n$ is the message block size and $m$ is the length of the key. Considering the previous best quantum attack, our key-recovery attacks achieve a quadratic speedup.