Twisted Reed-Solomon (TRS) codes are a family of codes that contains a large number of maximum distance separable codes that are non-equivalent to Reed--Solomon codes. TRS codes were recently proposed as an alternative to Goppa codes for the McEliece code-based cryptosystem, resulting in a potential reduction of key sizes. The use of TRS codes in the McEliece cryptosystem has been motivated by the fact that a large subfamily of TRS codes is resilient to a direct use of known algebraic key-recovery methods. In this paper, an efficient key-recovery attack on the TRS variant that was used in the McEliece cryptosystem is presented. The algorithm exploits a new approach based on recovering the structure of a well-chosen subfield subcode of the public code. It is proved that the attack always succeeds and breaks the system for all practical parameters in $O(n^4)$ field operations. A software implementation of the algorithm retrieves a valid private key from the public key within a few minutes, for parameters claiming a security level of 128 bits. The success of the attack also indicates that, contrary to common beliefs, subfield subcodes of the public code need to be precisely analyzed when proposing a McEliece-type code-based cryptosystem. Finally, the paper discusses an attempt to repair the scheme and a modification of the attack aiming at Gabidulin-Paramonov-Tretjakov cryptosystems based on twisted Gabidulin codes.

Elliptic curves play a prominent role in cryptography. For instance, the hardness of the elliptic curve discrete logarithm problem is a foundational assumption in public key cryptography. Drinfeld modules are positive characteristic function field analogues of elliptic curves. It is natural to ponder the existence/security of Drinfeld module analogues of elliptic curve cryptosystems. But the Drinfeld module discrete logarithm problem is easy even on a classical computer. Beyond discrete logarithms, elliptic curve isogeny based cryptosystems have have emerged as candidates for post-quantum cryptography, including supersingular isogeny Diffie-Hellman (SIDH) and commutative supersingular isogeny Diffie-Hellman (CSIDH) protocols. We formulate Drinfeld module analogues of these elliptic curve isogeny based cryptosystems and devise classical polynomial time algorithms to break these Drinfeld analogues catastrophically.

Privacy protection techniques have been thoroughly studied in the current blockchain research field with the famous representatives such as Monero and Zerocash, which have realized fully anonymous and confidential transactions. However, lack of audit can lead to abuse of privacy, and can help bad guys to conduct illegal activities, such as money laundering, transfer of illegal assets, illegal transactions, etc. Therefore, it is crucial to study the privacy-preserving cryptocurrency with full auditability. In this paper, under the framework similar to Monero, we propose FAPC, a fully auditable privacy-preserving cryptocurrency with security against malicious auditors. FAPC mainly consists of three schemes: a traceable and linkable ring signature scheme (TLRS), a traceable range proof (TRP), and a tracing scheme for long-term address (TSLA). In FAPC, the identities of UTXOs, transaction amounts and the corresponding long-term addresses can be traced by the auditor with maintaining anonymous and confidential to others. The constructions of TLRS and TRP are simple and modular, which only use standard ring signature as component, without any additional one-time signatures or zero-knowledge proofs. The TSLA is constructed by usage of standard ring signature and ElGamal encryption to realize traceability of long-term addresses in transactions. Moreover, all the schemes are secure against malicious auditors to realize a closer approach towards decentralization. We also give the security proofs and implementations of our schemes, as well as the performance results.

We present a new general framework for constructing compact and adaptively secure attribute-based encryption (ABE) schemes from $k$-Lin in asymmetric bilinear pairing groups. Previously, the only construction [Kowalczyk and Wee, Eurocrypt '19] that simultaneously achieves compactness and adaptive security from static assumptions supports policies represented by Boolean formulae. Our framework enables supporting more expressive policies represented by arithmetic branching programs. Our framework extends to ABE for policies represented by uniform models of computation such as Turing machines. Such policies enjoy the feature of being applicable to attributes of arbitrary lengths. We obtain the first compact adaptively secure ABE for deterministic and non-deterministic finite automata (DFA and NFA) from $k$-Lin, previously unknown from any static assumptions. Beyond finite automata, we obtain the first ABE for large classes of uniform computation, captured by deterministic and non-deterministic logspace Turing machines (the complexity classes $\mathsf{L}$ and $\mathsf{NL}$) based on $k$-Lin. Our ABE scheme has compact secret keys of size linear in the description size of the Turing machine $M$. The ciphertext size grows linearly in the input length, but also linearly in the time complexity, and exponentially in the space complexity. Irrespective of compactness, we stress that our scheme is the first that supports large classes of Turing machines based solely on standard assumptions. In comparison, previous ABE for general Turing machines all rely on strong primitives related to indistinguishability obfuscation.

We have proposed before a multivariate public key cryptosystem (MPKC) that does not rely on the difficulty of prime factorization, and whose modulus is the product of many small prime numbers. In this system, the prime factorization by the attackers is self-trivial, and the structure of the secret key is based on CRT (Chinese Remainder Theorem). In this paper we propose MPKC with security of IND-CPA by adding random numbers to central transformation vectors in the system proposed before.

In this paper, we introduce a polynomial-time algorithm to compute a connecting $\mathcal{O}$-ideal between two supersingular elliptic curves over $\mathbb{F}_p$ with common $\mathbb{F}_p$-endomorphism ring $\mathcal{O}$, given a description of their full endomorphism rings. This algorithm provides a reduction of the security of the CSIDH cryptosystem to the problem of computing endomorphism rings of supersingular elliptic curves. A similar reduction for SIDH appeared at Asiacrypt 2016, but relies on totally different techniques. Furthermore, we also show that any supersingular elliptic curve constructed using the complex-multiplication method can be located precisely in the supersingular isogeny graph by explicitly deriving a path to a known base curve. This result prohibits the use of such curves as a building block for a hash function into the supersingular isogeny graph.

Last year Takashima proposed a version of Charles, Goren and Lauter’s hash function using Richelot isogenies, starting from a genus-2 curve that allows for all subsequent arithmetic to be performed over a quadratic finite field Fp^2 . In a very recent paper Flynn and Ti point out that Takashima’s hash function is insecure due to the existence of small isogeny cycles. We revisit the construction and show that it can be repaired by imposing a simple restriction, which moreover clarifies the security analysis. The runtime of the resulting hash function is dominated by the extraction of 3 square roots for every block of 3 bits of the message, as compared to one square root per bit in the elliptic curve case; however in our setting the extractions can be parallelized and are done in a finite field whose bit size is reduced by a factor 3. Along the way we argue that the full supersingular isogeny graph is the wrong context in which to study higher-dimensional analogues of Charles, Goren and Lauter’s hash function, and advocate the use of the superspecial subgraph, which is the natural framework in which to view Takashima’s Fp^2-friendly starting curve.

We put forth a new framework for building pairing-based non-interactive zero- knowledge (NIZK) arguments for a wide class of algebraic languages, which are an extension of linear languages, containing disjunctions of linear languages and more. Our approach differs from the Groth-Sahai methodology, in that we rely on pairings to compile a $\Sigma$-protocol into a NIZK. Our framework enjoys a number of interesting features: – conceptual simplicity, parameters derive from the $\Sigma$-protocol; – proofs as short as resulting from the Fiat-Shamir heuristic applied to the underlying $\Sigma$-protocol; – fully adaptive soundness and perfect zero-knowledge in the common random string model with a single random group element as CRS; – yields simple and efficient two-round, public coin, publicly-verifiable perfect witness-indistinguishable (WI) arguments (ZAPs) in the plain model. To our knowledge, this is the first construction of two-rounds statistical witness-indistinguishable arguments from pairing assumptions. Our proof system relies on a new (static, falsifiable) assumption over pairing groups which generalizes the standard kernel Diffie-Hellman assumption in a natural way and holds in the generic group model (GGM) and in the algebraic group model (AGM). Replacing Groth-Sahai NIZKs with our new proof system allows to improve several important cryptographic primitives. In particular, we obtain the shortest tightly-secure structure-preserving signature scheme (which are a core component in anonymous credentials), the shortest tightly-secure quasi-adaptive NIZK with unbounded simulation soundness (which in turns implies the shortest tightly-mCCA-secure cryptosystem), and shorter ring signatures.

Attribute-Based Encryption (ABE) is a versatile one-to-many encryption primitive, which enables fine-grained access control over encrypted data. Due to its promising applications in practice, ABE schemes with high efficiency, security and expressivity have been continuously emerging. On the other hand, due to the nature of ABE, a malicious user may abuse its decryption privilege. Therefore, being able to identify such a malicious user is crucial towards the practicality of ABE. Although some specific ABE schemes in the literature enjoys the tracing function, they are only proceeded case by case. Most of the ABE schemes do not support traceability. It is thus meaningful and important to have \emph{a generic way of equipping any ABE scheme with traceability}. In this work we partially solve the aforementioned problem. Namely, we propose a way of transforming (non-traceable) ABE schemes satisfying certain requirements to \emph{fully collusion-resistant black-box traceable} ABE schemes, which adds only $O(\sqrt{\cal K})$ elements to the ciphertext where ${\cal K}$ is the number of users in the system. And to demonstrate the practicability of our transformation, we show how to convert a couple of existing non-traceable ABE schemes to support traceability.

CSIDH is a recent proposal for post-quantum non-interactive key-exchange, presented at ASIACRYPT 2018. Based on supersingular elliptic curve isogenies, it is similar in design to a previous scheme by Couveignes, Rostovtsev and Stolbunov, but aims at an improved balance between efficiency and security. In the proposal, the authors suggest concrete parameters in order to meet some desired levels of quantum security. These parameters are based on the hardness of recovering a hidden isogeny between two elliptic curves, using a quantum subexponential algorithm of Childs, Jao and Soukharev. This algorithm combines two building blocks: first, a quantum algorithm for recovering a hidden shift in a commutative group. Second, a computation in superposition of all isogenies originating from a given curve, which the algorithm calls as a black box. In this paper, we give a comprehensive security analysis of CSIDH. Our first step is to revisit three quantum algorithms for the abelian hidden shift problem from the perspective of non-asymptotic cost. There are many possible tradeoffs between the quantum and classical complexities of these algorithms and all of them should be taken into account by security levels. Second, we complete the non-asymptotic study of the black box in the hidden shift algorithm. This allows us to show that the parameters proposed by the authors of CSIDH do not meet their expected quantum security.

The CCA-secure lattice-based post-quantum key encapsulation scheme Saber is a candidate in the NIST's post-quantum cryptography standardization process. In this paper, we study the implementation aspects of Saber in resource-constrained microcontrollers from the ARM Cortex-M series which are very popular for realizing IoT applications. In this work, we carefully optimize various parts of Saber for speed and memory. We exploit digital signal processing instructions and efficient memory access for a fast implementation of polynomial multiplication. We also use memory efficient Karatsuba and just-in-time strategy for generating the public matrix of the module lattice to reduce the memory footprint. We also show that our optimizations can be combined with each other seamlessly to provide various speed-memory trade-offs. Our speed optimized software takes just 1,147K, 1,444K, and 1,543K clock cycles on a Cortex-M4 platform for key generation, encapsulation and decapsulation respectively. Our memory efficient software takes 4,786K, 6,328K, and 7,509K clock cycles on an ultra resource-constrained Cortex-M0 platform for key generation, encapsulation, and decapsulation respectively while consuming only 6.2 KB of memory at most. These results show that lattice-based key encapsulation schemes are perfectly practical for securing IoT devices from quantum computing attacks.

This work builds on the variant of the function field sieve (FFS) algorithm for the medium prime case introduced by Joux and Lercier in 2006. We make several contributions. The first contribution uses a divisibility and smoothness technique and goes on to develop a sieving method based on the technique. This leads to significant practical efficiency improvements in the descent phase and also provides improvement to Joux's pinpointing technique. The second contribution is a detailed analysis of the degree of freedom and the use of a walk technique in the descent phase of the algorithm. Such analysis shows that it is possible to compute discrete logarithms over certain fields which are excluded by the earlier analyses performed by Joux and Lercier (2006) and Joux (2013). In concrete terms, we present computations of discrete logs for fields with 16 and 19-bit prime characteristic. We also provide concrete analysis of the effectiveness of the FFS algorithm for certain fields of characteristic ranging from 16-bit to 32-bit primes. The final contribution is to perform a complete asymptotic analysis of the FFS algorithm for fields $\mathbb{F}_Q$ with $p=L_Q(1/3,c)$. This closes gaps and corrects errors in the analysis earlier performed by Joux-Lercier and Joux and also provides new insights into the asymptotic behaviour of the algorithm.

Since the introduction of the ring-learning with errors problem, the number theoretic transform (NTT) based polynomial multiplication algorithm has been studied extensively. Due to its faster quasilinear time complexity, it has been the preferred choice of cryptographers to realize ring-learning with errors cryptographic schemes. Compared to NTT, Toom-Cook or Karatsuba based polynomial multiplication algorithms, though being known for a long time, still have a fledgling presence in the context of post-quantum cryptography. In this work, we observe that the pre- and post-processing steps in Toom-Cook based multiplications can be expressed as linear transformations. Based on this observation we propose two novel techniques that can increase the efficiency of Toom-Cook based polynomial multiplications. Evaluation is reduced by a factor of 2, and we call this method precomputation, and interpolation is reduced from quadratic to linear, and we call this method lazy interpolation. As a practical application, we applied our algorithms to the Saber post-quantum key-encapsulation mechanism. We discuss in detail the various implementation aspects of applying our algorithms to Saber. We show that our algorithm can improve the efficiency of the computationally costly matrix-vector multiplication by12−37%compared to previous methods on their respective platforms. Secondly, we propose different methods to reduce the memory footprint of Saber for Cortex-M4microcontrollers. Our implementation shows between2.6 and 5.7KB reduction in memory usage with respect to the smallest implementation in the literature.

Homomorphic encryption primitives have the potential to be the main enabler of privacy preserving computation delegation to cloud environments. One of the avenues which has been explored to reduce their significant computational overhead with respect to cleartext computation is the one of the so-called noise-free homomorphic encryption schemes. In this work, we present an attack against fully homomorphic encryption primitives where a distinguisher for a single plaintext value exists. We employ two noise-free homomorphic encryption schemes where such a property holds as our case studies, providing detailed attack procedure against them. We validate the effectiveness and performance of our attacks on prototype implementations of the said schemes, and suggest two countermeasures to our attack tailored to the schemes at hand.

We present attacks on the cryptography formerly used in the IOTA blockchain, including under certain conditions the ability to forge signatures. We developed practical attacks on IOTA's cryptographic hash function Curl-P-27, allowing us to quickly generate short colliding messages. These collisions work even for messages of the same length. Exploiting these weaknesses in Curl-P-27, we broke the EU-CMA security of the former IOTA Signature Scheme (ISS). Finally, we show that in a chosen-message setting we could forge signatures and multi-signatures of valid spending transactions (called bundles in IOTA).

We construct the first tightly secure hierarchical identity-based encryption (HIBE) scheme based on standard assumptions, which solves an open problem from Blazy, Kiltz, and Pan (CRYPTO 2014). At the core of our constructions is a novel randomization technique that enables us to randomize user secret keys for identities with flexible length. The security reductions of previous HIBEs lose at least a factor of Q, which is the number of user secret key queries. Different to that, the security loss of our schemes is only dependent on the security parameter. Our schemes are adaptively secure based on the Matrix Diffie-Hellman assumption, which is a generalization of standard Diffie-Hellman assumptions such as k-Linear. We have two tightly secure constructions, one with constant ciphertext size, and the other with tighter security at the cost of linear ciphertext size. Among other things, our schemes imply the first tightly secure identity-based signature scheme by a variant of the Naor transformation.

Group signatures allow creating signatures on behalf of a group, while remaining anonymous. To prevent misuse, there exists a designated entity, named the opener, which can revoke anonymity by generating a proof which links a signature to its creator. Still, many intermediate cases have been discussed in the literature, where not the full power of the opener is required, or the users themselves require the power to claim (or deny) authorship of a signature and (un-)link signatures in a controlled way. However, these concepts were only considered in isolation. We unify these approaches, supporting all these possibilities simultaneously, providing fine-granular openings, even by members. Namely, a member can prove itself whether it has created a given signature (or not), and can create a proof which makes two created signatures linkable (or unlinkable resp.) in a controlled way. Likewise, the opener can show that a signature was not created by a specific member and can prove whether two signatures stem from the same signer (or not) without revealing anything else. Combined, these possibilities can make full openings irrelevant in many use-cases. This has the additional benefit that the requirements on the reachability of the opener are lessened. Moreover, even in the case of an involved opener, our framework is less privacy-invasive, as the opener no longer requires access to the signed message. Our provably secure black-box CCA-anonymous construction with dynamic joins requires only standard building blocks. We prove its practicality by providing a performance evaluation of a concrete instantiation, and show that our non-optimized implementation is competitive compared to other, less feature-rich, notions.

It has been suspected that in supersingular isogeny-based cryptosystems the two ending elliptic curves computed by the participants are exactly equal. Resolving this open problem has not been pressing because the elliptic curves are known to be isomorphic, and therefore share a $j$-invariant which can be used as a shared secret. However, this is still an interesting independent problem as other values of the elliptic curves may be valuable as shared information as well. This note answers this open problem in the affirmative.

We present in this paper a blind signature and its partially blind variant based on lattices assumptions. Blind signature is a cornerstone in privacy-oriented cryptography and we propose the first lattice based scheme without restart. Compare to related work, the key idea of our construction is to provide a trapdoor to the signer in order to let him perform some gaussian pre-sampling during the signature generation process, preventing this way to restart from scratch the whole protocol. We prove the security of our scheme under the ring k-SIS assumption, in the random oracle model. We also explain security issues in the other existing lattice-based blind signature schemes. Finally, we propose a partially blind variant of our scheme, which is done with no supplementary cost, as the number of elements generated and exchanged during the signing protocol is exactly the same.

Recently, Castryck, Lange, Martindale, Panny, and Renes proposed CSIDH (pronounced "sea-side") as a candidate post-quantum "commutative group action." It has attracted much attention and interest, in part because it enables noninteractive Diffie--Hellman-like key exchange with quite small communication. Subsequently, CSIDH has also been used as a foundation for digital signatures. In 2003--04, Kuperberg and then Regev gave asymptotically subexponential quantum algorithms for "hidden shift" problems, which can be used to recover the CSIDH secret key from a public key. In late 2011, Kuperberg gave a follow-up quantum algorithm called the collimation sieve ("c-sieve" for short), which improves the prior ones, in particular by using exponentially less quantum memory and offering more parameter tradeoffs. While recent works have analyzed the concrete cost of the original algorithms (and variants) against CSIDH, nothing of this nature was previously available for the c-sieve. This work fills that gap. Specifically, we generalize Kuperberg's collimation sieve to work for arbitrary finite cyclic groups, provide some practical efficiency improvements, give a classical (i.e., non-quantum) simulator, run experiments for a wide range of parameters up to the actual CSIDH-512 group order, and concretely quantify the complexity of the c-sieve against CSIDH. Our main conclusion is that the proposed CSIDH parameters provide relatively little quantum security beyond what is given by the cost of quantumly evaluating the CSIDH group action itself (on a uniform superposition). For example, the cost of CSIDH-512 key recovery is only about $2^{16}$ quantum evaluations using $2^{40}$ bits of quantumly accessible classical memory (plus relatively small other resources). This improves upon a prior estimate of $2^{32.5}$ evaluations and $2^{31}$ qubits of quantum memory, for a variant of Kuperberg's original sieve. Under the plausible assumption that quantum evaluation does not cost much more than what is given by a recent "best case" analysis, CSIDH-512 can therefore be broken using significantly less than $2^{64}$ quantum T-gates. This strongly invalidates its claimed NIST level 1 quantum security, especially when accounting for the MAXDEPTH restriction. Moreover, under analogous assumptions for CSIDH-1024 and -1792, which target higher NIST security levels, except near the high end of the MAXDEPTH range even these instantiations fall short of level 1.

In a transaction-output-based blockchain system, where each transaction spends UTXOs (the previously unspent transaction outputs), a user must provide a signature, or more precisely a \(\textit{scriptSig}\) for Bitcoin, to spend an UTXO, which proves the ownership of the spending output. When Pedersen commitment \(g^xh^a\) or ElGamal commitment \((g^xh^a,h^x)\) introduced into blockchain as transaction output, for supporting confidential transaction feature, where the input and output amounts in a transaction are hidden, the prior signature schemes such as Schnorr signature scheme and its variants does not directly work here if using the commitment as the public key, since nobody including the committer knows the private key of a \(g^xh^a\) when $a$ is not zero, meaning no one knows the $c$ such that \((g^c=g^xh^a)\). This is a signature scheme which is able to use the \(C=g^xh^a\) as the signature public key for any value of $a$. The signer, proceeding from a random Pedersen commitment \(R=g^{k_1}h^{k_2}\), generates a random bit sequence $e$, by multiplication of a stored private key $x$ with the bit sequence $e$ and by addition of the random number $k_1$ to get the $u$, by multiplication of the committed value $a$ with the bit sequence $e$ and by addition of the random number $k_2$ to get the $v$, finally constructs \(\sigma=(R,u,v)\) as the signature, with the corresponding public key $C$. In turn, the verifier calculates a Pedersen commitment \(S=g^uh^v\), and accepts the signature if \(S=RC^e\). For an electronic signature, a hash value $e$ is calculated from a random Pedersen commitment $R$, the Pedersen commitment $C$, and from the message $m$ to be signed. This signature scheme will be very helpful in the design of a non-interactive transaction in Mimblewimble.

Boneh, Waters and Zhandry (CRYPTO 2014) used multilinear maps to provide a solution to the long-standing problem of public-key broadcast encryption (BE) where all parameters in the system are small. In this work, we improve their result by providing a solution that uses only bilinear maps and Learning With Errors (LWE). Our scheme is fully collusion-resistant against any number of colluders, and can be generalized to an identity-based broadcast system with short parameters. Thus, we reclaim the problem of optimal broadcast encryption from the land of “Obfustopia”. Our main technical contribution is a ciphertext policy attribute based encryption (CP-ABE) scheme which achieves special efficiency properties – its ciphertext size, secret key size, and public key size are all independent of the size of the circuits supported by the scheme. We show that this special CP-ABE scheme implies BE with optimal parameters; but it may also be of independent interest. Our constructions rely on a novel interplay of bilinear maps and LWE, and are proven secure in the generic group model.

In this paper, a multivariate polynomial and exponential mappings based password protocol is presented. The method can be utilized in public domains. The key generator generates a vector, intended to be used as a password by the authentication protocol subsequently, such that when the vector is substituted and evaluated in certain fixed multivariate polynomials -- that may be listed in a public domain -- the value $0$ is found as a result of proper authentication. The public domain in this context could be internal to a large, and possibly distributed, system. The key generator can take hints from the owner of the password to generate the particular zero vector to suit the user. It may take into consideration biometric and any other user specific information at the time of key generation. The information collected by the key generator can be saved by the owner of the password for its possible retrieval upon requisition by the user, during the period of its validity, in case it is forgotten by the user.

This work presents sigma protocols to prove knowledge of: -a solution to a system of quadratic polynomials, -a solution to an instance of the Permuted Kernel Problem and -a witness for a variety of lattice statements (including SIS). Our sigma protocols have soundness error 1/q', where q' is any number bounded by the size of the underlying finite field. This is much better than existing proofs, which have soundness error 2/3 or (q'+1)/2q'. The prover and verifier time of our proofs are O(q'). We achieve this by first constructing so-called sigma protocols with helper, which are sigma protocols where the prover and the verifier are assisted by a trusted third party, and then eliminating the helper from the proof with a "cut-and-choose" protocol. We apply the Fiat-Shamir transform to obtain signature schemes with security proof in the QROM. We show that the resulting signature schemes, which we call the "MUltivariate quaDratic FIat-SHamir" scheme (MUDFISH) and the "ShUffled Solution to Homogeneous linear SYstem FIat-SHamir" scheme (SUSHSYFISH), are more efficient than existing signatures based on the MQ problem and the Permuted Kernel Problem. Our proof system can be used to improve the efficiency of applications relying on (generalizations of) Stern's protocol. We show that the proof size of our SIS proof is smaller than that of Stern's protocol by an order of magnitude and that our proof is more efficient than existing post-quantum secure SIS proofs.

We introduce a framework generalizing lattice reduction algorithms to module lattices in order to practically and efficiently solve the $\gamma$-Hermite Module-SVP problem over arbitrary cyclotomic fields. The core idea is to exploit the structure of the subfields for designing a doubly-recursive strategy of reduction: both recursive in the rank of the module and in the field we are working in. Besides, we demonstrate how to leverage the inherent symplectic geometry existing in the tower of fields to provide a significant speed-up of the reduction for rank two modules. The recursive strategy over the rank can also be applied to the reduction of Euclidean lattices, and we can perform a reduction in asymptotically almost the same time as matrix multiplication. As a byproduct of the design of these fast reductions, we also generalize to all cyclotomic fields and provide speedups for many previous number theoretical algorithms. Quantitatively, we show that a module of rank 2 over a cyclotomic field of degree $n$ can be heuristically reduced within approximation factor $2^{\tilde{O}(n)}$ in time $\tilde{O}(n^2B)$, where $B$ is the bitlength of the entries. For $B$ large enough, this complexity shrinks to $\tilde{O}(n^{\log_2 3}B)$. This last result is particularly striking as it goes below the estimate of $n^2B$ swaps given by the classical analysis of the LLL algorithm using the so-called potential. Finally, all this framework is fully parallelizable, and we provide a full implementation. We apply it to break multilinear cryptographic candidates on concrete proposed parameters. We were able to reduce matrices of dimension 4096 with 6675-bit integers in 4 days, which is more than a million times faster than previous state-of-the-art implementations. Eventually, we demonstrate a quasicubic time for the Gentry-Szydlo algorithm which finds a generator given the relative norm and a basis of an ideal. This algorithm is important in cryptanalysis and requires efficient ideal multiplications and lattice reductions; as such we can practically use it in dimension 1024.

Inner product functional encryption (IPFE) [1] is a popular primitive which enables inner product computations on encrypted data. In IPFE, the ciphertext is associated with a vector x, the secret key is associated with a vector y and decryption reveals the inner product <x,y>. Previously, it was known how to achieve adaptive indistinguishability (IND) based security for IPFE from the DDH, DCR and LWE assumptions [8]. However, in the stronger simulation (SIM) based security game, it was only known how to support a restricted adversary that makes all its key requests either before or after seeing the challenge ciphertext, but not both. In more detail, Wee [46] showed that the DDH-based scheme of Agrawal et al. (Crypto 2016) achieves semi-adaptive simulation-based security, where the adversary must make all its key requests after seeing the challenge ciphertext. On the other hand, O'Neill showed that all IND-secure IPFE schemes (which may be based on DDH, DCR and LWE) satisfy SIM-based security in the restricted model where the adversary makes all its key requests before seeing the challenge ciphertext. In this work, we resolve the question of SIM-based security for IPFE by showing that variants of the IPFE constructions by Agrawal et al., based on DDH, Paillier and LWE, satisfy the strongest possible adaptive SIM-based security where the adversary can make an unbounded number of key requests both before and after seeing the (single) challenge ciphertext. This establishes optimal security of the IPFE schemes, under all hardness assumptions on which it can (presently) be based.

Lattices used in cryptography are integer lattices. Defining and generating a "random integer lattice" are interesting topics. A generation algorithm for random integer lattice can be used to serve as a random input of all the lattice algorithms. In this paper, we recall the definition of random integer lattice given by G.Hu et al. and present an improved generation algorithm for it via Hermite Normal Form. It can be proved that with probability >= 0.99, this algorithm outputs an n-dim random integer lattice within O(n^2) operations.

In this work, we present: - the first adaptively secure ABE for DFA from the k-Lin assumption in prime-order bilinear groups; this resolves one of open problems posed by Waters [CRYPTO'12]; - the first ABE for NFA from the k-Lin assumption, provided the number of accepting paths is smaller than the order of the underlying group; the scheme achieves selective security; - the first compact adaptively secure ABE (supporting unbounded multi-use of attributes) for branching programs from the k-Lin assumption, which generalizes and simplifies the recent result of Kowalczyk and Wee for boolean formula (NC1) [EUROCRYPT'19]. Our adaptively secure ABE for DFA relies on a new combinatorial mechanism avoiding the exponential security loss in the number of states when naively combining two recent techniques from CRYPTO'19 and EUROCRYPT'19. This requires us to design a selectively secure ABE for NFA; we give a construction which is sufficient for our purpose and of independent interest. Our ABE for branching programs leverages insights from our ABE for DFA.

Isogeny-based cryptography is a kind of post-quantum cryptography whose security relies on the hardness of an isogeny problem over elliptic curves. In this paper, we study CSIDH, which is one of isogeny-based cryptography presented by Castryck et al. in Asiacrypt 2018. In CSIDH, the secret key is taken from an $L_\infty$-norm ball of integer vectors and the public key is generated by calculating the action of an ideal class corresponding to a secret key. For faster key exchange, it is important to accelerate the algorithm calculating the action of the ideal class group, many such approaches have been studied recently. Several papers showed that CSIDH becomes more efficient when a secret key space is changed to weighted $L_\infty$-norm ball. In this paper, we revisit the approach and try to find an optimal secret key space which minimizes the computational cost of the group action. At first, we obtain an optimal secret key space by analyzing computational cost of CSIDH with respect to the number of operations on $\mathbb{F}_p$. Since the optimal key space is too complicated to sample a secret key uniformly, we approximate the optimal key space by using $L_1$-norm ball and propose algorithms for uniform sampling with some precomputed table. By experiment with CSIDH-512, we show that the computational cost of the $L_1$-norm ball is reduced by about 20\% compared to that of the $L_\infty$-norm ball, using a precomputed table of 160 Kbytes. The cost is only 1.08 times of the cost of the optimal secret key space. Finally, we also discuss possible sampling algorithms using other norm balls and their efficiency.

Classically, selective-opening attack (SOA) has been studied for randomized primitives, like randomized encryption schemes and commitments. The study of SOA for deterministic primitives, which presents some unique challenges, was initiated by Bellare et al. (PKC 2015), who showed negative results. Subsequently, Hoang et al. (ASIACRYPT 2016) showed positive results in the non-programmable random oracle model. Here we show the first positive results for SOA security of deterministic primitives in the standard (RO devoid) model. Our results are: \begin{itemize} \item Any $2t$-wise independent hash function is SOA secure for an unbounded number of ``$t$-correlated'' messages, meaning any group of up to $t$ messages are arbitrarily correlated. \item An analogous result for deterministic encryption, from close variant of a NPROM scheme proposed by Hoang et al. \item We connect the one-more-RSA problem of Bellare et al. (J.~Cryptology 2003) to this context and demonstrate this problem is hard under the $\Phi$-Hiding Assumption with large enough encryption exponent. \end{itemize} Our results indicate that SOA for deterministic primitives in the standard model is more tractable than prior work would indicate.

Lattice-based encryption schemes are often subject to the possibility of decryption failures, in which valid encryptions are decrypted incorrectly. Such failures, in large number, leak information about the secret key, enabling an attack strategy alternative to pure lattice reduction. Extending the "failure boosting'' technique of D'Anvers et al. in PKC 2019, we propose an approach that we call "directional failure boosting'' that uses previously found "failing ciphertexts'' to accelerate the search for new ones. We analyse in detail the case where the lattice is defined over polynomial ring modules quotiented by <X^N + 1> and demonstrate it on a simple Mod-LWE-based scheme parametrized à la Kyber768/Saber. We show that, using our technique, for a given secret key (single-target setting), the cost of searching for additional failing ciphertexts after one or more have already been found, can be sped up dramatically. We thus demonstrate that, in this single-target model, these schemes should be designed so that it is hard to even obtain one decryption failure. Besides, in a wider security model where there are many target secret keys (multi-target setting), our attack greatly improves over the state of the art.

Attribute-based encryption (ABE) is an advanced cryptographic tool and useful to build various types of access control systems. Toward the goal of making ABE more practical, we propose key-policy (KP) and ciphertext-policy (CP) ABE schemes, which first support unbounded sizes of attribute sets and policies with negation and multi-use of attributes, allow fast decryption, and are fully secure under a standard assumption, simultaneously. The proposed schemes are more expressive than previous schemes and efficient enough. We also implement our schemes in 128-bit security level and present their benchmarks for an ordinary personal computer and smartphones. They show that all algorithms run in one second with the personal computer when they handle any policy or attribute set with one hundred attributes.

We show new partial and full instantiation results under chosen-ciphertext security for the widely implemented and standardized RSA-OAEP encryption scheme of Bellare and Rogaway (EUROCRYPT 1994) and two variants. Prior work on such instantiations either showed negative results or settled for ``passive'' security notions like IND-CPA. More precisely, recall that RSA-OAEP adds redundancy and randomness to a message before composing two rounds of an underlying Feistel transform, whose round functions are modeled as random oracles (ROs), with RSA. Our main results are: \begin{itemize} \item Either of the two oracles (while still modeling the other as a RO) can be instantiated in RSA-OAEP under IND-CCA2 using mild standard-model assumptions on the round functions and generalizations of algebraic properties of RSA shown by Barthe, Pointcheval, and Báguelin (CCS 2012). The algebraic properties are only shown to hold at practical parameters for small encryption exponent ($e=3$), but we argue they have value for larger $e$ as well. \item Both oracles can be instantiated simultaneously for two variants of RSA-OAEP, called ``$t$-clear'' and ``$s$-clear'' RSA-OAEP. For this we use extractability-style assumptions in the sense of Canetti and Dakdouk (TCC 2010) on the round functions, as well as novel yet plausible ``XOR-type'' assumptions on RSA. While admittedly strong, such assumptions may nevertheless be necessary at this point to make positive progress. \end{itemize} In particular, our full instantiations evade impossibility results of Shoup (J.~Cryptology 2002), Kiltz and Pietrzak (EUROCRYPT 2009), and Bitansky et al. (STOC 2014). Moreover, our results for $s$-clear RSA-OAEP yield the most efficient RSA-based encryption scheme proven IND-CCA2 in the standard model (using bold assumptions on cryptographic hashing) to date.

We construct the first hierarchical identity-based encryption (HIBE) scheme with tight adaptive security in the multi-challenge setting, where adversaries are allowed to ask for ciphertexts for multiple adaptively chosen identities. Technically, we develop a novel technique that can tightly introduce randomness into user secret keys for hierarchical identities in the multi-challenge setting, which cannot be easily achieved by the existing techniques for tightly multi-challenge secure IBE. In contrast to the previous constructions, the security of our scheme is independent of the number of user secret key queries and that of challenge ciphertext queries. We prove the tight security of our scheme based on the Matrix Decisional Diffie-Hellman Assumption, which is an abstraction of standard and simple decisional Diffie-Hellman assumptions, such as the k-Linear and SXDH assumptions. Finally, we also extend our ideas to achieve tight chosen-ciphertext security and anonymity, respectively. These security notions for HIBE have not been tightly achieved in the multi-challenge setting before.

We give the first public-key functional encryption that supports the generation of functional decryption keys for degree-2 polynomials, with succinct ciphertexts, whose semi-adaptive simulation-based security is proven under standard assumptions. At the heart of our new paradigm lies a so-called partially function-hiding functional encryption scheme for inner products, which admits public-key instances, and that is sufficient to build functional encryption for degree-2 polynomials. Doing so, we improve upon prior works, such as the constructions from Lin (CRYPTO 17) or Ananth Sahai (EUROCRYPT 17), both of which rely on function-hiding inner product FE, that can only exist in the private-key setting. The simplicity of our construction yields the most efficient FE for quadratic functions from standard assumptions (even those satisfying a weaker security notion). The interest of our methodology is that the FE for quadratic functions that builds upon any partially function-hiding FE for inner products inherits the security properties of the latter. In particular, we build a partially function-hiding FE for inner products that enjoys simulation security, in the semi-adaptive setting, where the challenge sent from the adversary can be chosen adaptively after seeing the public key (but before corrupting functional decryption keys). This is in contrast from prior public-key FE for quadratic functions from Baltico et al. (CRYPTO 17), which only achieved an indistinguishability-based, selective security. As a bonus, we show that we can obtain security against Chosen-Ciphertext Attacks straightforwardly. Even though this is the de facto security notion for encryption, this was not achieved by prior functional encryption schemes for quadratic functions, where the generic Fujisaki Okamoto transformation (CRYPTO 99) does not apply.

We consider the setting in which an untrusted server stores a collection of data and is asked to compute a function over it. In this scenario, we aim for solutions where the untrusted server does not learn information about the data and is prevented from cheating. This problem is addressed by verifiable and private delegation of computation, proposed by Gennaro, Gentry and Parno (CRYPTO’10), a notion that is close to both the active areas of homomorphic encryption and verifiable computation (VC). However, in spite of the efficiency advances in the respective areas, VC protocols that guarantee privacy of the inputs are still expensive. The only exception is a protocol by Fiore, Gennaro and Pastro (CCS’14) that supports arithmetic circuits of degree at most 2. In this paper we propose new efficient protocols for VC on encrypted data that improve over the state of the art solution of Fiore et al. in multiple aspects. First, we can support computations of degree higher than 2. Second, we achieve public delegatability and public verifiability whereas Fiore et al. need the same secret key to encode inputs and verify outputs. Third, we achieve a new property that guarantees that verifiers can be convinced about the correctness of the outputs without learning information on the inputs. The key tool to obtain our new protocols is a new SNARK that can efficiently handle computations over a quotient polynomial ring, such as the one used by Ring-LWE somewhat homomorphic encryption schemes. This SNARK in turn relies on a new commit-and-prove SNARK for proving evaluations on the same point of several committed polynomials. We propose a construction of this scheme under an extractability assumption over bilinear groups in the random oracle model.

We present NTTRU -- an IND-CCA2 secure NTRU-based key encapsulation scheme that uses the number theoretic transform (NTT) over the cyclotomic ring $Z_{7681}[X]/(X^{768}-X^{384}+1)$ and produces public keys and ciphertexts of approximately $1.25$ KB at the $128$-bit security level. The number of cycles on a Skylake CPU of our constant-time AVX2 implementation of the scheme for key generation, encapsulation and decapsulation is approximately $6.4$K, $6.1$K, and $7.9$K, which is more than 30X, 5X, and 8X faster than these respective procedures in the NTRU schemes that were submitted to the NIST post-quantum standardization process. These running times are also, by a large margin, smaller than those for all the other schemes in the NIST process. We also give a simple transformation that allows one to provably deal with small decryption errors in OW-CPA encryption schemes (such as NTRU) when using them to construct an IND-CCA2 key encapsulation.

The user of an imperfectly correct lattice-based public-key encryption scheme leaks information about their secret key with each decryption query that they answer---even if they answer all queries successfully. Through a refinement of the D'Anvers--Guo--Johansson--Nilsson--Vercauteren--Verbauwhede failure boosting attack, we show that an adversary can use this information to improve his odds of finding a decryption failure. We also propose a new definition of $\delta$-correctness, and we re-assess the correctness of several submissions to NIST's post-quantum standardization effort.

We initiate the study of threshold schemes based on the Hard Homogeneous Spaces (HHS) framework of Couveignes. Quantum-resistant HHS based on supersingular isogeny graphs have recently become usable thanks to the record class group precomputation performed for the signature scheme CSI-FiSh. Using the HHS equivalent of the technique of Shamir's secret sharing in the exponents, we adapt isogeny based schemes to the threshold setting. In particular we present threshold versions of the CSIDH public key encryption, and the CSI-FiSh signature schemes. The main highlight is a threshold version of CSI-FiSh which runs almost as fast as the original scheme, for message sizes as low as 1880 B, public key sizes as low as 128 B, and thresholds up to 56; other speed-size-threshold compromises are possible.

We initiate the study of indifferentiability for public key encryption and other public key primitives. Our main results are definitions and constructions of public key cryptosystems that are indifferentiable from ideal cryptosystems, in the random oracle model. Cryptosystems include Public key encryption, Digital signatures, Non-interactive key agreement. Our schemes are based on standard public key assumptions. By being indifferentiable from an ideal object, our schemes satisfy any security property that can be represented as a single-stage game and can be composed to operate in higher-level protocols.

We propose two polynomial memory collision finding algorithms for the low Hamming weight discrete logarithm problem in any abelian group $G$. The first one is a direct adaptation of the Becker-Coron-Joux (BCJ) algorithm for subset sum to the discrete logarithm setting. The second one significantly improves on this adaptation for all possible weights using a more involved application of the representation technique together with some new Markov chain analysis. In contrast to other low weight discrete logarithm algorithms, our second algorithm's time complexity interpolates to Pollard's $|G|^{\frac 1 2}$ bound for general discrete logarithm instances. We also introduce a new subset sum algorithm with polynomial memory that improves on BCJ's $2^{0.72n}$ time bound for random subset sum instances $a_1, \ldots, a_n, t \in \mathbb{Z}_{2^n}$. Technically, we introduce a novel nested collision finding for subset sum -- inspired by the NestedRho algorithm from Crypto '16 -- that recursively produces collisions. We first show how to instantiate our algorithm with run time $2^{0.649n}$. Using further tricks, we are then able to improve its complexity down to $2^{0.645n}$.

We revisit the method of designing public-key puncturable encryption schemes and present a generic conversion by leveraging the techniques of distributed key-distribution and revocable encryption. In particular, we first introduce a refined version of identity-based revocable encryption, named key-homomorphic identity-based revocable key encapsulation mechanism with extended correctness. Then, we propose a generic construction of puncturable key encapsulation mechanism from the former by merging the idea of distributed key-distribution. Compared to the state-of-the-art, our generic construction supports unbounded number of punctures and multiple tags per message, thus achieving more fine-grained revocation of decryption capability. Further, it does not rely on random oracles, not suffer from non-negligible correctness error, and results in a variety of efficient schemes with distinct features. More precisely, we obtain the first scheme with very compact ciphertexts in the standard model, and the first scheme with support for both unbounded size of tags per ciphertext and unbounded punctures as well as constant-time puncture operation. Moreover, we get a comparable scheme proven secure under the standard DBDH assumption, which enjoys both faster encryption and decryption than previous works based on the same assumption, especially when the number of tags associated with the ciphertext is large.

In the standard setting of functional encryption (FE), we assume both the Central Authority (CA) and the encryptors to run their respective algorithms faithfully. Badrinarayanan et al [ASIACRYPT 2016] put forth the concept of verifiable FE, which essentially guarantees that dishonest encryptors and authorities, even when colluding together, are not able to generate ciphertexts and tokens that give inconsistent results. They also provide a compiler turning any perfectly correct FE into a verifiable FE, but do not give efficient constructions. In this paper we improve on this situation by considering Inner-Product Encryption (IPE), which is a special case of functional encryption and a primitive that has attracted wide interest from both practitioners and researchers in the last decade. Specifically, we construct the first efficient verifiable IPE (VIPE) scheme according to the inner-product functionality of Katz, Sahai, and Waters [EUROCRYPT 2008]. To instantiate the general construction of Badrinarayanan et al, we need to solve several additional challenges. In particular, we construct the first efficient perfectly correct IPE scheme. Our VIPE satisfies unconditional verifiability, whereas its privacy relies on the DLin assumption.

BIKE (Bit-flipping Key Encapsulation) is a promising candidate running in the NIST Post-Quantum Cryptography Standardization process. It is a code-based cryptosystem that enjoys a simple definition, well-understood underlying security, and interesting performance. The most critical step in this cryptosystem consists of correcting errors in a QC-MDPC linear code. The BIKE team proposed variants of the Bit-Flipping Decoder for this step for Round 1 and 2 of the standardization process. In this paper, we propose an alternative decoder which is more friendly to hardware implementations, leading to a latency-area performance comparable to the literature while introducing power side channel resilience. We also show that our design can accelerate all key generation, encapsulation and decapsulation operations using very few common logic building blocks.

There have been notable improvements in discrete logarithm computations in finite fields since 2015 and the introduction of the Tower Number Field Sieve algorithm (TNFS) for extension fields. The Special TNFS is very efficient in finite fields that are target groups of pairings on elliptic curves, where the characteristic is special (e.g.~sparse). The key sizes for pairings should be increased, and alternative pairing-friendly curves can be considered. We revisit the Special variant of TNFS for pairing-friendly curves. In this case the characteristic is given by a polynomial of moderate degree (between 4 and 38) and tiny coefficients, evaluated at an integer (a seed). We present a polynomial selection with a new practical trade-off between degree and coefficient size. As a consequence, the security of curves computed by Barbulescu, El~Mrabet and Ghammam in 2019 should be revised: we obtain a smaller estimated cost of STNFS for all curves except BLS12 and BN. To obtain TNFS-secure curves, we reconsider the Brezing--Weng generic construction of families of pairing-friendly curves and estimate the cost of our new Special TNFS algorithm for these curves. This improves on the work of Fotiadis and Konstantinou, Fotiadis and Martindale, and Barbulescu, El~Mrabet and Ghammam. We obtain a short-list of interesting families of curves that are resistant to the Special TNFS algorithm, of embedding degrees 10 to 16 for the 128-bit security level. We conclude that at the 128-bit security level, BLS-12 and Fotiadis--Konstantinou--Martindale curves with $k=12$ over a 440 to 448-bit prime field seem to be the best choice for pairing efficiency. We also give hints at the 192-bit security level.

We propose a new family of public key encryption (PKE) and key encapsulation mechanism (KEM) schemes based on the plain learning with errors (LWE) problem. Two new design techniques are adopted in the proposed scheme named SCloud: the sampling method and the error-reconciliation mechanism. The new sampling method is obtained by studying the property of the convolution of central binomial distribution and bounded uniform distribution which can achieve higher efficiency and more flexibility w.r.t the parameter choice. Besides, it is shown to be more secure against the dual attack due to its advantage in distinguish property. The new error-reconciliation mechanism is constructed by combining the binary linear codes and Gray codes. It can reduce the size of parameters, and then improve the encryption/decryption efficiency as well as communication efficiency, by making full use of the encryption space. Based on these two techniques, SCloud can provide various sets of parameters for refined security level.

Though Fully Homomorphic Encryption (FHE) has been realized, most practical implementations utilize leveled Somewhat Homomorphic Encryption (SHE) schemes, which have limits on the multiplicative depth of the circuits they can evaluate and avoid computationally intensive bootstrapping. Many SHE schemes exist, among which those based on Ring Learning With Error (RLWE) with operations on large polynomial rings are popular. Of these, variants allowing operations to occur fully in Residue Number Systems (RNS) have been constructed. This optimization allows homomorphic operations directly on RNS components without needing to reconstruct numbers from their RNS representation, making SHE implementations faster and highly parallel. In this paper, we present a set of optimizations to a popular RNS variant of the B/FV encryption scheme that allow for the use of significantly larger ciphertext moduli (e.g., thousands of bits) without increased overhead due to excessive numbers of RNS components or computational overhead, as well as computational optimizations. This allows for the use of larger ciphertext moduli, which leads to a higher multiplicative depth with the same computational overhead. Our experiments show that our optimizations yield runtime improvements of up to 4.48 for decryption and 14.68 for homomorphic multiplication for large ciphertext moduli.

For primes \(p \equiv 3 \bmod 4\), we show that setting up CSIDH on the surface, i.e., using supersingular elliptic curves with endomorphism ring \(Z[(1 + \sqrt{-p})/2]\), amounts to just a few sign switches in the underlying arithmetic. If \(p \equiv 7 \bmod 8\) then the availability of very efficient horizontal 2-isogenies allows for a noticeable speed-up, e.g., our resulting CSURF-512 protocol runs about 5.68% faster than CSIDH-512. This improvement is completely orthogonal to all previous speed-ups, constant-time measures and construction of cryptographic primitives that have appeared in the literature so far. At the same time, moving to the surface gets rid of the redundant factor \(Z_3\) of the acting ideal-class group, which is present in the case of CSIDH and offers no extra security.

We propose FO-AKE a generic construction of two-message authenticated key exchange (AKE) from any passively secure public key encryption (PKE) in the quantum random oracle model (QROM). Whereas previous AKE constructions relied on a Diffie-Hellman key exchange or required the underlying PKE scheme to be perfectly correct, our transformation allows arbitrary PKE schemes with non-perfect correctness. Furthermore, we avoid the use of (quantum-secure) digital signature schemes which are considerably less efficient than their PKE counterparts. As a consequence, we can instantiate our AKE transformation with any of the submissions to the recent NIST post-quantum competition, e.g., ones based on codes and lattices. FO-AKE can be seen as a generalization of the well known Fujisaki-Okamoto transformation (for building actively secure PKE from passively secure PKE) to the AKE setting. Therefore, as a helper result, we also provide a security proof for the Fujisaki-Okamoto transformation in the QROM for PKE with non-perfect correctness. Our reduction fixes several gaps in a previous proof (CRYPTO 2018), is tighter, and tolerates a larger correctness error.

Let $A/\overline{\mathbb{F}}_p$ and $A'/\overline{\mathbb{F}}_p$ be supersingular principally polarized abelian varieties of dimension $g>1$. For any prime $\ell \ne p$, we give an algorithm that finds a path $\phi : A \rightarrow A'$ in the $(\ell, \dots , \ell)$-isogeny graph in $\widetilde{O}(p^{g-1})$ group operations on a classical computer, and $\widetilde{O}(\sqrt{p^{g-1}})$ calls to the Grover oracle on a quantum computer. The idea is to find paths from $A$ and $A'$ to nodes that correspond to products of lower dimensional abelian varieties, and to recurse down in dimension until an elliptic path-finding algorithm (such as Delfs--Galbraith) can be invoked to connect the paths in dimension $g=1$. In the general case where $A$ and $A'$ are any two nodes in the graph, this algorithm presents an asymptotic improvement over all of the algorithms in the current literature. In the special case where $A$ and $A'$ are a known and relatively small number of steps away from each other (as is the case in higher dimensional analogues of SIDH), it gives an asymptotic improvement over the quantum claw finding algorithms and an asymptotic improvement over the classical van Oorschot--Wiener algorithm.

We present improved quantum circuits for elliptic curve scalar multiplication, the most costly component in Shor's algorithm to compute discrete logarithms in elliptic curve groups. We optimize low-level components such as reversible integer and modular arithmetic through windowing techniques and more adaptive placement of uncomputing steps, and improve over previous quantum circuits for modular inversion by reformulating the binary Euclidean algorithm. Overall, we obtain an affine Weierstrass point addition circuit that has lower depth and uses fewer T gates than previous circuits. While previous work mostly focuses on minimizing the total number of qubits, we present various trade-offs between different cost metrics including the number of qubits, circuit depth and T-gate count. Finally, we provide a full implementation of point addition in the Q# quantum programming language that allows unit tests and automatic quantum resource estimation for all components.

We consider a key encapsulation mechanism (KEM) based on ring-LWE where reconciliation is performed on an $N$-dimensional lattice using Wyner-Ziv coding. More precisely, we consider Barnes-Wall lattices and use Micciancio and Nicolosi's bounded distance decoder with polynomial complexity $\mathcal{O}(N \log^2(N))$. We show that in the asymptotic regime for large $N$, the achievable key rate is $\Theta(\log N)$ bits per dimension, while the error probability $P_e$ vanishes exponentially in $N$. Unlike previous works, our scheme does not require a dither.

Given the current research status in lattice-based cryptography, it is commonly suggested that lattice-based signature could be subtler and harder to achieve. Among them, Dilithium is one of the most promising signature candidates for the post-quantum era, for its simplicity, efficiency, small public key size, and resistance against side channel attacks. The design of Dilithium is based on a list of pioneering works (e.g.,[VL09,VL12,BG14]), and has very remarkable performance by very careful and comprehensive optimizations in implementation and parameter selection. Whether better trade-offs on the already remarkable performance of Dilithium can be made is left in \cite{CRYSTALS} as an interesting open question. In this work, we provide new insights in interpreting the design of Dilithium, in terms of key consensus previously proposed in the literature for key encapsulation mechanisms (KEM) and key exchange (KEX). Based on the deterministic version of the optimal key consensus with noise (OKCN) mechanism, originally developed in [JZ16] for KEM/KEX, we present \emph{signature from key consensus with noise} (SKCN), which could be viewed as generalization and optimization of Dilithium. The construction of SKCN is generic, modular and flexible, which in particular allows a much broader range of parameters for searching better tradeoffs among security, computational efficiency, and bandwidth. For example, on the recommended parameters, compared with Dilithium our SKCN scheme is more efficient both in computation and in bandwidth, while preserving the same level of post-quantum security. In addition, using the same routine of OKCN for both KEM/KEX and digital signature eases (hardware) implementation and deployment in practice, and is useful to simplify the system complexity of lattice-based cryptography in general.

LAC is a Ring Learning With Error based cryptosystem that has been proposed to the NIST call for post-quantum standardization and passed the first round of the submission process. The particularity of LAC is to use an error-correction code ensuring a high security level with small key sizes and small ciphertext sizes. LAC team proposes a CPA secure cryptosystem, LAC.CPA, and a CCA secure one, LAC.CCA, obtained by applying the Fujisaki-Okamoto transformation on LAC.CPA. In this paper, we study the security of LAC Key Exchange (KE) mechanism, using LAC.CPA, in a misuse context: when the same secret key is reused for several key exchanges and an active adversary has access to a mismatch oracle. This oracle indicates information on the possible mismatch at the end of the KE protocol. In this context, we show that an attacker needs at most $8$ queries to the oracle to retrieve one coefficient of a static secret key. This result has been experimentally confirmed using the reference and optimized implementations of LAC. Since our attack can break the CPA version in a misuse context, the Authenticated KE protocol, based on the CCA version, is not impacted. However, this research provides a tight estimation of LAC resilience against this type of attacks.

Horizontal attacks are a suitable tool to evaluate the (nearly) worst-case side-channel security level of ECC implementations, due to the fact that they allow extracting a large amount of information from physical observations. Motivated by the difficulty of mounting such attacks and inspired by evaluation strategies for the security of symmetric cryptography implementations, we derive shortcut formulas to estimate the success rate of horizontal differential power analysis attacks against ECSM implementations, for efficient side-channel security evaluations. We then discuss the additional leakage assumptions that we exploit for this purpose, and provide experimental confirmation that the proposed tools lead to good predictions of the attacks' success.

Aigis-Enc is an encryption algorithm based on asymmetrical LWE. In this algorithm, the compression process is utilized during both key generation and encryption (which is equivalent to add some LWR noise). Then encapsulation is realized by FO transformation. It is well known that FO transformation is not considered for discussing CPA security. On the other hand, since the security reduction of LWR is hard to proceed, it is not considered for discussing the CPA security of Aigis-Enc. But compression must be put into consideration when we discuss decryption failure probability. In other words, when we discuss the CPA security of Aigis-Enc, the compression and FO transformation are ignored. But when decryption failure probability is discussed, compression should be taken into consideration while FO transformation remains ignored. According to the assumptions above, Aigis-Enc designers claim that the CPA security of Aigis-Enc is approximately equal to that of the symmetrical LWE scheme in the same scale, and the decryption failure probability of Aigis-Enc is far below that of the symmetrical LWE scheme in the same scale. In this paper, we make a thorough comparison between Aigis-Enc (with the recommended parameters) and the symmetrical LWE encryption scheme in the same scale. Our conclusion is as followed: (1) The comparison on CPA security. The former’s is 160.898, and the latter’s is 161.836. (2) The comparison on computation complexity. In key generation phase, the ratio of the former and the latter on sampling amount of distribution \(\left[ {\begin{array}{*{20}{c}} 0&1\\ {\frac{1}{2}}&{\frac{1}{2}} \end{array}} \right]\) is 5:4; In encryption phase, that ratio is 19:14. The other computations remain the same. (3) The comparison on decryption failure probability. The former’s is $2^{-128.699}$, the latter's is $2^{-67.0582}$. The comparison seems to be dramatic. But in fact, we can slightly increase some traffic to keep failure probability unchanged. In other words, by compressing less to keep decryption failure probability unchanged. In specific: we change the parameters \(\left( {{d_1},{d_2},{d_3}} \right)\) from \(\left( {9,9,4} \right)\) to \(\left( {10,10,4} \right)\), which means a large part of the public key remains the same, the small part of the public key changes from 9 bits per entry into 10bits. A large part of the ciphertext changes from 9 bits per entry into 10 bits, the small part of the ciphertext remains the same. As thus, the communication traffic increases less than $\frac{1}{9}$, while the decryption failure probability is lower than $2^{-128.699}$. We generalize those attacks presented by designers of Aigis-Enc, including primal attacks and dual attacks. More detailedly, our attacks are more extensive, simpler, and clearer. With them, we obtain the optimal attacks and “the optimal-optimal attack” on Aigis-Enc and the symmetrical LWE scheme in the same scale.

The Supersingular Isogeny-based Diffie-Hellman key exchange protocol (SIDH) was introduced by Jao an De Feo in 2011. SIDH operates on supersingular elliptic curves defined over quadratic extension fields of the form GF($p^2$), where $p$ is a large prime number of the form $p = 4^{e_A} 3^{e_B} - 1,$ where $e_A, e_B$ are positive integers such that $4^{e_A} \approx 3^{e_B}.$ In this paper, a variant of the SIDH protocol that we dubbed extended SIDH (eSIDH) is presented. The eSIDH variant makes use of primes of the form, $p = 4^{e_A} \ell_B^{e_B}\ell_C^{e_C} f - 1.$ Here $\ell_B, \ell_C $ are two small prime numbers; $f$ is a cofactor; and $e_A, e_B$ and $e_C$ are positive integers such that $4^{e_A} \approx \ell_B^{e_B}\ell_C^{e_C}.$ We show that for many relevant instantiations of the SIDH protocol, this new family of primes enjoys a faster field arithmetic than the one associated to traditional SIDH primes. Furthermore, the proposed eSIDH protocol preserves the length and format of SIDH private/public keys, and its richer opportunities for parallelism yields a noticeable speedup factor when implemented on multi-core platforms. Using a single-core SIDH $p_{751}$ implementation as a baseline, a parallel eSIDH $p_{765}$ instantiation yields an acceleration factor of $1.05, 1.30$ and $1.41,$ when implemented on $k = \{1, 2, 3\}$-core processors. In addition, eSIDH $p_{765}$ yields an acceleration factor of $1.050, 1.160$ and $1.162.$ when both protocols are implemented on $k = \{1, 2, 3\}$-core processors. To our knowledge, this work reports the first multi-core implementation of SIDH.

In this paper, we propose a novel lattice-based group key exchange protocol with dynamic membership. Our protocol is constructed by generalizing Dutta-Barua protocol to RLWE setting, inspired by Apon et al.’s recent paper in PQCrypto 2019. We describe our (static) group key exchange protocol from Apon et al.’s paper by modifying its third round and computation step. Then, we present both authenticated and dynamic group key exchange protocol with Join and Leave algorithms. The number of rounds for authenticated group key exchange remains the same as unauthenticated one. Our protocol also supports the scalable property so that the number of rounds does not change depending on the number of group participants. By assuming the hardness of RLWE assumption and unforgeability of digital signatures, we give a full security proof for (un-)authenticated (dynamic) group key exchange protocols.

We present a reduction from the module learning with errors problem (MLWE) in dimension \(d\) and with modulus \(q\) to the ring learning with errors problem (RLWE) with modulus \(q^{d}\). Our reduction increases the LWE error rate \(\alpha\) by a factor of \( n^{c+1/2} \cdot \sqrt{d} \) for ring dimension \(n\), module rank \(d\) and any constant \(c>0\) in the case of power-of-two cyclotomics. Since, on the other hand, MLWE is at least as hard as RLWE, we conclude that the two problems are polynomial-time equivalent. As a corollary, we obtain that the RLWE instance described above is equivalent to solving lattice problems on module lattices. We also present a self reduction for power-of-two cyclotomic RLWE that reduces the ring dimension \(n\) by a power-of-two factor \(2^i\), while increasing the modulus by a power of \(2^i\) and the error rate by a factor of \( 2^{i\cdot (1-c)} \cdot n^{c+1/2} \) for any constant \(c>0\). Our results suggest that when discussing hardness to drop the RLWE/MLWE distinction in favour of distinguishing problems by the module rank required to solve them.

NewHope Key Encapsulation Mechanism (KEM) has been presented at USENIX 2016 by Alchim et al. and is one of the remaining lattice-based candidates to the post-quantum standardization initiated by the NIST. However, despite the relative simplicity of the protocol, the bound on the decapsulation failure probability resulting from the original analysis is not tight. In this work we refine this analysis to get a tight upper-bound on this probability which happens to be much lower than what was originally evaluated. As a consequence we propose a set of alternnative parameters, increasing the security and the compactness of the scheme. However using a smaller modulus prevent the use of a full NTT algorithm to perform multiplications of elements in dimension 512 or 1024. Nonetheless, similarly to previous works, we combine different multiplication algorithms and show that our new parameters are competitive on a constant time vectorized implementation. Our most compact parameters bring a speed- up of 17% (resp. 11%) in performance but allow to gain more than 19% over the bandwidth requirements and to increase the security of 10% (resp. 7%) in dimension 512 (resp. 1024).

In order to obtain an efficient elliptic curve with 128-bit security and a prime order, we explore the use of finite fields $GF(p^n)$, with $p$ a small modulus (less than $2^{16}$) and $n$ a prime. Such finite fields allow for an efficient inversion algorithm due to Itoh and Tsujii, which we can leverage to make computations on an ordinary curve (short Weierstraß equation) in affine coordinates. We describe a very efficient variant of Montgomery reduction for computations modulo $p$, and choose $p = 9767$ and $n = 19$ to better map the abilities of small microcontrollers of the ARM Cortex-M0+ class. Inversion cost is only six times the cost of multiplication. Our fully constant-time implementation of curve point multiplication runs in about 4.5 million cycles (only 1.29 times slower than the best reported Curve25519 implementations); it also allows for efficient key pair generation (about 1.9 million cycles) and Schnorr signature verification (about 5.6 million cycles). Moreover, we describe variants of the Itoh-Tsujii algorithms that allow fast computations of square roots and cube roots (in less than twenty times the cost of a multiplication), leading to efficient point compression and constant-time hash-to-curve operations with Icart's map.

The GPV construction [GPV08] presents a generic construction of signature schemes in the Hash and Sign paradigm. This construction requires a family F of trapdoor preimage sampleable functions (TPSF). In this work we extend this notion to the weaker Average TPSF (ATPSF) and show that the GPV construction also holds for ATPSF in the Random Oracle Model. We also introduce the problem of finding a Claw with a random function (Claw(RF)) and present a tight security reduction to the Claw(RF) problem. Our reduction is also optimal meaning that an algorithm that solves the Claw(RF) problem breaks the scheme. We extend these results to the quantum setting and prove this same tight and optimal reduction in the QROM. Finally, we apply these results to code-based signatures, notably the Wave signature scheme and prove tight and optimal reductions for it in the ROM and the QROM improving and extending the original analysis of [DST19a]

Constructing an elliptic curve of prime order has a significant role in elliptic curve cryptography. For security purposes, we need an elliptic curve of almost prime order. In this paper, we propose an efficient technique to generate an elliptic curve of nearly prime order. In practice, this algorithm produces an elliptic curve of order 2 times a prime number. Therefore, these elliptic curves are appropriate for practical uses. Presently, the most known working algorithms for generating elliptic curves of prime order are based on complex multiplication. The advantages of the proposed technique are: it does not require a deep mathe- matical theory, it is easy to implement in any programming language and produces an elliptic curve with a remarkably simple expression.

Recently, Srinath and Chandrasekaran have proposed an undeniable blind signature scheme (UBSS) from supersingular isogeny to provide signer’s control in a quantum-resistant blind signature. However, certain weaknesses of undeniable signature have already been observed and have been overcome by formalizing the designated verifier signature (DVS). In this paper, we explore the possibility of generic construction of a DVS from hard homogeneous spaces. Further, following this motivation, we realize a quantum-resistant designated verifier blind signature (DVBS) scheme based on supersingular isogenies from the proposed generic construction. In contrast to the UBSS, our construction do not require interactive communication between the signer and the verifier, yet engages the signer in the verification. The compact signature adds more security properties in a quantum-resistant blind signature to be useful in specific applications including electronic tendering, online auctions etc.

Fine-grained cryptographic primitives are secure against adversaries with bounded resources and can be computed by honest users with less resources than the adversaries. In this paper, we revisit the results by Degwekar, Vaikuntanathan, and Vasudevan in Crypto 2016 on fine-grained cryptography and show constructions of three key fundamental fine-grained cryptographic primitives: one-way permutations, hash proof systems (which in turn implies a public-key encryption scheme against chosen chiphertext attacks), and trapdoor one-way functions. All of our constructions are computable in $\mathsf{NC}^1$ and secure against (non-uniform) $\mathsf{NC}^1$ circuits under the widely believed worst-case assumption $\mathsf{NC}^1 \subsetneq \oplus \mathsf{L/poly}$.

Recently, Lyubashevsky & Seiler (Eurocrypt 2018) showed that small polynomials in the cyclotomic ring $Z_q[X]/(X^n+1)$, where $n$ is a power of two, are invertible under special congruence conditions on prime modulus $q$. This result has been used to prove certain security properties of lattice-based constructions against unbounded adversaries. Unfortunately, due to the special conditions, working over the corresponding cyclotomic ring does not allow for efficient use of the Number Theoretic Transform (NTT) algorithm for fast multiplication of polynomials and hence, the schemes become less practical. In this paper, we present how to overcome this limitation by analysing zeroes in the Chinese Remainder (or NTT) representation of small polynomials. Concretely, we follow the proof techniques from Stehlé and Steinfeld (Eprint 2013/004) and provide upper bounds on the probabilities related to the (non)-existence of a short vector in a random module lattice with no assumptions on the prime modulus. Then, we apply these results, along with the generic framework by Kiltz et al. (Eurocrypt 2018), to a number of lattice-based Fiat-Shamir signatures so they can both enjoy tight security in the quantum random oracle model and support fast multiplication algorithms (at the cost of slightly larger public keys and signatures), such as the Bai-Galbraith signature scheme (CT-RSA 2014), Dilithium-QROM (Kiltz et al., Eurocrypt 2018) and qTESLA (Alkim et al., PQCrypto 2017). These techniques can also be applied to prove that recent commitment schemes by Baum et al. (SCN 2018) are statistically binding with no additional assumptions on $q$.

The existence of secure indistinguishability obfuscators ($i\mathcal{O}$) has far-reaching implications, significantly expanding the scope of problems amenable to cryptographic study. A recent line of work [Ananth, Jain, and Sahai, 2018; Aggrawal, 2018; Lin and Matt, 2018; Jain, Lin, Matt, and Sahai, 2019] has developed a new theory for building $i\mathcal{O}$~from simpler building blocks, and represents the state of the art in constructing $i\mathcal{O}$~from succinct and instance-independent assumptions. This line of work has culminated in a construction of $i\mathcal{O}$~from four assumptions, consisting of two standard assumptions, namely sub-exponentially secure LWE and SXDH over bilinear groups, and two other pseudorandomness assumptions: The first assumes weak pseudorandomness properties of generators computable by constant-degree polynomials over the integers, as well as an LWE leakage assumption, introduced by [Jain, Lin, Matt, and Sahai, 2019]. The second assumes the existence of Boolean PRGs with constant block locality [Goldreich 2000, Lin and Tessaro 2017]. In this work, we make the following contributions: \begin{itemize} \item We completely remove the need to assume a constant-block local PRG. This yields a construction of $i\mathcal{O}$ based on three assumptions of LWE, SXDH and a constant degree perturbation resilient generator [Jain, Lin, Matt, and Sahai, 2019] \item Our construction is arguably simpler and more direct than previous constructions. We construct the notion of special homomorphic encoding (SHE) for all $P/poly$ from LWE, by adapting techniques from Predicate Encryption [Gorbunov, Vaikunthanathan and Wee, 2015]. Prior to our work, SHE was only known for the class $\mathsf{NC}^0$, from Ring LWE [Agrawal and Rosen, 2017]. Our new SHE allows our construction of $i\mathcal{O}$ to avoid an intermediate step of bootstrapping via randomized encodings. Indeed, we construct a functional encryption scheme whose ciphertext grows sublinearly only in the output length of the circuits as opposed to its size. This is first such scheme that does not rely on multilinear maps. \item Finally, we investigate a main technical concept facilitating the line of work on $i\mathcal{O}$; namely the notion of \emph{partially hiding functional encryption} introduced by [Ananth, Jain, and Sahai 2018]. The partially hiding functional encryption used in these $i\mathcal{O}$ constructions allows an encryptor to encrypt vectors of the form $\vec{x},\vec{y},\vec{z} \in \mathbb{Z}^n_{p}$ and allows any decrptor with a key for function $f$ to learn $\langle f(\vec{x}), \vec{y}\otimes \vec{z} \rangle$. The encryption is allowed to reveal $\vec{x}$ while keeping $\vec{y},\vec{z}$ hidden. Furthermore, the size of the cipher-text should grow linearly in $n$. We significantly improve the starte of the art for partially hiding functional encryption: Assuming SXDH over bilinear maps, we construct a partially hiding FE scheme where the function $f$ is allowed to be any polynomial sized arithmetic branching program. Prior to our work, the best partially hiding FE only supported the class of constant degree polynomials over $\mathbb{Z}_{p}$ [Jain, Lin, Matt, and Sahai 2019]. \end{itemize}

Vélu's formulas for computing isogenies over Weierstrass model of elliptic curves has been extended to other models of elliptic curves such as the Huff model, the Edwards model and the Jacobi model of elliptic curves. This work continues this line of research by providing efficient formulas for computing isogenies over elliptic curves of Hessian form. We provide explicit formulas for computing isogenies of degree 3 and isogenies of degree l not divisible by 3. The theoretical cost of computing these maps in this case is slightly faster than the case with other curves. We also extend the formulas to obtain isogenies over twisted and generalized Hessian forms of elliptic curves. The formulas in this work have been verified with the Sage software and are faster than previous results on the same curve.

We present an advanced encoding framework for predicate encryption (PE) in prime order groups. Our framework captures a wider range of adaptively secure PE schemes such as non-monotonic attribute-based encryption by allowing PE schemes to have more flexible structures. Prior to our work, frameworks featuring adaptively secure PE schemes in prime order groups require strong structural restrictions on the schemes. In those frameworks, exponents of public keys and master secret keys of PE schemes, which are also referred to as common variables, must be linear. In our work, we introduce a modular framework which includes non-linear common variables in PE schemes. First, we formalize non-linear structures which can appear in PE by improving Attrapadung's pair encoding framework (Eurocrypt'14). Then, we provide a generic compiler that features encodings under our framework to PE schemes in prime order groups. Particularly, the security of our compiler is proved by introducing a new technique which decomposes common variables into two types and makes one of them be shared between semi-functional and normal spaces on processes of the dual system encryption to mitigate the linear restriction. As instances of our new framework, we introduce new attribute-based encryption schemes supporting non-monotonic access structures, namely non-monotonic ABE, in prime order groups. We introduce adaptively secure non-monotonic ABE schemes having either short ciphertexts (if KP-ABE) or short keys (if CP-ABE) for the first time. Additionally, we introduce the first non-monotonic ABE schemes supporting both adaptive security and multi-use of attributes property in prime order groups.

Encryption is an indispensable tool for securing digital infra- structures as it reduces the problem of protecting the data to just protecting decryption keys. Unfortunately, this also makes it easier for users to share protected data by simply sharing decryption keys. Kiayias and Tang (ACM CCS 2013) were the first to address this important issue pre-emptively rather than a posteriori like traitor tracing schemes do. They proposed leakage-deterring encryption schemes that work as follows. For each user, a piece of secret information valuable to her is embedded into her public key. As long as she does not share her ability to decrypt with someone else, her secret is safe. As soon as she does, her secret is revealed to her beneficiaries. However, their solution suffers from serious drawbacks: (1) their model requires a fully-trusted registration authority that is privy to user secrets; (2) it only captures a CPA-type of privacy for user secrets, which is a very weak guarantee; (3) in their construction which turns any public-key encryption scheme into a leakage-deterring one, the new public keys consist of linearly (in the bit-size of the secrets) many public keys of the original scheme, and the ciphertexts are large. In this paper, we redefine leakage-deterring schemes. We remove the trust in the authority and guarantee full protection of user secrets under CCA attacks. Furthermore, in our construction, all keys and ciphertexts are short and constant in the size of the secrets. We achieve this by taking a different approach: we require users to periodically refresh their secret keys by running a protocol with a third party. Users do so anonymously, which ensures that they cannot be linked, and that the third party cannot perform selective failure attacks. We then leverage this refresh protocol to allow for the retrieval of user secrets in case they share their decryption capabilities. This refresh protocol also allows for the revocation of user keys and for the protection of user secrets in case of loss or theft of a decryption device. We provide security definitions for our new model as well as efficient instantiations that we prove secure.

Learning with Errors (LWE) and Ring-LWE (RLWE) problems allow the construction of efficient key exchange and public-key encryption schemes. However, while improving the security through the use of error distributions with large standard deviations, the decryption failure rate increases as well. Currently, the independence of individual coefficient failures is assumed to estimate the overall decryption failure rate of many LWE/RLWE schemes. However, previous work has shown that this assumption is not correct. This assumption leads to wrong estimates of the decryption failure probability and consequently of the security level of the LWE/RLWE cryptosystem. An exploration of the influence of the LWE/RLWE parameters on the stochastic dependence among the coefficients is still missing. In this paper, we propose a method to analyze the stochastic dependence between decryption failures in LWE/RLWE cryptosystems. We present two main contributions. First, we use statistical methods to analyze the influence of fixing the norm of the error distribution on the stochastic dependence among decryption failures. The results have shown that fixing the norm of the error distribution indeed reduces the stochastic dependence of decryption failures. Therefore, the independence assumption gives a very close approximation to the true behavior of the cryptosystem. Second, we analyze and explore the influence of the LWE/RLWE parameters on the stochastic dependence. This exploration gives designers of LWE/RLWE based schemes the opportunity to compare different schemes with respect to the inaccuracy made by using the independence assumption. This work shows that the stochastic dependence depends on three LWE/RLWE parameters in different ways: i) it increases with higher lattice dimensions ($n$) and higher standard deviations of the error distribution ($\sqrt{k/2}$); and ii) it decreases with higher modulus ($q$).

A trapdoor over NTRU lattice proposed by Ducas, Lyubashevsky and Prest~(ASIACRYPT 2014) has been widely used in various crytographic primitives such as identity-based encryption~(IBE) and digital signature, due to its high efficiency compared to previous lattice trapdoors. However, the most of applications use this trapdoor with the power-of-two cyclotomic rings, and hence to obtain higher security level one should double the ring dimension which results in a huge loss of efficiency. In this paper, we give a new way to overcome this problem by introducing a generalized notion of NTRU lattices which we call \emph{Module-NTRU}~(MNTRU) lattices, and show how to efficiently generate a trapdoor over MNTRU lattices. Moreover, beyond giving parameter flexibility, we further show that the Gram-Schmidt norm of the trapdoor can be reached to about $q^{1/d},$ where MNTRU covers $d \ge 2$ cases while including NTRU as $d = 2$ case. Since the efficiency of trapdoor-based IBE is closely related to the Gram-Schmidt norm of trapdoor, our trapdoor over MNTRU lattice brings more efficient IBE scheme than the previously best one of Ducas, Lyubashevsky and Prest, while providing the same security level.

We propose an instantiation of public key encryption scheme based on the ring learning with error problem, where the modulus is at a byte level and the noise is at a bit level, achieving one of the most compact lattice based schemes in the literature. The main technical challenges are a) the decryption error rates increases and needs to be handled elegantly, and b) we cannot use the Number Theoretic Transform (NTT) technique to speed up the implementation. We overcome those limitations with some customized parameter sets and heavy error correction codes. We give a treatment of the concrete security of the proposed parameter set, with regards to the recent advance in lattice based cryptanalysis. We present an optimized implementation taking advantage of our byte level modulus and bit level noise. In addition, a byte level modulus allows for high parallelization and the bit level noise avoids the modulus reduction during multiplication. Our result shows that \LAC~is more compact than most of the existing (Ring-)LWE based solutions, while achieving a similar level of efficiency, compared with popular solutions in this domain, such as Kyber.

In 2018, Shi et al. 's showed that Kaushik et al.'s quantum signature scheme is defective. It suffers from the forgery attack. They further proposed an improvement, trying to avoid the attack. However, after examining we found their improved quantum signature is deniable, because the verifier can impersonate the signer to sign a message. After that, when a dispute occurs, he can argue that the signature was not signed by him. It was from the signer. To overcome the drawback, in this paper, we raise an improvement to make it publicly verifiable and hence more suitable to be applied in real life. After cryptanalysis, we confirm that our improvement not only resist the forgery attack but also is undeniable.

In this paper, we extend the notion of server-aided revocable identity-based encryption (SR-IBE) to the hierarchical IBE (HIBE) setting and propose a generic construction of server-aided revocable hierarchical IBE (SR-HIBE) schemes with decryption key exposure resistance (DKER) from any (weak) L-level revocable HIBE scheme without DKER and (L+1)-level HIBE scheme. In order to realize the server-aided revocation mechanism, we use the “double encryption” technique, and this makes our construction has short ciphertext size. Furthermore, when the maximum hierarchical depth is one, we obtain a generic construction of SR-IBE schemes with DKER from any IBE scheme and two-level HIBE scheme.

Revocable identity-based encryption (RIBE) is an extension of IBE which can support a key revocation mechanism, and it is important when deploying an IBE system in practice. Boneh and Franklin (Crypto'01) presented the first generic construction of RIBE, however, their scheme is not scalable where the size of key updates is linear in the number of users in the system. The first generic construction of RIBE is presented by Ma and Lin with complete subtree (CS) method by combining IBE and hierarchical IBE (HIBE) schemes. Recently, Lee proposed a new generic construction using the subset difference (SD) method by combining IBE,identity-based revocation (IBR), and two-level HIBE schemes. In this paper, we present a new primitive called Identity-Based Encryption with Ciphertext Delegation (CIBE) and propose a generic construction of RIBE scheme via subset difference method using CIBE and HIBE as building blocks. CIBE is a special type of Wildcarded IBE (WIBE) and Identity-Based Broadcast Encryption (IBBE). Furthermore, we show that CIBE can be constructed from IBE in a black-box way. Instantiating the underlying building blocks with different concrete schemes, we can obtain a RIBE scheme with constant-size public parameter, ciphertext, private key and $O(r)$ key updates in the selective-ID model. Additionally, our generic RIBE scheme can be easily converted to a sever-aided RIBE scheme which is more suitable for lightweight devices.

In a series of recent articles (from 2011 to 2017), Schindler et al. show that exponent/scalar blinding is not as effective a countermeasure as expected against side-channel attacks targeting RSA modular exponentiation and ECC scalar multiplication. Precisely, these works demonstrate that if an attacker is able to retrieve many randomizations of the same secret, this secret can be fully recovered even when a significative proportion of the blinded secret bits are erroneous. With a focus on ECC, this paper improves the best results of Schindler et al. in the specific case of structured-order elliptic curves. Our results show that larger blinding material and higher error rates can be successfully handled by an attacker in practice. This study also opens new directions in this line of work by the proposal of a three-steps attack process that isolates the attack critical path (in terms of complexity and success rate) and hence eases the development of future solutions.

Characterizing the decoding failure rate of iteratively decoded Low- and Moderate-Density Parity Check (LDPC/MDPC) codes is paramount to build cryptosystems based on them, able to achieve indistinguishability under adaptive chosen ciphertext attacks. In this paper, we provide a statistical worst-case analysis of our proposed iterative decoder obtained through a simple modification of the classic in-place bit-flipping decoder. This worst case analysis allows both to derive the worst-case behavior of an LDPC/MDPC code picked among the family with the same length, rate and number of parity checks, and a code-specific bound on the decoding failure rate. The former result allows us to build a code-based cryptosystem enjoying the $\delta$-correctness property required by IND-CCA2 constructions, while the latter result allows us to discard code instances which may have a decoding failure rate significantly different from the average one (i.e., representing weak keys), should they be picked during the key generation procedure.

Proxy re-encryption(PRE) is a primitive that is used to facilitate secure access delegation in the cloud. Proxy re-encryption allows a proxy server to transform ciphertexts encrypted under one user's public key to that under another user's public key without learning anything about the underlying message or the secret key. Over the years proxy re-encryption schemes have been proposed in different settings. In this paper we restrict our analysis to certificate based proxy re-encryption. The first CCA secure certificate based PRE without bilinear pairings was proposed by Lu and Li in Future Generation Computer Systems, 2016. In this paper we present a concrete attack on their scheme and prove that it is not CCA secure.

McEliece-like code-based key exchange mechanisms using QC-MDPC codes can reach IND-CPA security under hardness assumptions from coding theory, namely quasi-cyclic syndrome decoding and quasi-cyclic codeword finding. To reach higher security requirements, like IND-CCA security, it is necessary in addition to prove that the decoding failure rate (DFR) is negligible, for some decoding algorithm and a proper choice of parameters. Getting a formal proof of a low DFR is a difficult task. Instead, we propose to ensure this low DFR under some additional security assumption on the decoder. This assumption relates to the asymptotic behavior of the decoder and is supported by several other works. We define a new decoder, Backflip, which features a low DFR. We evaluate the Backflip decoder by simulation and extrapolate its DFR under the decoder security assumption. We also measure the accuracy of our simulation data, in the form of confidence intervals, using standard techniques from communication systems.

QC-MDPC code-based KEMs rely on decoders that have a small or even negligible Decoding Failure Rate (DFR). These decoders should be efficient and implementable in constant-time. One example for a QC-MDPC KEM is the Round-2 candidate of the NIST PQC standardization project, "BIKE". We have recently shown that the Black-Gray decoder achieves the required properties. In this paper, we deffine several new variants of the Black-Gray decoder. One of them, called Black-Gray-Flip, needs only 7 steps to achieve a smaller DFR than Black-Gray with 9 steps, for the same block size. On current AVX512 platforms, our BIKE-1 (Level-1) constant-time decapsulation is 1:9x faster than the previous decapsulation with Black-Gray. We also report an additional 1:25x decapsulating speedup using the new AVX512-VBMI2 and vector-PCLMULQDQ instructions available on "Ice-Lake" micro-architecture.

Certificateless signature was proposed by Al-Riyami and Paterson to eliminate the certificate management in the public-key infrastructures and solve the key escrow problem in the identity-based signature. In 2007, Hu et al. proposed a generic construction of certificateless signature. They construct certificateless signature scheme from any standard identity-based signature and signature scheme.However, their security reduction is loose; the security of the constructed scheme depends on the number of users. In this paper, we give the tight reduction for their construction and instantiate a tightly-secure certificateless signature scheme without pairing from DDH assumption. Best of our knowledge, this scheme is the first tightly-secure certificateless signature scheme.

Finding an isogenous supersingular elliptic curve of a prescribed odd degree is an important building block for all the isogeny-based protocols proposed to date. In this note we present several strategies for the efficient construction of odd degree isogenies, which outperform previously reported methods when dealing with isogeny degrees in the range $[7, 2^{20}].$

In this paper, we present an efficient method to compute arbitrary odd-degree isogenies on Edwards curves. By using the $w$-coordinate, we optimized the isogeny formula on Edwards curves by Moody and Shumow. We demonstrate that Edwards curves have an additional benefit when recovering the coefficient of the image curve during isogeny computation. For $\ell$-degree isogeny where $\ell=2s+1$, our isogeny formula on Edwards curves outperforms Montgomery curves when $s \geq 2$. To better represent the performance improvements when $w$-coordinate is used, we implement CSIDH using our isogeny formula. Our implementation is about 20\% faster than the previous implementation. The result of our work opens the door for the usage of Edwards curves in isogeny-based cryptography, especially for CSIDH which requires higher degree isogenies.

After Cheon et al. (Asiacrypt' 17) proposed an approximate homomorphic encryption scheme, Heaan, for operations between encrypted real (or complex) numbers, the scheme is widely used in a variety of fields with needs on privacy-preserving in data analysis. After that, a bootstrapping method for Heaan is proposed by Cheon et al. (Eurocrypt' 18) with modulus reduction being replaced by a sine function. In this paper, we generalize the Full-RNS variant of Heaan proposed by Cheon et al. (SAC, 19) to reduce the number of temporary moduli used in key-switching. As a result, our scheme can support more depth computations without bootstrapping while ensuring the same level of security. We also propose a new polynomial approximation method to evaluate a sine function in an encrypted state, which is specialized for the bootstrapping for Heaan. Our method considers a ratio between the size of a plaintext and the size of a ciphertext modulus. Consequently, it requires a smaller number of non-scalar multiplications, which is about half of the Chebyshev method. With our variant of the Full-RNS scheme and a new sine evaluation method, we firstly implement bootstrapping for a Full-RNS variant of approximate homomorphic encryption scheme. Our method enables bootstrapping for a plaintext in the space $\mathbb{C}^{16384}$ to be completed in 52 seconds while preserving 11 bit precision of each slot.

A new multivariate cryptosystem based on a linear code was proposed by Smith-Tone and Tone quite recently. This short note points out that it is a variant of UOV.

Code-based public key cryptosystems have been found to be an interesting option in the area of Post-Quantum Cryptography. In this work, we present a key encapsulation mechanism (KEM) using a parity check matrix of the Generalized Srivastava code as the public key matrix. Generalized Srivastava codes are privileged with the decoding technique of Alternant codes as they belong to the family of Alternant codes. We exploit the dyadic structure of the parity check matrix to reduce the storage of the public key. Our encapsulation leads to a shorter ciphertext as compared to DAGS proposed by Banegas et al. in Journal of Mathematical Cryptology which also uses Generalized Srivastava code. Our KEM provides IND-CCA security in the random oracle model. Also, our scheme can be shown to achieve post-quantum security in the quantum random oracle model.

The key escrow problem is one of the main barriers to the widespread real-world use of identity-based encryption (IBE). Specifically, a key generation center (KGC), which generates secret keys for a given identity, has the power to decrypt all ciphertexts. At PKC 2009, Chow defined a notion of security against the KGC, that relies on assuming that it cannot discover the underlying identities behind ciphertexts. However, this is not a realistic assumption since, in practice, the KGC manages an identity list, and hence it can easily guess the identities corresponding to given ciphertexts. Chow later amended this issue by introducing a new entity called an identity-certifying authority (ICA) and proposed an anonymous key-issuing protocol. Essentially, this allows the users, KGC, and ICA to interactively generate secret keys without users ever having to reveal their identities to the KGC. Unfortunately, since Chow separately defined the security of IBE and that of the anonymous key-issuing protocol, his IBE definition did not provide any formal treatment when the ICA is used to authenticate the users. Effectively, all of the subsequent works following Chow lack the formal proofs needed to determine whether or not it delivers a secure solution to the key escrow problem. In this paper, based on Chow's work, we formally define an IBE scheme that resolves the key escrow problem and provide formal definitions of security against corrupted users, KGC, and ICA. Along the way, we observe that if we are allowed to assume a fully trusted ICA, as in Chow's work, then we can construct a trivial (and meaningless) IBE scheme that is secure against the KGC. Finally, we present two instantiations in our new security model: a lattice-based construction based on the Gentry--Peikert--Vaikuntanathan IBE scheme (STOC 2008) and R{ü}ckert's lattice-based blind signature scheme (ASIACRYPT 2010), and a pairing-based construction based on the Boneh--Franklin IBE scheme (CRYPTO 2001) and Boldyreva's blind signature scheme (PKC 2003).

In Proof-of-Stake (PoS) and permissioned blockchains, a committee of verifiers agrees and sign every new block of transactions. These blocks are validated, propagated, and stored by all users in the network. However, posterior corruptions pose a common threat to these designs, because the adversary can corrupt committee verifiers after they certified a block and use their signing keys to certify a different block. Designing efficient and secure digital signatures for use in PoS blockchains can substantially reduce bandwidth, storage and computing requirements from nodes, thereby enabling more efficient applications. We present Pixel, a pairing-based forward-secure multi-signature scheme optimized for use in blockchains, that achieves substantial savings in bandwidth, storage requirements, and verification effort. Pixel signatures consist of two group elements, regardless of the number of signers, can be verified using three pairings and one exponentiation, and support non-interactive aggregation of individual signatures into a multi-signature. Pixel signatures are also forward-secure and let signers evolve their keys over time, such that new keys cannot be used to sign on old blocks, protecting against posterior corruptions attacks on blockchains. We show how to integrate Pixel into any PoS blockchain. Next, we evaluate Pixel in a real-world PoS blockchain implementation, showing that it yields notable savings in storage, bandwidth, and block verification time. In particular, Pixel signatures reduce the size of blocks with 1500 transactions by 35% and reduce block verification time by 38%.

The RLWE family algorithms submitted to the NIST post-quantum cryptography standardization process have each merit in terms of security, correctness, performance, and bandwidth. However, there is no splendid algorithm in all respects. Besides, various recent studies have been published that affect security and correctness, such as side-channel attacks and error dependencies. To date, though, no algorithm has fully considered all the aspects. We propose a novel Key Encapsulation Mechanism scheme called LizarMong, which is based on RLizard. LizarMong combines the merit of each algorithm and state-of-the-art studies. As a result, it achieves up to 85% smaller bandwidth and 3.3 times faster performance compared to RLizard. Compared to the NIST's candidate algorithms with a similar security, the bandwidth is about 5-42% smaller, and the performance is about 1.2-4.1 times faster. Also, our scheme resists the known side-channel attacks.

We design a very simple private-key encryption scheme whose decryption function is a rational function. This scheme is not born naturally homomorphic. To get homomorphic properties, a nonlinear additive homomorphic operator is specifically developed. The security analysis is based on symmetry considerations and we prove some formal results under the factoring assumption. In particular, we prove IND-CPA security in the generic ring model. Even if our security proof is not complete, we think that it is convincing and that the technical tools considered in this paper are interesting by themselves. Moreover, the factoring assumption is just needed to ensure that solving nonlinear equations or finding non-null polynomials with many roots is difficult. Consequently, the ideas behind our construction could be re-used in rings satisfying these properties. As motivating perspectives, we then propose to develop a simple multiplicative operator. To achieve this, randomness is added in our construction giving hope to remove the factoring assumption in order to get a pure multivariate encryption scheme.

The security proofs for isogeny-based undeniable signature schemes have been based primarily on the assumptions that the One-Sided Modified SSCDH problem and the One-More SSCDH problem are intractable. We challenge the validity of these assumptions, showing that both the decisional and computational variants of these problems can be solved in polynomial time. We further demonstrate an attack, applicable to two undeniable signature schemes, one of which was proposed at PQCrypto 2014. The attack allows to forge signatures in $2^{4\lambda/5}$ steps on a classical computer. This is an improvement over the expected classical security of $2^{\lambda}$, where $\lambda$ denotes the chosen security parameter.

In this paper, we propose a new leakage-resilient identity-based encryption (IBE) scheme that is secure against chosen-ciphertext attacks (CCA) in the bounded memory leakage model. It is the first CCA-secure leakage-resilient IBE scheme which does not depend on $\mathtt{q}$-type assumptions. More precisely, it is secure under the external k-Linear assumption. The leakage rate 1/10 is achieved under the XDLIN assumption.

We introduce a new technique for building multivariate encryption schemes based on random linear codes. The construction is versatile, naturally admitting multiple modifications. Among these modifications is an interesting embedding modifier--- any efficiently invertible multivariate system can be embedded and used as part of the inversion process. In particular, even small scale secure multivariate signature schemes can be embedded producing reasonably efficient encryption schemes. Thus this technique offers a bridge between multivariate signatures, many of which have remained stable and functional for many years, and multivariate encryption, a historically more troubling area.

Wildcard identity-based encryption (WIBE) allows a sender to simultaneously encrypt messages to a group of users matching a certain pattern, defined as a sequence of identifiers and wildcards. We propose a novel scalable wildcarded identity-based encryption, called SWIBE, which reduces the ciphertext size to be constant. To the best of our knowledge, SWIBE is the first wildcard identity-based encryption scheme that generates a constant size ciphertext regardless of the depth of the identities with fast decryption. The proposed scheme improves the decryption time. According to our experiment results, decryption of the SWIBE scheme is 3, 10, and 650 times faster than existing WIBE, WW-IBE, and CCP-ABE schemes. The SWIBE scheme also subsumes the generalized key derivation naturally by allowing wildcards in the key delegation process. We prove CPA security of the proposed scheme and extend it to be CCA secure.

Classical NTRUEncrypt is one of the fastest known lattice-based encryption schemes. Its counterpart, NTRUSign, also has many advantages, such as moderate key sizes, high efficiency and potential of resisting attacks from quantum computers. However, like classical NTRUEncrypt, the security of NTRUSign is also heuristic. Whether we can relate the security of NTRUSign to the worst-case lattice problems like NTRUEncrypt is still an open problem. Our main contribution is that we propose a detailed construction of Collision Resistance Preimage Sampleable Functions $($CRPSF$)$ over any cyclotomic field based on NTRU. By using GPV's construction, we can give a provably secure NTRU Signature scheme $($NTRUSign$)$, which is strongly existentially unforgeable under adaptive chosen-message attacks in the $($quantum$)$ random oracle model. The security of CRPSF $($NTRUSign$)$ is reduced to the corresponding ring small integer solution problem $($Ring-SIS$)$. More precisely, the security of our scheme is based on the worst-case approximate shortest independent vectors problem $($SIVP$_\gamma$$)$ over ideal lattices. For any fixed cyclotomic field, we give a probabilistic polynomial time $($PPT$)$ key generation algorithm which shows how to extend the secret key of NTRUEncrypt to the secret key of NTRUSign. This algorithm is important for constructions of many cryptographic primitives based on NTRU, for example, CRPSF, NTRUSign, identity-based encryption and identity-based signature. We also delve back into former construction of NTRUEncrypt, give a much tighter reduction from decision dual-Ring-LWE problem (where the secret is chosen form the codifferent ideal) to decision primal-Ring-LWE problem (where the secret is chosen form the ring of integers) and give a provably secure NTRUEncrypt over any cyclotomic ring. Some useful results about $q$-ary lattices, regularity and uniformity of distribution of the public keys of NTRUEncrypt are also extended to more general algebraic fields.

Kyber is a KEM based their security on the Modular Learning with Errors problem and was selected in the second round of NIST Post-quantum standardization process. Before we put Kyber into practical application, it is very important to assess its security in hard practical conditions especially when the Fujisaki-Okamoto transformations are neglected. In this paper, we propose an efficient key mismatch attacks on Kyber, which can recover one participant's secret key if the public key is reused. We first define the oracles in which the adversary is able to launch the attacks. Then, we show that by accessing the oracle multiple times, the adversary is able to recover the coefficients in the secret key. Furthermore, we propose two strategies to reduce the queries and time in recovering the secret key. It turns out that it is actually much easier to use key mismatch attacks to break Kyber than NewHope, another NIST second round candidate, due to their different design structures. Our implementations have demonstrated the efficiency of the proposed attacks and verified our findings. Another interesting observation from the attack is that in the most powerful Kyber-1024, it is easier to recover each coefficient compared with that in Kyber-512 and Kyber-768. Specifically, for Kyber-512 on average we recover each coefficient with $2.7$ queries, while in Kyber-1024 and 768, we only need $2.4$ queries. This demonstrates further that implementations of LWE based schemes in practice is very delicate.

Proxy re-encryption (PRE) enables delegation of decryption rights by entrusting a proxy server with special information, that allows it to transform a ciphertext under one public key into a ciphertext of the same message under a different public key. It is important to note that, the proxy which performs the re-encryption learns nothing about the message encrypted under either public keys. Due to its transformation property, proxy re-encryption schemes have practical applications in distributed storage, encrypted email forwarding, Digital Rights Management (DRM) and cloud storage. From its introduction, several proxy re-encryption schemes have been proposed in the literature, and a majority of them have been realized using bilinear pairing. In Africacrypt 2010, the first PKI-based collusion resistant CCA secure PRE scheme without pairing was proposed in the random oracle model. In this paper, we point out an important weakness in the scheme. We also present the first collusion-resistant pairing-free unidirectional proxy re-encryption scheme which meets CCA security under a variant of the computational Diffie-Hellman hardness assumption in the random oracle model.

Proxy re-encryption (PRE) is a cryptographic primitive introduced by Blaze, Bleumer and Strauss to provide delegation of decryption rights. A semi-trusted proxy agent re-encrypts ciphertexts under the public key of Alice into ciphertexts under the public key of Bob, without learning anything about the underlying message. In IWSEC 2017, Kuchta et al. presented a pairing-free certificateless proxy re-encryption scheme, and claimed that their scheme is the first to provide the certificateless property without resorting to pairing. They proved their construction is CCA-secure in the random oracle model, under the Computational Diffie-Hellman assumption. In this work, we show that the recently proposed construction of Kuchta et al. is vulnerable to several attacks.

Verifiable random functions (VRFs) are essentially digital signatures with additional properties, namely verifiable uniqueness and pseudorandomness, which make VRFs a useful tool, e.g., to prevent enumeration in DNSSEC Authenticated Denial of Existence and the CONIKS key management system, or in the random committee selection of the Algorand blockchain. Most standard-model VRFs rely on admissible hash functions (AHFs) to achieve security against adaptive attacks in the standard model. Known AHF constructions are based on error-correcting codes, which yield asymptotically efficient constructions. However, previous works do not clarify how the code should be instantiated concretely in the real world. The rate and the minimal distance of the selected code have significant impact on the efficiency of the resulting cryptosystem, therefore it is unclear if and how the aforementioned constructions can be used in practice. First, we explain inherent limitations of code-based AHFs. Concretely, we show that even if we were given codes that achieve the well-known Gilbert-Varshamov or McEliece-Rodemich-Rumsey-Welch bounds, existing AHF-based constructions of VRFs can only be instantiated quite inefficiently. Then we introduce and construct computational AHFs (cAHFs). While classical AHFs are information-theoretic, and therefore work even in presence of computationally unbounded adversaries, cAHFs provide only security against computationally bounded adversaries. However, we show that cAHFs can be instantiated significantly more efficiently. Finally, we present a new VRF scheme using cAHFs and show that it is currently the most efficient verifiable random function with full adaptive security in the standard model.