Yao’s garbling scheme is one of the most fundamental cryptographic constructions. Lindell and Pinkas (Journal of Cryptograhy 2009) gave a formal proof of security in the selective setting where the adversary chooses the challenge inputs before seeing the garbled circuit assuming secure symmetric-key encryption (and hence one-way functions). This was followed by results, both positive and negative, concerning its security in the, stronger, adaptive setting. Applebaum et al. (Crypto 2013) showed that it cannot satisfy adaptive security as is, due to a simple incompressibility argument. Jafargholi and Wichs (TCC 2017) considered a natural adaptation of Yao’s scheme (where the output mapping is sent in the online phase, together with the garbled input) that circumvents this negative result, and proved that it is adaptively secure, at least for shallow circuits. In particular, they showed that for the class of circuits of depth $\delta$, the loss in security is at most exponential in $\delta$. The above results all concern the simulation-based notion of security. In this work, we show that the upper bound of Jafargholi and Wichs is basically optimal in a strong sense. As our main result, we show that there exists a family of Boolean circuits, one for each depth $\delta\in\mathbb{N}$, such that any black-box reduction proving the adaptive indistinguishability of the natural adaptation of Yao’s scheme from any symmetric-key encryption has to lose a factor that is exponential in $\sqrt(\delta)$. Since indistinguishability is a weaker notion than simulation, our bound also applies to adaptive simulation. To establish our results, we build on the recent approach of Kamath et al. (Eprint 2021), which uses pebbling lower bounds in conjunction with oracle separations to prove fine-grained lower bounds on loss in cryptographic security.

Profiling attacks, especially those based on machine learning, proved to be very successful techniques in recent years when considering the side-channel analysis of symmetric-key crypto implementations. At the same time, the results for implementations of asymmetric-key cryptosystems are very sparse. This paper considers several machine learning techniques to mount side-channel attacks on two implementations of scalar multiplication on the elliptic curve Curve25519. The first implementation follows the baseline implementation with complete formulae as used for EdDSA in WolfSSl, where we exploit power consumption as a side-channel. The second implementation features several countermeasures, and in this case, we analyze electromagnetic emanations to find side-channel leakage. Most techniques considered in this work result in potent attacks, and especially the method of choice appears to be convolutional neural networks (CNNs), which can break the first implementation with only a single measurement in the attack phase. The same convolutional neural network demonstrated excellent performance for attacking AES cipher implementations. Our results show that some common grounds can be established when using deep learning for profiling attacks on very different cryptographic algorithms and their corresponding implementations.

In this work we introduce a new (circuit-dependent) homomorphic secret sharing (HSS) scheme for any $\log/\log\log$-local circuit, with communication proportional only to the width of the circuit and polynomial computation, which is secure assuming the super-polynomial hardness of learning parity with noise (LPN). At the heart of our new construction is a pseudorandom correlation generator (PCG) which allows two parties to locally stretch short seeds into pseudorandom instances of an arbitrary $\log/\log\log$-local additive correlation. Our main application, and the motivation behind this work, is a generic two-party secure computation protocol for every layered (boolean or arithmetic) circuit of size $s$ with total communication $O(s/\log\log s)$ and polynomial computation, assuming the super-polynomial hardness of the standard learning parity with noise assumption (a circuit is layered if its nodes can be partitioned in layers, such that any wire connects adjacent layers). This expands the set of assumptions under which the `circuit-size barrier' can be broken, for a large class of circuits. The strength of the underlying assumption is tied to the sublinearity factor: we achieve communication $O(s/k(s))$ under the $s^{2^{k(s)}}$-hardness of LPN, for any $k(s) \leq (\log\log s) / 4$. Previously, the set of assumptions known to imply a PCG for correlations of degree $\omega(1)$ or generic secure computation protocols with sublinear communication was restricted to LWE, DDH, and a circularly secure variant of DCR.

Ring signatures allow a user to sign a message on behalf of a ``ring'' of signers, while hiding the true identity of the signer. As the degree of anonymity guaranteed by a ring signature is directly proportional to the size of the ring, an important goal in cryptography is to study constructions that minimize the size of the signature as a function of the number of ring members. In this work, we present the first compact ring signature scheme (i.e., where the size of the signature grows logarithmically with the size of the ring) from the (plain) learning with errors (LWE) problem. The construction is in the standard model and it does not rely on a common random string or on the random oracle heuristic. In contrast with the prior work of Backes et al. [EUROCRYPT'2019], our scheme does not rely on bilinear pairings, which allows us to show that the scheme is post-quantum secure assuming the quantum hardness of LWE. At the heart of our scheme is a new construction of compact and statistically witness indistinguishable ZAP arguments for NP $\cap$ coNP, that we show to be sound based on the plain LWE assumption. Prior to our work, statistical ZAPs (for all of NP) were known to exist only assuming sub-exponential LWE. We believe that this scheme might find further applications in the future.

Cryptographic software is particularly vulnerable to side-channel attacks when programmed in embedded devices. Indeed, the leakage is particularly intense compared to the noise level, making it mandatory for the developer to implement side-channel attack protections. Random masking is a customary option, but in this case, the countermeasure must be high-order, meaning that each sensitive variable is splitted into multiple (at least two) shares. Attacks therefore become computationally challenging. In this paper, we show that high-order template attacks can be expressed under the form of a convolution. This formulation allows for a considerable speed-up in their computation thanks to fast Fourier transforms. To further speed-up the attack, we also provide an interesting multi-threading implementation of this approach. This strategy naturally applies to template attacks where the leakage of each share is multivariate. We show that this strategy can be adapted to several masking schemes, inherently to the way the splitting is realized. This technique allows us to validate multiple very high-order attacks (order of some tens). In particular, it revealed a non-trivial flaw (hard to detect otherwise) in a multivariate extension of the DSM masking (and subsequently to fix it, and validate its rationale).

Data secrecy is a major concern in many domains. Nowadays, the data are kept in tight security with high privacy. Users do not want to share their secret information with anyone; however, the users' confidential data are not protected from the administrators. Administrators can read the users' data. Why should any Administrator read users' data? To address this issue, we propose a new secrecy protocol to store data secretly, named Secret Cloud Storage, SecretStore for short, to enable Secrecy as a Service model over the Cloud Computing paradigm. This article demonstrates how to protect users' data from any unintended users, including the data administrators. Moreover, we introduce tight security using the client-side symmetric cryptography method. In addition, we devise a forgetful private key to generate or regenerate a private key to encrypt or decrypt based on a secret word. We also show how to strengthen the weak password. Finally, we demonstrate how to implement the Secrecy as a Service model in Cloud Storage using highly unpredictable private keys.

We propose OmniLytics, a blockchain-based secure data trading marketplace for machine learning applications. Utilizing OmniLytics, many distributed data owners can contribute their private data to collectively train an ML model requested by some model owners, and receive compensation for data contribution. OmniLytics enables such model training while simultaneously providing 1) model security against curious data owners; 2) data security against the curious model and data owners; 3) resilience to malicious data owners who provide faulty results to poison model training; and 4) resilience to malicious model owners who intend to evade payment. OmniLytics is implemented as a blockchain smart contract to guarantee the atomicity of payment. In OmniLytics, a model owner splits its model into the private and public parts and publishes the public part on the contract. Through the execution of the contract, the participating data owners securely aggregate their locally trained models to update the model owner's public model and receive reimbursement through the contract. We implement a working prototype of OmniLytics on Ethereum blockchain and perform extensive experiments to measure its gas cost, execution time, and model quality under various parameter combinations. For training a CNN on the MNIST dataset, the MO is able to boost its model accuracy from 62% to 83% within 500ms in blockchain processing time.This demonstrates the effectiveness of OmniLytics for practical deployment.

Plactic signatures use the plactic monoid (semistandard tableaus with Knuth’s associative multiplication) and full-domain hashing (SHAKE). Monico found an attack which likely makes plactic signatures insecure.

Licensing of software that will run in offline environments introduces constraints on the licensing model that can be supported. The difficulty arises in cases where information needs to be recorded about the usage of the software, for example in a consumption-based licensing model. We describe a method that makes it harder for an adversary to tamper with the recorded data as well as ways for software vendors to detect if tampering with this information would still occur.

Fault Injection Analysis is seen as a powerful attack against implementations of cryptographic algorithms. Over the last two decades, researchers proposed a plethora of countermeasures to secure such implementations. However, the design process and implementation are still error-prone, complex, and manual tasks which require long-standing experience in hardware design and physical security. Moreover, the validation of the claimed security is often only done by empirical testing in a very late stage of the design process. To prevent such empirical testing strategies, approaches based on formal verification are applied instead providing the designer early feedback. In this work, we present a fault verification framework to validate the security of countermeasures against fault-injection attacks designed for ICs. The verification framework works on netlist-level, parses the given digital circuit into a model based on Binary Decision Diagrams, and performs symbolic fault injections. This verification approach constitutes a novel strategy to evaluate protected hardware designs against fault injections offering new opportunities as performing full analyses under a given fault models. Eventually, we apply the proposed verification framework to real-world implementations of well-established countermeasures against fault-injection attacks. Here, we consider protected designs of the lightweight ciphers CRAFT and LED-64 as well as AES. Due to several optimization strategies, our tool is able to perform more than 90 million fault injections in a single-round CRAFT design and evaluate the security in under 50 min while the symbolic simulation approach considers all $2^128$ primary inputs.

Oblivious Transfer (OT) is a fundamental primitive in cryptography, supporting protocols such as Multi-Party Computation and Private Set Intersection (PSI), that are used in applications like contact discovery, remote diagnosis and contact tracing. Due to its fundamental nature, it is utterly important that its execution is secure even if arbitrarily composed with other instances of the same, or other protocols. This property can be guaranteed by proving its security under the Universal Composability model. Herein, a 3-round Random Oblivious Transfer (ROT) protocol is proposed, which achieves high computational efficiency, in the Random Oracle Model. The security of the protocol is based on the Ring Learning With Errors assumption (for which no quantum solver is known). ROT is the basis for OT extensions and, thus, achieves wide applicability, without the overhead of compiling ROTs from OTs. Finally, the protocol is implemented in a server-class Intel processor and four application-class ARM processors, all with different architectures. The usage of vector instructions provides on average a 40% speedup. The implementation shows that our proposal is at least one order of magnitude faster than the state-of-the-art, and is suitable for a wide range of applications in embedded systems, IoT, desktop, and servers. From a memory footprint perspective, there is a small increase (16%) when compared to the state-of-the-art. This increase is marginal and should not prevent the usage of the proposed protocol in a multitude of devices. In sum, the proposal achieves up to 37k ROTs/s in an Intel server-class processor and up to 5k ROTs/s in an ARM application-class processor. A PSI application, using the proposed ROT, is up to 6.6 times faster than related art.

We advance the state-of-the art for zero-knowledge commit-and-prove SNARKs (CP-SNARKs). CP-SNARKs are an important class of SNARKs which, using commitments as ``glue'', allow to efficiently combine proof systems---e.g., general-purpose SNARKs (an efficient way to prove statements about circuits) and $\Sigma$-protocols (an efficient way to prove statements about group operations). Thus, CP-SNARKs allow to efficiently provide zero-knowledge proofs for composite statements such as $h=H(g^{x})$ for some hash-function $H$. Our main contribution is providing the first construction of CP-SNARKs where the proof size is succinct in the number of commitments. We achieve our result by providing a general technique to compile Algebraic Holographic Proofs (AHP) (an underlying abstraction used in many modern SNARKs) with special ``decomposition'' properties into an efficient CP-SNARK. We then show that some of the most efficient AHP constructions---Marlin, PLONK, and Sonic---satisfy our compilation requirements. Our resulting SNARKs achieve universal and updatable reference strings, which are highly desirable features as they greatly reduce the trust needed in the SNARK setup phase.

To factor an integer $N$ we construct $n$ triples of $p_n$-smooth integers $u,v,|u-vN|$ for the $n$-th prime $p_n$. Denote such triple a fac-relation. We get fac-relations from a nearly shortest vector of the lattice $\mathcal L(\mathbf R_{n, f})$ with basis matrix $\mathbf R_{n, f} \in \mathbb R^{(n+1)\times(n+1)}$ where $f\colon [1, n]\to[1, n]$ is a permutation of $[1, 2, \ldots, n]$ and $(f(1),\ldots,f(n),N'\ln N)$ is the diagonal and $(N' \ln p_1,\ldots, N' \ln p_n,N' \ln N)$ for $N' = N^{\frac{1}{n+1}}$ is the last line of $\mathbf R_{n, f}$. An independent permutation $f'$ yields an independent fac-relation. We find sufficiently short lattice vectors by strong primal-dual reduction of $\mathbf R_{n, f}$. We factor $N\approx 2^{400}$ by $n = 47$ and $N\approx 2^{800}$ by $n = 95$. Our accelerated strong primal-dual reduction of [GN08] factors integers $N\approx 2^{400}$ and $N\approx 2^{800}$ by $4.2\cdot 10^9$ and $8.4\cdot 10^{10}$ arithmetic operations, much faster then the quadratic sieve and the number field sieve and using much smaller primes $p_n$. This destroys the RSA cryptosystem.

A succinct functional commitment (SFC) scheme for a circuit class $\mathbf{CC}$ enables, for any circuit $\mathcal{C} \in \mathbf{CC}$, the committer to first succinctly commit to a vector $\vec{\alpha}$, and later succinctly open the commitment to $\mathcal{C} (\vec{\alpha}, \vec{\beta})$, where the verifier chooses $\vec{\beta}$ at the time of opening. Unfortunately, SFC commitment schemes are known only for severely limited function classes like the class of inner products. By making non-black-box use of SNARK-construction techniques, we propose an SFC scheme for the large class of semi-sparse polynomials. The new SFC scheme can be used to, say, efficiently (1) implement sparse polynomials, and (2) aggregate various interesting SFC (e.g., vector commitment and polynomial commitment) schemes. The new scheme is evaluation-binding under a new instantiation of the computational uber-assumption. We provide a thorough analysis of the new assumption.

FlexAEAD is a block cipher candidate submitted to the NIST Lightweight Cryptography standardization project, based on repeated application of an Even-Mansour construction. In order to optimize performance, the designers chose a relatively small number of rounds, using properties of the mode and bounds on differential and linear characteristics to substantiate their security claims. Due to a forgery attack with complexity $2^{46}$, FlexAEAD was not selected to the second round of evaluation in the NIST project. In this paper we present a practical key recovery attack on FlexAEAD, using clusters of differentials for the internal permutation and the interplay between different parts of the mode. Our attack, which was fully verified in practice, allows recovering the secret subkeys of FlexAEAD-64 with a time complexity of less than $2^{31}$ encryptions (with an experimental success rate of $75\,\%$). This is the first practical key recovery attack on a candidate of the NIST standardization project.

This document describes Darlin, a succinct zero-knowledge argument of knowledge based on the Marlin SNARK (Chiesa et al., Eurocrypt 2020) and the `dlog' polynomial commitment scheme from Bootle et al. EUROCRYPT 2016. Darlin addresses recursive proofs by integrating the amortization technique from Halo (IACR eprint 2019/099) for the non-succinct parts of the dlog verifier, and we adapt their strategy for bivariate circuit encoding polynomials to aggregate Marlin's inner sumchecks across the nodes the recursive scheme. We estimate the performance impact of inner sumcheck aggregation by about 30% in a tree-like scheme of in-degree 2, and beyond when applied to linear recursion.

The Sidon cryptosystem is a new multivariate encryption scheme based on the theory of Sidon spaces which was presented at PKC 2021. As is usual for this kind of schemes, its security relies on the hardness of solving particular instances of the MQ problem and of the MinRank problem. A nice feature of the scheme is that it enjoys a homomorphic property due the bilinearity of its public polynomials. Unfortunately, we will show that the Sidon cryptosystem can be broken by a polynomial time key-recovery attack. This attack relies on the existence of solutions to the underlying MinRank instance which lie in a subfield and which are inherent to the structure of the secret Sidon space. We prove that such solutions can be found in polynomial time. Our attack consists in recovering an equivalent key for the cryptosystem by exploiting these particular solutions, and this task can be performed very efficiently.

Grain and Trivium are two typical stream ciphers based on nonlinear feedback shift registers (NFSRs). The 160-stage Galois NFSR used in Grain was found conditionally equivalent to a 160-stage Fibonacci NFSR before Grain was introduced. But it remains unknown whether the 288-stage Galois NFSR used in Trivium is conditionally equivalent to a Fibonacci NFSR, though Trivium exists for over ten years and several types of Galois NFSRs have been found conditionally equivalent to Fibonacci ones with same stage number over the last decades. This paper applies the NFSR's dynamic system description, and obtains some necessary and sufficient conditions for Galois NFSRs to be conditionally equivalent to Fibonacci ones with same stage number, covering and improving the previous work on this research. As an application, the paper reveals that the 288-stage Galois NFSR used in Trivium is not conditionally equivalent to any Fibonacci NFSR, indicating the infeasibility of applying a conditionally equivalent Fibonacci NFSR to simplify its cryptanalysis, and indicating the good confusion and diffusion of the initial state to the output sequence generated from the Galois NFSR's 288-th bit that is used as one of inputs of Trivium's filtering function. This provides a formal extra justification of Trivium's good design, and allows future designs to be built by the same principle.

Many of the recent advanced lattice-based $\Sigma$-/public-coin honest verifier (HVZK) interactive protocols based on the techniques developed by Lyubashevsky (Asiacrypt'09, Eurocrypt'12) can be transformed into a non-interactive zero-knowledge (NIZK) proof in the random oracle model (ROM) using the Fiat-Shamir transform. Unfortunately, although they are known to be secure in the $\mathit{classical}$ ROM, existing proof techniques are incapable of proving them secure in the $\mathit{quantum}$ ROM (QROM). Alternatively, while we could instead rely on the Unruh transform (Eurocrypt'15), the resulting QROM secure NIZK will incur a large overhead compared to the underlying interactive protocol. In this paper, we present a new simple semi-generic transform that compiles many existing lattice-based $\Sigma$-/public-coin HVZK interactive protocols into QROM secure NIZKs. Our transform builds on a new primitive called $\textit{extractable linear homomorphic commitment}$ protocol. The resulting NIZK has several appealing features: it is not only a proof of knowledge but also straight-line extractable; the proof overhead is smaller compared to the Unruh transform; it enjoys a relatively small reduction loss; and it requires minimal background on quantum computation. To illustrate the generality of our technique, we show how to transform the recent Bootle et al.'s 5-round protocol with an exact sound proof (Crypto'19) into a QROM secure NIZK by increasing the proof size by a factor of $2.6$. This compares favorably to the Unruh transform that requires a factor of more than $50$.

We show that Yao’s garbling scheme is adaptively indistinguishable for the class of Boolean circuits of size S and treewidth w with only a S^O(w) loss in security. For instance, circuits with constant treewidth are as a result adaptively indistinguishable with only a polynomial loss. This (partially) complements a negative result of Applebaum et al. (Crypto 2013), which showed (assuming one-way functions) that Yao’s garbling scheme cannot be adaptively simulatable. As main technical contributions, we introduce a new pebble game that abstracts out our security reduction and then present a pebbling strategy for this game where the number of pebbles used is roughly O(d w log(S)), d being the fan-out of the circuit. The design of the strategy relies on separators, a graph-theoretic notion with connections to circuit complexity.

Dijk et al. presents Remote Attestation (RA) for secure processor technology which is secure in the presence of an All Digital State Observing (ADSO) adversary. The scheme uses a combination of hardware security primitives and design principles together with a new cryptographic primitive called a Public Key Session based One-Time Signature Scheme with Secret Key Exposure (OTS-SKE). Dijk et al. show a hash based realization of OTS-SKE which is post quantum secure but suffers long $8.704$ KB signatures for 128-bit quantum security or 256-bit classical security. From a classical cryptographic perspective we complete the picture by introducing a bilinear map based OTS-SKE with short $0.125$ KB signatures, $65$ times shorter, and for which the security reduces to the Computational Diffie-Hellman Problem (CDHP) -- at the cost of a $9\times$ longer initialization phase in the RA scheme if implemented in software (this can be improved with appropriate elliptic curve hardware acceleration). Signing takes 560 ms at most $60\%$ of the $>936$ ms needed for the hash based scheme.

Digital signatures following the methodology of “Fiat-Shamir with Aborts”, proposed by Lyubashevsky, are capable of achieving the smallest public-key and signature sizes among all the existing lattice signature schemes based on the hardness of the Ring-SIS and Ring-LWE problems. Since its introduction, several variants and optimizations have been proposed, and two of them (i.e., Dilithium and qTESLA) entered the second round of the NIST post-quantum cryptography standardization. This method of designing signatures relies on rejection sampling during the signing process. Rejection sampling is crucial for ensuring both the correctness and security of these signature schemes. In this paper, we investigate the possibility of removing the two rejection conditions used both in Dilithium and qTESLA. First, we show that removing one of the rejection conditions is possible, and provide a variant of Lyubashevsky’s signature with comparable parameters with Dilithium and qTESLA. Second, we give evidence on the difficulty of removing the other rejection condition, by showing that two very general approaches do not yield a signature scheme with correctness or security.

Roughly four decades ago, Taher ElGamal put forward what is today one of the most widely known and best understood public key encryption schemes. ElGamal encryption has been used in many different contexts, chiefly among them by the OpenPGP standard. Despite its simplicity, or perhaps because of it, in reality there is a large degree of ambiguity on several key aspects of the cipher. Each library in the OpenPGP ecosystem seems to have implemented a slightly different "flavour" of ElGamal encryption. While --taken in isolation-- each implementation may be secure, we reveal that in the interoperable world of OpenPGP, unforeseen cross-configuration attacks become possible. Concretely, we propose different such attacks and show their practical efficacy by recovering plaintexts and even secret keys.

Digital signature is one of the most important public key cryptographic primitive for message authentication. In a digital signature scheme, receiver of a message-signature pair gets assurance about the fact that the message belongs to the sender and neither receiver nor any third party can manipulate the message. In the current state of art, most of the existing digital signatures' security relies on classical cryptographic assumption based hard problems, such as discrete log, integer factorization, etc. However, rapid development of quantum computing creates a security threat to these classical digital signature schemes. It indicates the recruitment of an alternative solution which can prevent quantum attacks. We focus on this concern by implementing a post-quantum secure isogeny based digital signature scheme without making use of SIDH and CSIDH. Our scheme achieves uf-cma security under a hard problem in isogeny. The proposed signature scheme incurs 256 byte public key size and 128 byte signature size to achieve 128-bit security level (NIST-1 level of security). In particular, the size of signature of our design is smaller than all other IBC based signature schemes at the 128-bit security level.

This paper presents a new technique for disturbing the algebraic structure of linear codes in code-based cryptography. Specifically, we introduce the so-called semilinear transformations in coding theory and then creatively apply them to the construction of code-based cryptosystems. Note that $\mathbb{F}_{q^m}$ can be viewed as an $\mathbb{F}_q$-linear space of dimension $m$, a semilinear transformation $\varphi$ is therefore defined as an $\mathbb{F}_q$-linear automorphism of $\mathbb{F}_{q^m}$. Then we impose this transformation to a linear code $\mathcal{C}$ over $\mathbb{F}_{q^m}$. It is clear that $\varphi(\mathcal{C})$ forms an $\mathbb{F}_q$-linear space, but generally does not preserve the $\mathbb{F}_{q^m}$-linearity any longer. Inspired by this observation, a new technique for masking the structure of linear codes is developed in this paper. Meanwhile, we endow the underlying Gabidulin code with the so-called partial cyclic structure to reduce the public-key size. Compared to some other code-based cryptosystems, our proposal admits a much more compact representation of public keys. For instance, 2592 bytes are enough to achieve the security of 256 bits, almost 403 times smaller than that of Classic McEliece entering the third round of the NIST PQC project.

We construct, under standard hardness assumptions, the first non-malleable commitments secure against quantum attacks. Our commitments are statistically binding and satisfy the standard notion of non-malleability with respect to commitment. We obtain a $\log^\star(\lambda)$-round classical protocol, assuming the existence of post-quantum one-way functions. Previously, non-malleable commitments with quantum security were only known against a restricted class of adversaries known as synchronizing adversaries. At the heart of our results is a new general technique that allows to modularly obtain non-malleable commitments from any extractable commitment protocol, obliviously of the underlying extraction strategy (black-box or non-black-box) or round complexity. The transformation may also be of interest in the classical setting.

We prove that the path-finding problem in $\ell$-isogeny graphs and the endomorphism ring problem for supersingular elliptic curves are equivalent under reductions of polynomial expected time, assuming the generalised Riemann hypothesis. The presumed hardness of these problems is foundational for isogeny-based cryptography. As an essential tool, we develop a rigorous algorithm for the quaternion analog of the path-finding problem, building upon the heuristic method of Kohel, Lauter, Petit and Tignol. This problem, and its (previously heuristic) resolution, are both a powerful cryptanalytic tool and a building-block for cryptosystems.

We study the round complexity of zero-knowledge for QMA (the quantum analogue of NP). Assuming the quantum quasi-polynomial hardness of the learning with errors (LWE) problem, we obtain the following results: - 2-Round statistical witness indistinguishable (WI) arguments for QMA. - 4-Round statistical zero-knowledge arguments for QMA in the plain model, additionally assuming the existence of quantum fully homomorphic encryption. This is the first protocol for constant-round statistical zero-knowledge arguments for QMA. - 2-Round computational (statistical, resp.) zero-knowledge for QMA in the timing model, additionally assuming the existence of post-quantum non-parallelizing functions (time-lock puzzles, resp.). All of these protocols match the best round complexity known for the corresponding protocols for NP with post-quantum security. Along the way, we introduce and construct the notions of sometimes-extractable oblivious transfer and sometimes-simulatable zero-knowledge, which might be of independent interest.

Encrypted databases systems and searchable encryption schemes still leak critical information (e.g.: access patterns) and require a choice between privacy and efficiency. We show that using ORAM schemes as a black-box is not a panacea and that optimizations are still possible by improving the data structures. We design an ORAM-based secure database that is built from the ground up: we replicate the typical data structure of a database system using different optimized ORAM constructions and derive a new solution for oblivious searches on databases. Our construction has a lower bandwidth overhead than state-of-the-art ORAM constructions by moving client-side computations to a proxy with an intermediate (rigorously defined) level of trust, instantiated as a server-side isolated execution environment. We formally prove the security of our construction and show that its access patterns depend only on public information. We also provide an implementation compatible with SQL databases (PostgresSQL). Our system is 1.2 times to 4 times faster than state-of-the-art ORAM-based solutions.

Stake-based multiparty cryptographic primitives operate in a setting where participants are associated with their stake, security is argued against an adversary that is bounded by the total stake it possesses —as opposed to number of parties— and we are interested in scalability, i.e., the complexity of critical operations depends only logarithmically in the number of participants (who are assumed to be numerous). In this work we put forth a new stake-based primitive, stake-based threshold multisignatures (STM, or “Mithril” signatures), which allows the aggregation of individual signatures into a compact multisignature provided the stake that supports a given message exceeds a stake threshold. This is achieved by having for each message a pseudorandomly sampled subset of participants eligible to issue an individual signature; this ensures the scalability of signing, aggregation and verification. We formalize the primitive in the universal composition setting and propose efficient constructions for STMs. We also showcase that STMs are eminently useful in the cryptocurrency setting by providing two applications: (i) stakeholder decision-making for Proof of Work (PoW) blockchains, specifically, Bitcoin, and (ii) fast bootstrapping for Proof of Stake (PoS) blockchains.

The celebrated PCP Theorem states that any language in NP can be decided via a verifier that reads $O(1)$ bits from a polynomially long proof. Interactive oracle proofs (IOP), a generalization of PCPs, allow the verifier to interact with the prover for multiple rounds while reading a small number of bits from each prover message. While PCPs are relatively well understood, the power captured by IOPs (beyond NP) has yet to be fully explored. We present a generalization of the PCP theorem for interactive languages. We show that any language decidable by a $k(n)$-round IP has a $k(n)$-round public-coin IOP, where the verifier makes its decision by reading only $O(1)$ bits from each (polynomially long) prover message and $O(1)$ bits from each of its own (random) messages to the prover. Our result and the underlying techniques have several applications. We get a new hardness of approximation result for a stochastic satisfiability problem, we show IOP-to-IOP transformations that previously were known to hold only for IPs, and we formulate a new notion of PCPs (index-decodable PCPs) that enables us to obtain a commit-and-prove SNARK in the random oracle model for nondeterministic computations.

Principal component analysis(PCA) is one of the most pop-ular linear dimensionality reduction techniques in machine learning. Inthis paper, we try to present a method for performing PCA on encrypted data using a homomorphic encryption scheme. In a client-server model where the server performs computations on the encrypted data,it (server) does not require to perform any matrix operations like multiplication, inversion, etc. on the encrypted data. This reduces the number of computations significantly since matrix operations on encrypted data are very computationally expensive. For our purpose, we used the CKKS homomorphic encryption scheme since it is most suitable for machine learning tasks allowing approximate computations on real numbers.We also present the experimental results of our proposed Homomorphic PCA(HPCA) algorithm on a few datasets. We measure the R2 score on the reconstructed data and use it as an evaluation metric for our HPCA algorithm.

Solving a polynomial system over a finite field is an NP-complete problem of fundamental importance in both pure and applied mathematics. In~particular, the security of the so-called multivariate public-key cryptosystems, such as HFE of Patarin and UOV of Kipnis et~al., is based on the postulated hardness of solving quadratic polynomial systems over a finite field. Lokshtanov et al.~(2017) were the first to introduce a probabilistic algorithm that, in the worst-case, solves a Boolean polynomial system in time $O^{*}(2^{\delta n})$, for some $\delta \in (0, 1)$ depending only on the degree of the system, thus beating the brute-force complexity $O^{*}(2^n)$. Later, B\"jorklund et al.~(2019) and then Dinur~(2021) improved this method and devised probabilistic algorithms with a smaller exponent coefficient $\delta$. We survey the theory behind these probabilistic algorithms, and we illustrate the results that we obtained by implementing them in C. In~particular, for random quadratic Boolean systems, we estimate the practical complexities of the algorithms and their probabilities of success as their parameters change.

FO derandomization is a common step in protecting against chosen-ciphertext attacks. There are theorems qualitatively stating that FO derandomization preserves ROM OW-CPA security. However, quantitatively, these theorems are loose, allowing the possibility of the derandomized security level being considerably smaller than the original security level. Many cryptosystems rely on FO derandomization without adjusting parameters to account for this looseness. This paper proves, for two examples of a randomized ROM PKE, that derandomizing the PKE degrades ROM OW-CPA security by a factor close to the number of hash queries. The first example can be explained by the size of the message space of the PKE; the second cannot. This paper also gives a concrete example of a randomized non-ROM PKE that appears to have the same properties regarding known attacks. As a spinoff, this paper presents a 2^88-guess attack exploiting derandomization to break one out of 2^40 ciphertexts for a FrodoKEM-640 public key. This attack contradicts the official FrodoKEM claim that "the FrodoKEM parameter sets comfortably match their target security levels with a large margin". The official responses to this attack so far include (1) renaming FrodoKEM as "ephemeral FrodoKEM" and (2) proposing a newly patched "FrodoKEM". This paper does not involve new cryptanalysis: the attacks are straightforward. What is new is finding examples where derandomization damages security.

Blockchain as an enabler to current Internet infrastructure has provided many unique features and revolutionized current distributed systems into a new era. Its decentralization, immutability, and transparency have attracted many applications to adopt the design philosophy of blockchain and customize various replicated solutions. Under the hood of blockchain, consensus protocols play the most important role to achieve distributed replication systems. The distributed system community has extensively studied the technical components of consensus to reach agreement among a group of nodes. Due to trust issues, it is hard to design a resilient system in practical situations because of the existence of various faults. Byzantine fault-tolerant (BFT) state machine replication (SMR) is regarded as an ideal candidate that can tolerate arbitrary faulty behaviors. However, the inherent complexity of BFT consensus protocols and their rapid evolution makes it hard to practically adapt themselves into application domains. There are many excellent Byzantine-based replicated solutions and ideas that have been contributed to improving performance, availability, or resource efficiency. This paper conducts a systematic and comprehensive study on BFT consensus protocols with a specific focus on the blockchain era. We explore both general principles and practical schemes to achieve consensus under Byzantine settings. We then survey, compare, and categorize the state-of-the-art solutions to understand BFT consensus in detail. For each representative protocol, we conduct an in-depth discussion of its most important architectural building blocks as well as the key techniques they used. We aim that this paper can provide system researchers and developers a concrete view of the current design landscape and help them find solutions to concrete problems. Finally, we present several critical challenges and some potential research directions to advance the research on exploring BFT consensus protocols in the age of blockchains.

The 2014 European eIDAS regulation regulates strong electronic authentication and legally binding electronic signatures. Both require user "sole control". Historically smartcards are used based on direct interaction between user and relying party. Here sole control is provided by giving users both physical possession and control of the cryptographic key used for signing/authentication through a PIN. Such **classical** sole control is required in the 1999 electronic signature directive by some interpretations. The eIDAS regulation repeals the directive and explicitly relaxes its sole control requirements in a trade-off between security and usability. This allows user interaction to be outsourced to intermediary parties (authentication providers, signing services). This also allows mobile applications as user friendly alternatives for smartcards. However, current mobile platforms are only equipped with limited cryptographic hardware not supporting secure knowledge factors (PINs) controlling keys. The eIDAS relaxation raises concerns on sole control; intermediary parties should not be able to act as man-in-the-middle and impersonate users. In this paper we present a simple cryptographic design for signing and authentication on standard mobile platforms providing classical sole control. We argue that our design can meet the highest eIDAS requirements, effectively introducing a new signature category in a 2016 decision of the European Commission. We also sketch a SECDSA based implementation of the European Digital Identity Wallet recently proposed by the European Commission as part of the eIDAS regulation update.

Deep Learning based Side-Channel Attacks (DL-SCA) are considered as fundamental threats against secure cryptographic implementations. Side-channel attacks aim to recover a secret key using the least number of leakage traces. In DL-SCA, this often translates in having a model with the highest possible accuracy. Increasing an attack’s accuracy is particularly important when an attacker targets public-key cryptographic implementations where the recovery of each secret key bits is directly related to the model’s accuracy. Commonly used in the deep learning field, ensemble models are a well suited method that combine the predictions of multiple models to increase the ensemble accuracy by reducing the correlation between their errors. Linked to this correlation, the diversity is considered as an indicator of the ensemble model performance. In this paper, we propose a new loss, namely Ensembling Loss (EL), that generates an ensemble model which increases the diversity between the members. Based on the mutual information between the ensemble model and its related label, we theoretically demonstrate how the ensemble members interact during the training process. We also study how an attack’s accuracy gain translates to a drastic reduction of the remaining time complexity of a side-channel attacks through multiple scenarios on public-key implementations. Finally, we experimentally evaluate the benefits of our new learning metric on RSA and ECC secure implementations. The Ensembling Loss increases by up to $6.8\%$ the performance of the ensemble model while the remaining brute-force is reduced by up to $2^{22}$ operations depending on the attack scenario.

The keys of modern cryptographic algorithms have an enormous size, so the testing of the algorithm performance for all key combinations, will take practically an infinite time. To avoid this, the sampling method is used, where a much smaller number of keys is tested and then the estimation of the algorithm performance for all the keys is calculated with a predetermined sampling error. For each sampling key, an output sample of the algorithm must be generated and tested. Therefore, in order to have sampling results as close as possible to the real performance of the algorithm, the key question is whether the selection of the keys should be random or it must follow some rules. If the selection of the keys is completely random, there is a high probability that the tests will not find some "weak" or "equivalent" keys, which give non-random or similar outputs and therefore reduce the total number of active keys. But if the sampling keys are selected with some specific criteria, there is a much greater probability of detecting any weak or equivalent key. In this study an optimal key selection methodology is proposed, which combines the random and the non-random key selection.

Businesses that are subject to AML/CTF regulation must meet their KYC obligations. In this context, to establish and verify a customer’s identity, the customer is required to share personal information with these businesses. This creates a Pareto dominated situation where a customer’s privacy is typically traded off for the mandated transparency requirements. In addition, this privacy erosion also reduces the security and safety of the customer as shared personal information can be passed on or stolen and used against the best interest of the customer (e.g. identity theft). Recent innovations in self-sovereign identity and zero-knowledge cryptography, along with proper ecosystem design, allow for a novel approach to KYC that protects the customer’s privacy without reducing transparency. The proposed solution concept, zkKYC, removes the need for the customer to share any personal information with a regulated business for the purpose of KYC, and yet provides the transparency to allow for a customer to be identified if and when that is ruled necessary by a designated governing entity (e.g. regulator, law enforcement). This approach breaks the traditional privacy vs. transparency trade-off and provides structured transparency, resulting in a net positive outcome for all parties involved.

This paper presents two public-key cryptosystems based on the so-called expanded Gabidulin codes, which are constructed by expanding Gabidulin codes over the base field. Exploiting the fast decoder of Gabidulin codes, we propose an efficient algorithm to decode these new codes when the noise vector satisfies a certain condition. Additionally, these new codes have an excellent error-correcting capability because of the optimality of their parent Gabidulin codes. Based on different masking techniques, we give two encryption schemes by using expanded Gabidulin codes in the McEliece setting. According to our analysis, these two cryptosystems can both resist the existing structural attacks. Furthermore, our proposals also have an obvious advantage in public-key representation without using the cyclic or quasi-cyclic structure compared to some other code-based cryptosystems. To achieve the security of 256 bits, for instance, a public-key size of 37005 bytes is enough for our first proposal, while around 1044992 bytes are needed for Classic McEliece selected as a candidate of the third round of the NIST PQC project.

Advances in cryptography have enabled the features of confidentiality, security, and integrity on small embedded devices such as IoT devices. While mathematically strong, the platform on which an algorithm is implemented plays a significant role in the security of the final product. Side-channel attacks exploit the variations in the system’s physical characteristics to obtain information about the sensitive data. In our scenario, a software implementation of a cryptographic algorithm is flashed on devices from different manufactures with the same instruction set configured for identical execution. To analyze the influence of the microarchitecture on side-channel leakage, we acquire thirty-two sets of power traces from four physical devices. While we notice minor differences in the leakage behaviour for different physical boards from the same manufacturer, our results confirm that the difference in microarchitecture implementations will leak different side-channel information. We also show that TVLA leakage prediction should be treated with caution as it is sensitive to both false positives and negatives.

Practical side-channel attacks on recent devices may be challenging due to the poor quality of acquired signals. It can originate from different factors, such as the growing architecture complexity, especially in System-on-Chips, creating unpredictable and concurrent operation of multiple signal sources on the device. This work makes use of mixture distributions to formalize this complexity, allowing us to explain the benefit of using a technique like Scatter, where different samples of the traces are aggregated into the same distribution. Some observations of the conditional mixture distributions are made in order to model the leakage in such context. From this, we infer local coherency of information held in the distribution as a general property of side-channel leakage in mixture distributions. This leads us to introduce how spatial analysis tools, such as Moran's Index, can be used to significantly improve non-profiled attacks compared to other techniques from the state-of-the-art. Exploitation of this technique is experimentally shown very promising, as demonstrated on two AES implementations including masking and shuffling countermeasures.

Symmetric Searchable Encryption (SSE) allows users to outsource encrypted data to a possibly untrusted remote location while simultaneously being able to perform keyword search directly through the stored ciphertexts. An ideal SSE scheme should reveal no information about the content of the encrypted information nor about the searched keywords and their mapping to the stored files. However, most of the existing SSE schemes fail to fulfill this property since in every search query, some information potentially valuable to a malicious adversary is leaked. The leakage becomes even bigger if the underlying SSE scheme is dynamic. In this paper, we minimize the leaked information by proposing a forward and backward private SSE scheme in a multi-client setting. Our construction achieves optimal search and update costs. In contrast to many recent works, each search query only requires one round of interaction between a user and the cloud service provider. In order to guarantee the security and privacy of the scheme and support the multi-client model (i.e. synchronization between users), we exploit the functionality offered by AMD's Secure Encrypted Virtualization (SEV).

In this paper, we show that a software implementation of CCA secure Saber KEM protected by first-order masking and shuffling can be broken by deep learning-based power analysis. Using an ensemble of deep neural networks created at the profiling stage, we can recover the session key and the long-term secret key from $257 \times N$ and $24 \times 257 \times N$ traces, respectively, where $N$ is the number of repetitions of the same measurement. The value of $N$ depends on the implementation, environmental factors, acquisition noise, etc.; in our experiments $N = 10$ is enough to succeed. The neural networks are trained on a combination of 80% of traces from the profiling device with a known shuffling order and 20% of traces from the device under attack captured for all-0 and all-1 messages. ``Spicing'' the training set with traces from the device under attack helps minimize the negative effect of device variability.

Several constructions of Mutually Unbiased Bases (MUBs) borrow tools from combinatorial objects. In this paper we focus how one can construct Approximate Real MUBs (ARMUBs) with improved parameters using results from the domain of Resolvable Block Designs (RBDs). We first explain the generic idea of our strategy in relating the RBDs with MUBs/ARMUBs, which are sparse (the basis vectors have small number of non-zero co-ordinates). Then specific parameters are presented, for which we can obtain new classes and improve the existing results. To be specific, we present an infinite family of $\lceil\sqrt{d}\rceil$ many ARMUBs for dimension $d = q(q+1)$, where $q \equiv 3 \bmod 4$ and it is a prime power, such that for any two vectors $v_1, v_2$ belonging to different bases, $|\braket{v_1|v_2}| < \frac{2}{\sqrt{d}}$. We also demonstrate certain cases, such as $d = sq^2$, where $q$ is a prime power and $sq \equiv 0 \bmod 4$. These findings subsume and improve our earlier results in [Cryptogr. Commun. 13, 321-329, January 2021]. This present construction idea provides several infinite families of such objects, not known in the literature, which can find efficient applications in quantum information processing for the sparsity, apart from suggesting that parallel classes of RBDs are intimately linked with MUBs/ARMUBs.

The bulk of Internet interactions is highly redundant and also security sensitive. To reduce communication bandwidth and provide a desired level of security, a data stream is first compressed to squeeze out redundant bits and then encrypted using authenticated encryption. This generic solution is very flexible and works well for any pair of (compression, encryption) algorithms. Its downside, however, is the fact that the two algorithms are designed independently. One would expect that designing a single algorithm that compresses and encrypts (called compcrypt) should produce benefits in terms of efficiency and security. The work investigates how to design a compcrypt algorithm using the ANS compression. First, we examine basic properties of ANS and show that a plain ANS with a hidden encoding table can be broken by statistical attacks. Next, we study ANS behaviour when its states are chosen at random. Our compcrypt algorithm is built using ANS with randomised state jumps and a sponge MonkeyDuplex encryption. Its security and efficiency are discussed. The design provides 128-bit security for both confidentiality and integrity/authentication. Our implementation experiments show that our compcrypt algorithm processes symbols with a rate up to 269 MB/s (with a slight loss of compression rate).

Many privacy preserving blockchain and e-voting systems are based on the modified ElGamal scheme that supports homomorphic addition of encrypted values. For practicality reasons though, decryption requires the use of precomputed discrete-log (dlog) lookup tables along with algorithms like Shanks's baby-step giant-step and Pollard's kangaroo. We extend the Shanks approach as it is the most commonly used method in practice due to its determinism and simplicity, by proposing a truncated lookup table strategy to speed up decryption and reduce memory requirements. While there is significant overhead at the precomputation phase, these costs can be parallelized and only paid once and for all. As a starting point, we evaluated our solution against the widely-used secp family of elliptic curves and show that we can achieve storage reduction by 7x-14x, depending on the group size. Our algorithm can be immediately imported to existing works, especially when the range of encrypted values is known, such as in Zether, PGC and Solidus protocols.

Expanding graphs are known due to their remarkable applications to Computer Science. We are looking for their applications to Post Quantum Cryptography. One of them is postquantum analog of Diffie-Hellman protocol in the area of intersection of Noncommutative and Multivariate Cryptographies .This graph based protocol allows correspondents to elaborate collision cubic transformations of affine space Kn defined over finite commutative ring K. Security of this protocol rests on the complexity of decomposition problem of nonlinear polynomial map into given generators. We show that expanding graphs allow to use such output as a ‘’seed’’ for secure construction of infinite sequence of cubic transformation of affine spaces of increasing dimension. Correspondents can use the sequence of maps for extracting passwords for one time pads in alphabet K and other symmetric or asymmetric algorithms. We show that cubic polynomial maps of affine spaces of prescribed dimension can be used for transition of quadratic public keys of Multivariate Cryptography into the shadow of private areas.

Game-theoretic analyses of cryptocurrencies and---more generally---blockchain-based decentralized ledgers offer insight on their economic robustness and behavior when even their underpinning cryptographic assumptions fail. In this work we utilize the recently proposed blockchain adaptation of the rational protocol design (RPD) framework [EUROCRYPT '18] to analyze 51% double-spending attacks against Nakamoto-style proof-of-work based cryptocurrencies. We first observe a property of the originally proposed utility class that yields an unnatural conclusion against such attacks, and show how to devise a utility that avoids this pitfall and makes predictions that match the observable behavior---i.e., that renders attacking a dominant strategy in settings where an attack was indeed observed in reality. We then propose a generic remedy to the underlying protocol parameters that provably deter adversaries controlling a majority of the system's resources from attacks on blockchain consistency, including the 51% double-spending attack. This can be used as guidance to patch systems that have suffered such attacks, e.g., Ethereum Classic and Bitcoin Cash, and serves as a demonstration of the power of game-theoretic analyses.

In the recent ePrint report 2021/583 titled "Entropoid-based cryptography is group exponentiation in disguise" Lorenz Panny gave a cryptanalysis of the entropoid based instances proposed in our eprint report 2021/469. We acknowledge the correctness of his claims for the concrete instances described in our original report 2021/469. However, we find that claims for the general applicability of his attack on the general Entropoid framework are misleading. Namely, based on the Theorem 1 in his report, which claims that for every entropic quasigroup $(G, *)$, there exists an Abelian group $(G, \cdot)$, commuting automorphisms $\sigma$, $\tau$ of $(G, \cdot)$, and an element $c \in G$, such that $x * y = \sigma(x) \cdot \tau(y) \cdot c$ the author infers that \emph{"all instantiations of the entropoid framework should be breakable in polynomial time on a quantum computer."} There are two misleading parts in these claim: \textbf{1.} It is implicitly assumed that all instantiations of the entropoid framework would define entropic quasigroups - thus fall within the range of algebraic objects addressed by Theorem 1. \emph{We will show a construction of entropic groupoids that are not quasigroups}; \textbf{2.} It is implicitly assumed that finding the group $(G, \cdot)$, the commuting automorphisms $\sigma$ and $\tau$ and the constant $c$ \emph{would be easy for every given entropic operation} $*$ and its underlying groupoid $(G, *)$. However, the provable existence of a mathematical object \emph{does not guarantee an easy finding} of that object. Treating the original entropic operation $* := *_1$ as a one-dimensional entropic operation, we construct multidimensional entropic operations $* := *_m$, for $m\geq 2$ and we show that newly constructed operations do not have the properties of $* = *_1$ that led to the recovery of the automorphism $\sigma$, the commutative operation $\cdot$ and the linear isomorphism $\iota$ and its inverse $\iota^{-1}$. We give proof-of-concept implementations in SageMath 9.2 for the new multidimensional entropic operations $* := *_m$ defined over several basic operations $* := *_1$ and we show how the non-associative and non-commutative exponentiation works for the key exchange and digital signature schemes originally proposed in report 2021/469.

Lossy trapdoor functions, introduced by Peikert and Waters (STOC '08), can be initialized in one of two indistinguishable modes: in injective mode, the function preserves all information about its input, and can be efficiently inverted given a trapdoor, while in lossy mode, the function loses some information about its input. Such functions have found countless applications in cryptography, and can be constructed from a variety of number-theoretic or algebraic ``Cryptomania'' assumptions. In this work, we introduce targeted lossy functions (TLFs), which relax lossy trapdoor functions along two orthogonal dimensions. First, they do not require an inversion trapdoor in injective mode. Second, the lossy mode of the function is initialized with some target input, and the function is only required to lose information about this particular target. The injective and lossy modes should be indistinguishable even given the target. We construct TLFs from ``Minicrypt'' assumptions, namely, injective pseudorandom generators, or even one-way functions under a natural relaxation of injectivity. We then generalize TLFs to incorporate branches, and construct all-injective-but-one and all-lossy-but-one variants. We show a wide variety of applications of targeted lossy functions. In several cases, we get the first Minicrypt constructions of primitives that were previously only known under Cryptomania assumptions. Our applications include: -Pseudo-entropy functions from one-way functions. -Deterministic leakage-resilient message-authentication codes and improved leakage-resilient symmetric-key encryption from one-way functions. -Extractors for extractor-dependent sources from one-way functions. -Selective-opening secure symmetric-key encryption from one-way functions. -A new construction of CCA PKE from (exponentially secure) trapdoor functions and injective pseudorandom generators. We also discuss a fascinating connection to distributed point functions.

We present a history of how cryptographic key sizes have been determined for various schemes.

Apple's file-sharing service AirDrop leaks phone numbers and email addresses by exchanging vulnerable hash values of the user's own contact identifiers during the authentication handshake with nearby devices. In a paper presented at USENIX Security'21, we theoretically describe two attacks to exploit these vulnerabilities and propose "PrivateDrop" as a privacy-preserving drop-in replacement for Apple's AirDrop protocol based on private set intersection. In this demo, we show how these vulnerabilities are efficiently exploitable via Wi-Fi and physical proximity to a target. Privacy and security implications include the possibility of conducting advanced spear phishing attacks or deploying multiple "collector" devices in order to build databases that map contact identifiers to specific locations. For our proof-of-concept, we leverage a custom rainbow table construction to reverse SHA-256 hashes of phone numbers in a matter of milliseconds. We discuss the trade-off between success rate and storage requirements of the rainbow table and, after following responsible disclosure with Apple, we publish our proof-of-concept implementation as "AirCollect" on GitHub.

Correct application of masking on hardware implementation of cryptographic primitives necessitates the instantiation of registers in order to achieve the non-completeness (commonly said to stop the propagation of glitches). This sometimes leads to a high latency overhead, making the implementation not necessarily suitable for the underlying application. As a concrete example, this holds for Keccak. Application of d + 1 Domain Oriented Masking (DOM) on a round-based implementation of Keccak leads to the introduction of two register stages per round, i.e., two times higher latency. On the other hand, Rhythmic-Keccak, introduced in CHES 2018, unrolls two rounds to half the latency compared to an unprotected ordinary round-based implementation. To that end, td + 1 masking is used which requires a notable area, and – apart from the difficulty to construct – its extension to higher orders seems beyond the bounds of feasibility. In this paper, we focus on d + 1 masking and introduce a methodology which enables us to stay with the latency of an unprotected round-based implementation, i.e., one register stage per round. While being secure under glitch-extended probing model, we provide a general design where the desired security order can be easily adjusted without any effect on the above-given latency. Compared to the Rhythmic-Keccak, the synthesis results show that our first-order design is able to accomplish the entire operations of Keccak-f[200] in the same period of time while decreasing the area by 74.5%. Notably, our implementations achieve around 30% less delay compared to the corresponding original DOM-Keccak designs.

Traitor tracing aims to identify the source of leaked decryption keys. Since the "traitor" can try to hide their key within obfuscated code in order to evade tracing, the tracing algorithm should work for general, potentially obfuscated, decoder programs. In the setting of such general decoder programs, prior work uses black box tracing: the tracing algorithm ignores the implementation of the decoder, and instead traces just by making queries to the decoder and observing the outputs. We observe that, in some settings, such black box tracing leads to consistency and user privacy issues. On the other hand, these issues do not appear inherent to white box tracing, where the tracing algorithm actually inspects the decoder implementation. We therefore develop new white box traitor tracing schemes providing consistency and/or privacy. Our schemes can be instantiated under various assumptions ranging from public key encryption and NIZKs to indistinguishability obfuscation, with different trade-offs. To the best of our knowledge, ours is the first work to consider white box tracing in the general decoder setting.

We show equivalence between the existence of one-way functions and the existence of a \emph{sparse} language that is hard-on-average w.r.t. some efficiently samplable ``high-entropy'' distribution. In more detail, the following are equivalent: - The existence of a $S(\cdot)$-sparse language $L$ that is hard-on-average with respect to some samplable distribution with Shannon entropy $h(\cdot)$ such that $h(n)-\log(S(n)) \geq 4\log n$; - The existence of a $S(\cdot)$-sparse language $L \in \NP$, that is hard-on-average with respect to some samplable distribution with Shannon entropy $h(\cdot)$ such that $h(n)-\log(S(n)) \geq n/3$; - The existence of one-way functions. Our results are inspired by, and generalize, the recent elegant paper by Ilango, Ren and Santhanam (ECCC'21), which presents similar characterizations for concrete sparse languages.

We study several strengthening of classical circular security assumptions which were recently introduced in four new lattice-based constructions of indistinguishability obfuscation: Brakerski-Döttling-Garg-Malavolta (Eurocrypt 2020), Gay-Pass (STOC 2021), Brakerski-Döttling-Garg-Malavolta (Eprint 2020) and Wee-Wichs (Eprint 2020). We provide explicit counterexamples to the {\em $2$-circular shielded randomness leakage} assumption w.r.t.\ the Gentry-Sahai-Waters fully homomorphic encryption scheme proposed by Gay-Pass, and the {\em homomorphic pseudorandom LWE samples} conjecture proposed by Wee-Wichs. Our work suggests a separation between classical circular security of the kind underlying un-levelled fully-homomorphic encryption from the strengthened versions underlying recent iO constructions, showing that they are not (yet) on the same footing. Our counterexamples exploit the flexibility to choose specific implementations of circuits, which is explicitly allowed in the Gay-Pass assumption and unspecified in the Wee-Wichs assumption. Their indistinguishabilty obfuscation schemes are still unbroken. Our work shows that the assumptions, at least, need refinement. In particular, generic leakage-resilient circular security assumptions are delicate, and their security is sensitive to the specific structure of the leakages involved.

In this paper, we show that standard model black-box reductions naturally lift to various setup assumptions, such as the random oracle (ROM) or ideal cipher model. Concretely, we prove that a black-box reduction from a security notion P to security notion Q in the standard model can be turned into a non-programmable black-box reduction from P_O to Q_O in a model with a setup assumption O, where P_O and Q_O are the natural extensions of P and Q to a model with a setup assumption O. Our results rely on a generalization of the recent framework by Hofheinz and Nguyen (PKC 2019) to support primitives which make use of a trusted setup. Our framework encompasses standard idealized settings like the random oracle and the ideal cipher model. At the core of our main result lie novel properties of negligible functions that can be of independent interest.

A two-party authenticated key exchange (AKE) protocol allows each of the two parties to share a common secret key over insecure channels even in the presence of active adversaries who can actively control and modify the exchanged messages. To capture the various kind of malicious behaviors of the adversaries, there have been lots of efforts to define the security models. Amongst them, the extended Canetti-Krawczyk (eCK) security model is considered as one of the strongest ones and widely adopted. In this paper, we present a pairing-based eCK-secure AKE protocol in the standard model. The underlying assumptions of our construction are the hardness of the decisional bilinear Diffie-Hellman (DBDH) problem and the existence of pseudorandom functions. It is notable that the previous constructions either relied their security on random oracles or used somewhat strong assumptions such as the existence of strong-pseudorandom functions. We believe our construction is well-suited for real-world implementations such as the TLS protocol suite since our construction is simple and based on standard assumptions without random oracles.

SHA-256 is a secure cryptographic hash function. As such, its output should not have any detectable property. This paper describes three bit strings whose hashes by SHA-256 are nevertheless correlated in a non-trivial way: the first half of their hashes XORs to zero. They were found by “brute-force”, without exploiting any cryptographic weakness in the hash function itself. This does not threaten the security of the hash function and does not have any cryptographic implication. This is an example of a large “combinatorial” computation in which at least 8.7 × 10 22 integer operations have been performed. This was made possible by the combination of: 1) recent progress on algorithms for the underlying problem, 2) creative use of "dedicated" hardware accelerators, 3) adapted implementations of the relevant algorithms that could run on massively parallel machines. The actual computation was done on aging hardware. It required seven calendar months using two obsolete second-hand bitcoin mining devices converted into "useful" computational devices. A second step required 570 CPU-years on an 8-year old IBM BlueGene/Q computer, a few weeks before it was scrapped. To the best of our knowledge, this is the first practical 128-bit collision-like result obtained by brute-force, and it is the first bitcoin miner-accelerated computation.

We study new candidates for symmetric cryptographic primitives that leverage alternation between linear functions over $\mathbb{Z}_2$ and $\mathbb{Z}_3$ to support fast protocols for secure multiparty computation (MPC). This continues the study of weak pseudorandom functions of this kind initiated by Boneh et al. (TCC 2018) and Cheon et al. (PKC 2021). We make the following contributions. (Candidates). We propose new designs of symmetric primitives based on alternating moduli. These include candidate one-way functions, pseudorandom generators, and weak pseudorandom functions. We propose concrete parameters based on cryptanalysis. (Protocols). We provide a unified approach for securely evaluating modulus-alternating primitives in different MPC models. For the original candidate of Boneh et al., our protocols obtain at least 2x improvement in all performance measures. We report efficiency benchmarks of an optimized implementation. (Applications). We showcase the usefulness of our candidates for a variety of applications. This includes short "Picnic-style" signature schemes, as well as protocols for oblivious pseudorandom functions, hierarchical key derivation, and distributed key generation for function secret sharing.

In recent years, research has shown the networking layer’s significant influence on the scalability, security, and privacy of blockchain systems. Such large-scale networks however exhibit a degree of complexity that demands model-based simulations as real-world experiments are often not possible. In this work, we methodically characterize blockchain networks by reference to the paradigmatic Bitcoin peer-to-peer network, explore the state-of-the-art protocols, and emphasize this key design space. To this end, we conducted a longitudinal measurement study on the Bitcoin network, from which we extract a comprehensive network model and implement it as part of the bns network simulation framework. We validate the model in comparison to real-world measurements as well as to results from related work. Moreover, we experimentally show how network utilization and miners’ geographical location impact the block propagation characteristics.

Many recent private set intersection (PSI) protocols encode input sets as polynomials. We consider the more general notion of an oblivious key-value store (OKVS), which is a data structure that compactly represents a desired mapping $k_i \mapsto v_i$. When the $v_i$ values are random, the OKVS data structure hides the $k_i$ values that were used to generate it. The simplest (and size-optimal) OKVS is a polynomial $p$ that is chosen using interpolation such that $p(k_i)=v_i$. We initiate the formal study of oblivious key-value stores, and show new constructions resulting in the fastest OKVS to date. Similarly to cuckoo hashing, current analysis techniques are insufficient for finding {\em concrete} parameters to guarantee a small failure probability for our OKVS constructions. Moreover, it would cost too much to run experiments to validate a small upper bound on the failure probability. We therefore show novel techniques to amplify an OKVS construction which has a failure probability $p$, to an OKVS with a similar overhead and failure probability $p^c$. Setting $p$ to be moderately small enables to validate it by running a relatively small number of $O(1/p)$ experiments. This validates a $p^c$ failure probability for the amplified OKVS. Finally, we describe how OKVS can significantly improve the state of the art of essentially all variants of PSI. This leads to the fastest two-party PSI protocols to date, for both the semi-honest and the malicious settings. Specifically, in networks with moderate bandwidth (e.g., 30 - 300 Mbps) our malicious two-party PSI protocol has 40\% less communication and is 20-40\% faster than the previous state of the art protocol, even though the latter only has heuristic confidence.

Secure multi-party computation allows mutually distrusting parties to compute securely over their private data. However, guaranteeing output delivery to honest parties when the adversarial parties may abort the protocol has been a challenging objective. As a representative task, this work considers two-party coin-tossing protocols with guaranteed output delivery, a.k.a., fair coin-tossing. In the information-theoretic plain model, as in two-party zero-sum games, one of the parties can force an output with certainty. In the commitment-hybrid, any $r$-message coin-tossing protocol is ${1/\sqrt r}$-unfair, i.e., the adversary can change the honest party's output distribution by $1/\sqrt r$ in the statistical distance. Moran, Naor, and Segev (TCC--2009) constructed the first $1/r$-unfair protocol in the oblivious transfer-hybrid. No further security improvement is possible because Cleve (STOC--1986) proved that $1/r$-unfairness is unavoidable. Therefore, Moran, Naor, and Segev's coin-tossing protocol is optimal. However, is oblivious transfer necessary for optimal fair coin-tossing? Maji and Wang (CRYPTO--2020) proved that any coin-tossing protocol using one-way functions in a black-box manner is at least $1/\sqrt r$-unfair. That is, optimal fair coin-tossing is impossible in Minicrypt. Our work focuses on tightly characterizing the hardness of computation assumption necessary and sufficient for optimal fair coin-tossing within Cryptomania, outside Minicrypt. Haitner, Makriyannia, Nissim, Omri, Shaltiel, and Silbak (FOCS--2018 and TCC--2018) proved that better than $1/\sqrt r$-unfairness, for any constant $r$, implies the existence of a key-agreement protocol. We prove that any coin-tossing protocol using public-key encryption (or, multi-round key agreement protocols) in a black-box manner must be $1/\sqrt r$-unfair. Next, our work entirely characterizes the additional power of secure function evaluation functionalities for optimal fair coin-tossing. We augment the model with an idealized secure function evaluation of $f$, \aka, the $f$-hybrid. If $f$ is complete, that is, oblivious transfer is possible in the $f$-hybrid, then optimal fair coin-tossing is also possible in the $f$-hybrid. On the other hand, if $f$ is not complete, then a coin-tossing protocol using public-key encryption in a black-box manner in the $f$-hybrid is at least $1/\sqrt r$-unfair.

Code-based public key cryptosystems are one of the main techniques available in the area of Post-Quantum Cryptography. This work aims to propose a key encapsulation mechanism (KEM) with short ciphertext and secret key. Our goal is achieved in two steps. We first present a public key encryption (PKE) scheme, basicPKE, using a parity check matrix of Maximum Distance Separable (MDS) code as the public key matrix. In our construction, we exploit the structure of a companion matrix to obtain an MDS code which significantly reduces the storage of the secret key. The scheme basicPKE provides security against Indistinguishability under Chosen Plaintext Attacks (IND-CPA). Secondly, following the design framework of basicPKE, we construct another PKE scheme, fullPKE, that leads us to design our KEM scheme, fullKEM. We have shown that the scheme fullPKE is secure against One-Wayness under Plaintext and Validity Checking Attacks (OW-PCVA) and the scheme fullKEM achieves security against Indistinguishability under Chosen Ciphertext Attacks (IND-CCA) in the random oracle model. Moreover, our KEM can be shown to accomplish post-quantum security in the quantum random oracle model.

Proving the security of masked implementations in theoretical models that are relevant to practice and match the best known attacks of the side-channel literature is a notoriously hard problem. The random probing model is a good candidate to contribute to this challenge, due to its ability to capture the continuous nature of physical leakage (contrary to the threshold probing model), while also being convenient to manipulate in proofs and to automate with verification tools. Yet, despite recent progresses in the design of masked circuits with good asymptotic security guarantees in this model, existing results still fall short when it comes to analyze the security of concretely useful circuits under realistic noise levels and with low number of shares. In this paper, we contribute to this issue by introducing a new composability notion, the Probe Distribution Table (PDT), and a new tool (called STRAPS, for the Sampled Testing of the RAndom Probing Security). Their combination allows us to significantly improve the tightness of existing analyses in the most practical (low noise, low number of shares) region of the design space. We illustrate these improvements by quantifying the random probing security of an AES S-box circuit, masked with the popular multiplication gadget of Ishai, Sahai and Wagner from Crypto 2003, with up to six shares.

Symmetric Searchable Encryption (SSE) schemes enable keyword searches over encrypted documents. To obtain efficiency, SSE schemes incur a certain amount of leakage. The vast majority of the literature on SSE considers only leakage from one component of the overall SSE system, the encrypted search index. This component is used to identify which documents to return in response to a keyword query. The actual fetching of the documents is left to another component, usually left unspecified in the literature, but generally envisioned as a simple storage system matching document identifiers to encrypted documents. This raises the question: do SSE schemes actually protect the security of data and queries when considered from a system-wide viewpoint? We answer this question in the negative. We do this by introducing a new inference attack that achieves practically efficient, highly scalable, accurate query reconstruction against end-to-end SSE systems. In particular, our attack works even when the SSE schemes are built in the natural way using the state-of-the-art techniques (namely, volume-hiding encrypted multi-maps) designed to suppress leakage and protect against previous generations of attack. A second question is whether the state-of-the-art leakage suppression techniques can instead be applied on a system-wide basis, to protect both the encrypted search index and the encrypted document store, to produce efficient SSE systems. We also answer this question in the negative. To do so, we implement SSE systems using those state-of-the-art leakage suppression methods, and evaluate their performance. We show that storage overheads range from $100\times$ to $800\times$ while bandwidth overheads range from $20\times$ to $100\times$, as compared to a naive baseline system. Our results motivate the design of new SSE systems that are designed with system-wide security in mind from the outset. In this regard, we show that one such SSE system due to Chen et al. (IEEE INFOCOM 2018), with provable security guarantees based on differential privacy, is also vulnerable to our new attack. In totality, our results force a re-evaluation of how to build end-to-end SSE systems that offer both security and efficiency.

Side-channel and fault injection attacks reveal secret information by monitoring or manipulating the physical effects of computations involving secret variables. Circuit-level countermeasures help to deter these attacks, and traditionally such countermeasures have been developed for each attack vector separately. We demonstrate a multipurpose ring oscillator design - Programmable Ring Oscillator (PRO) to address both fault attacks and side-channel attacks in a generic, application-independent manner. PRO, as an integrated primitive, can provide on-chip side-channel resistance, power monitoring, and fault detection capabilities to a secure design. We present a grid of PROs monitoring the on-chip power network to detect anomalies. Such power anomalies may be caused by external factors such as electromagnetic fault injection and power glitches, as well as by internal factors such as hardware Trojans. By monitoring the frequency of the ring oscillators, we are able to detect the on-chip power anomaly in time as well as in location. Moreover, we show that the PROs can also inject a random noise pattern into a design's power consumption. By randomly switching the frequency of a ring oscillator, the resulting power-noise pattern significantly reduces the power-based side-channel leakage of a cipher. We discuss the design of PRO and present measurement results on a Xilinx Spartan-6 FPGA prototype, and we show that side-channel and fault vulnerabilities can be addressed at a low cost by introducing PRO to the design. We conclude that PRO can serve as an application-independent, multipurpose countermeasure.

The idea of smart contracts has been around for a long time. The introduction of Ethereum has taken the concept of smart contracts to new heights because of its integration with Blockchain technology. As a result, the applications of smart contracts have also surged in areas such as e-Voting, Insurance, Crowdfunding, etc. In this paper, we aim to present the construction of a “Fully Anonymous e-Voting” protocol using the concepts of zkHawk and Zcash. zkHawk is a novel smart contract protocol designed during this Ph.D. that improves upon the Hawk protocol by solving the underlying anonymity problem of a trusted manager. We will leverage the concept of zk-SNARKs in Zcash to carry out the voting phase of the election and the zkHawk smart contract protocol to tally the results of the election. The voting phase employing Zcash will be initially designed with Non-Universal zk-SNARKs and improved upon with Universal zk-SNARKs.

Consider the identification (ID) via channels problem, where a receiver decides whether the transmitted identifier is its identifier, rather than decoding it. This model allows to transmit identifiers whose size scales doubly-exponentially in the blocklength, unlike common transmission codes with exponential scaling. Binary constant-weight codes (CWCs) suffice to achieve the ID capacity. Relating parameters of a binary CWC to the minimum distance of a code and using higher-order correlation moments, two upper bounds on binary CWC sizes are proposed. These bounds are also upper bounds on identifier sizes for ID codes constructed by using binary CWCs. We propose two constructions based on optical orthogonal codes (OOCs), which are used in optical multiple access schemes, have constant-weight codewords, and satisfy cyclic cross-correlation and auto-correlation constraints. These constructions are modified and concatenated with outer Reed-Solomon codes to propose new binary CWCs being optimal for ID. Improvements to the finite-parameter performance of both our and existing code constructions are shown by using outer codes with larger minimum distance vs. blocklength ratios. We illustrate ID regimes for which our ID code constructions perform significantly better than existing constructions. An extensive list of other modified OOCs that can be used as binary CWCs is provided.

The Signal protocol is used in many messaging applications today. While it is an active research topic to design a post-quantum variant of the protocol, no such variant is currently realized in the real world. In the following document we describe a hybrid version of the Signal protocol, that will be implemented to achieve post-quantum security for Tutanota’s end-to-end encrypted e-mails.

This study proposes a chosen-ciphertext side-channel attack against a lattice-based key encapsulation mechanism (KEM), the third-round candidate of the national institute of standards and technology (NIST) standardization project. Unlike existing attacks that target operations such as inverse NTT and message encoding/decoding, we target Barrett Reduction in the decapsulation phase of CRYSTALS-KYBER to obtain a secret key. We show that a sensitive variable-dependent leakage of Barrett Reduction exposes an entire secret key. The results of experiments conducted on the ARM Cortex-M4 microcontroller accomplish a success rate of 100%. We only need six chosen ciphertexts for KYBER512 and KYBER768 and eight chosen ciphertexts for KYBER1024. We also show that the m4 scheme of the pqm4 library, an implementation with the ARM Cortex-M4 specific optimization (typically in assembly), is vulnerable to the proposed attack. In this scheme, six, nine, and twelve chosen ciphertexts are required for KYBER512, KYBER768, and KYBER1024, respectively.

OPAQUE [Jarecki et al., Eurocrypt 2018] is an asymmetric password authenticated key exchange (aPAKE) protocol that is being developed as an Internet standard and for use within TLS 1.3. OPAQUE combines an Oblivious PRF (OPRF) with an authenticated key exchange to provide strong security properties, including security against pre-computation attacks (called saPAKE security). However, the security of OPAQUE relies crucially on the security of the OPRF. If the latter breaks (by cryptanalysis, quantum attacks or security compromise), the user's password is exposed to an offline dictionary attack. To address this weakness, we present KHAPE, a variant of OPAQUE that does not require the use of an OPRF to achieve aPAKE security, resulting in improved resilience and near-optimal computational performance. An OPRF can be optionally added to KHAPE, for enhanced saPAKE security, but without opening the password to an offline dictionary attack upon OPRF compromise. In addition to resilience to OPRF compromise, a DH-based implementation of KHAPE (using HMQV) offers the best performance among aPAKE protocols in terms of exponentiations with less than the cost of an exponentiation on top of an UNauthenticated Diffie-Hellman exchange. KHAPE uses three messages if the server initiates the exchange or four when the client does (one more than OPAQUE in the latter case). All results in the paper are proven within the UC framework in the ideal cipher model. Of independent interest is our treatment of key-hiding AKE which KHAPE uses as a main component as well as our UC proofs of AKE security for protocols 3DH (a basis of Signal), HMQV and SKEME, that we use as efficient instantiations of KHAPE.

We introduce a new key generation mechanism where users can generate a "back up key'', securely nested inside the secret key of a signature scheme. Our main motivation is that in case of leakage of the secret key, established techniques based on zero-knowledge proofs of knowledge are void since the key becomes public. On the other hand, the "back up key'', which is secret, can be used to generate a "proof of ownership'', i.e., only the real owner of this secret key can generate such a proof. To the best of our knowledge, this extra level of security is novel, and could have already been used in practice, if available, in digital wallets for cryptocurrencies that suffered massive leakage of account private keys. In this work, we formalize the notion of "Proof of Ownership'' and "Fallback'' as new properties. Then, we introduce our construction, which is compatible with major designs for wallets based on ECDSA, and adds a W-OTS(+) signing key as a "back up key''. Thus offering a quantum secure fallback. This design allows the hiding of any quantum secure signature key pair, and is not exclusive to W-OTS(+). Finally, we briefly discuss the construction of multiple generations of proofs of ownership.

Consider a scenario where Alice stores some secret data $s$ on $n$ servers using a $t$-out-of-$n$ secret sharing scheme. Trudy (the collector) is interested in the secret data of Alice and is willing to pay for it. Trudy publishes an advertisement on the internet which describes an elaborate cryptographic scheme to collect the shares from the $n$ servers. Each server who decides to submit its share is paid a hefty monetary reward and is guaranteed ``immunity" from being caught or prosecuted in a court for violating its service agreement with Alice. Bob is one of the servers and sees this advertisement. On examining the collection scheme closely, Bob concludes that there is no way for Alice to prove anything in a court that he submitted his share. Indeed, if Bob is rational, he might use the cryptographic scheme in the advertisement and submit his share since there are no penalties and no fear of being caught and prosecuted. Can we design a secret sharing scheme which Alice can use to avoid such a scenario? We introduce a new primitive called as Traceable Secret Sharing to tackle this problem. In particular, a traceable secret sharing scheme guarantees that a cheating server always runs the risk of getting traced and prosecuted by providing a valid evidence (which can be examined in a court of law) implicating its dishonest behavior. We explore various definitional aspects and show how they are highly non-trivial to construct (even ignoring efficiency aspects). We then give an efficient construction of traceable secret sharing assuming the existence of a secure two-party computation protocol. We also show an application of this primitive in constructing traceable protocols for multi-server delegation of computation.

Many new ciphers target a concise algebraic description for efficient evaluation in a proof system or a multi-party computation. This new target for optimization introduces algebraic vulnerabilities, particularly involving Gröbner basis analysis. Unfortunately, the literature on Gröbner bases tends to be either purely mathematical, or focused on small fields. In this paper, we survey the most important algorithms and present them in an intuitive way. The discussion of their complexities enables researchers to assess the security of concrete arithmetization-oriented ciphers. Aside from streamlining the security analysis, this paper helps newcomers enter the field.

While privacy preserving distributed payment schemes manage to drastically improve user privacy, they come at the cost of generating new regulatory concerns: in a private ledger the transactions cannot be subject to any level of auditing, and thus are not compatible with tracing illegal behaviors. In this work we present MiniLedger, a distributed payment system which not only guarantees the privacy of transactions, but also offers built-in functionalities for various types of audits by any external authority. MiniLedger is the first private and auditable payment system with storage costs independent of the number of transactions. To achieve such a storage improvement, we introduce pruning functionalities for the transaction history while maintaining integrity and auditing. We provide formal security definitions and a number of extensions for various auditing levels. Our evaluation results show that MiniLedger is practical in terms of storage requiring as low as 70KB per participant for 128 bits of security, and depending on the implementation choices, can prune 1 million transactions in less than a second.

Efficient implementation of Boolean masking in terms of low latency has evolved into a hot topic due to the necessity of embedding a physically secure and at-the-same-time fast implementation of cryptographic primitives in e.g., the memory encryption of pervasive devices. Instead of fully minimizing the circuit's area and randomness requirements at the cost of latency, the focus has changed into finding optimal tradeoffs between the circuit area and the execution time. The main latency bottleneck in hardware masking lies in the need for registers to stop the propagation of glitches and maintain non-completeness. Usually, an exponentially growing number of shares (hence an extremely large circuit), as well as a high demand for fresh randomness, are the result of avoiding registers in a securely masked hardware implementation of a block cipher. In this paper, we present several first-order secure and low-latency implementations of PRINCE. In particular, we show how to realize the masked variant of round-based PRINCE with only a single register stage per cipher round. We compare the resulting architectures, based on the popular TI and GLM masking scheme based on the area, latency, and randomness requirements and point out that both designs are suited for specific use cases.

This paper revisits Key-Policy Attribute-Based Encryption (KP-ABE), allowing dele- gation of keys, traceability of compromised keys, and key anonymity, as additional properties. Whereas delegation of rights has been addressed in the seminal paper by Goyal et al. in 2006, introducing KP-ABE, this feature has almost been neglected in all subsequent works in favor of better security levels. However, in multi-device scenarios, this is quite important to allow users to independently authorize their own devices, and thus to delegate their initial rights with possibly more restrictions to their everyday-use devices. But then, one may also require tracing capabilities in case of corrupted devices and anonymity for the users and their devices. To this aim, we define a new variant of KP-ABE including delegation, with switchable attributes, in both the ciphertexts and the keys, and new indistinguishability properties. We then provide a concrete and efficient instantiation with adaptive security under the sole SXDH assumption in the standard model. We eventually explain how this new primitive can address all our initial goals.

The one more-discrete logarithm assumption (OMDL) underlies the security analysis of identification protocols, blind signature and multi-signature schemes, such as blind Schnorr signatures and the recent MuSig2 multi-signatures. As these schemes produce standard Schnorr signatures, they are compatible with existing systems, e.g. in the context of blockchains. OMDL is moreover assumed for many results on the impossibility of certain security reductions. Despite its wide use, surprisingly, OMDL is lacking any rigorous analysis; there is not even a proof that it holds in the generic group model (GGM). (We show that a claimed proof is flawed.) In this work we give a formal proof of OMDL in the GGM. We also prove a related assumption, the one-more computational Diffie-Hellman assumption, in the GGM. Our proofs deviate from prior proofs in the GGM and replace the use of the Schwartz-Zippel Lemma by a new argument.

Ternary LWE, i.e., LWE with coefficients of the secret and the error vectors taken from $\{-1, 0, 1\}$, is a popular choice among NTRU-type cryptosystems and some signatures schemes like BLISS and GLP. In this work we consider quantum combinatorial attacks on ternary LWE. Our algorithms are based on the quantum walk framework of Magniez-Nayak-Roland-Santha. At the heart of our algorithms is a combinatorial tool called the representation technique that appears in algorithms for the subset sum problem. This technique can also be applied to ternary LWE resulting in faster attacks. The focus of this work is quantum speed-ups for such representation-based attacks on LWE. When expressed in terms of the search space $\mathcal{S}$ for LWE keys, the asymptotic complexity of the representation attack drops from $\mathcal{S}^{0.24}$ (classical) down to $\mathcal{S}^{0.19}$ (quantum). This translates into noticeable attack's speed-ups for concrete NTRU instantiations like NTRU-HRSS and NTRU Prime. Our algorithms do not undermine current security claims for NTRU or other ternary LWE based schemes, yet they can lay ground for improvements of the combinatorial subroutines inside hybrid attacks on LWE.

We build the first construction of a partially oblivious pseudorandom function (POPRF) that does not rely on bilinear pairings. Our construction can be viewed as combining elements of the 2HashDH OPRF of Jarecki, Kiayias, and Krawczyk with the Dodis-Yampolskiy PRF. We analyze our POPRF’s security in the random oracle model via reduction to a new one-more gap strong Diffie-Hellman inversion assumption. The most significant technical challenge is establishing confidence in the new assumption, which requires new proof techniques that enable us to show that its hardness is implied by the $q$-DL assumption in the algebraic group model. Our new construction is as fast as the current, standards-track OPRF 2HashDH protocol, yet provides a new degree of flexibility useful in a variety of applications. We show how POPRFs can be used to prevent token hoarding attacks against Privacy Pass, reduce key management complexity in the OPAQUE password authenticated key exchange protocol, and ensure stronger security for password breach alerting services.

We construct the first authenticated key exchange protocols that achieve tight security in the standard model. Previous works either relied on techniques that seem to inherently require a random oracle, or achieved only “Multi-Bit-Guess” security, which is not known to compose tightly, for instance, to build a secure channel. Our constructions are generic, based on digital signatures and key encapsulation mechanisms (KEMs). The main technical challenges we resolve is to determine suitable KEM security notions which on the one hand are strong enough to yield tight security, but at the same time weak enough to be efficiently instantiable in the standard model, based on standard techniques such as universal hash proof systems. Digital signature schemes with tight multi-user security in presence of adaptive corruptions are a central building block, which is used in all known constructions of tightly-secure AKE with full forward security. We identify a subtle gap in the security proof of the only previously known efficient standard model scheme by Bader et al. (TCC 2015). We develop a new variant, which yields the currently most efficient signature scheme that achieves this strong security notion without random oracles and based on standard hardness assumptions.

In this work we resolve the open problem raised by Prabhakaran and Rosulek at CRYPTO 2007, and present the first anonymous, rerandomizable, Replayable-CCA (RCCA) secure public-key encryption scheme. This solution opens the door to numerous privacy-oriented applications with a highly desired RCCA security level. At the core of our construction is a non-trivial extension of smooth projective hash functions (Cramer and Shoup, EUROCRYPT 2002), and a modular generic framework developed for constructing rerandomizable RCCA-secure encryption schemes with receiver-anonymity. The framework gives an enhanced abstraction of the original Prabhakaran and Rosulek's scheme (which was the first construction of rerandomizable RCCA-secure encryption in the standard model), where the most crucial enhancement is the first realization of the desirable property of receiver-anonymity, essential to privacy settings. It also serves as a conceptually more intuitive and generic understanding of RCCA security, which leads, for example, to new implementations of the notion. Finally, note that (since CCA security is not applicable to the privacy applications motivating our work) the concrete results and the conceptual advancement presented here, seem to substantially expand the power and relevance of the notion of rerandomizable RCCA-secure encryption.

With the development of side-channel attacks, a necessity arises to invent authenticated key exchange protocols in a leakage-resilient manner. Constructing authenticated key exchange protocols using existing cryptographic schemes is an effective method, as such construction can be instantiated with any appropriate scheme in a way that the formal security argument remains valid. In parallel, constructing authenticated key exchange protocols that are proven to be secure in the standard model is more preferred as they rely on real-world assumptions. In this paper, we present a Diffie-Hellman-style construction of a leakage-resilient authenticated key exchange protocol, that can be instantiated with any CCLA2-secure public-key encryption scheme and a function from the pseudo-random function family. Our protocol is proven to be secure in the standard model assuming the hardness of the decisional Diffie-Hellman problem. Furthermore, it is resilient to continuous partial leakage of long-term secret keys, that happens even after the session key is established, while satisfying the security features defined by the eCK security model.

We introduce a novel method for reducing an arbitrary $\delta$-noisy leakage function to a collection of $\epsilon$-random probing leakages. These reductions combined with linear algebra tools are utilized to study the security of linear Boolean masked circuits in a practical and concrete setting. The secret recovery probability (SRP) that measures an adversary's ability to obtain secrets of a masked circuit is used to quantify the security. Leakage data and the parity-check relations imposed by the algorithm's structure are employed to estimate the SRP Both the reduction method and the SRP metric were used in the previous works. Here, as our main contribution, the SRP evaluation task is decomposed from the given $\mathbb{F}_q$ field to $q-1$ different binary systems indexed with $i$. Where for the $i$th system, the equivalent $\delta_i$-noisy leakage is reduced optimally to a $\epsilon_i$-random probing leakage with $\epsilon_i=2\delta_i$. Each binary system is targeting a particular bit-composition of the secret. The $q-1$ derived $\delta_i\leq \delta$ values are shown to be a good measure for the informativeness of the given $\delta$-noisy leakage function. Our works here can be considered as an extension of the work of TCC 2016. There, only $ \delta$-noisy leakage from the shares of a secret was considered. Here, we also incorporate the leakages that are introduced by the computations over the shares.

We study masked implementation's security when an adversary randomly probes each of its internal variables, intending to recover non-trivial knowledge about its secrets. We introduce a novel metric called Secret Recovery Probability (SRP) for assessing the informativeness of the probing leakages about the masked secrets. To evaluate SRP, our starting point is to describe the relations of the intermediate variables with a parity equation system where the target secret is an unknown of this system ...

This paper describes the first practical single-trace side-channel power analysis of SIKE. While SIKE is a post-quantum key exchange, the scheme still relies on a secret elliptic curve scalar multiplication which involves a loop of a double-and-add procedure, of which each iteration depends on a single bit of the private key. The attack therefore exploits the nature of elliptic curve point addition formulas which require the same function to be executed multiple times. We show how a single trace of a loop iteration can be segmented into several power traces on which 32-bit words can be hypothesised based on the value of a single private key bit. This segmentation enables a classical correlation power analysis in an extend-and-prune approach. Further error-correction techniques based on depth-search are suggested. The attack is explicitly geared towards and experimentally verified on an STM32F3 featuring a Cortex-M4 microcontroller which runs the SIKEp434 implementation adapted to 32-bit ARM that is part of the official implementations of SIKE. We obtained a resounding 100% success rate recovering the full private key in each experiment. We argue that our attack defeats many countermeasures which were suggested in a previous power analysis of SIKE, and finally show that the well-known countermeasure of projective coordinate randomisation stops the attack with a negligible overhead.

Secure computation enables two or more parties to jointly evaluate a function without revealing to each other their private input. G-module is an abelian group M, where the group G acts compatibly with the abelian group structure on M. In this work, we present several secure computation protocols for G-module operations in the online/offline mode. We then show how to instantiate those protocols to implement many widely used secure computation primitives in privacy-preserving machine learning and data mining, such as oblivious cyclic shift, one-round shared OT, oblivious permutation, oblivious shuffle, secure comparison, oblivious selection, DReLU, and ReLU, etc. All the proposed protocols are constant-round, and they are 2X - 10X more efficient than the-state-of-the-art constant-round protocols in terms of communication complexity.

When generating quartets for the rectangle attacks on ciphers with linear key-schedule, we find the right quartets which may suggest key candidates have to satisfy some nonlinear relations. However, some quartets generated always violate these relations, so that they will never suggest any key candidates. Inspired by previous rectangle frameworks, we find that guessing certain key cells before generating quartets may reduce the number of invalid quartets. However, guessing a lot of key cells at once may lose the benefit from the early abort technique, which may lead to a higher overall complexity. To get better tradeoff, we build a new rectangle framework on ciphers with linear key-schedule with the purpose of reducing overall complexity or attacking more rounds. In the tradeoff model, there are many parameters affecting the overall complexity, especially for the choices of the number and positions of key guessing cells before generating quartets. To identify optimal parameters, we build a uniform automatic tool on SKINNY as an example, which includes the optimal rectangle distinguishers for key-recovery phase, the number and positions of guessing key cells before generating quartets, the size of key counters to build that affecting the exhaustive search step, etc. Based on the automatic tool, we identify a 32-round key-recovery attack on SKINNY-128-384 in the related-key setting, which extends the best previous attack by 2 rounds. For other versions with n-2n or n-3n, we also achieve one more round than before. In addition, using the previous rectangle distinguishers, we achieve better attacks on round-reduced ForkSkinny, Deoxys-BC-384 and GIFT-64. At last, we discuss the conversion of our rectangle framework from related-key setting into single-key setting and give new single-key rectangle attack on 10-round Serpent.

Payment channel networks (PCNs) mitigate the scalability issues of current decentralized cryptocurrencies. They allow for arbitrarily many payments between users connected through a path of intermediate payment channels, while requiring interacting with the blockchain only to open and close the channels. Unfortunately, PCNs are (i) tailored to payments, excluding more complex smart contract functionalities, such as the oracle-enabling Discreet Log Contracts and (ii) their need for active participation from intermediaries may make payments unreliable, slower, expensive, and privacy-invasive. Virtual channels are among the most promising techniques to mitigate these issues, allowing two endpoints of a path to create a direct channel over the intermediaries without any interaction with the blockchain. After such a virtual channel is constructed, (i) the endpoints can use this direct channel for applications other than payments and (ii) the intermediaries are no longer involved in updates. In this work, we first introduce the Domino attack, a new DoS/griefing style attack that leverages virtual channels to destruct the PCN itself and is inherent to the design adopted by the existing Bitcoin-compatible virtual channels. We then demonstrate its severity by a quantitative analysis on a snapshot of the Lightning Network (LN), the most widely deployed PCN at present. We finally discuss other serious drawbacks of existing virtual channel designs, such as the support for only a single intermediary, a latency and blockchain overhead linear in the path length, or a non-constant storage overhead per user. We then present Donner, the first virtual channel construction that overcomes the shortcomings above, by relying on a novel design paradigm. We formally define and prove security and privacy properties in the Universal Composability framework. Our evaluation shows that Donner is efficient, reduces the on-chain number of transactions for disputes from linear in the path length to a single one, which is the key to prevent Domino attacks, and reduces the storage overhead from logarithmic in the path length to constant. Donner is Bitcoin-compatible and can be easily integrated in the LN.

Post-quantum cryptography (PQC) is nowadays a very active research field [1]. We follow a non-standard way to achieve it, taking any common protocol and replacing arithmetic with GF(2^8) field operations, a procedure defined as R-Propping [2-7]. The resulting protocol security relies on the intractability of a generalized discrete log problem, combined with the power sets of algebraic ring extension tensors and resilience to quantum and algebraic attacks. Oblivious Transfer (OT) is a keystone for Secure Multiparty Computing (SMPC) [8], one of the most pursued cryptographic areas. It is a critical issue to develop a fast OT solution because of its intensive use in many protocols. Here, we adopt the simple OT protocol developed by Chou and Orlandi [9] as the base model to be propped. Our solution is fully scalable to achieve quantum and classical security levels as needed. We present a step-by-step numerical example of the proposed protocol.

We introduce the problem of private signaling. In this problem, a sender posts a message to a certain location of a public bulletin board, and then computes a signal that allows only the intended recipient (and no one else) to learn that it is the recipient of the posted message. Besides privacy, this problem has the following crucial efficiency requirements. First, the sender and recipient do not participate in any out-of-band communication, and second, the overhead of the recipient should be asymptotically better than scanning the entire board. Existing techniques, such as the server-aided fuzzy message detection (Beck et al., CCS’21), could be employed to solve the private signaling problem. However, this solution requires that the computational effort of the recipient grows with the amount of privacy desired, providing no saving over scanning the entire board if the maximum privacy is required. In this work, we present a server-aided solution to the private signaling problem that guar- antees full privacy for all recipients, while requiring only constant amount of work for both the recipient and the sender. We provide the following contributions. First, we provide a formal definition of private signaling in the Universal Composability (UC) framework and show that it generalizes several real-world settings where recipient anonymity is desired. Second, we present two protocols that UC-realize our definition: one using a single server equipped with a trusted execution environment, and one based on two servers that employs garbled circuits. Third, we provide an open-source implementation of both of our protocols and evaluate their performance and show that they are practical.

We introduce a new technique for indexing joins in encrypted SQL databases called partially precomputed joins which achieves lower leakage and bandwidth than those used in prior constructions. These techniques are incorporated into state-of-the-art structured encryption schemes for SQL data, yielding a hybrid indexing scheme with both partially and fully precomputed join indexes. We then introduce the idea of leakage-aware query planning by giving a heuristic that helps the client decide, at query time, which index to use so as to minimize leakage and stay below a given bandwidth budget. We conclude by simulating our constructions on real datasets, showing that our heuristic is accurate and that partially-precomputed joins perform well in practice.

In an election where each voter may express $P$ preferences among $M$ possible choices, the Amun protocol allows to secure vote casting against over-the-shoulder adversaries, retaining privacy, fairness, end-to-end verifiability, and correctness. Before the election, each voter receives a ballot containing valid and decoy tokens: only valid tokens contribute in the final tally, but they remain indistinguishable from the decoys. Since the voter is the only one who knows which tokens are valid (without being able to prove it to a coercer), over-the-shoulder attacks are thwarted. We prove the security of the construction under the standard Decisional Diffie Hellman assumption in the random oracle model.

The threat of quantum computers has sparked the development of a new kind of cryptography to resist their attacks. Isogenies between elliptic curves are one of the tools used for such cryptosystems. They are championed by SIKE (Supersingular isogeny key encapsulation), an "alternate candidate" of the third round of the NIST Post-Quantum Cryptography Standardization Process. While all candidates are believed to be mathematically secure, their implementations may be vulnerable to hardware attacks. In this work we investigate for the first time whether Ti's 2017 theoretical fault injection attack is exploitable in practice. We also examine suitable countermeasures. We manage to recover the secret thanks to electromagnetic fault injection on an ARM Cortex A53 using a correct and an altered public key generation. Moreover we propose a suitable countermeasure to detect faults that has a low overhead as it takes advantage of a redundancy already present in SIKE implementations.

This paper presents a side-channel analysis (SCA) on key encapsulation mechanism (KEM) based on the Fujisaki–Okamoto (FO) transformation and its variants. The FO transformation has been widely used in actively securing KEMs from passively secure public key encryption (PKE), as it is employed in most of NIST post-quantum cryptography (PQC) candidates for KEM. The proposed attack exploits side-channel leakage during execution of a psuedorandom function (PRF) in the re-encryption of KEM decapsulation as a plaintext-checking oracle that tells whether the PKE decryption result is equivalent to the reference plaintext. The generality and practicality of the plaintext-checking oracle allows the proposed attack to attain a full-key recovery of various KEMs when an active attack on the underlying PKE is known. This paper demonstrates that the proposed attack can be applied to most NIST PQC third-round KEM candidates, namely, Kyber, Saber, FrodoKEM, NTRU, NTRU Prime, HQC, BIKE, and SIKE (for BIKE, the proposed attack achieves a partial key recovery). The applicability to Classic McEliece is unclear because there is no known active attack on this cryptosystem. This paper also presents a side-channel distinguisher design based on deep learning (DL) for mounting the proposed attack on practical implementation without the use of a profiling device. The feasibility of the proposed attack is demonstrated through experimental attacks on various PRF implementations (a SHAKE software, an AES software, an AES hardware, a bit-sliced masked AES software, and a masked AES hardware based on threshold implementation). The success of the proposed attack against all of these implementations, which include masked hardware based on threshold implementation, confirms its practicality.

The classic work of Gorbunov, Vaikuntanathan and Wee (CRYPTO 2012) and follow-ups provided constructions of bounded collusion Functional Encryption (FE) for circuits from mild assumptions. In this work, we improve the state of affairs for bounded collusion FE in several ways: 1. $New$ $Security$ $Notion$. We introduce the notion of $dynamic$ bounded collusion FE, where the declaration of collusion bound is delayed to the time of encryption. This enables the encryptor to dynamically choose the collusion bound for different ciphertexts depending on their individual level of sensitivity. Hence, the ciphertext size grows linearly with its own collusion bound and the public key size is independent of collusion bound. In contrast, all prior constructions have public key and ciphertext size that grow at least linearly with a fixed bound $Q$. 2. $CPFE$ $for$ $circuits$ $with$ $Dynamic$ $Bounded$ $Collusion$. We provide the first CPFE schemes for circuits enjoying dynamic bounded collusion security. By assuming identity based encryption (IBE), we construct CPFE for circuits of $unbounded$ size satisfying $non-adaptive$ simulation based security. By strengthening the underlying assumption to IBE with receiver selective opening security, we obtain CPFE for circuits of $bounded$ size, output length and depth enjoying $adaptive$ simulation based security. Moreover, we show that IBE is a necessary assumption for these primitives. Moreover, by relying on the Learning With Errors (LWE) assumption, we obtain the first $succinct$ CPFE for circuits, i.e. supporting circuits with unbounded size, but fixed output length and depth. This scheme achieves $adaptive$ simulation based security. 3. $KPFE$ $for$ $circuits$ $with$ $dynamic$ $bounded$ $collusion$. We provide the first KPFE for circuits of unbounded size, but bounded depth and output length satisfying dynamic bounded collusion security. Our construction relies on LWE and achieves $adaptive$ simulation based security. This improves the security of succinct KPFE by Goldwasser et al. [GKPVZ13b]. 4. $KP$ $and$ $CP$ $FE$ $for$ $TM/NL$ $with$ $dynamic$ $bounded$ $collusion$. We provide the first KPFE and CPFE constructions of bounded collusion functional encryption for Turing machines in the public key setting from LWE. Our constructions achieve non-adaptive simulation based security. Both the input and the machine in our construction can be of $unbounded$ polynomial length but the ciphertext size grows with the upper bound on the running time of the Turing machine on the given input. Given RAM access to the ciphertext, the scheme enjoys input specific decryption time. We provide a variant of the above scheme that satisfies $adaptive$ security, but at the cost of supporting a smaller class of computation, namely Nondeterministic Logarithmic-space (NL). Since NL contains Nondeterministic Finite Automata (NFA), this result subsumes $all$ prior work of bounded collusion FE for uniform models from standard assumptions [AMY19,AS17].

Functional Encryption is a powerful notion of encryption in which each decryption key is associated with a function $f$ such that decryption recovers the function evaluation $f(m)$. Informally, security states that a user with access to function keys $\mathsf{sk}_{f_1}, \mathsf{sk}_{f_2}, \ldots$ (and so on) can only learn $f_1(m), f_2(m), \ldots$ (and so on) but nothing more about the message. The system is said to be $q$-bounded collusion resistant if the security holds as long as an adversary gets access to at most $q = q(\lambda)$ function keys. A major drawback of such "statically" bounded collusion systems is that the collusion bound $q$ must be declared at setup time and is fixed for the entire lifetime of the system. We initiate the study of "dynamically" bounded collusion resistant functional encryption systems which provide more flexibility in terms of selecting the collusion bound, while reaping the benefits of statically bounded collusion FE systems (such as quantum resistance, simulation security, and general assumptions). Briefly, the virtues of a dynamically bounded scheme can be summarized as: (i) [Fine-grained individualized selection.] It lets each encryptor select the collusion bound by weighing the trade-off between performance overhead and the amount of collusion resilience. (ii) [Evolving encryption strategies.] Since the system is no longer tied to a single collusion bound, thus it allows to dynamically adjust the desired collusion resilience based on any number of evolving factors such as the age of the system, or a number of active users, etc. (iii) [Ease and simplicity of updatability.] None of the system parameters have to be updated when adjusting the collusion bound. That is, the same key $\mathsf{sk}_f$ can be used to decrypt ciphertexts for collusion bound $q = 2$ as well as $q = 2^\lambda$. We construct such a dynamically bounded functional encryption scheme for the class of all polynomial-size circuits under the general assumption of Identity-Based Encryption.

This is team SmartPools’ submission for the first Ergo Hackathon. It suggests that Ergo lacks the decentralization, and focus on regular people that it was designed for, and presents a potential solution for these problems in laying the framework for crowdfunded smart contract pools compatible with non-outsourceabilty. It should allow for pool formation with a greater level of decentralization than previously possible by including metrics for diminishing returns on over-contributing hash power to pools with data gathered from Ergo Oracles. This work is informal and preliminary. Further research is required to formalize this work and attempt to provide functional proof for its arguments; readers are highly encouraged to read the included references, and their references, for greater clarity.