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.

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.

At Crypto 2018, Aggarwal, Joux, Prakash and Santha (AJPS) described a new public-key encryption scheme based on Mersenne numbers. Shortly after the publication of the cryptosystem, Beunardeau et al. described an attack with complexity O(2^(2h)). In this paper, we describe an improved attack with complexity O(2^(1.75h)).

The LWE problem with its ring variants is today the most prominent candidate for building efficient public key cryptosystems resistant to quantum computers. NTRU-type cryptosystems use an LWE-type variant with small max-norm secrets, usually with ternary coefficients from the set $\{-1,0,1\}$. The presumably best attack on these schemes is a hybrid attack that combines lattice reduction techniques with Odlyzko's Meet-in-the-Middle approach. Odlyzko's algorithm is a classical combinatorial attack that for key space size S runs in time $S^{0.5}$. We substantially improve on this Meet-in-the-Middle approach, using the representation technique developed for subset sum algorithms. Asymptotically, our heuristic Meet-in-the-Middle attack runs in time roughly $S^{0.25}$, which also beats the $S^{\frac 1 3}$ complexity of the best known quantum algorithm. For the round-3 NIST post-quantum encryptions NTRU and NTRU Prime we obtain non-asymptotic instantiations of our attack with complexity roughly $S^{0.3}$. As opposed to other combinatorial attacks, our attack benefits from larger LWE field sizes $q$, as they are often used in modern lattice-based signatures. For example, for BLISS and GLP signatures we obtain non-asymptotic combinatorial attacks around $S^{0.28}$. Our attacks do not invalidate the security claims of the aforementioned schemes. However, they establish improved combinatorial upper bounds for their security. We leave it is an open question whether our new Meet-in-the-Middle attack in combination with lattice reduction can be used to speed up the hybrid attack.

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.

Quantum-access security, where an attacker is granted superposition access to secret-keyed functionalities, is a fundamental security model and its study has inspired results in post-quantum security. We revisit, and fill a gap in, the quantum-access security analysis of the Lamport one-time signature scheme (OTS) in the quantum random oracle model (QROM) by Alagic et al.~(Eurocrypt 2020). We then go on to generalize the technique to the Winternitz OTS. Along the way, we develop a tool for the analysis of hash chains in the QROM based on the superposition oracle technique by Zhandry (Crypto 2019) which might be of independent interest.

We consider the problem of recovering the entries of diagonal matrices $\{U_a\}_a$ for $a = 1,\ldots,t$ from multiple ``incomplete'' samples $\{W_a\}_a$ of the form $W_a=PU_aQ$, where $P$ and $Q$ are unknown matrices of low rank. We devise practical algorithms for this problem depending on the ranks of $P$ and $Q$. This problem finds its motivation in cryptanalysis: we show how to significantly improve previous algorithms for solving the approximate common divisor problem and breaking CLT13 cryptographic multilinear maps.

Indistinguishability obfuscation constructions based on matrix branching programs generally proceed in two steps: first apply Kilian's randomization of the matrix product computation, and then encode the matrices using a multilinear map scheme. In this paper we observe that by applying Kilian's randomization after encoding, the complexity of the best attacks is significantly increased for CLT13 multilinear maps. This implies that much smaller parameters can be used, which improves the efficiency of the constructions by several orders of magnitude. As an application, we describe the first concrete implementation of non-interactive Diffie-Hellman key exchange secure against existing attacks. Key exchange was originally the most straightforward application of multilinear maps; however it was quickly broken for the three known families of multilinear maps (GGH13, CLT13 and GGH15). Here we describe the first implementation of key exchange based on CLT13 that is resistant against the Cheon et al. attack. For N=4 users and a medium level of security, our implementation requires 18 GB of public parameters, and a few minutes for the derivation of a shared key.

Many constructions based on multilinear maps require independent slots in the plaintext, so that multiple computations can be performed in parallel over the slots. Such constructions are usually based on CLT13 multilinear maps, since CLT13 inherently provides a composite encoding space. However, a vulnerability was identified at Crypto 2014 by Gentry, Lewko and Waters, with a lattice-based attack in dimension 2, and the authors have suggested a simple countermeasure. In this paper, we identify an attack based on higher dimension lattice reduction that breaks the author’s countermeasure for a wide range of parameters. Combined with the Cheon et al. attack from Eurocrypt 2015, this leads to a total break of CLT13 multilinear maps with independent slots. We also show how to apply our attack against various constructions based on composite-order CLT13. For the [FRS17] construction, our attack enables to recover the secret CLT13 plaintext ring for a certain range of parameters; however, breaking the indistinguishability of the branching program remains an open problem.

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.

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].

The classical heuristic complexity of the Number Field Sieve (NFS) is the solution of an optimization problem that involves an unknown function, usually noted $o(1)$ and called $\xi(N)$ throughout this paper, which tends to zero as the entry $N$ grows. The aim of this paper is to find optimal asymptotic choices of the parameters of NFS as $N$ grows, in order to minimize its heuristic asymptotic computational cost. This amounts to minimizing a function of the parameters of NFS bound together by a non-linear constraint. We provide precise asymptotic estimates of the minimizers of this optimization problem, which yield refined formulas for the asymptotic complexity of NFS. One of the main outcomes of this analysis is that $\xi(N)$ has a very slow rate of convergence: We prove that it is equivalent to $4{\log}{\log}{\log}\,N/(3{\log}{\log}\,N)$. Moreover, $\xi(N)$ has an unpredictable behavior for practical estimates of the complexity. Indeed, we provide an asymptotic series expansion of $\xi$ and numerical experiments indicate that this series starts converging only for $N>\exp(\exp(25))$, far beyond the practical range of NFS. This raises doubts on the relevance of NFS running time estimates that are based on setting $\xi=0$ in the asymptotic formula.

One of the finalists in the NIST post-quantum cryptography competition is the Classic McEliece cryptosystem. Unfortunately, its public key size represents a practical limitation. One option to address this problem is to use different families of error-correcting codes. Most of such attempts failed as those cryptosystems were proved not secure. In this paper, we propose a McEliece type cryptosystem using high minimum distance self-dual codes and punctured codes derived from them. To the best of our knowledge, such codes have not been implemented in a code-based cryptosystem until now. For the 80-bit security case, we construct an optimal self-dual code of length 1\,064, which, as far as we are aware, was not presented before. Compared to the original McEliece cryptosystem, this allows us to reduce the key size by about 38.5\%.

This work provides a systematic investigation of the use of approximate enumeration oracles in BKZ, building on recent technical progress on speeding-up lattice enumeration: relaxing (the search radius of) enumeration and extended preprocessing which preprocesses in a larger rank than the enumeration rank. First, we heuristically justify that relaxing enumeration with certain extreme pruning asymptotically achieves an exponential speed-up for reaching the same root Hermite factor (RHF). Second, we perform simulations/experiments to validate this and the performance for relaxed enumeration with numerically optimised pruning for both regular and extended preprocessing. Upgrading BKZ with such approximate enumeration oracles gives rise to our main result, namely a practical and faster (wrt. previous work) polynomial-space lattice reduction algorithm for reaching the same RHF in practical and cryptographic parameter ranges. We assess its concrete time/quality performance with extensive simulations and experiments.

To mark the 10-year anniversary of supersingular isogeny Diffie-Hellman, I will touch on 10 points in defense and support of the SIKE protocol, including the rise of classical hardness, the fact that quantum computers do not seem to offer much help in solving the underlying problem, and the importance of concrete cryptanalytic clarity. In the final section I present the two SIKE challenges: $55k USD is up for grabs for the solutions of mini instances that, according to the SIKE team's security analysis, provide significantly less than 64 bits of classical security. I conclude by urging the proponents of other schemes to construct analogous challenge instances.

Nath and Sarkar propose algorithms to improve the efficiency of Diffie-Hellman key agreement using Curve448. In this note an error in the proof of correctness of the subtraction algorithm is described. An alternative argument is offered to fix this error without changing the algorithm or statement of correctness.

Since its invention in 1982, the LLL lattice reduction algorithm (Lenstra, Lenstra, Lovasz 1982) has found countless applications. In cryptanalysis, the two most prominent applications of LLL and its generalisations --e.g. Slide, BKZ and SD-BKZ-- are factoring RSA keys with extra information on the secret key via Coppersmith's method and the cryptanalysis of lattice-based schemes. After almost 40 years of cryptanalytic applications, predicting and optimising lattice reduction algorithms remains an active area of research. While we do have theorems bounding the worst-case performance of these algorithms, those bounds are asymptotic and not necessarily tight when applied to practical or even cryptographic instances. Reasoning about the behaviour of those algorithms relies on heuristics and approximations, some of which are known to fail for relevant corner cases. Decades after Lenstra, Lenstra, and Lovász gave birth to this fascinating and lively research area, this state of affairs became a more pressing issue recently. Motivated by post-quantum security, standardisation bodies, governments and industry started to move towards deploying lattice-based cryptographic algorithms. This spurred the refinement of those heuristics and approximations, leading to a better understanding of the behaviour of these algorithms over the last few years. Lattice reduction algorithms, such as LLL and BKZ, proceed with repeated local improvements to the lattice basis, and each such local improvement means solving the short(est) vector problem in a lattice of a smaller dimension. Therefore, two questions arise: how costly is it to find those local improvements and what is the global behaviour as those improvements are applied. While those two questions may not be perfectly independent, we will, in this survey, focus on the second one, namely, the global behaviour of such algorithms, given oracle access for finding local improvements. Our focus on the global behaviour is motivated by our intent to draw more of the community's attention to this aspect. We will take a particular interest in the behaviour of such algorithms on a specific class of lattices, underlying the most popular lattice problems to build cryptographic primitives, namely the LWE problem and the NTRU problem. We will emphasise on the approximations that have been made, their progressive refinements and highlight open problems to be addressed.

We take a look at the current implementation of NTRU submitted to the NIST post-quantum standardization project, and identify two strong sources of leakage in the unpacking of the secret key. The strength of the leakages is due to the target processor handling data with very different Hamming weight depending on parts of the secret key. We focus on using only these strong leakages, present a single-trace side-channel attack that reliably recovers a large portion of the secret key, and use lattice reduction techniques to find the remaining parts. Further, we show how small changes to the implementation greatly reduces the leakage without any overhead.

In two of the main areas of post-quantum cryptography, based on lattices and codes, nearest neighbor techniques have been used to speed up state-of-the-art cryptanalytic algorithms, and to obtain the lowest asymptotic cost estimates to date [May-Ozerov, Eurocrypt'15; Becker-Ducas-Gama-Laarhoven, SODA'16]. These upper bounds are useful for assessing the security of cryptosystems against known attacks, but to guarantee long-term security one would like to have closely matching lower bounds, showing that improvements on the algorithmic side will not drastically reduce the security in the future. As existing lower bounds from the nearest neighbor literature do not apply to the nearest neighbor problems appearing in this context, one might wonder whether further speedups to these cryptanalytic algorithms can still be found by only improving the nearest neighbor subroutines. We derive new lower bounds on the costs of solving the nearest neighbor search problems appearing in these cryptanalytic settings. For the Euclidean metric we show that for random data sets on the sphere, the locality-sensitive filtering approach of [Becker-Ducas-Gama-Laarhoven, SODA 2016] using spherical caps is optimal, and hence within a broad class of lattice sieving algorithms covering almost all approaches to date, their asymptotic time complexity of $2^{0.292d + o(d)}$ is optimal. Similar conditional optimality results apply to lattice sieving variants, such as the $2^{0.265d + o(d)}$ complexity for quantum sieving [Laarhoven, PhD thesis 2016] and previously derived complexity estimates for tuple sieving [Herold-Kirshanova-Laarhoven, PKC 2018]. For the Hamming metric we derive new lower bounds for nearest neighbor searching which almost match the best upper bounds from the literature [May-Ozerov, Eurocrypt 2015]. As a consequence we derive conditional lower bounds on decoding attacks, showing that also here one should search for improvements elsewhere to significantly undermine security estimates from the literature.

This article discusses the decoding of Gabidulin codes and shows how to extend the usual decoder to any supercode of a Gabidulin code at the cost of a significant decrease of the decoding radius. Using this decoder, we provide polynomial time attacks on the rank–metric encryption schemes Ramesses and Liga.

In this work we study the quantum security of public key encryption schemes (PKE). Boneh and Zhandry (CRYPTO'13) initiated this research area for PKE and symmetric key encryption (SKE), albeit restricted to a classical indistinguishability phase. Gagliardoni et al. (CRYPTO'16) advanced the study of quantum security by giving, for SKE, the first definition with a quantum indistinguishability phase. For PKE, on the other hand, no notion of quantum security with a quantum indistinguishability phase exists. Our main result is a novel quantum security notion (qIND-qCPA) for PKE with a quantum indistinguishability phase, which closes the aforementioned gap. We show a distinguishing attack against code-based schemes and against LWE-based schemes with certain parameters. We also show that the canonical hybrid PKE-SKE encryption construction is qIND-qCPA-secure, even if the underlying PKE scheme by itself is not. Finally, we classify quantum-resistant PKE schemes based on the applicability of our security notion. Our core idea follows the approach of Gagliardoni et al. by using so-called type-2 operators for encrypting the challenge message. At first glance, type-2 operators appear unnatural for PKE, as the canonical way of building them requires both the secret and the public key. However, we identify a class of PKE schemes - which we call recoverable - and show that for this class type-2 operators require merely the public key. Moreover, recoverable schemes allow to realise type-2 operators even if they suffer from decryption failures, which in general thwarts the reversibility mandated by type-2 operators. Our work reveals that many real-world quantum-resistant PKE schemes, including most NIST PQC candidates and the canonical hybrid construction, are indeed recoverable.

Let \(q~=~2^n\), and let \(\mathcal{E} / \mathbb{F}_{q^{\ell}}\) be a generalized Galbraith--Lin--Scott (GLS) binary curve, with $\ell \ge 2$ and \((\ell, n) = 1\). We show that the GLS endomorphism on \(\mathcal{E} / \mathbb{F}_{q^{\ell}}\) induces an efficient endomorphism on the Jacobian \(\mathrm{Jac}_\mathcal{H}(\mathbb{F}_q)\) of the genus-\(g\) hyperelliptic curve \(\mathcal{H}\) corresponding to the image of the GHS Weil-descent attack applied to \(\mathcal{E} / \mathbb{F}_{q^\ell}\), and that this endomorphism yields a factor-$n$ speedup when using standard index-calculus procedures for solving the Discrete Logarithm Problem (DLP) on \(\mathrm{Jac}_\mathcal{H}(\mathbb{F}_q)\). Our analysis is backed up by the explicit computation of a discrete logarithm defined on a prime-order subgroup of a GLS elliptic curve over the field $\mathbb{F}_{2^{5\cdot 31}}$. A Magma implementation of our algorithm finds the aforementioned discrete logarithm in about $1,035$ CPU-days.

Attribute-based encryption (ABE) schemes by lattices are likely to resist quantum attacks, and can be widely applied to many Internet of Thing or cloud scenarios. One of the most attractive feature for ABE is the ability of fine-grained access control which provides an effective way to ensure data security. In this work, we propose an efficient ciphertext policy attribute-based encryption scheme based on hardness assumption of LWE. Being different from other similar schemes, a user's secret key can only be generated once only and it can be used to decrypt ciphertext under different access policies by making combinations of secret key fragments. Specially, we propose a method for binding users' secret keys with their attributes and identities, which solves the collusion attack problem. The security of the scheme is proved to be selective secure under the LWE assumption.

In the random oracle model (ROM), it is provable from the DL assumption, whereas there is negative circumstantial evidence in the standard model. Fleischhacker, Jager, and Schröder showed that the tight security of the Schnorr signature is unprovable from a strong cryptographic assumption, such as the One-More DL (OM-DL) assumption and the computational and decisional Diffie-Hellman assumption, in the ROM via a generic reduction as long as the underlying cryptographic assumption holds. However, it remains open whether or not the impossibility of the provable security of the Schnorr signature from a strong assumption via a non-tight and reasonable reduction. In this paper, we show that the security of the Schnorr signature is unprovable from the OM-DL assumption in the non-programmable ROM as long as the OM-DL assumption holds. Our impossibility result is proven via a non-tight Turing reduction.

The potential development of large-scale quantum computers is raising concerns among IT and security research professionals due to their ability to solve (elliptic curve) discrete logarithm and integer factorization problems in polynomial time. This would jeopardize IT security as we know it. In this work, we investigate two quantum-safe, hash-based signature schemes published by the Internet Engineering Task Force and submitted to the National Institute of Standards and Technology for use in secure boot. We evaluate various parameter sets for the use-case in question and we prove that post-quantum signatures with less than one second signing and less than 10ms verification would not have material impact (less than1‰) on secure boot. We evaluate the hierarchical design of these signatures in hardware-based and virtual secure boot. In addition, we develop Hardware Description Language code and show that the code footprint is just a few kilobytes in size which would fit easily in almost all modern FPGAs. We also analyze and evaluate potential challenges for integration in existing technologies and we discuss considerations for vendors embarking on a journey of image signing with hash-based signatures.

We study the relationship among public-key encryption (PKE) satisfying indistinguishability against chosen plaintext attacks (IND-CPA security), that against chosen ciphertext attacks (IND-CCA security), and trapdoor functions (TDF). Specifically, we aim at finding a unified approach and some additional requirement to realize IND-CCA secure PKE and TDF based on IND-CPA secure PKE, and show the following two main results. As the first main result, we show how to achieve IND-CCA security via a weak form of key-dependent-message (KDM) security. More specifically, we construct an IND-CCA secure PKE scheme based on an IND-CPA secure PKE scheme and a secret-key encryption (SKE) scheme satisfying one-time KDM security with respect to projection functions (projection-KDM security). Projection functions are elementary functions with respect to which KDM security has been widely studied. Since the existence of projection-KDM secure PKE implies that of the above two building blocks, as a corollary of this result, we see that the existence of IND-CCA secure PKE is implied by that of projection-KDM secure PKE. As the second main result, we extend the above construction of IND-CCA secure PKE into that of TDF by additionally requiring a mild requirement for each building block. Our TDF satisfies adaptive one-wayness. We can instantiate our TDF based on a wide variety of computational assumptions. Especially, we obtain the first TDF (with adaptive one-wayness) based on the sub-exponential hardness of the constant-noise learning-parity-with-noise (LPN) problem. In addition, we show that by extending the above constructions, we can obtain PKE schemes satisfying advanced security notions under CCA, that is, optimal rate leakage-resilience under CCA and selective-opening security under CCA. As a result, we obtain the first PKE schemes satisfying these security notions based on the computational Diffie-Hellman (CDH) assumption or the low-noise LPN assumption.

Hierarchical identity-based encryption (HIBE) can be extended to revocable HIBE (RHIBE) if a private key of a user can be revoked when the private key is revealed or expired. Previously, many selectively secure RHIBE schemes were proposed, but it is still unsolved problem to construct an adaptively secure RHIBE scheme. In this work, we propose two RHIBE schemes in composite-order bilinear groups and prove their adaptive security under simple static assumptions. To prove the adaptive security, we use the dual system encryption framework, but it is not simple to use the dual system encryption framework in RHIBE since the security model of RHIBE is quite different with that of HIBE. We show that it is possible to solve the problem of the RHIBE security proof by carefully designing hybrid games.

An aggregatable subvector commitment (aSVC) scheme is a vector commitment (VC) scheme that can aggregate multiple proofs into a single, small subvector proof. In this paper, we formalize aSVCs and give a construction from constant-sized polynomial commitments. Our construction is unique in that it has linear-sized public parameters, it can compute all constant-sized proofs in quasilinear time, it updates proofs in constant time and it can aggregate multiple proofs into a constant-sized subvector proof. Furthermore, our concrete proof sizes are small due to our use of pairing-friendly groups. We use our aSVC to obtain a payments-only stateless cryptocurrency with very low communication and computation overheads. Specifically, our constant-sized, aggregatable proofs reduce each block’s proof overhead to a single group element, which is optimal. Furthermore, our subvector proofs speed up block verification and our smaller public parameters further reduce block size.

In a recent paper Faonio, Nielsen and Venturi (ICALP 2015) gave new constructions of leakage-resilient signature schemes. The signature schemes proposed remain unforgeable against an adversary leaking arbitrary information on the entire state of the signer, including the random coins of the signing algorithm. The main feature of their signature schemes is that they offer a graceful degradation of security in situations where standard existential unforgeability is impossible. The notion, put forward by Nielsen, Venturi, and Zottarel (PKC 2014), defines a slack parameter $\gamma$ which, roughly speaking, describes how gracefully the security degrades. Unfortunately, the standard-model signature scheme of Faonio,Nielsen and Venturi has a slack parameter that depends on the number of signatures queried by the adversary. In this paper we show two new constructions in the standard model where the above limitation is avoided. Specifically, the first scheme achieves slack parameter $O(1/\lambda)$ where $\lambda$ is the security parameter and it is based on standard number theoretic assumptions, the second scheme achieves optimal slack parameter (i.e. $\gamma = 1$) and it is based on knowledge of the exponent assumptions. Our constructions are efficient and have leakage rate $1 - o(1)$, most notably our second construction has signature size of only 8 group elements which makes it the leakage-resilient signature scheme with the shortest signature size known to the best of our knowledge.

This paper introduces a new approach to computing isogenies called "radical isogenies" and a corresponding method to compute chains of $N$-isogenies that is very efficient for small $N$. The method is fully deterministic and completely avoids generating $N$-torsion points. It is based on explicit formulae for the coordinates of an $N$-torsion point $P'$ on the codomain of a cyclic $N$-isogeny $\varphi : E \to E'$, such that composing $\varphi$ with $E' \to E' / \langle P' \rangle$ yields a cyclic $N^2$-isogeny. These formulae are simple algebraic expressions in the coefficients of $E$, the coordinates of a generator $P$ of $\ker \varphi$, and an $N$th root $\sqrt[N]{\rho}$, where the radicand $\rho$ itself is given by an easily computable algebraic expression in the coefficients of $E$ and the coordinates of $P$. The formulae can be iterated and are particularly useful when computing chains of $N$-isogenies over a finite field $\mathbb{F}_q$ with $\gcd(q-1, N) = 1$, where taking an $N$th root is a simple exponentiation. Compared to the state-of-the-art, our method results in an order of magnitude speed-up for $N \leq 13$; for larger $N$, the advantage disappears due to the increasing complexity of the formulae. When applied to CSIDH, we obtain a speed-up of about $19 \%$ over the implementation by Bernstein, De Feo, Leroux and Smith for the CSURF-512 parameters.

In this note, we review lattice-based public-key encryption with the keyword search against inside keyword guess attacks (IKGAs) proposed by Zhang \textit{et al}. in IEEE Transactions on Dependable and Secure Computing in 2021. We demonstrate that this scheme is insecure for IKGAs, although Zhang \textit{et al.} demonstrated a secure proof.

In this work, we demonstrate generic and practical side-channel assisted chosen ciphertext attacks on multiple LWE/LWR-based Public Key Encryption (PKE) and Key Encapsulation Mechanism (KEM) secure in the chosen ciphertext model (IND-CCA security). Firstly, we identified EM-based side-channel vulnerabilities in the error correcting codes (ECC) used in LWE/LWR-based schemes that enable to distinguish the value/validity of the codewords output from the decryption operation. We also identified a similar vulnerability in the Fujisaki-Okamoto transformation which leaks side-channel information about decrypted messages, applicable to multiple lattice-based schemes/variants of schemes that do not use ECC. Our attacks are applicable to about six CCA-secure lattice-based PKE/KEMs currently in the second round of the NIST standardization process. We perform experimental validation of our attacks on implementations taken from the open-source pqm4 library, running on the ARM Cortex-M4 microcontroller. Our attacks are performed in a non-profiled setting and complete key-recovery could be performed in a matter of minutes on all the targeted schemes, thus showing the ease and effectiveness of our attack. We thus attempt to demonstrate the side-channel weaknesses of error correcting codes in CCA-secure LWE/LWR-based schemes and also establish/strengthen the notion that IND-CCA secure LWE/LWR-based schemes are as in-secure as IND-CPA secure schemes in the presence of side-channels unless suitably masked/protected.

We propose a new framework for trapdoor sampling over lattices. Our framework can be instantiated in a number of ways. In a departure from classical samplers, it allows for example to sample from uniform, affine, ``product affine'' and exponential distributions. It allows for example to sample from uniform, affine and ``product affine'' distributions. Another salient point of our framework is that the output distributions of our samplers are perfectly indistinguishable from ideal ones, in contrast with classical samplers that are statistically indistinguishable. One caveat of our framework is that all our current instantiations entail a rather large standard deviation.

Dynamic group signatures (DGS) enable a user to generate a signature on behalf of a group of users, allowing a prospective user to join via an appropriate join protocol. A natural security requirement in the dynamic setting is to permit an adversary to concurrently perform join protocol executions. To date, most of DGS schemes do not provide the efficient concurrent join protocols in their security analysis, because of the need to use knowledge extractors. Also, DGS schemes have to provide efficient batch verifications for practical applications such as Vehicle-to-Vehicle (V2V) and Vehicle-to-Infrastructure (V2I) communication, where a large number of group signatures should be verified in a very short time. In this paper, we propose a new practical DGS scheme that supports not only efficient concurrent joins but also batch verifications. The concurrent security is proven by showing that our join protocols are simulated without any knowledge extractor in security analysis. To do this, we introduce a modified Pointcheval-Sanders (PS) problem that can guarantee efficiently checking equality of discrete logarithms. In terms of efficiency, when considering a type-3 pairing, our DGS scheme has the advantages that the signature generation and verification are faster and especially our batch verification is at least 7 times faster in case of verifying 100 signatures, compared to other comparable pairing-based DGS schemes in the literature.

Revocable identity-based encryption (RIBE) is an extension of IBE with an efficient key revocation mechanism. Revocable hierarchical IBE (RHIBE) is its further extension with key delegation functionality. Although there are various adaptively secure pairing-based RIBE schemes, all known hierarchical analogs only satisfy selective security. In addition, the currently known most efficient adaptively secure RIBE and selectively secure RHIBE schemes rely on non-standard assumptions, which are referred to as the augmented DDH assumption and $q$-type assumptions, respectively. In this paper, we propose a simple but effective design methodology for RHIBE schemes. We provide a generic design framework for RHIBE based on an HIBE scheme with a few properties. Fortunately, several state-of-the-art pairing-based HIBE schemes have the properties. In addition, our construction preserves the sizes of master public keys, ciphertexts, and decryption keys, as well as the complexity assumptions of the underlying HIBE scheme. Thus, we obtain the first RHIBE schemes with adaptive security under the standard $k$-linear assumption. We prove adaptive security by developing a new proof technique for RHIBE. Due to the compactness-preserving construction, the proposed R(H)IBE schemes have similar efficiencies to the most efficient existing schemes.

At Asiacrypt 2020, Moriya et al. introduced two new IND-CPA secure supersingular isogeny based Public Key Encryption (PKE) protocols: SiGamal and C-SiGamal. Unlike the PKEs canonically derived from SIDH and CSIDH, the new protocols provide IND-CPA security without the use of hash functions. SiGamal and C-SiGamal are however not IND-CCA secure. Moriya et al. suggested a variant of SiGamal that could be IND-CCA secure, but left its study as an open problem. In this paper, we revisit the protocols introduced by Moriya et al. First, we show that the SiGamal variant suggested by Moriya et al. for IND-CCA security is, in fact, not IND-CCA secure. Secondly, we propose a new isogeny-based PKE protocol named SimS, obtained by simplifying SiGamal. SimS has smaller public keys and ciphertexts than (C-)SiGamal and it is more efficient. We prove that SimS is IND-CCA secure under CSIDH security assumptions and one Knowledge of Exponent-type assumption we introduce. Interestingly, SimS is also much closer to the CSIDH protocol, facilitating a comparison between SiGamal and CSIDH.

For a hyperelliptic curve defined over a finite field $\bbbf_{q^n}$ with $n>1$, the discrete logarithm problem is subject to index calculus attacks. We exploit the endomorphism of the curve to reduce the size of the factorization basis and hence improve the complexity of the index calculus attack for certain families of ordinary elliptic curves and genus 2 hyperelliptic Jacobians defined over finite fields. This approach adds an extra cost when performing operation on the factor basis, but the experiences show that reducing the size of the factor basis allows to have a gain on the total complexity of index calculus algorithm with respect to the generic attacks.

Lattice-based schemes are promising candidates to replace the current public-key cryptographic infrastructure in wake of the looming threat of quantum computers. One of the Round 3 candidates of the ongoing NIST post-quantum standardization effort is FrodoKEM. It was designed to provide conservative security, which comes with the caveat that implementations are often bigger and slower compared to alternative schemes. In particular, the most time-consuming arithmetic operation of FrodoKEM is the multiplication of matrices with entries in Z_q. In this work, we investigate the performance of different matrix multiplication approaches in the specific setting of FrodoKEM. We consider both optimized “naïve” matrix multiplication with cubic complexity, as well as the Strassen multiplication algorithm which has a lower asymptotic run-time complexity. Our results show that for the proposed parameter sets of FrodoKEM we can improve over the state-of-the-art implementation with a row-wise blocking and packing approach, denoted as RWCF in the following. For the matrix multiplication in FrodoKEM, this results in a factor two speed-up. The impact of these improvements on the full decapsulation operation is up to 22 percent. We additionally show that for batching use-cases, where many inputs are processed at once, the Strassen approach can be the best choice from batch size 8 upwards. For a practically-relevant batch size of 128 inputs the observed speed-up is in the range of 5 to 11 percent over using the efficient RWCF approach and this speed-up grows with the batch size.

In time-specific signatures (TSS) [Paterson \& Quaglia, SCN'10] [Ishizaka \& Kiyomoto, ISC'20] with $T$ numerical values, each signer is given a secret-key associated with a numerical value $t\in[0,T-1]$ and each signature on a message is generated under a numerical range $[L,R]$ s.t. $0\leq L\leq R\leq T-1$. A signer with $t$ can correctly generate a signature under $[L,R]$ if $t$ is truly included in $[L,R]$, i.e., $t\in[L,R]$. As a generalized primitive of TSS, we propose multi-dimensional \textit{sub}-range signatures (MDSBRS). As a related primitive, we also propose multi-dimensional \textit{super}-range signatures (MDSPRS). In MDSBRS (resp. MDSPRS) with $D\in\mathbb{N}$ dimensions, each secret-key is associated with a set of $D$ ranges $\{[l_i,r_i]\mid i\in[1,D]\}$ s.t. $0 \leq l_i\leq r_i\leq T_i-1$ and a threshold value $d\in[1,D]$, and it correctly produces a signature on any message under a set of $D$ ranges $\{[L_i,R_i]\mid i\in[1,D]\}$ s.t. $0 \leq L_i\leq R_i\leq T_i-1$, if and only if total number of key-ranges every one $[l_i,r_i]$ of which is a \textit{sub}-range (resp. \textit{super}-range) of the corresponded signature-range $[L_i,R_i]$, i.e., $L_i\leq l_i\leq r_i\leq R_i$ (resp. $l_i\leq L_i\leq R_i\leq r_i$), is more than $d-1$. We show that, by extending (or generalizing) an existing TSS scheme, we obtain MDSBRS and MDSPRS schemes each one of which is secure, i.e., existentially unforgeable and perfectly (signer-)private, under standard assumption and asymptotically efficient.

Revocable identity-based encryption (RIBE) is an extension of IBE that satisfies a key revocation mechanism to manage a number of users dynamically and efficiently. To resist quantum attacks, two adaptively secure lattice-based RIBE schemes are known in the (quantum) random oracle model ((Q)ROM). Wang et al.'s scheme that is secure in the ROM has large secret keys depending on the depth of a binary tree and its security reduction is not tight. Ma and Lin's scheme that is secure in the QROM has large ciphertexts depending on the length of identities and is not anonymous. In this paper, we propose an adaptively secure lattice-based RIBE scheme that is secure in the QROM. Our scheme has compact parameters, where the ciphertext-size is smaller than Wang et al.'s scheme and the secret key size is the same as Ma and Lin's scheme. Moreover, our scheme is anonymous and its security reduction is completely tight. We design the proposed scheme by modifying Ma-Lin's scheme instantiated by the Gentry-Peikert-Vaikuntanathan (GPV) IBE. We can obtain the advantages of our scheme by making use of Katsumata et al.'s proof technique of the GPV IBE in the QROM.

We introduce a novel variant of Lagrange interpolation called modular Lagrange interpolation that allows us to obtain and prove error bounds for explicit low-degree polynomial approximations of a function on a union of equally-spaced small intervals even if the function overall is not continuous. We apply our technique to the mod function and obtain explicit low-degree polynomial approximations with small error. In particular, for every $k$ and $N >>k$, we construct low-degree polynomials that approximate $f(x) = x \mod N$, for $|f(x)| \leq 1$ and $|x| \leq kN$, to within O($1/N$) additive approximation. For $k= O(\log N)$, the result is generalized to give O($d$)-degree polynomial approximations to within O($N^{-d}$) error for any $d \geq 1$. Literature in approximation theory allows for arbitrary precision polynomial approximation of only smooth functions, whereas the mod function is only piecewise linear. These polynomials can be used in bootstrapping for approximate homomorphic encryption, which requires computing the mod function near multiples of the modulus. Our work bypasses the fundamental error of approximation in prior works caused by first approximating the mod function by a scaled sine function. We implement the bootstrapping of $\mathsf{HEAAN}$ using our polynomials and profile various parameter settings. For example, we demonstrate bootstrapping that can achieve 67 bit message precision, larger than the precision of a $\mathsf{double}$ variable, whereas the most advanced prior work was only capable of up to 40 bit message precision.

Basic key exchange protocols built from the learning with errors (LWE) assumption are insecure if secret keys are reused in the face of active attackers. One example of this is Fluhrer’s attack on the Ding, Xie, and Lin (DXL) LWE key exchange protocol, which exploits leakage from the signal function for error correction. Protocols aiming to achieve security against active attackers generally use one of two techniques: demonstrating well-formed keyshares using re-encryption like in the Fujisaki–Okamoto transform; or directly combining multiple LWE values, similar to MQV-style Diffie–Hellman-based protocols. In this work, we demonstrate improved and new attacks exploiting key reuse in several LWE-based key exchange protocols. First, we show how to greatly reduce the number of samples required to carry out Fluhrer’s attack and reconstruct the secret period of a noisy square waveform, speeding up the attack on DXL key exchange by a factor of over 200. We show how to adapt this to attack a protocol of Ding, Branco, and Schmitt (DBS) designed to be secure with key reuse, breaking the claimed 128-bit security level in under a minute. We also apply our technique to a second authenticated key exchange protocol of DBS that uses an additive MQV design, although in this case our attack makes use of ephemeral key compromise powers of the eCK security model, which was not in scope of the claimed BR-model security proof. Our results show that building secure authenticated key exchange protocols directly from LWE remains a challenging and mostly open problem.

It follows from a result by Friedl, Ivanyos, Magniez, Santha and Sen from 2014 that, for any fixed integer $m > 0$ (thought of as being small), there exists a quantum algorithm for solving the hidden shift problem in an arbitrary finite abelian group $(G, +)$ with time complexity poly$( \log |G|) \cdot 2^{O(\sqrt{\log |mG|})}$. As discussed in the current paper, this can be viewed as a modest statement of Pohlig-Hellman type for hard homogeneous spaces. Our main contribution is a somewhat simpler algorithm achieving the same runtime for $m = 2^tp$, with $t$ any non-negative integer and $p$ any prime number, where additionally the memory requirements are mostly in terms of quantum random access classical memory; indeed, the amount of qubits that need to be stored is poly$( \log |G|)$. Our central tool is an extension of Peikert's adaptation of Kuperberg's collimation sieve to arbitrary finite abelian groups. This allows for a reduction, in said time, to the hidden shift problem in the quotient $G/2^tpG$, which can then be tackled in polynomial time, by combining methods by Friedl et al. for $p$-torsion groups and by Bonnetain and Naya-Plasencia for $2^t$-torsion groups.

Dynamic group signature (DGS) allows a user to generate a signature on behalf of a group, while preserving anonymity. Although many existing DGS schemes have been proposed in the random oracle model for achieving efficiency, their security proofs require knowledge extractors that cause loose security reductions. In this paper, we first propose a new practical DGS scheme whose security can be proven without knowledge extractors in the random oracle model. Moreover, our scheme can also be proven in the strong security model where an adversary is allowed to generate group managers’ keys maliciously. The efficiency of our scheme is comparable to existing secure DGS schemes in the random oracle model using knowledge extractors. The security of our scheme is based on a new complexity assumption that is obtained by generalizing the Pointcheval-Sanders (PS) assumption. Although our generalized PS (GPS) assumption is interactive, we prove that, under the symmetric discrete logarithm (SDL) assumption, the new GPS assumption holds in the algebraic group model.

We consider threshold public-key encryption, where the decryption servers distributively hold the private key shares, and we need a threshold of these servers to decrypt the message (while the system remains secure when less than the threshold is corrupt). We investigate the notion of chosen-ciphertext secure threshold systems which has been historically hard to achieve. We further require the systems to be, both, adaptively secure (i.e., secure against a strong adversary making corruption decisions dynamically during the protocol), and non-interactive (i.e., where decryption servers do not interact amongst themselves but rather efficiently contribute, each, a single message). To date, only pairing-based implementations were known to achieve security in the standard security model without relaxation (i.e., without assuming the random oracle idealization) under the above stringent requirements. Here, we investigate how to achieve the above using other assumptions (in order to understand what other algebraic building blocks and mathematical assumptions are needed to extend the domain of encryption methods achieving the above). Specifically, we show realizations under the Decision Composite Residuosity (DCR) and Learning-With-Errors (LWE) assumptions.

The Ring-LWE over two-to-power cyclotomic integer rings has been the hard computational problem for lattice cryptographic constructions. Its hardness and the conjectured hardness of approximating ideal SIVP for ideal lattices in two-to-power cyclotomic fields have been the fundamental open problems in lattice cryptography and the computational number theory. In our previous paper we presented a general theory of subset attack on the Ring-LWE with not only the Gaussian error distribution but also general error distributions. By the usage of our subset attack from sublattice quadruples we prove that the decision Ring-LWE (then the search version) over two-to-power cyclotomic integer rings with certain sufficiently large polynomially bounded modulus parameters when degrees d_n = 2^{n-1} going to the infinity can be solved by a polynomial (in d_n) time algorithm for wide error distributions with widths in the range of Peikert-Regev-Stephens-Davidowitz hardness reduction results in their STOC 2017 paper. Hence we also prove that approximating idealSIV Ppoly(dn) with some polynomial factors for ideal lattices in two-to-power cyclotomic fields can be solved within the quantum polynomial time. Therefore post-quantum lattice cryptographic constructions can not be based on the ”hardness” of Ring-LWE over two-to-power cyclotomic integer rings even in the classical computational model.

The multivariate scheme HFEv- used to be considered a promising candidate for a post-quantum signature system. First suggested in the early 2000s, a version of the scheme made it to the third round of the ongoing NIST post-quantum standardization process. In late 2020, the system suffered from an efficient rank attack due to Tao, Petzoldt, and Ding. In this paper, we inspect how this recent rank attack is affected by the projection modification. This modification was introduced to secure the signature scheme PFLASH against its predecessor's attacks. We prove upper bounds for the rank of projected HFEv- (pHFEv-) and PFLASH under the new attack, which are tight for the experiments we have performed. We conclude that projection could be a useful tool in protecting against this recent cryptanalysis.

We give a sieving algorithm for finding pairs of consecutive smooth numbers that utilizes solutions to the Prouhet-Tarry-Escott (PTE) problem. Any such solution induces two degree-$n$ polynomials, $a(x)$ and $b(x)$, that differ by a constant integer $C$ and completely split into linear factors in $\mathbb{Z}[x]$. It follows that for any $\ell \in \mathbb{Z}$ such that $a(\ell) \equiv b(\ell) \equiv 0 \bmod{C}$, the two integers $a(\ell)/C$ and $b(\ell)/C$ differ by 1 and necessarily contain $n$ factors of roughly the same size. For a fixed smoothness bound $B$, restricting the search to pairs of integers that are parameterized in this way increases the probability that they are $B$-smooth. Our algorithm combines a simple sieve with parametrizations given by a collection of solutions to the PTE problem. The motivation for finding large twin smooth integers lies in their application to compact isogeny-based post-quantum protocols. The recent key exchange scheme B-SIDH and the recent digital signature scheme SQISign both require large primes that lie between two smooth integers; finding such a prime can be seen as a special case of finding twin smooth integers under the additional stipulation that their sum is a prime $p$. When searching for cryptographic parameters with $2^{240} \leq p <2^{256}$, an implementation of our sieve found primes $p$ where $p+1$ and $p-1$ are $2^{15}$-smooth; the smoothest prior parameters had a similar sized prime for which $p-1$ and $p+1$ were $2^{19}$-smooth. In targeting higher security levels, our sieve found a 376-bit prime lying between two $2^{21}$-smooth integers, a 384-bit prime lying between two $2^{22}$-smooth integers, and a 512-bit prime lying between two $2^{28}$-smooth integers. Our analysis shows that using previously known methods to find high-security instances subject to these smoothness bounds is computationally infeasible.

Lattice-based cryptography relies on generating random bases which are difficult to fully reduce. Given a lattice basis (such as the private basis for a cryptosystem), all other bases are related by multiplication by matrices in $GL(n,\mathbb{Z})$. How can one sample random elements from $GL(n,\mathbb{Z})$? We consider various methods, finding some are stronger than others with respect to the problem of recognizing rotations of the $\mathbb{Z}^n$ lattice. In particular, the standard algorithm of multiplying unipotent generators together (as implemented in Magma's RandomSLnZ command) generates instances of this last problem which can be efficiently broken, even in dimensions nearing 1,500. Likewise, we find that the random basis generation method in one of the NIST Post-Quantum Cryptography competition submissions (DRS) generates instances which can be efficiently broken, even at its 256-bit security settings. Other random basis generation algorithms (some older, some newer) are described which appear to be much stronger.

Cryptographic constructions based on $\textit{ring learning with errors}$ (RLWE) have emerged as one of the front runners for the standardization of post quantum public key cryptography. As the standardization process continues, optimizing specific parts of proposed schemes becomes a worthwhile endeavor. In this work we focus on using error correcting codes to alleviate a natural trade-off present in most schemes; namely, we would like a wider error distribution to increase security, but a wider error distribution comes at the cost of an increased probability of decryption error. The motivation of this work is to improve the security level of RLWE-based public key encryption (PKE) while keeping the target decryption failure rate (DFR) achievable using error-correcting codes. Specifically, we explore how to implement a family member of error correcting codes, known as polar codes, in RLWE-based PKE schemes in order to effectively lower the DFR. The dependency existing in the additive noise term is handled by mapping every error term (e.g., $e,t,s,e_1,e_2$) under canonical embedding to the space $H$ where a product in the number field $K$ gives rise to a coordinate-wise product in $H$. An attempt has been made to make the modulation constellation (message basis) fit in with the canonical basis. Furthermore, we exploit the actuality of some error terms known by the decoder to further lower the DFR. Using our method, the DFR is expected to be as low as $2^{-298}$ for code rate 0.25, $n=1024,q=12289$ and binomial parameter $k=8$ as is exactly the setting of the post-quantum scheme NewHope; DFR is $2^{-156}$ for code rate 0.25, $n=1024,q=12289,k=16$. This new DFR margin enables us to improve the security level by $9.4\%$ compared with NewHope. Moreover, polar encoding and decoding have quasi-linear complexity $O(N\log N)$ and they can be implemented in constant time.

Attribute-based conditional proxy re-encryption (AB-CPRE) allows delegators to carry out attribute-based control on the delegation of decryption by setting policies and attribute vectors. The fine-grained control of AB-CPRE makes it suitable for a variety of applications, such as cloud storage and distributed file systems. However, all existing AB-CPRE schemes are constructed under classical number-theoretic assumptions, which are vulnerable to quantum cryptoanalysis. Therefore, we propose the first AB-CPRE scheme based on the learning with errors (LWE) assumption. Constructed from fully key-homomorphic encryption (FKHE) and key-switching techniques, our scheme is unidirectional, single-hop, and enables a polynomial-deep boolean circuit as its policy. Furthermore, we split the ciphertext into two independent parts to avoid two-level or multi-level encryption/decryption mechanisms. Taking advantage of it, we then extend our single-hop AB-CPRE into an efficient and concise multi-hop one. No matter how many transformations are performed, the re-encrypted ciphertext is in constant size, and only one encryption/decryption algorithm is needed. Both of our schemes are proved to be selective secure against chosen-plaintext attacks (CPA) in the standard model.

A new ``Weighted Bit-flipping'' (WBF) iterative decoder is presented and analyzed with respect to its Decoding Failure Rate (DFR). We show that the DFR is indeed lower than that of the BGF decoder as suggested by the BIKE third round submission to the NIST PQC standardization process. The WBF decoder requires more iterations to complete than BGF, but by creating a hybrid decoder we show that a lower DFR compared to that of the BGF decoder can still be achieved while keeping the computational tradeoff to a minimum.

In this paper, we study the effect of two modifications to multivariate public key encryption schemes: internal perturbation (ip), and Q_+. Focusing on the Dob encryption scheme, a construction utilising these modifications, we accurately predict the number of degree fall polynomials produced in a Gröbner basis attack, up to and including degree five. The predictions remain accurate even when fixing variables. Based on this new theory we design a novel attack on the Dob encryption scheme, which breaks Dob using the parameters suggested by its designers. While our work primarily focuses on the Dob encryption scheme, we also believe that the presented techniques will be of particular interest to the analysis of other big-field schemes.

We focus on exploring more potential of Longa and Sica's algorithm (ASIACRYPT 2012), which is an elaborate iterated Cornacchia algorithm that can compute short bases for 4-GLV decompositions. The algorithm consists of two sub-algorithms, the first one in the ring of integers $\mathbb{Z}$ and the second one in the Gaussian integer ring $\mathbb{Z}[i]$. We observe that $\mathbb{Z}[i]$ in the second sub-algorithm can be replaced by another Euclidean domain $\mathbb{Z}[\omega]$ $(\omega=\frac{-1+\sqrt{-3}}{2})$. As a consequence, we design a new twofold Cornacchia-type algorithm with a theoretic upper bound of output $C\cdot n^{1/4}$, where $C=\frac{3+\sqrt{3}}{2}\sqrt{1+|r|+|s|}$ with small values $r, s$ given by the curves. The new twofold algorithm can be used to compute $4$-GLV decompositions on two classes of curves. First it gives a new and unified method to compute all $4$-GLV decompositions on $j$-invariant $0$ elliptic curves over $\mathbb{F}_{p^2}$. Second it can be used to compute the $4$-GLV decomposition on the Jacobian of the hyperelliptic curve defined as $\mathcal{C}/\mathbb{F}_{p}:y^{2}=x^{6}+ax^{3}+b$, which has an endomorphism $\phi$ with the characteristic equation $\phi^2+\phi+1=0$ (hence $\mathbb{Z}[\phi]=\mathbb{Z}[\omega]$). As far as we know, none of the previous algorithms can be used to compute the $4$-GLV decomposition on the latter class of curves.

Software implementations of cryptographic algorithms are slow but highly flexible and relatively easy to implement. On the other hand, hardware implementations are usually faster but provide little flexibility and require a lot of time to implement efficiently. In this paper, we develop a hybrid software-hardware implementation of the third round of Supersingular Isogeny Key Encapsulation (SIKE), a post-quantum cryptography algorithm candidate for NIST. We implement an isogeny field accelerator for the hardware and integrate it with a RISC-V processor which also acts as the main control unit for the field accelerator. The main advantage of this design is the high performance gain from the hardware implementation and the flexibility and fast development the software implementation provides. This is the first hybrid RISC-V and accelerator of SIKE. Furthermore, we provide one implementation for all NIST security levels of SIKE. Our design has the best area-time at NIST security levels 3 and 5 out of all hardware and hybrid designs provided in the literature.

This work studies signcryption of classical data in the quantum setting. Essentially, we investigate the quantum security of generic constructions of signcryption schemes based on three paradigms, viz., encrypt-then-sign (EtS), sign-then-encrypt (StE) and commit-then-encrypt-and-sign (CtE&S). For doing that we define the confidentiality and authenticity of signcryption for classical data both in insider and outsider models against quantum adversaries. In the insider model, we show that the quantum variants of the classical results hold in the quantum setting. However, for arguing authenticity in outsider model of StE and CtE&S paradigms, we need to consider an intermediate setting in which the adversary is given quantum access to unsigncryption oracle but classical access to signcryption oracle. In two-user outsider model, as in the classical setting, we show that post-quantum CPA security of the base encryption scheme is amplified in the EtS paradigm if the base signature scheme satisfies a stronger definition. We prove an analogous result in the StE paradigm. Interestingly, in the multi-user setting, our results strengthen the known classical results. Furthermore, our results for the EtS and StE paradigms in the two-user outsider model also extend to the setting of authenticated encryption. Finally, we briefly discuss concrete instantiations in various paradigms utilizing some available candidates of quantum secure encryption and signature schemes.

We construct the first decentralized multi-authority attribute-based encryption (MA-ABE) scheme for a non-trivial class of access policies whose security is based (in the random oracle model) solely on the Learning With Errors (LWE) assumption. The supported access policies are ones described by DNF formulas. All previous constructions of MA-ABE schemes supporting any non-trivial class of access policies were proven secure (in the random oracle model) assuming various assumptions on bilinear maps. In our system, any party can become an authority and there is no requirement for any global coordination other than the creation of an initial set of common reference parameters. A party can simply act as a standard ABE authority by creating a public key and issuing private keys to different users that reflect their attributes. A user can encrypt data in terms of any DNF formulas over attributes issued from any chosen set of authorities. Finally, our system does not require any central authority. In terms of efficiency, when instantiating the scheme with a global bound $s$ on the size of access policies, the sizes of public keys, secret keys, and ciphertexts, all grow with $s$. Technically, we develop new tools for building ciphertext-policy ABE (CP-ABE) schemes using LWE. Along the way, we construct the first provably secure CP-ABE scheme supporting access policies in $\mathsf{NC}^1$ that avoids the generic universal-circuit-based key-policy to ciphertext-policy transformation. In particular, our construction relies on linear secret sharing schemes with new properties and in some sense is more similar to CP-ABE schemes that rely on bilinear maps. While our CP-ABE construction is not more efficient than existing ones, it is conceptually intriguing and further we show how to extend it to get the MA-ABE scheme described above.

As lattice-based key encapsulation, digital signature, and fully homomorphic encryption schemes near standardisation, ever more focus is being directed to the precise estimation of the security of these schemes. The primal attack reduces key recovery against such schemes to instances of the unique Shortest Vector Problem (uSVP). Dachman-Soled et al. (Crypto 2020) recently proposed a new approach for fine-grained estimation of the cost of the primal attack when using Progressive BKZ for lattice reduction. In this paper we review and extend their technique to BKZ 2.0 and provide extensive experimental evidence of its accuracy. Using this technique we also explain results from previous primal attack experiments by Albrecht et al. (Asiacrypt 2017) where attacks succeeded with smaller than expected block sizes. Finally, we use our simulators to reestimate the cost of attacking the three lattice KEM finalists of the NIST Post Quantum Standardisation Process.

A digital signature scheme (DSS), which consists of a key-generation, a signing, and a verification algorithm, is an invaluable tool in cryptography. The first and still most widely used security definition for a DSS, existential unforgeability under chosen-message attack, was introduced by Goldwasser, Micali, and Rivest in 1988. As DSSs serve as a building block in numerous complex cryptographic protocols, a security definition that specifies the guarantees of a DSS under composition is needed. Canetti (FOCS 2001, CSFW 2004) as well as Backes, Pfitzmann, and Waidner (CCS 2003) have described ideal functionalities for signatures in their respective composable-security frameworks. While several variants of these functionalities exist, they all share that the verification key and signature values appear explicitly. In this paper, we describe digital signature schemes from a different, more abstract perspective. Instead of modeling all aspects of a DSS in a monolithic ideal functionality, our approach characterizes a DSS as a construction of a repository for authentically reading values written by a certain party from certain assumed repositories, e.g., for transmitting verification key and signature values. This approach resolves several technical complications of previous simulation-based approaches, captures the security of signature schemes in an abstract way, and allows for modular proofs. We show that our definition is equivalent to existential unforgeability. We then model two example applications: (1) the certification of values via a signature from a specific entity, which with public keys as values is the core functionality of public-key infrastructures, and (2) the authentication of a session between a client and a server with the help of a digitally signed assertion from an identity provider. Single-sign-on mechanisms such as SAML rely on the soundness of the latter approach.

The dual attack has long been considered a relevant attack on lattice-based cryptographic schemes relying on the hardness of learning with errors (LWE) and its structured variants. As solving LWE corresponds to finding a nearest point on a lattice, one may naturally wonder how efficient this dual approach is for solving more general closest vector problems, such as the classical closest vector problem (CVP), the variants bounded distance decoding (BDD) and approximate CVP, and preprocessing versions of these problems. While primal, sieving-based solutions to these problems (with preprocessing) were recently studied in a series of works on approximate Voronoi cells, for the dual attack no such overview exists, especially for problems with preprocessing. With one of the take-away messages of the approximate Voronoi cell line of work being that primal attacks work well for approximate CVP(P) but scale poorly for BDD(P), one may wonder if the dual attack suffers the same drawbacks, or if it is a better method for solving BDD(P). In this work we provide an overview of cost estimates for dual algorithms for solving these ''classical'' closest lattice vector problems. Heuristically we expect to solve the search version of average-case CVPP in time and space $2^{0.293d + o(d)}$. For the distinguishing version of average-case CVPP, where we wish to distinguish between random targets and targets planted at distance approximately the Gaussian heuristic from the lattice, we obtain the same complexity in the single-target model, and we obtain query time and space complexities of $2^{0.195d + o(d)}$ in the multi-target setting, where we are given a large number of targets from either target distribution. This suggests an inequivalence between distinguishing and searching, as we do not expect a similar improvement in the multi-target setting to hold for search-CVPP. We analyze three slightly different decoders, both for distinguishing and searching, and experimentally obtain concrete cost estimates for the dual attack in dimensions $50$ to $80$, which confirm our heuristic assumptions, and show that the hidden order terms in the asymptotic estimates are quite small. Our main take-away message is that the dual attack appears to mirror the approximate Voronoi cell line of work -- whereas using approximate Voronoi cells works well for approximate CVP(P) but scales poorly for BDD(P), the dual approach scales well for BDD(P) instances but performs poorly on approximate CVP(P).

The potential development of large-scale quantum computers is raising concerns among IT and security research professionals due to their ability to solve (elliptic curve) discrete logarithm and integer factorization problems in polynomial time. All currently used, public-key cryptography algorithms would be deemed insecure in a post-quantum setting. In response, the United States National Institute of Standards and Technology has initiated a process to standardize quantum-resistant cryptographic algorithms, focusing primarily on their security guarantees. Additionally, the Internet Engineering Task Force has published two quantum-secure signature schemes and has been looking into adding quantum-resistant algorithms in protocols. In this work, we investigate two post-quantum, hash-based signature schemes published by the Internet Engineering Task Force and submitted to the National Institute of Standards and Technology for use in secure boot. We evaluate various parameter sets for the use-cases in question and we prove that post-quantum signatures would not have material impact on image signing. We also study the hierarchical design of these signatures in different scenarios of hardware secure boot.

The security of code-based cryptography usually relies on the hardness of the syndrome decoding (SD) problem for the Hamming weight. The best generic algorithms are all improvements of an old algorithm by Prange, and they are known under the name of Information Set Decoding (ISD) algorithms. This work aims to extend ISD algorithms’ scope by changing the underlying weight function and alphabet size of SD. More precisely, we show how to use Wagner’s algorithm in the ISD framework to solve SD for a wide range of weight functions. We also calculate the asymptotic complexities of ISD algorithms, both for the classical and quantum case. We then apply our results to the Lee metric, which is currently receiving a significant amount of attention. By providing the parameters of SD for the Lee weight for which decoding seems to be the hardest, our study could have several applications for designing code-based cryptosystems and their security analysis, especially against quantum adversaries.

Revocable hierarchical identity-based encryption (RHIBE) is a variant of the standard hierarchical identity-based encryption (HIBE) satisfying the key revocation functionality. Recently, the first adaptively secure RHIBE scheme with compact ciphertexts was proposed by Emura et al. by sacrificing the efficiency of the schemes for achieving adaptive security so that the secret keys are much larger than Seo and Emura's selectively secure scheme with compact ciphertexts. In this paper, we propose a more efficient adaptively secure RHIBE scheme with compact ciphertexts. Our scheme has much shorter secret keys and key updates than Emura et al.'s scheme. Moreover, our scheme has much shorter key updates than Seo and Emura's selectively secure scheme. Emura et al. proved the adaptive security of their scheme by reducing the security of the underlying HIBE schemes to that of their proposed RHIBE scheme, where the adaptive security of the HIBE scheme is inherently proven through the dual system encryption methodology. In contrast, we prove the adaptive security of the proposed RHIBE scheme directly through the dual system encryption methodology. Furthermore, our security proof achieves a tighter reduction than that of Emura et al.

Revocable hierarchical identity-based encryption (RHIBE) is an extension of hierarchical identity-based encryption (HIBE) supporting the key revocation mechanism. In this paper, we propose a generic construction of RHIBE from HIBE with the complete subtree method. Then, we obtain the first RHIBE schemes under the quadratic residuosity assumption, CDH assumption without pairing, factoring Blum integers, LPN assumption, and code-based assumption, and the first almost tightly secure RHIBE schemes under the k-linear assumption. Furthermore, by using pairing-based (dual) identity-based broadcast encryption, we obtain the variants of the scheme with shorter ciphertexts or shorter key updates.

A signer and message ambiguous signature enables a recipient to request a signer to sign a sensible message such that the signer cannot guess what message he signed and the receiver cannot deduce the signer's identity. In this work, we formalize this type of signature, introduce the corresponding security requirements and describe two instantions. The first one assumes that the signer hides his identity in $n$ independently generated public keys, while the second one assumes that all $n$ public keys share the same public parameters.

Haber and Pinkas discussed the principle of when it is secure to reuse key material between public-key cryptosystems. They showed that this can be secure for multiple combinations of systems, including Schnorr signatures. Degabriele, Lehmann, Paterson, Smart and Strefler proved the security of sharing a key pair between a generic elliptic curve Schnorr signature scheme and an elliptic curve Diffie-Hellman based KEM in the random oracle model (ROM). They essentially ran the original security proofs in parallel by leveraging domain separation for the random oracle (RO) usage between the signature scheme and the specific KDF of the KEM. We make two contributions. First, we extend the result in Degabriele et al. by proving the joint security in the ROM of an X25519 based KEM with an HKDF-Extract-like KDF construction and Ed25519. Second, we make no assumptions about domain separation of RO usage between the two systems while making minimal assumptions about the format of the RO usage in Ed25519. Our result is applicable to Ed448 and a corresponding KEM based on X448 as well.

The "Multivariate Ring Learning with Errors" problem was presented as a generalization of Ring Learning with Errors (RLWE), introducing efficiency improvements with respect to the RLWE counterpart thanks to its multivariate structure. Nevertheless, the recent attack presented by Bootland, Castryck and Vercauteren has some important consequences on the security of the multivariate RLWE problem with "non-coprime" cyclotomics; this attack transforms instances of $m$-RLWE with power-of-two cyclotomic polynomials of degree $n = \prod_i n_i$ into a set of RLWE samples with dimension $\max_i{\{ n_i \}}$. This is especially devastating for low-degree cyclotomics (e.g., $\Phi_4(x) = 1 + x^2$). In this work, we revisit the security of multivariate RLWE and propose new alternative instantiations of the problem that avoid the attack while still preserving the advantages of the multivariate structure, especially when using low-degree polynomials. Additionally, we show how to parameterize these instances in a secure and practical way, therefore enabling constructions and strategies based on $m$-RLWE that bring notable space and time efficiency improvements over current RLWE-based constructions.

Fully homomorphic encryption (FHE) allows us to perform computations directly over encrypted data and can be widely used in some highly regulated industries. Gentry's bootstrapping procedure is used to refresh noisy ciphertexts and is the only way to achieve the goal of FHE up to now. In this paper, we optimize the LWE-based GSW-type bootstrapping procedure. Our optimization decreases the lattice approximation factor for the underlying worst-case lattice assumption from $\tilde{O}(N^{2.5})$ to $\tilde{O}(N^{2})$, and is time-efficient by a $O(\lambda)$ factor. Our scheme can also achieve the best factor in prior works on bootstrapping of standard lattice-based FHE by taking a larger lattice dimension, which makes our scheme as secure as the standard lattice-based PKE. Furthermore, in this work we present a technique to perform more operations per bootstrapping in the LWE-based FHE scheme. Although there have been studies to evaluate large FHE gates using schemes over ideal lattices, (i.e. using FHEW or TFHE), we are the first to study how to perform complex functions homomorphically over standard lattices.

In this paper, we present new algorithms for the field arithmetic of supersingular isogeny Diffie-Hellman; one of the fifteen remaining candidates in the NIST post-quantum standardization process. Our approach uses a polynomial representation of the field elements together with mechanisms to keep the coefficients within bounds during the arithmetic operations. We present timings and comparisons for SIKEp503 and suggest a novel 736-bit prime that offers a $1.17\times$ speedup compared to SIKEp751 for a similar level of security.

In TCC 2013, Boyen suggested the first lattice based construction of attribute based encryption (ABE) for the circuit class $NC1$. Unfortunately, soon after, a flaw was found in the security proof of the scheme. However, it remained unclear whether the scheme is actually insecure, and if so, whether it can be repaired. Meanwhile, the construction has been heavily cited and continues to be extensively studied due to its technical novelty. In particular, this is the first lattice based ABE which uses linear secret sharing schemes (LSSS) as a crucial tool to enforce access control. In this work, we show that the scheme is in fact insecure. To do so, we provide a polynomial-time attack that completely breaks the security of the scheme. We suggest a route to fix the security of the scheme, via the notion of admissible linear secret sharing schemes (LSSS) and instantiate these for the class of DNFs. Subsequent to our work, Datta, Komargodski and Waters (Eurocrypt 2021) provided a construction of admissible LSSS for NC1 and resurrected Boyen's claimed result.

This paper presents two modifications for Loidreau’s code-based cryptosystem. Loidreau’s cryptosystem is a rank metric code-based cryptosystem constructed by using Gabidulin codes in the McEliece setting. Recently a polynomial-time key recovery attack was proposed to break Loidreau’s cryptosystem in some cases. To prevent this attack, we propose the use of subcodes to disguise the secret codes in Modification I. In Modification II, we choose a random matrix of low column rank over F q to mix with the secret matrix. According to our analysis, these two modifications can both resist the existing structural attacks. Additionally, we adopt the systematic generator matrix of the public code to make a reduction in the public-key size.

Xifrat was a cryptosystem proposed about half a month ago. This paper demonstrate an attack that computes the mixing function without knowing its key.

In this paper, we propose a new public-key cryptosystem based on a quasigroup with the special property of "restricted-commutativity". We argue its security empirically and present constructions for key exchange and digital signature. To the best of our knowledge, our primitive and construction have no known polynomial-time attack from quantum computers yet. We note that quasigroups with such property had been independently proposed for use in public-key cryptography and termed "entropic" quasigroups or "entropoids" by D.Gligoroski.

One can bootstrap LWE-based fully homomorphic encryption (FHE) schemes in less than one second, but bootstrapping AGCD-based FHE schemes, also known as FHE over the integers, is still very slow. In this work we propose a fast bootstrapping method for FHE over the integers, closing thus this gap between these two types of schemes. We use a variant of the AGCD problem to construct a new GSW-like scheme that can natively encrypt polynomials, then, we show how the single-gate bootstrapping method proposed by Ducas and Micciancio (EUROCRYPT 2015) can be adapted to FHE over the integers using our scheme, and we implement a bootstrapping that, using around 400 MB of key material, runs in less than one second in a common personal computer.

In a recent eprint, Rahman and Shpilrain proposed a Diffie-Hellman style key exchange based on a semidirect product of $n × n$-matrices over a finite field. We show that, using public information, an adversary can recover the agreed upon secret key by solving a system of $n^2$ linear equations.

Ed25519 has significant performance benefits compared to ECDSA using Weierstrass curves such as NIST P-256, therefore it is considered a good digital signature algorithm, specially for low performance IoT devices. However, such devices often have very limited resources and thus, implementations for these devices need to be as small and as performant as possible while being secure. In this paper we describe a scenario in which an obvious strategy to aggressively optimize an Ed25519 implementation for code size leads to a small memory footprint that is functionally correct but vulnerable to side-channel attacks. This strategy serves as an example of aggressive optimizations that might be considered by cryptography engineers, developers, and practitioners unfamiliar with the power of Side-Channel Analysis (SCA). As a solution to the flawed implementation example, we use a computer-aided cryptography tool generating formally verified finite field arithmetic to generate two secure Ed25519 implementations fulfilling different size requirements. After benchmarking and comparing these implementations to other widely used implementations our results show that computer-aided cryptography is capable of generating competitive code in terms of security, speed, and size.

The algebraic structures that are non-commutative and non-associative known as entropic groupoids that satisfy the "Palintropic" property i.e., $x^{\mathbf{A} \mathbf{B}} = (x^{\mathbf{A}})^{\mathbf{B}} = (x^{\mathbf{B}})^{\mathbf{A}} = x^{\mathbf{B} \mathbf{A}}$ were proposed by Etherington in '40s from the 20th century. Those relations are exactly the Diffie-Hellman key exchange protocol relations used with groups. The arithmetic for non-associative power indices known as Logarithmetic was also proposed by Etherington and later developed by others in the 50s-70s. However, as far as we know, no one has ever proposed a succinct notation for exponentially large non-associative power indices that will have the property of fast exponentiation similarly as the fast exponentiation is achieved with ordinary arithmetic via the consecutive rising to the powers of two. In this paper, we define ringoid algebraic structures $(G, \boxplus, *)$ where $(G, \boxplus) $ is an Abelian group and $(G, *)$ is a non-commutative and non-associative groupoid with an entropic and palintropic subgroupoid which is a quasigroup, and we name those structures as Entropoids. We further define succinct notation for non-associative bracketing patterns and propose algorithms for fast exponentiation with those patterns. Next, by an analogy with the developed cryptographic theory of discrete logarithm problems, we define several hard problems in Entropoid based cryptography, such as Discrete Entropoid Logarithm Problem (DELP), Computational Entropoid Diffie-Hellman problem (CEDHP), and Decisional Entropoid Diffie-Hellman Problem (DEDHP). We post a conjecture that DEDHP is hard in Sylow $q$-subquasigroups. Next, we instantiate an entropoid Diffie-Hellman key exchange protocol. Due to the non-commutativity and non-associativity, the entropoid based cryptographic primitives are supposed to be resistant to quantum algorithms. At the same time, due to the proposed succinct notation for the power indices, the communication overhead in the entropoid based Diffie-Hellman key exchange is very low: for 128 bits of security, 64 bytes in total are communicated in both directions, and for 256 bits of security, 128 bytes in total are communicated in both directions. Our final contribution is in proposing two entropoid based digital signature schemes. The schemes are constructed with the Fiat-Shamir transformation of an identification scheme which security relies on a new hardness assumption: computing roots in finite entropoids is hard. If this assumption withstands the time's test, the first proposed signature scheme has excellent properties: for the classical security levels between 128 and 256 bits, the public and private key sizes are between 32 and 64, and the signature sizes are between 64 and 128 bytes. The second signature scheme reduces the finding of the roots in finite entropoids to computing discrete entropoid logarithms. In our opinion, this is a safer but more conservative design, and it pays the price in doubling the key sizes and the signature sizes. We give a proof-of-concept implementation in SageMath 9.2 for all proposed algorithms and schemes in an appendix.

Post-quantum cryptography has known a Cambrian explosion in the last decade. What started as a very theoretical and mathematical area has now evolved into a sprawling research field, complete with side-channel resistant embedded implementations, large scale deployment tests and standardization efforts. This study systematizes the current state of knowledge on post-quantum cryptography. Compared to existing studies, we adopt a transversal point of view and center our study around three areas: (i) paradigms, (ii) implementation, (iii) deployment. Our point of view allows to cast almost all classical and post-quantum schemes into just a few paradigms. We highlight trends, common methodologies, and pitfalls to look for and recurrent challenges.

We introduce a new technique called `Measure-Rewind-Measure' (MRM) to achieve tighter security proofs in the quantum random oracle model (QROM). We first apply our MRM technique to derive a new security proof for a variant of the `double-sided' quantum One-Way to Hiding Lemma (O2H) of Bindel et al. [TCC 2019] which, for the first time, avoids the square-root advantage loss in the security proof. In particular, it bypasses a previous `impossibility result' of Jiang, Zhang and Ma [IACR eprint 2019]. We then apply our new O2H Lemma to give a new tighter security proof for the Fujisaki-Okamoto transform for constructing a strong (INDCCA) Key Encapsulation Mechanism (KEM) from a weak (INDCPA) public-key encryption scheme satisfying a mild injectivity assumption.

We study the memory-tightness of security reductions in public-key cryptography, focusing in particular on Hashed ElGamal. We prove that any straightline (i.e., without rewinding) black-box reduction needs memory which grows linearly with the number of queries of the adversary it has access to, as long as this reduction treats the underlying group generically. This makes progress towards proving a conjecture by Auerbach et al. (CRYPTO 2017), and is also the first lower bound on memory-tightness for a concrete cryptographic scheme (as opposed to generalized reductions across security notions). Our proof relies on compression arguments in the generic group model.

Three-party key exchange, where two clients aim to agree a session key with the help of a trusted server, is prevalent in present-day systems. In this paper, we present a practical and secure three-party password-based authenticated key exchange protocol over ideal lattices. Aside from hash functions our protocol does not rely on external primitives in the construction and the security of our protocol is directly relied on the Ring Learning with Errors (RLWE) assumption. Our protocol attains provable security. A proof-of-concept implementation shows our protocol is indeed practical.

Proxy signature is a kind of digital signature, in which a user called original signer can delegate his signing rights to another user called proxy signer and the proxy signer can sign messages on behalf of the original signer. Certificateless proxy signature (CLPS) means proxy signature in the certificateless setting in which there exists neither the certificate management issue as in traditional PKI nor private key escrow problem as in Identity-based setting. Up to now, a number of CLPS schemes have been proposed, but some of those schemes either lack formal security analysis or turn out to be insecure and others are less efficient because of using costly operations including bilinear pairings and map-to-point hashing on elliptic curve groups. In this paper, we formalize the definition and security model of CLPS schemes. We then construct a pairing-free CLPS scheme from the standard ECDSA and prove its security in the random oracle model under the discrete semi-logarithm problem’s hardness assumption as in the provable security result of ECDSA.

A software watermarking scheme enables one to embed a ``mark " (i.e., a message) into a program without significantly changing the functionality. Moreover, any removal of the watermark from a marked program is futile without significantly changing the functionality of the program. At present, the construction of software watermarking mainly focuses on watermarking pseudorandom functions (PRFs), watermarking public key encryption, watermarking signature, etc. In this work, we construct new watermarking PRFs from lattices which provide collusion resistant and public extraction. Our schemes are the first to simultaneously achieve all of these properties. The key to the success of our new constructions lies in two parts. First, we relax the notion of functionality-preserving. In general, we require that a marked program (approximately) preserve the input/output behavior of the original program. For our scheme, the output circuit is divided into two parts, one for PRF output and the other for auxiliary functions. As a result, we only require the PRF output circuit to satisfy functionality-preserving. Second, the marking method we use is essentially different form the previous scheme. In general, the mark program will change the output of some special point. The extraction algorithm determines whether the circuit is marked by determining whether the output of some special points has been changed. In our schemes, we use the constrained signature to mark a PRF circuit.

Multivariate cryptography is dominated by schemes supporting various tweaks, or ``modifiers,'' designed to patch certain algebraic weaknesses they would otherwise exhibit. Typically these modifiers are linear in nature--- either requiring an extra composition with an affine map, or being evaluated by a legitimate user via an affine projection. This description applies to the minus, plus, vinegar and internal perturbation modifiers, to name a few. Though it is well-known that combinations of various modifiers can offer security against certain classes of attacks, cryptanalysts have produced ever more sophisticated attacks against various combinations of these linear modifiers. In this article, we introduce a more fundamentally nonlinear modifier, called Q, that is inspired from relinearization. The effect of the Q modifier on multivariate digital signature schemes is to maintain inversion efficiency at the cost of slightly slower verification and larger public keys, while altering the algebraic properties of the public key. Thus the Q modifier is ideal for applications of digital signature schemes requiring very fast signing and verification without key transport. As an application of this modifier, we propose new multivariate digital signature schemes with fast signing and verification that are resistant to all known attacks.

We formally prove that the C implementation of the X25519 key-exchange protocol in the TweetNaCl library is correct. We prove both that it correctly implements the protocol from Bernstein's 2006 paper, as standardized in RFC 7748, as well as the absence of undefined behavior like arithmetic overflows and array out-of-bounds errors. We also formally prove, based on the work of Bartzia and Strub, that X25519 is mathematically correct, i.e., that it correctly computes scalar multiplication on the elliptic curve Curve25519. The proofs are all computer-verified using the Coq theorem prover. To establish the link between C and Coq we use the Verified Software Toolchain (VST).

Anonymous identity-based identification scheme in the ad-hoc group is a multi-party cryptographic primitive that allows participants to form an ad-hoc group and prove membership anonymously in such a group. In this paper, we cryptanalyze an ad-hoc anonymous identity-based identification scheme proposed by Barapatre and Rangan and show that the scheme is not secure against key-only universal impersonation attack. We note that anyone can impersonate as a valid group member to convince the honest verifier successfully, even without knowing the group secret key. Moreover, we proposed a fix on the scheme and provide a security proof for our fixed scheme. The fixed scheme we proposed fulfills the security requirements of an ad-hoc anonymous identity-based identification scheme that are correctness, soundness, and anonymity.

The comparison operation for two numbers is one of the most commonly used operations in several applications, including deep learning. Several studies have been conducted to efficiently evaluate the comparison operation in homomorphic encryption schemes, termed homomorphic comparison operation. Recently, Cheon et al. (Asiacrypt 2020) proposed new comparison methods that approximate the sign function using composite polynomial in homomorphic encryption and proved that these methods have optimal asymptotic complexity. In this paper, we propose a practically optimal method that approximates the sign function by using compositions of minimax approximate polynomials. It is proved that this approximation method is optimal with respect to depth consumption and the number of non-scalar multiplications. In addition, a polynomial-time algorithm that determines the optimal compositions of minimax approximate polynomials for the proposed homomorphic comparison operation is proposed by using dynamic programming. The numerical analysis demonstrates that the proposed homomorphic comparison operation reduces running time by approximately 45\% (resp. 41\%) on average, compared with the previous algorithm if running time (resp. depth consumption) is to be minimized. In addition, when $N$ is $2^{17}$, and the precision parameter $\alpha$ is 20, the previous algorithm does not achieve 128-bit security, while the proposed algorithm achieves 128-bit security due to small depth consumption.

What is the funniest number in cryptography? 0. The reason is that for all x, x*0 = 0, i.e., the equation is always satisfied no matter what x is. This article discusses crypto bugs in four BLS signatures’ libraries (ethereum/py ecc, supranational/blst, herumi/bls, sigp/milagro bls) that revolve around 0. Furthermore, we develop ”splitting zero” attacks to show a weakness in the proof-of-possession aggregate signature scheme standardized in BLS RFC draft v4. Eth2 bug bounties program generously awarded $35,000 in total for the reported bugs.

Forward secrecy is an important feature for modern cryptographic systems and is widely used in secure messaging such as Signal and WhatsApp as well as in common Internet protocols such as TLS, IPSec, or SSH. The benefit of forward secrecy is that the damage in case of key-leakage is mitigated. Forward-secret encryption schemes provide security of past ciphertexts even if a secret key leaks, which is interesting in settings where cryptographic keys often reside in memory for quite a long time and could be extracted by an adversary, e.g., in cloud computing. The recent concept of puncturable encryption (PE; Green and Miers, IEEE S&P'15) provides a versatile generalization of forward-secret encryption: it allows to puncture secret keys with respect to ciphertexts to prevent the future decryption of these ciphertexts. We introduce the abstraction of allow-list/deny-list encryption schemes and classify different types of PE schemes using this abstraction. Based on our classification, we identify and close a gap in existing work by introducing a novel variant of PE which we dub Dual-Form Puncturable Encryption (DFPE). DFPE significantly enhances and, in particular, generalizes previous variants of PE by allowing an interleaved application of allow- and deny-list operations. We present a construction of DFPE in prime-order bilinear groups, discuss a direct application of DPFE for enhancing security guarantees within Cloudflare's Geo Key Manager, and show its generic use to construct forward-secret IBE and forward-secret digital signatures.

RSA key generation requires devices to generate large prime numbers. The naïve approach is to generate candidates at random, and then test each one for (probable) primality. However, it is faster to use a sieve method, where the candidates are chosen so as not to be divisible by a list of small prime numbers $\{p_i\}$. Sieve methods can be somewhat complex and time-consuming, at least by the standards of embedded and hardware implementations, and they can be tricky to defend against side-channel analysis. Here we describe an improvement on Joye et al.'s sieve based on the Chinese Remainder Theorem (CRT). We also describe a new sieve method using quadratic residuosity which is simpler and faster than previously known methods, and which can produce values in desired RSA parameter ranges such as $(2^{n-1/2}, 2^n)$ with minimal additional work. The same methods can be used to generate strong primes and DSA moduli. We also demonstrate a technique for RSA private key operations using the Chinese Remainder Theorem (RSA-CRT) without $q^{-1}$ mod $p$. This technique also leads to inversion-free batch RSA and inversion-free RSA mod $p^k q$. We demonstrate how an embedded device can use our key generation and RSA-CRT techniques to perform RSA efficiently without storing the private key itself: only a symmetric seed and one or two short hints are required.

This work presents a hardware accelerator, for the optimization of latency and area at the same time, to improve the performance of point multiplication process in Elliptic Curve Cryptography. In order to reduce the overall computation time in the proposed 2-stage pipelined architecture, a rescheduling of point addition and point doubling instructions is performed along with an efficient use of required memory locations. Furthermore, a 41-bit multiplier is also proposed. Consequently, the FPGA and ASIC implementation results have been provided. The performance comparison with state-of-the-art implementations, in terms of latency and area, proves the significance of the proposed accelerator.

In 1989, Shamir presented an efficient identification scheme (IDS) based on the permuted kernel problem (PKP). After 21 years, PKP was generalized by Lampe and Patarin, who were able to build an IDS similar to Shamir's one, but using the binary field. This binary variant presented some interesting advantages over Shamir's original IDS, such as reduced number of operations and inherently resistance against side-channel attacks. In the security analysis, considering the best attacks against the original PKP, the authors concluded that none of these existing attacks appeared to have a significant advantage when attacking the binary variant. In this paper, we propose the first attack that targets the binary PKP. The attack is analyzed in detail, and its practical performance is compared with our theoretical models. For the proposed parameters originally targeting 79 and 98 bits of security, our attack can recover about 100% of all keys using less than $2^{63}$ and $2^{77}$ operations, respectively.

The problem of Blockwise Isomorphism of Polynomials was introduced by Santoso at PQCrypto 2020 as a generalization of the problem of Isomorphism of Polynomials. In the present paper, we describe how to solve this problem with circulant matrices, used in Santoso's Diffie-Hellman type encryption scheme.

In this work, we introduce the first practical post-quantum verifiable random function (VRF) that relies on well-known (module) lattice problems, namely Module-SIS and Module-LWE. Our construction, named LB-VRF, results in a VRF value of only 84 bytes and a proof of around only 5 KB (in comparison to several MBs in earlier works), and runs in about 3 ms for evaluation and about 1 ms for verification. In order to design a practical scheme, we need to restrict the number of VRF outputs per key pair, which makes our construction few-time. Despite this restriction, we show how our few-time LB-VRF can be used in practice and, in particular, we estimate the performance of Algorand using LB-VRF. We find that, due to the significant increase in the communication size in comparison to classical constructions, which is inherent in all existing lattice-based schemes, the throughput in LB-VRF-based consensus protocol is reduced, but remains practical. In particular, in a medium-sized network with 100 nodes, our platform records a 1.14x to 3.4x reduction in throughput, depending on the accompanying signature used. In the case of a large network with 500 nodes, we can still maintain at least 24 transactions per second. This is still much better than Bitcoin, which processes only about 5 transactions per second.

This article discusses existing attacks and known weaknesses of BLS aggregate signatures. The goal is clarify the threat model of BLS aggregate signatures, what security properties that they have and do not have. It’s unfortunate that the weaknesses are not documented anywhere in BLS RFC draft v4 [1]. Confusion, ambiguity, misunderstanding all may cause security issues in practice. We hope that this article can help cryptographic practitioners make informed decisions when using BLS aggregate signatures and deploy mitigations at the application/protocol layer because BLS aggregate signatures might not have security guarantees that you need.

Schnorr's signature scheme provides an elegant method to derive signatures with security rooted in the hardness of the discrete logarithm problem, which is a well-studied assumption and conducive to efficient cryptography. However, unlike pairing-based schemes which allow arbitrarily many signatures to be aggregated to a single constant sized signature, achieving significant non-interactive compression for Schnorr signatures and their variants has remained elusive. This work shows how to compress a set of independent EdDSA/Schnorr signatures to roughly half their naive size. Our technique does not employ generic succinct proofs; it is agnostic to both the hash function as well as the specific representation of the group used to instantiate the signature scheme. We demonstrate via an implementation that our aggregation scheme is indeed practical. Additionally, we give strong evidence that achieving better compression would imply proving statements specific to the hash function in Schnorr's scheme, which would entail significant effort for standardized schemes such as SHA2 in EdDSA. Among the others, our solution has direct applications to compressing Ed25519-based blockchain blocks because transactions are independent and normally users do not interact with each other.

We construct two tightly secure signature schemes based on the computational Diffie-Hellman (CDH) and factoring assumptions in the random oracle model. Our schemes are proven secure in the multi-user setting, and their security loss is constant and does not depend on the number of users or signing queries. They are the first schemes that achieve this based on standard search assumptions, as all existing schemes we are aware of are either based on stronger decisional assumptions, or proven tightly secure in the less realistic single-user setting. Under a concrete estimation, in a truly large scale, the cost of our CDH-based scheme is about half of Schnorr and DSA (in terms of signature size and running time for signing).

Proxy signature (PS) is a kind of digital signature, in which an entity called original signer can delegate his signing rights to another entity called proxy signer. Designated verifier signature (DVS) is a kind of digital signature where the authenticity of any signature can be verified by only one verifier who is designated by the signer when generating it. Designated verifier proxy signature (DVPS) combines the idea of DVS with the concept of proxy signature (PS) and is suitable for being applied in many scenarios from e-tender, e-voting, e-auction, e-health and e-commerce, etc. Many DVPS schemes have been proposed and Identity-based DVPS (IBDVPS) schemes have also been discussed. Certificateless public-key cryptography (CL-PKC) is acknowledged as an appealing paradigm because there exists neither the certificate management issue as in traditional PKI nor private key escrow problem as in Identity-based setting. A number of certificateless designated verifier signature (CLDVS) schemes and many certificateless proxy signature (CLPS) schemes have been proposed. However, to the best of our knowledge, the concept of Certificateless Designated Verifier Proxy Signature (CLDVPS) has not been appeared in the literature. In this paper, we formalize the definition and the security model of CLDVPS schemes. We then construct the first CLDVPS scheme and prove its security.

We give an exposition of supersingular isogeny graphs, quaternion ideal graphs and Bruhat–Tits trees, and of their connections. Bruhat–Tits trees are combinatorial objects whose vertices and edges have a very simple representation as two-by-two matrices, which, as we show, is useful for understanding certain aspects of the corresponding elliptic curves and isogenies. Moreover Bruhat–Tits trees can be given an orientation and a notion of depth that we translate into the setting of supersingular isogeny graphs. We give some suggestions towards using Bruhat–Tits trees as a tool for cryptanalysis of certain cryptosystems based on supersingular isogeny graphs.