The supersingular isogeny-based key encapsulation (SIKE) suite stands as an attractive post-quantum cryptosystem with its relatively small public keys. Public key sizes in SIKE can further be compressed by computing pairings and solving discrete logarithms in certain subgroups of finite fields. This comes at a cost of precomputing and storing large discrete logarithm tables. In this paper, we propose several techniques to optimize memory requirements in computing discrete logarithms in SIKE, and achive to reduce table sizes by a factor of 4. We implement our techniques and verify our theoretical findings.

Cryptographic objects with updating capabilities have been proposed by Bellare, Goldreich and Goldwasser (CRYPTO'94) under the umbrella of incremental cryptography. They have recently seen increased interest, motivated by theoretical questions (Ananth et al., EC'17) as well as concrete practical motivations (Lehmann et al., EC'18; Groth et al. CRYPTO'18; Klooss et al., EC'19). In this work, the form of updatability we are particularly interested in is that primitives are key-updatable and allow to update old cryptographic objects, e.g., signatures or message authentication codes, from the old key to the updated key at the same time without requiring full access to the new key (i.e., only via a so-called update token). Inspired by the rigorous study of updatable encryption by Lehmann and Tackmann (EC'18) and Boyd et al. (CRYPTO'20), we introduce a definitional framework for updatable signatures (USs) and message authentication codes (UMACs). We discuss several applications demonstrating that such primitives can be useful in practical applications, especially around key rotation in various domains, as well as serve as building blocks in other cryptographic schemes. We then turn to constructions and our focus there is on ones that are secure and practically efficient. In particular, we provide generic constructions from key-homomorphic primitives (signatures and PRFs) as well as direct constructions. This allows us to instantiate these primitives from various assumptions such as DDH or CDH (latter in bilinear groups), or the (R)LWE and the SIS assumptions. As an example, we obtain highly practical US schemes from BLS signatures or UMAC schemes from the Naor-Pinkas-Reingold PRF.

In this note, we conduct a cryptanalysis of the paper published by Zhu et al. on Future Generation Computer Systems in 2021. We demonstrate that their quantum-resistant identity-based proxy signcryption scheme cannot achieve the confidentiality as they claimed.

The Schnorr-Lyubashevsky approach has been shown able to produce secure and efficient signature schemes without trapdoors in the lattice-based setting, exploiting small vectors in the Euclidean metric and rejection sampling in the signature generation. Translating such an approach to the code-based setting has revealed to be challenging, especially for codes in the Hamming metric. In this paper, we propose a novel adaptation of the Schnorr-Lyubashevsky framework to the code-based setting, by relying on random non-binary linear codes and vectors with restricted entries to produce signatures. We provide some preliminary arguments to assess the security of the new scheme and to compute its parameters. We show that it achieves compact and competitive key and signature sizes, even without resorting to structured random codes.

In this paper, we improve the theoretical background of the attacks on the DSA schemes given in [1, 29], and we present some new more practical attacks.

The KEM BIKE is a Round-3 alternative finalist in the NIST Post-Quantum Cryptography project. It uses the FO$^{\not \bot}$ transformation so that an instantiation with a decoder that has a DFR of $2^{-128}$ will make it IND-CCA secure. The current BIKE design does not bind the randomness of the ciphertexts (i.e., the error vectors) to a specific public key. We propose to change this design, although currently, there is no attack that leverages this property. This modification can be considered if BIKE is eventually standardized.

The security proofs of post-quantum cryptographic schemes often consider only classical adversaries. Therefore, whether such schemes are really post-quantum secure remains unknown until the proofs take quantum adversaries into account. Switching to a quantum adversary might require to adapt the security notion. In particular, post-quantum security proofs for schemes which use random oracles have to be in the quantum random oracle model (QROM), while classical security proofs are in the random oracle model (ROM). We remedy this state of affairs by introducing a framework to obtain the post-quantum security of public key encryption schemes which use random oracles. We define a class of encryption schemes, called oracle-simple, and identify game hops which are used to prove such schemes secure in the ROM. For these game hops, we state both simple and sufficient conditions to validate that a proof also holds in the QROM. The strength of our framework lies in its simplicity, its generality, and its applicability. We demonstrate this by applying it to the code-based encryption scheme ROLLO (Round 2 NIST candidate) and the lattice-based encryption scheme LARA (FC 2019). This proves that both schemes are post-quantum secure, which had not been shown before.

Forward secrecy is considered an essential design goal of modern key establishment (KE) protocols, such as TLS 1.3, for example. Furthermore, efficiency considerations such as zero round-trip time (0-RTT), where a client is able to send cryptographically protected payload data along with the very first KE message, are motivated by the practical demand for secure low-latency communication. For a long time, it was unclear whether protocols that simultaneously achieve 0-RTT and full forward secrecy exist. Only recently, the first forward-secret 0-RTT protocol was described by Günther et al. (Eurocrypt 2017). It is based on Puncturable Encryption. Forward secrecy is achieved by "puncturing" the secret key after each decryption operation, such that a given ciphertext can only be decrypted once (cf. also Green and Miers, S&P 2015). Unfortunately, their scheme is completely impractical, since one puncturing operation takes between 30 seconds and several minutes for reasonable security and deployment parameters, such that this solution is only a first feasibility result, but not efficient enough to be deployed in practice. In this paper, we introduce a new primitive that we term Bloom Filter Encryption (BFE), which is derived from the probabilistic Bloom filter data structure. We describe different constructions of BFE schemes, and show how these yield new puncturable encryption mechanisms with extremely efficient puncturing. Most importantly, a puncturing operation only involves a small number of very efficient computations, plus the deletion of certain parts of the secret key, which outperforms previous constructions by orders of magnitude. This gives rise to the first forward-secret 0-RTT protocols that are efficient enough to be deployed in practice. We believe that BFE will find applications beyond forward-secret 0-RTT protocols.

Attribute-based encryption (ABE) is a cryptographic primitive which supports fine-grained access control on encrypted data, making it an appealing building block for many applications. Pair encodings (Attrapadung, EUROCRYPT 2014) are simple primitives that can be used for constructing fully secure ABE schemes associated to a predicate relative to the encoding. We propose a generic transformation that takes any pair encoding scheme (PES) for a predicate $P$ and produces a PES for its negated predicate $\bar{P}$ . This construction finally solves a problem that was open since 2015. Our techniques bring new insight to the expressivity and generality of PES and can be of independent interest. We also provide, to the best of our knowledge, the first pair encoding scheme for negated doubly spatial encryption (obtained with our transformation) and explore several other consequences of our results.

The paper is about algorithms for the inhomogeneous short integer solution problem: Given $(A,s)$ to find a short vector $x$ such that $Ax \equiv s \pmod{q}$. We consider algorithms for this problem due to Camion and Patarin; Wagner; Schroeppel and Shamir; Minder and Sinclair; Howgrave-Graham and Joux (HGJ); Becker, Coron and Joux (BCJ). Our main results include: Applying the Hermite normal form (HNF) to get faster algorithms; A heuristic analysis of the HGJ and BCJ algorithms in the case of density greater than one; An improved cryptanalysis of the SWIFFT hash function; A new method that exploits symmetries to speed up algorithms for Ring-SIS in some cases. This paper is published in Journal of Cryptology, Volume 32, Issue 1 (2019) 35--83.

We present passive attacks against CKKS, the homomorphic encryption scheme for arithmetic on approximate numbers presented at Asiacrypt 2017. The attack is both theoretically efficient (running in expected polynomial time) and very practical, leading to complete key recovery with high probability and very modest running times. We implemented and tested the attack against major open source homomorphic encryption libraries, including HEAAN, SEAL, HElib and PALISADE, and when computing several functions that often arise in applications of the CKKS scheme to machine learning on encrypted data, like mean and variance computations, and approximation of logistic and exponential functions using their Maclaurin series. The attack shows that the traditional formulation of IND-CPA security (or indistinguishability against chosen plaintext attacks) achieved by CKKS does not adequately capture security against passive adversaries when applied to approximate encryption schemes, and that a different, stronger definition is required to evaluate the security of such schemes. We provide a solid theoretical basis for the security evaluation of homomorphic encryption on approximate numbers (against passive attacks) by proposing new definitions, that naturally extend the traditional notion of INDCPA security to the approximate computation setting. We propose both indistinguishability-based and simulation-based variants, as well as restricted versions of the definitions that limit the order and number of adversarial queries (as may be enforced by some applications). We prove implications and separations among different definitional variants, and discuss possible modifications to CKKS that may serve as a countermeasure to our attacks.

Lattice-based algorithms in cryptanalysis often search for a target vector satisfying integer linear constraints as a shortest or closest vector in some lattice. In this work, we observe that these formulations may discard non-linear information from the underlying application that can be used to distinguish the target vector even when it is far from being uniquely close or short. We formalize lattice problems augmented with a predicate distinguishing a target vector and give algorithms for solving instances of these problems. We apply our techniques to lattice-based approaches for solving the Hidden Number Problem, a popular technique for recovering secret DSA or ECDSA keys in side-channel attacks, and demonstrate that our algorithms succeed in recovering the signing key for instances that were previously believed to be unsolvable using lattice approaches. We carried out extensive experiments using our estimation and solving framework, which we also make available with this work.

Supersingular isogeny Diffie-Hellman key exchange (SIDH) is a post-quantum protocol based on the presumed hardness of computing an isogeny between two supersingular elliptic curves given some additional torsion point information. Unlike other isogeny-based protocols, SIDH has been widely believed to be immune to subexponential quantum attacks because of the non-commutative structure of the endomorphism rings of supersingular curves. We contradict this commonly believed misconception in this paper. More precisely, we highlight the existence of an abelian group action on the SIDH key space, and we show that for sufficiently unbalanced and overstretched SIDH parameters, this action can be efficiently computed (heuristically) using the torsion point information revealed in the protocol. This reduces the underlying hardness assumption to a hidden shift problem instance which can be solved in quantum subexponential time. We formulate our attack in a new framework allowing the inversion of one-way functions in quantum subexponential time provided a malleability oracle with respect to some commutative group action. This framework unifies our new attack with earlier subexponential quantum attacks on isogeny-based protocols, and it may be of further interest for cryptanalysis.

In this work we introduce Banquet, a digital signature scheme with post-quantum security, constructed using only symmetric-key primitives. The design is based on the MPC-in-head paradigm also used by Picnic (CCS 2017) and BBQ (SAC 2019). Like BBQ, Banquet uses only standardized primitives, namely AES and SHA-3, but signatures are more than 50% shorter, making them competitive with Picnic (which uses a non-standard block cipher to improve performance). The MPC protocol in Banquet uses a new technique to verify correctness of the AES S-box computations, which is efficient because the cost is amortized with a batch verification strategy. Our implementation and benchmarks also show that both signing and verification can be done in under 10ms on a current x64 CPU. We also explore the parameter space to show the range of trade-offs that are possible with the Banquet design, and show that Banquet can nearly match the signature sizes possible with Picnic (albeit with slower, but still practical run times) or have speed within a factor of two of Picnic (at the cost of larger signatures).

We present a new, simple candidate construction of indistinguishability obfuscation (iO). Our scheme is inspired by lattices and learning-with-errors (LWE) techniques, but we are unable to prove security under a standard assumption. Instead, we formulate a new falsifiable assumption under which the scheme is secure. Furthermore, the scheme plausibly achieves post-quantum security. Our construction is based on the recent "split FHE" framework of Brakerski, Döttling, Garg, and Malavolta (EUROCRYPT '20), and we provide a new instantiation of this framework. As a first step, we construct an iO scheme that is provably secure assuming that LWE holds \emph{and} that it is possible to obliviously generate LWE samples without knowing the corresponding secrets. We define a precise notion of oblivious LWE sampling that suffices for the construction. It is known how to obliviously sample from any distribution (in a very strong sense) using iO, and our result provides a converse, showing that the ability to obliviously sample from the specific LWE distribution (in a much weaker sense) already also implies iO. As a second step, we give a heuristic contraction of oblivious LWE sampling. On a very high level, we do this by homomorphically generating pseudoradnom LWE samples using an encrypted pseudorandom function.

Key-homomorphic properties of cryptographic objects, i.e., homomorphisms on their key space, have proven to be useful, both from a theoretical as well as a practical perspective. Important cryptographic objects such as pseudorandom functions or (public key) encryption have been studied previously with respect to key-homomorphisms. Interestingly, however, signature schemes have not been explicitly investigated in this context so far. We close this gap and initiate the study of key-homomorphic signatures, which turns out to be an interesting and versatile concept. In doing so, we firstly propose a definitional framework for key-homomorphic signatures distilling various natural flavours of key-homomorphic properties. Those properties aim to classify existing signature schemes and thus allow to infer general statements about signature schemes from those classes by simply making black-box use of the respective properties. We apply our definitional framework to show elegant and simple compilers from classes of signature schemes admitting different types of key-homomorphisms to a number of other interesting primitives such as ring signature schemes, (universal) designated verifier signature schemes, simulation-sound extractable non-interactive zero-knowledge (NIZK) arguments, and multisignature schemes. Additionally, using the formalisms provided by our framework, we can prove a tight implication from single-user security to key-prefixed multi-user security for a class of schemes admitting a certain key-homomorphism. Finally, we discuss schemes that provide homomorphic properties on the message space of signatures under different keys in context of key-homomorphisms and present some first constructive results from key-homomorphic schemes.

We focus on exploring more potential of Longa and Sica's algorithm (ASIACRYPT 2012), which is an elaborate iterated Cornacchia algorithm that can compute short bases for 4-GLV decompositions. The algorithm consists of two sub-algorithms, the first one in the ring of integers $\mathbb{Z}$ and the second one in the Gaussian integer ring $\mathbb{Z}[i]$. We observe that $\mathbb{Z}[i]$ in the second sub-algorithm can be replaced by another Euclidean domain $\mathbb{Z}[\omega]$ $(\omega=\frac{-1+\sqrt{-3}}{2})$. As a consequence, we design a new twofold Cornacchia-type algorithm with a theoretic upper bound of output $C\cdot n^{1/4}$, where $C=\frac{3+\sqrt{3}}{2}\sqrt{1+|r|+|s|}$ with small values $r, s$ given by the curve. Besides, we give some applications of our new algotithm in some cuvres not considered in Longa and Sica's algorithm.

This paper studies how to incorporate small information leakages (called “hints”) into information-set decoding (ISD) algorithms. In particular, the influence of these hints on solving the (n, k, t)-syndrome-decoding problem (SDP), i.e., generic syndrome decoding of a code of length n, dimension k, and an error of weight t, is analyzed. We motivate all hints by leakages obtainable through realistic side-channel attacks on code-based post-quantum cryptosystems. One class of studied hints consists of partial knowledge of the error or message, which allow to reduce the length, dimension, or error weight using a suitable transformation of the problem. As a second class of hints, we assume that the Hamming weights of subblocks of the error are known, which can be motivated by a template attack. We present adapted ISD algorithms for this type of leakage. For each third-round code-based NIST submission (Classic McEliece, BIKE, HQC), we show how many hints of each type are needed to reduce the work factor below the claimed security level. E.g., for Classic McEliece mceliece348864, the work factor is reduced below 2^128 for 175 known message entries, 9 known error locations, 650 known error-free positions, or known Hamming weights of 29 subblocks of roughly equal size.

The crucial step in elliptic curve scalar multiplication based on scalar decompositions using efficient endomorphisms—such as GLV, GLS or GLV+GLS—is to produce a short basis of a lattice involving the eigenvalues of the endomorphisms, which usually is obtained by lattice basis reduction algorithms or even more specialized algorithms. Recently, lattice basis reduction is found to be unnecessary. Benjamin Smith (AMS 2015) was able to immediately write down a short basis of the lattice for the GLV, GLS, GLV+GLS of quadratic twists using elementary facts about quadratic rings. Certainly it is always more convenient to use a ready-made short basis than to compute a new one by some algorithm. In this paper, we extend Smith's method on GLV+GLS for quadratic twists to quartic and sextic twists, and give ready-made short bases for $4$-dimensional decompositions on these high degree twisted curves. In particular, our method gives a unified short basis compared with Hu et. al's method (DCC 2012) for $4$-dimensional decompositions on sextic twisted curves.

Xagawa and Yamakawa (PQCrypto 2019) proved the transformation SXY can tightly turn DS secure PKEs into IND-qCCA secure KEMs in the quantum random oracle model (QROM). But transformations such as KC, TPunc that turn PKEs with standard security (OW-CPA or IND-CPA) into DS secure PKEs still suffer from quadratic security loss in the QROM. In this paper, we give a tighter security reduction for the transformation KC that turns OW-CPA secure deterministic PKEs into modified DS secure PKEs in the QROM. We use the Measure-Rewind-Measure One-Way to Hiding Lemma recently introduced by Kuchta et al. (EUROCRYPT 2020) to avoid the square-root advantage loss. Moreover, we extend it to the case that underlying PKEs are not perfectly correct. Combining with other transformations, we finally obtain a generic KEM from any IND-CPA secure PKE. Our security reduction has roughly the same tightness as the result of Kuchta et al. without any other assumptions and we achieve the stronger IND-qCCA security. We also give a similar result for another KEM transformation achieving the same security notion from any OW-CPA secure deterministic PKE.

We construct the first multi-input functional encryption \allowbreak(MIFE) scheme for quadratic functions from pairings. Our construction supports polynomial number of users, where user $i$, for $i \in [n]$, encrypts input $\bfx_i \in \mbZ^m$ to obtain ciphertext $\ct_i$, the key generator provides a key $\sk_\bfc$ for vector $\bfc \in \mbZ^{({mn})^2}$ and decryption, given $\ct_1,\ldots,\ct_n$ and $\sk_\bfc$, recovers $\ip{\bfc}{\bfx \otimes \bfx}$ and nothing else. We achieve indistinguishability-based (selective) security against unbounded collusions under the standard bilateral matrix Diffie-Hellman assumption. All previous MIFE schemes either support only inner products (linear functions) or rely on strong cryptographic assumptions such as indistinguishability obfuscation or multi-linear maps.

Any non-zero ideal in a number field can be factored into a product of prime ideals. In this paper we report a surprising connection between the complexity of the shortest vector problem (SVP) of prime ideals in number fields and their decomposition groups. When applying the result to number fields popular in lattice based cryptosystems, such as power-of-two cyclotomic fields, we show that a majority of rational primes lie under prime ideals admitting a polynomial time algorithm for SVP. Although the shortest vector problem of ideal lattices underpins the security of the Ring-LWE cryptosystem, this work does not break Ring-LWE, since the security reduction is from the worst case ideal SVP to the average case Ring-LWE, and it is one-way.

In this note, an LWE problem with a hidden trapdoor is introduced. It is used to construct an efficient public-key crypto-system EHT. The new system is significantly different from LWE based NIST candidates like FrodoKEM. The performance of EHT compares favorably with FrodoKEM.

We put forward the notion of universal proxy re-encryption (UPRE). A UPRE scheme enables a proxy to convert a ciphertext under a (delegator) public key of any existing public-key encryption (PKE) scheme into another ciphertext under a (delegatee) public key of any existing PKE scheme (possibly different from the delegator one). The proxy has a re-encryption key generated from the delegator's secret key and the delegatee public key. Thus UPRE generalizes proxy re-encryption by supporting arbitrary PKE schemes and allowing to convert ciphertexts into ones of possibly different PKE schemes. In this work, we - provide syntax and definitions for both UPRE and a variant we call relaxed UPRE. The relaxed variant means that decryption algorithms for re-encrypted ciphertexts are slightly modified but still only use the original delegatee secret keys for decryption. - construct a UPRE based on probabilistic indistinguishability obfuscation (PIO). It allows us to re-encrypt ciphertexts polynomially many times. - construct relaxed UPRE from garbled circuits (GCs). We provide two variants of this construction, one which allows us to re-encrypt ciphertexts polynomially many times, and a second one which satisfies a stronger security requirement but only allows us to re-encrypt ciphertexts a constant number of times.

Modern public key encryption relies on various hardness assumptions for its security. Hardness assumptions may cause security uncertainty, for instance, when a hardness problem is no longer hard or the best solution to a hard problem might not be publicly released. In this paper, we propose a public key encryption scheme Compact-LWE-MQ^{H} to demonstrate the feasibility of constructing public key encryption without relying on hardness assumptions. Instead, its security is based on problems that are called factually hard. The two factually hard problems we propose in this work are stratified system of linear and quadratic equations, and layered learning with relatively big errors. The factually hard problems are characterized by their layered structures, which ensure that the secrets at a lower layer can only be recovered after the secrets in a upper layer have been found {\it correctly} (i.e., leading to consistent lower layer secrets, not necessarily the original upper layer ones). On the other hand, without knowing the secrets in the lower layer, the upper layer subproblem can only be solved by exhaustive search. Based on the structure of factually hard problems, we prove that without brute-force search the adversary cannot recover plaintexts or correct private key, and then discuss CPA-security and CCA-security of Compact-LWE-MQ^{H}. We have implemented Compact-LWE-MQ^{H} with a number of lines of SageMath code. Simplicity of Compact-LWE-MQ^{H} makes it easy for understanding, cryptanalysis, and implementation. In our configuration for 128-bit security, the dimensional parameter is $n=4$ ($n$ has the same meaning as in LWE). For such a tiny parameter, the current analysis tools like LLL lattice reduction algorithm are already efficient enough to perform attacks if the security claim of Compact-LWE-MQ^{H} does not hold. That is, the security of Compact-LWE-MQ^{H} is not assumed with the capability of cryptanalysis tools. SageMath code of verifying Compact-LWE-MQ^{H} security is also included in Appendix.

There has been a lot of recent progress in constructing efficient zero-knowledge proofs for showing knowledge of an $\vec{\mathbf{s}}$ with small coefficients satisfying $\bm{A}\vec{\mathbf{s}}=\vec{\mathbf{t}}$. For typical parameters, the proof sizes have gone down from several megabytes to a bit under $50$KB (Esgin et al., Asiacrypt 2020). These are now within an order of magnitude of the sizes of lattice-based signatures, which themselves constitute proof systems which demonstrate knowledge of something weaker than the aforementioned equation. One can therefore see that this line of research is approaching optimality. In this paper, we modify a key component of these proofs, as well as apply several other tweaks, to achieve a further reduction of around $30\%$ in the proof output size. We also show that this savings propagates itself when these proofs are used in a general framework to construct more complex protocols.

In this work, we describe an integer version of ring-LWE over the polynomial rings and prove that its hardness is equivalent to one of the polynomial ring-LWE. Moreover, we also present a public key cryptosystem using this variant of the polynomial ring-LWE.

The progress on constructing quantum computers and the ongoing standardization of post-quantum cryptography (PQC) have led to the development and refinement of promising new digital signature schemes and key encapsulation mechanisms (KEM). Especially lattice-based schemes have gained some popularity in the research community, presumably due to acceptable key, ciphertext, and signature sizes as well as good performance results and cryptographic strength. However, in some practical applications like smart cards, it is also crucial to secure cryptographic implementations against side-channel and fault attacks. In this work, we analyze the so-called redundant number representation (RNR) that can be used to counter side-channel attacks. We show how to avoid security issues with the RNR due to unexpected de-randomization and we apply it to the Kyber KEM and show that the RNR has a very low overhead. We then verify the RNR methodology by practical experiments, using the non-specific t-test methodology and the ChipWhisperer platform. Furthermore, we present a novel countermeasure against fault attacks based on the Chinese remainder theorem (CRT). On an ARM Cortex-M4, our implementation of the RNR and fault countermeasure offers better performance than masking and redundant calculation. Our methods thus have the potential to expand the toolbox of a defender implementing lattice-based cryptography with protection against two common physical attacks.

In this paper, we study the {\em hybrid dual attack} over Learning with Errors (LWE) problems for {\em any} secret distribution. Prior to our work, hybrid attacks are only considered for sparse and/or small secrets. A new and interesting result from our analysis shows that for most cryptographic use cases a hybrid dual attack outperforms a standalone dual attack, regardless of the secret distribution. We formulate our results into a framework of predicting the performance of the hybrid dual attacks. We also present a few tricks that further improve our attack. To illustrate the effectiveness of our result, we re-evaluate the security of {\em all} LWE related proposals in round 3 of NIST's post-quantum cryptography process, and improve the state-of-the-art cryptanalysis results by 2-14 bits, under the BKZ-core-SVP model.

Quantum Key Distribution or QKD provides symmetric key distribution using the quantum mechanics/channels with new security properties. The security of QKD relies on the difficulty of the quantum state discrimination problem. We discover that the recent developments in PT symmetry can be used to expedite the quantum state discrimination problem and therefore to attack the BB84 QKD scheme. We analyze the security of the BB84 scheme and show that the attack significantly increases the eavesdropping success rate over the previous Hermitian quantum state discrimination approach. We design and analyze the approaches to attack BB84 QKD protocol exploiting an extra degree of freedom provided by the PT-symmetric quantum mechanics.

Deterministic generation of per-signature randomness has been a widely accepted solution to mitigate the catastrophic risk of randomness failure in Fiat--Shamir type signature schemes. However, recent studies have practically demonstrated that such de-randomized schemes, including EdDSA, are vulnerable to differential fault attacks, which enable adversaries to recover the entire secret signing key, by artificially provoking randomness reuse or corrupting computation in other ways. In order to balance concerns of both randomness failures and the threat of fault injection, some signature designs are advocating a ``hedged'' derivation of the per-signature randomness, by hashing the secret key, message, and a nonce. Despite the growing popularity of the hedged paradigm in practical signature schemes, to the best of our knowledge, there has been no attempt to formally analyze the fault resilience of hedged signatures. We perform a formal security analysis of the fault resilience of signature schemes constructed via the Fiat--Shamir transform. We propose a model to characterize bit-tampering fault attacks, and investigate their impact across different steps of the signing operation. We prove that, for some types of faults, attacks are mitigated by the hedged paradigm, while attacks remain possible for others. As concrete case studies, we then apply our results to XEdDSA, a hedged version of EdDSA used in the Signal messaging protocol, and to Picnic2, a hedged Fiat--Shamir signature scheme in Round 2 of the NIST Post-Quantum standardization process.

In this paper, we provide a notable step towards filling the gap between theory (estimates of running-time) and practice (a discrete logarithm record computation) for the Tower Number Field Sieve (TNFS) algorithm. We propose a generalisation of ranking formula for selecting the polynomials used in the very first step of TNFS algorithm. For this we provide a definition and an exact implementation (Magma and SageMath) of the alpha function. This function measures the bias in the smoothness probability of norms in number fields compared to random integers of the same size. We use it to estimate the yield of polynomials, that is the expected number of relations, as a generalisation of Murphy's E function, and finally the total amount of operations needed to compute a discrete logarithm with TNFS algorithm in the targeted fields. This is an improvement of the earlier work of Barbulescu and Duquesne on estimating the running-time of the algorithm. We apply our estimates to a wide size range of finite fields GF(p^n), for small composite n = 12, 16, 18, 24, that are target fields of pairing-friendly curves.

The notion of functional encryption (FE) was proposed as a generalization of plain public-key encryption to enable a much more fine-grained handling of encrypted data, with advanced applications such as cloud computing, multi-party computations, obfuscating circuits or Turing machines. While FE for general circuits or Turing machines gives a natural instantiation of the many cryptographic primitives, existing FE schemes are based on indistinguishability obfuscation or multilinear maps which either rely on new computational hardness assumptions or heuristically claimed to be secure. In this work, we present new techniques directly yielding FE for inner product functionality where secret-keys provide access control via polynomial-size bounded-depth circuits. More specifically, we encrypt messages with respect to attributes and embed policy circuits into secret-keys so that a restricted class of receivers would be able to learn certain property about the messages. Recently, many inner product FE schemes were proposed. However, none of them uses a general circuit as an access structure. Our main contribution is designing the first construction for an attribute-based FE scheme in key-policy setting for inner products from well-studied Learning With Errors (LWE) assumption. Our construction takes inspiration from the attribute-based encryption of Boneh et al. from Eurocrypt 2014 and the inner product functional encryption of Agrawal et al. from Crypto 2016. The scheme is proved in a stronger setting where the adversary is allowed to ask secret-keys that can decrypt the challenge ciphertext. Doing so requires a careful setting of parameters for handling the noise in ciphertexts to enable correct decryption. Another main advantage of our scheme is that the size of ciphertexts and secret-keys depends on the depth of the circuits rather than its size. Additionally, we extend our construction in a much desirable multi-input variant where secret-keys are associated with multiple policies subject to different encryption slots. This enhances the applicability of the scheme with finer access control.

Group signatures allow users to create signatures on behalf of a group while remaining anonymous. Such signatures are a powerful tool to realize privacy-preserving data collections, where e.g., sensors, wearables or vehicles can upload authenticated measurements into a data lake. The anonymity protects the user’s privacy yet enables basic data processing of the uploaded unlinkable information. For many applications, full anonymity is often neither desired nor useful though, and selected parts of the data must eventually be correlated after being uploaded. Current solutions of group signatures do not provide such functionality in a satisfactory way: they either rely on a trusted party to perform opening or linking of signatures, which clearly conflicts with the core privacy goal of group signatures; or require the user to decide upon the linkability of signatures before they are generated. In this paper we propose a new variant of group signatures that provides linkability in a flexible and user-centric manner. Users – and only they – can decide before and after signature creation whether they should remain linkable or be correlated. To prevent attacks where a user omits certain signatures when a sequence of events in a certain section (e.g., time frame), should be linked, we further extend this new primitive to allow for sequential link proofs. Such proofs guarantee that the provided sequence of data is not only originating from the same signer, but also occurred in that exact order and contains all of the user’s signatures within the time frame. We formally define the desired security and privacy properties, propose a provably secure construction based on DL-related assumptions and report on a prototypical implementation of our scheme.

ECDSA algorithm is usually used in ICT system to achieve communication authenticity. But weakness in various implementations of the algorithm may make its security deviate from theoretical guarantee. This paper proposes a new lattice-based weak curve fault attack on ECDSA. An elliptic curve is weak if the problem of ECDLP in a \emph{subgroup} of the point group $\langle G \rangle$ is computationally solvable in practice, where $G$ is the specified basis point of ECDSA algorithm. Since ECDLP is not required to be computationally practical in the whole group of $\langle G \rangle$, our approach extends the known existing attacks along this line. In detail, the proposed attack assumes a fault injection process can perturb a segment of consecutive bits of the curve parameter $a$ in the Weierstrass equation of ECDSA. An analysis on the density of smooth numbers indicates the faulty value $a'$ parameterized elliptic curve is weak in high probability. Then we show the faulty value $a'$ can be recovered by a dedicated quadratic residue distinguisher, which makes it possible to collect enough side channel information about the nonce used in the ECDSA signature generation process. With the help of these information, we can construct a lattice to recover the private key with lattice basis reduction techniques. Further, we show the same strategy can defeat the nonce masking countermeasure if the random mask is not too long, and makes the commonly employed countermeasures ineffective. To our knowledge, the problem remains untractable to the existing weak curve fault attacks. Thus the proposed approach can find more applications than the existing ones. This is demonstrated by the experimental analysis.

Let $E_a/ \mathbb{F}_{2}: y^2+xy=x^3+ax^2+1$ be a Koblitz curve. The window $\tau$-adic non-adjacent form (window $\tau$NAF) is currently the standard representation system to perform scalar multiplications on $E_a/ \mathbb{F}_{2^m}$ utilizing the Frobenius map $\tau$. This work focuses on the pre-computation part of scalar multiplication. We first introduce $\mu\bar{\tau}$-operations where $\mu=(-1)^{1-a}$ and $\bar{\tau}$ is the complex conjugate of $\tau$. Efficient formulas of $\mu\bar{\tau}$-operations are then derived and used in a novel pre-computation scheme. Our pre-computation scheme requires $6${\bf M}$+6${\bf S}, $18${\bf M}$+17${\bf S}, $44${\bf M}$+32${\bf S}, and $88${\bf M}$+62${\bf S} ($a=0$) and $6${\bf M}$+6${\bf S}, $19${\bf M}$+17${\bf S}, $46${\bf M}$+32${\bf S}, and $90${\bf M}$+62${\bf S} ($a=1$) for window $\tau$NAF with widths from $4$ to $7$ respectively. It is about two times faster, compared to the state-of-the-art technique of pre-computation in the literature. The impact of our new efficient pre-computation is also reflected by the significant improvement of scalar multiplication. Traditionally, window $\tau$NAF with width at most $6$ is used to achieve the best scalar multiplication. Because of the dramatic cost reduction of the proposed pre-computation, we are able to increase the width for window $\tau$NAF to $7$ for a better scalar multiplication. This indicates that the pre-computation part becomes more important in performing scalar multiplication. With our efficient pre-computation and the new window width, our scalar multiplication runs in at least 85.2\% the time of Kohel's work (Eurocrypt'2017) combining the best previous pre-computation. Our results push the scalar multiplication of Koblitz curves, a very well-studied and long-standing research area, to a significant new stage.

Group signature with verifier-local revocation (VLR-GS) is a special type of revocable group sig- nature which enables a user to sign messages without referring to information regarding revoked users. Although there have been several proposals of VLR-GS schemes since the first scheme proposed by Boneh and Shacham [CCS 2004], all of these schemes only achieve a security notion called selfless anonymity, which is strictly weaker than the de facto standard security notion, full anonymity. Thus, for more than a decade, it has been an open problem whether a fully anonymous VLR-GS scheme can be achieved. In this paper, we give an affirmative answer to this problem. Concretely, we show the construction of a fully anonymous VLR-GS scheme from a digital signature scheme, a key-private public key encryption scheme, and a non-interactive zero-knowledge proof system. Also, we show that backward unlinkability, which ensures that even after a user is revoked, signatures produced by the user before the revocation remain anonymous, can be realized without additional building blocks. Although the size of group public key and signing key depend on the number of time periods, finally, we show that the size of these keys can be reduced by employing an identity-based encryption scheme.

Isomorphism of polynomials with two secrets (IP2S) problem was proposed by Patarin et al. at Eurocrypt 1996 and the problem is to find two secret linear maps filling in the gap between two polynomial maps over a finite field. At PQC 2020, Santoso proposed a problem originated from IP2S, which is called block isomorphism of polynomials with circulant matrices (BIPC) problem. The BIPC problem is obtained by linearizing IP2S and restricting secret linear maps to linear maps represented by circulant matrices. Using the commutativity of products of circulant matrices, Santoso also proposed an El-Gamal-like encryption scheme based on the BIPC problem. In this paper, we give a new security analysis on the El-Gamal-like encryption scheme. In particular, we introduce a new attack (called linear stack attack) which finds an equivalent key of the El-Gamal-like encryption scheme by using the linearity of the BIPC problem. We see that the attack is a polynomial-time algorithm and can break some 128-bit proposed parameters of the El-Gamal-like encryption scheme within 10 hours on a standard PC.

We construct more efficient cryptosystems with provable security against adaptive attacks, based on simple and natural hardness assumptions in the standard model. Concretely, we describe: - An adaptively-secure variant of the efficient, selectively-secure LWE-based identity-based encryption (IBE) scheme of Agrawal, Boneh, and Boyen (EUROCRYPT 2010). In comparison to the previously most efficient such scheme by Yamada (CRYPTO 2017) we achieve smaller lattice parameters and shorter public keys of size $\mathcal{O}(\log \lambda)$, where $\lambda$ is the security parameter. - Adaptively-secure variants of two efficient selectively-secure pairing-based IBEs of Boneh and Boyen (EUROCRYPT 2004). One is based on the DBDH assumption, has the same ciphertext size as the corresponding BB04 scheme, and achieves full adaptive security with public parameters of size only $\mathcal{O}(\log \lambda)$. The other is based on a $q$-type assumption and has public key size $\mathcal{O}(\lambda)$, but a ciphertext is only a single group element and the security reduction is quadratically tighter than the corresponding scheme by Jager and Kurek (ASIACRYPT 2018). - A very efficient adaptively-secure verifiable random function where proofs, public keys, and secret keys have size $\mathcal{O}(\log \lambda)$. As a technical contribution we introduce blockwise partitioning, which leverages the assumption that a cryptographic hash function is weak near-collision resistant to prove full adaptive security of cryptosystems.

We offer a public key exchange protocol based on a semidirect product of two cyclic (semi)groups of matrices over Z_p. One of the (semi)groups is additive, the other one multiplicative. This allows us to take advantage of both operations on matrices to diffuse information. We note that in our protocol, no power of any matrix or of any element of Z_p is ever exposed, so all standard attacks on Diffie-Hellman-like protocols are not applicable.

Development of signature schemes providing short signatures is a quite relevant non-trivial challenge for cryptographers. Since the late 1980’s many short signature schemes have been proposed. The most perspective schemes are multivariate schemes and schemes based on Weil pairing. Unfortunately, the cryptographic tools used in these schemes are still not supported by most cryptographic software that complicates their effortless use in practice. In the current paper we investigate the opportunity of shortening the standard ElGamal-type signatures. We propose three methods of shortening signatures (for any ElGamal-type schemes such as ECDSA, GOST and SM2) and analyze how applying these methods affects the security. Applying all three methods to the GOST signature scheme with elliptic curve subgroup order $q$, $2^{255} < q < 2^{256}$, can reduce the signature size from $512$ to $320$ bits. The modified scheme provides sufficient security and acceptable (for non-interactive protocols) signing and verifying time.

To deal with dynamically changing user's credentials in identity-based encryption (IBE), providing an efficient key revocation method is a very important issue. Recently, Ma and Lin proposed a generic method of designing a revocable IBE (RIBE) scheme that uses the complete subtree (CS) method by combining IBE and hierarchical IBE (HIBE) schemes. In this paper, we propose a new generic method for designing an RIBE scheme that uses the subset difference (SD) method instead of using the CS method. In order to use the SD method, we generically design an RIBE scheme by combining two-level HIBE and single revocation encryption (SRE) schemes. If the underlying HIBE and SRE schemes are adaptively (or selectively) secure, then our RIBE scheme is also adaptively (or selectively) secure. In addition, we show that the layered SD (LSD) method can be applied to our RIBE scheme and a chosen-ciphertext secure RIBE scheme also can be designed generically.

Regev (2005) introduced the learning with errors (LWE) problem and showed a quantum reduction from a worst case lattice problem to LWE. Building on the work of Peikert (2009), a classical reduction from the gap shortest vector problem to LWE was obtained by Brakerski et al. (2013). A concrete security analysis of Regev's reduction by Chatterjee et al. (2016) identified a huge tightness gap. The present work performs a concrete analysis of the tightness gap in the classical reduction of Brakerski et al. It turns out that the tightness gap in the Brakerski et al. classical reduction is even larger than the tightness gap in the quantum reduction of Regev. This casts doubts on the implication of the reduction to security assurance of practical cryptosystems.

In this work, we study GPU implementations of various state-of-the-art sieving algorithms for lattices (Becker-Gama-Joux 2015, Becker-Ducas-Gama-Laarhoven 2016, Herold-Kirshanova 2017) inside the General Sieve Kernel (G6K, Albrecht et al. 2019). In particular, we extensively exploit the recently introduced *Tensor Cores* -- originally designed for raytracing and machine learning -- and demonstrate their fitness for the cryptanalytic task at hand. We also propose a new *dual-hash* technique for efficient detection of `lift-worthy' pairs to accelerate a key ingredient of G6K: finding short lifted vectors. We obtain new computational records, reaching dimension $180$ for the SVP Darmstadt Challenge improving upon the previous record for dimension $155$. This computation ran for $51.6$ days on a server with $4$ NVIDIA Turing GPUs and $1.5$TB of RAM. This corresponds to a gain of about two orders of magnitude over previous records both in terms of wall-clock time and of energy efficiency.

The Classic McEliece cryptosystem is one of the most trusted quantum-resistant cryptographic schemes. Deploying it in practical applications, however, is challenging due to the size of its public key. In this work, we bridge this gap. We present an implementation of Classic McEliece on an ARM Cortex-M4 processor, optimized to overcome memory constraints. To this end, we present an algorithm to retrieve the public key ad-hoc. This reduces memory and storage requirements and enables the generation of larger key pairs on the device. To further improve the implementation, we perform the public key operation by streaming the key to avoid storing it as a whole. This additionally reduces the risk of denial of service attacks. Finally, we use these results to implement and run TLS on the embedded device.

So far, most of the Identity-Based Encryption (IBE) schemes have been realized by employing bilinear pairings, lattices, trapdoor discrete logarithm, or based on the quadratic residue problem. Among the IBE schemes, only pairing-based methods seem to be practical. Previously published non-pairing-based schemes are generally inefficient in encryption, decryption, key generation, ciphertext size or key size. In this paper, we propose an IBE scheme based on a hybrid of Diffie-Hellman and RSA-like hardness assumption. The computational cost of the proposed scheme is lower than the previous schemes and the ciphertext size for an $l$-bit plaintext is only $2l$ bits. The proposed scheme is similar to the well-known ElGamal encryption algorithm; therefore it might be used in applications such as oblivious computation.

In this article, we propose a new public key cryptosystem, called \textbf{NAB}. The most important features of NAB are that its security strength is no easier than the security issues of the NTRU cryptosystem~\cite{Hoffstein96} and the encryption/decryption process is very fast compared to the previous public key cryptosystems RSA~\cite{Rivest78amethod}, Elgamal~\cite{ElGamal85}, NTRU~\cite{Hoffstein96}. Since the NTRU cryptosystem~\cite{Hoffstein96} is still not known to be breakable using quantum computers, NAB is also the same. In addition, the expansion of the ciphertext is barely greater than the plaintext and the ratio of the bit-size of the ciphertext to the bit-size of the plaintext can be reduced to just over one. We suggest that NAB is an alternative to RSA~\cite{Rivest78amethod}, Elgamal~\cite{ElGamal85} and NTRU~\cite{Hoffstein96} cryptosystems.

We give secure parameter suggestions to use sparse secret vectors in LWE based encryption schemes. This should replace existing security parameters, because homomorphic encryption(HE) schemes use quite different variables from the existing parameters. In particular HE schemes using sparse secrets should be supported by experimental analysis, here we summarize existing attacks to be considered and security levels for each attacks. Based on the analysis and experiments, we compute optimal scaling factors for CKKS.

In a recent paper Géraud-Stewart and Naccache \cite{gsn2021} (GSN) described an non-interactive process allowing a prover $\mathcal P$ to convince a verifier $\mathcal V$ that a modulus $n$ is the product of two randomly generated primes ($p,q$) of about the same size. A heuristic argument conjectures that $\mathcal P$ cannot control $p,q$ to make $n$ easy to factor. GSN's protocol relies upon elementary number-theoretic properties and can be implemented efficiently using very few operations. This contrasts with state-of-the-art zero-knowledge protocols for RSA modulus proper generation assessment. This paper proposes an alternative process applicable in settings where $\mathcal P$ co-generates a modulus $n=p_1q_1p_2q_2$ with a certification authority $\mathcal V$. If $\mathcal P$ honestly cooperates with $\mathcal V$, then $\mathcal V$ will only learn the sub-products $n_1=p_1q_1$ and $n_2=p_2q_2$. A heuristic argument conjectures that at least two of the factors of $n$ are beyond $\mathcal P$'s control. This makes $n$ appropriate for cryptographic use provided that \emph{at least one party} (of $\mathcal P$ and $\mathcal V$) is honest. This heuristic argument calls for further cryptanalysis.

CSIDH is an isogeny-based key exchange protocol proposed by Castryck \textit{et al.} in 2018. It is based on the ideal class group action on $\mathbb{F}_p$-isomorphism classes of Montgomery curves. The original CSIDH algorithm requires a calculation over $\mathbb{F}_p$ by representing points as $x$-coordinate over Montgomery curves. There is a special coordinate on Edwards curves (the $w$-coordinate) to calculate group operations and isogenies. If we try to calculate the class group action on Edwards curves by using the $w$-coordinate in a similar way on Montgomery curves, we have to consider points defined over $\mathbb{F}_{p^4}$. Therefore, it is not a trivial task to calculate the class group action on Edwards curves with $w$-coordinates over only $\mathbb{F}_p$. In this paper, we prove some theorems about the properties of Edwards curves. By these theorems, we construct the new CSIDH algorithm on Edwards curves with $w$-coordinates over $\mathbb{F}_p$. This algorithm is as fast as (or a little bit faster than) the algorithm proposed by Meyer and Reith. This paper is an extend version of [25]. We added the construction of a technique similar to Elligator on Edwards curves. This technique contributes the efficiency of the constant-time CSIDH algorithm. We also added the construction of new formulas to compute isogenies in $\tilde{O}(\sqrt{\ell})$ times on Edwards curves. It is based on formulas on Montgomery curves proposed by Bernstein \textit{et al.} ($\sqrt{\vphantom{2}}$élu's formulas). In our analysis, these formulas on Edwards curves is a little bit faster than those on Montgomery curves.

Chosen ciphertext security for lattice based encryption schemes is generally achieved through a generic transformation such as the Fujisaki-Okamoto transformation. This method requires full re-encryption of the plaintext during decapsulation, which typically dominates the cost of the latter procedure. In this work we show that it is possible to develop alternative transformations specifically designed for lattice based encryption schemes. We propose two novel chosen ciphertext transformations, $\mathtt{ETC1}$ and $\mathtt{ETC2}$, in which re-encryption is replaced by checking the error term of the input ciphertext. We show that our new ciphertext validity check can be securely applied to lattice based encryption schemes under specific conditions. For the NIST post-quantum standardization candidate Threebears we show a speed-up for decapsulation of up to $37.4\%$. Moreover, as our method only changes the validation check during decapsulation, it is fully backwards compatible with existing implementations of the Fujisaki-Okamoto transformation.

In this paper, we present the first side-channel attack on a first-order masked implementation of IND-CCA secure Saber KEM. We show how to recover both the session key and the long-term secret key from 16 traces by deep learning-based power analysis without explicitly extracting the random mask at each execution. Since the presented method is not dependent on the mask, we can improve success probability by combining score vectors of multiple traces captured for the same ciphertext. This is an important advantage over previous attacks on LWE/LWR-based KEMs, which must rely on a single trace. Another advantage is that the presented method does not require a profiling device with deactivated countermeasure, or known secret key. Thus, if a device under attack is accessible, it can be used for profiling. This typically maximizes the classification accuracy of deep learning models. In addition, we discovered a leakage point in the primitive for masked logical shifting on arithmetic shares which has not been known before. We also present a new approach for secret key recovery, using maps from error-correcting codes. This approach can compensate for some errors in the recovered message.

This paper describes a non-interactive process allowing a prover to convince a verifier that a modulus $n$ is the product of two primes ($p,q$) of about the same size. A further heuristic argument conjectures that $p-1$ and $q-1$ have sufficiently large prime factors for cryptographic applications. The new protocol relies upon elementary number-theoretic properties and can be implemented efficiently using very few operations. This contrasts with state-of-the-art zero-knowledge protocols for RSA modulus proper generation assessment. The heuristic argument at the end of our construction calls for further cryptanalysis by the community and is, as such, an interesting research question in its own right.

In a witness encryption scheme, to decrypt a ciphertext associated with an NP statement, the decrypter takes as input a witness testifying that the statement is in the language. When the statement is not in the language, then the message is hidden. Thus far, the only provably secure constructions assume the existence of indistinguishability obfuscation (iO) and multilinear maps (MMaps). We make progress towards building polynomially efficient witness encryption for NP without resorting to iO or MMaps. In particular, we give a witness encryption scheme from Yao's garbled circuit technique and a new type of fully homomorphic encryption (FHE) that we call annihilating. Interestingly, we require a version of the annihilating FHE that is circularly insecure, i.e., allows testing the presence of a key cycle. We prove our witness encryption's security from a novel assumption about our annihilating FHE. We formulate the assumption as an interplay between an annihilating FHE and ideal ciphers. We show a candidate (leveled) annihilating FHE built from a multikey variant of the BGV/BFV fully homomorphic cryptosystems.

We introduce a new signature scheme, SQISign, (for Short Quaternion and Isogeny Signature) from isogeny graphs of supersingular elliptic curves. The signature scheme is derived from a new one-round, high soundness, interactive identification protocol. Targeting the post-quantum NIST-1 level of security, our implementation results in signatures of $204$ bytes, secret keys of $16$ bytes and public keys of $64$ bytes. In particular, the signature and public key sizes combined are an order of magnitude smaller than all other post-quantum signature schemes. On a modern workstation, our implementation in C takes 0.6s for key generation, 2.5s for signing, and 50ms for verification. While the soundness of the identification protocol follows from classical assumptions, the zero-knowledge property relies on the second main contribution of this paper. We introduce a new algorithm to find an isogeny path connecting two given supersingular elliptic curves of known endomorphism rings. A previous algorithm to solve this problem, due to Kohel, Lauter, Petit and Tignol, systematically reveals paths from the input curves to a `special' curve. This leakage would break the zero-knowledge property of the protocol. Our algorithm does not directly reveal such a path, and subject to a new computational assumption, we prove that the resulting identification protocol is zero-knowledge.

Often times, the ability to distinguish between random data and a public key can leads to an attack against the cryptosystem itself. In this paper, we will show experimentally a very efficient distinguisher based on the distribution of ranks of the symmetric matrices associated with the central map in the multivariate cryptosystem HFE when the degree D of the central map is very small.

The Schnorr blind signing protocol allows blind issuing of Schnorr signatures, one of the most widely used signatures. Despite its practical relevance, its security analysis is unsatisfactory. The only known security proof is rather informal and in the combination of the generic group model (GGM) and the random oracle model (ROM) assuming that the ``ROS problem'' is hard. The situation is similar for (Schnorr-)signed ElGamal encryption, a simple CCA2-secure variant of ElGamal. We analyze the security of these schemes in the algebraic group model (AGM), an idealized model closer to the standard model than the GGM. We first prove tight security of Schnorr signatures from the discrete logarithm assumption (DL) in the AGM+ROM. We then give a rigorous proof for blind Schnorr signatures in the AGM+ROM assuming hardness of the one-more discrete logarithm problem and ROS. As ROS can be solved in sub-exponential time using Wagner's algorithm, we propose a simple modification of the signing protocol, which leaves the signatures unchanged. It is therefore compatible with systems that already use Schnorr signatures, such as blockchain protocols. We show that the security of our modified scheme relies on the hardness of a problem related to ROS that appears much harder. Finally, we give tight reductions, again in the AGM+ROM, of the CCA2 security of signed ElGamal encryption to DDH and signed hashed ElGamal key encapsulation to DL.

In a hybrid key encapsulation construction, multiple independent key encapsulation mechanisms are combined in a way that ensures the resulting key is secure according to the strongest mechanism. Such constructions can combine mechanisms that are secure in different settings and achieve the combined security of all mechanisms. For example classical and post-quantum mechanisms can be combined in order to secure communication against current threats as well as future quantum adversaries. This paper contains proofs of security for two hybrid key encapsulation mechanisms along with the relevant security definitions. Practical interpretation of these results is also provided in order to guide the use of these mechanisms in applications and standards.

Tropical linear algebra has been recently put forward by Grigoriev and Shpilrain ~\cite{grigoriev2014tropical,grigoriev2018tropical} as a promising platform for the implementation of protocols of Diffie-Hellman and Stickel type. Based on the CSR expansion of tropical matrix powers, we suggest a simple algorithm for the following tropical discrete logarithm problem: ``Given that $A=V\otimes F^{\otimes t}$ for a unique $t$ and matrices $A$, $V$, $F$ of appropriate dimensions, find this $t$.'' We then use this algorithm to suggest a simple attack on a protocol based on the tropical semidirect product. The algorithm and the attack are guaranteed to work in some important special cases and are shown to be efficient in our numerical experiments.

Garg, Gentry and Halevi (GGH13) described the first candidate multilinear maps using ideal lattices. However, Hu and Jia recently presented an efficient attack on the GGH13 map, which breaks the multipartite key exchange (MPKE) and witness encryption (WE) based on GGH13. In this work, we describe a new variant of GGH13 using secret ring, which preserves the origin functionality of GGH13. The security of our variant depends upon the following new hardness problem. Given the determinant of the circular matrix of some element in a secret ring, the problem is to find this secret ring and reconstruct this element.

A tropical version of Stickel’s key exchange protocol was suggested by Grigoriev and Sphilrain [2] and successfully attacked by Kotov and Ushakov [5]. We suggest some modifications of this scheme that use commuting matrices in tropical algebra and discuss some possibilities of attacks on these new modifications. We suggest some simple heuristic attacks on one of our new protocols, and then we generalize the Kotov and Ushakov attack on Stickel’s protocol and discuss the application of that generalised attack to all our new protocols

We revisit some well-known cryptographic problems in a black box modular ring model of computation. This model allows us to compute with black box access to the ring $\mathbb{Z}/m\mathbb{Z}$. We develop new generic ring algorithms to recover $m$ even if it is unknown. At the end, Maurer's generic algorithm allows to recover an element from its black box representation. However, we avoid Maurer's idealized model with CDH oracle for the multiplication in the hidden ring by introducing a new representation compatible with ring operations. An element is encoded by its action over the factor basis. Consequently, we can multiply two elements with classical descent computations in sieving algorithms. As the algorithms we propose work without using an expensive linear algebra computation at the end, even though they manipulate large sparse matrices, we can exploit a high-level of parallelism. Then, we consider general groups such as imaginary quadratic class group and the Jacobian of a hyperelliptic curve, and obtain new methods for group order computation. The repeated squaring problem and the adaptive root problem used in the construction of Verifiable Delay Functions are particularly easy to solve in the black box modular ring, the high degree of parallelism provided by our method allows a reduction in the time to solve them. We improve the smoothing time, and as a result, we break Verifiable Delay Functions and factorize weak keys with lower Area-Time cost. Finally, we show new AT costs for computing a discrete logarithm over an adversarial basis in finite fields.

We observe that all previously known lattice-based blind signature schemes contain subtle flaws in their security proofs (e.g., Rückert, ASIACRYPT '08) or can be attacked (e.g., BLAZE by Alkadri et al., FC '20). Motivated by this, we revisit the problem of constructing blind signatures from standard lattice assumptions. We propose a new three-round lattice-based blind signature scheme whose security can be proved, in the random oracle model, from the standard SIS assumption. Our starting point is a modified version of the (insecure) BLAZE scheme, which itself is based Lyubashevsky's three-round identification scheme combined with a new aborting technique to reduce the correctness error. Our proof builds upon and extends the recent modular framework for blind signatures of Hauck, Kiltz, and Loss (EUROCRYPT '19). It also introduces several new techniques to overcome the additional challenges posed by the correctness error which is inherent to all lattice-based constructions. While our construction is mostly of theoretical interest, we believe it to be an important stepping stone for future works in this area.

Zhang et al. recently proposed a lattice-based proxy-oriented identity-based encryption with keyword search (PO-IBEKS) at Information Sciences in 2019. They claimed that their scheme can resist insider keyword guessing attacks by preventing cloud server from generating ciphertext. In this note, we provide a cryptanalysis of their PO-IBEKS and demonstrate that their scheme cannot resist outsider/insider keyword guessing attacks, even though they satisfy unforgeability requirement. Furthermore, we uncover the root cause of the attack and provide a possible solution for Zhang et al.'s scheme to aid future designs of secure PO-IBEKS schemes.

In this paper, we introduce a distributed key generation (DKG) protocol with aggregatable and publicly-verifiable transcripts. Compared with prior publicly-verifiable approaches, our DKG reduces the size of the final transcript and the time to verify it from $O(n^2)$ to $O(n log(n))$, where $n$ denotes the number of parties. As compared with prior non-publicly-verifiable approaches, our DKG leverages gossip rather than all-to-all communication to reduce verification and communication complexity. We also revisit existing DKG security definitions, which are quite strong, and propose new and natural relaxations. As a result, we can prove the security of our aggregatable DKG as well as that of several existing DKGs, including the popular Pedersen variant. We show that, under these new definitions, these existing DKGs can be used to yield secure threshold variants of popular cryptosystems such as El-Gamal encryption and BLS signatures. We also prove that our DKG can be securely combined with a new efficient verifiable unpredictable function (VUF), whose security we prove in the random oracle model. % Finally, we experimentally evaluate our DKG and show that the per-party overheads scale linearly and are practical. For $64$ parties, it takes $71$ms to share and $359$ms to verify the overall transcript, while for $8192$ parties, it takes $8$s and $42.2$s respectively.

Existing lattice signature schemes are much less efficient than encryption schemes due to the rejection sampling paradigm. We give a construction of comparable efficiency with lattice encryption that avoids sampling using structured secrets together with temporary keys. Structured secrets (and randoms) also improve existing lattice encryption schemes to nearly the same extreme efficiency. Our signature scheme allows the same parameters of any encryption schemes (a variation of the basic form is needed when the modulus is as small as 1-byte) and has comparable efficiency with our extreme encryption efficiency. For lightweight implementation, our techniques allow integrating of public-key encryption and signature in a simple circuit which only needs to do small integer additions as the main part of the computation.

In Chen-Cramer Crypto 2006 paper \cite{cc} algebraic geometric secret sharing schemes were proposed such that the ``Fundamental Theorem in Information-Theoretically Secure Multiparty Computation" by Ben-Or, Goldwasser and Wigderson \cite{BGW88} and Chaum, Crépeau and Damgård \cite{CCD88} can be established over constant-size base finite fields. These algebraic geometric secret sharing schemes defined by a curve of genus $g$ over a constant size finite field ${\bf F}_q$ is quasi-threshold in the following sense, any subset of $u \leq T-1$ players (non qualified) has no information of the secret and any subset of $u \geq T+2g$ players (qualified) can reconstruct the secret. It is natural to ask that how far from the threshold these quasi-threshold secret sharing schemes are? How many subsets of $u \in [T, T+2g-1]$ players can recover the secret or have no information of the secret? In this paper it is proved that almost all subsets of $u \in [T,T+g-1]$ players have no information of the secret and almost all subsets of $u \in [T+g,T+2g-1]$ players can reconstruct the secret when the size $q$ goes to the infinity and the genus satisfies $\lim \frac{g}{\sqrt{q}}=0$. Then algebraic geometric secretsharing schemes over large finite fields are asymptotically threshold in this case. We also analyze the case when the size $q$ of the base field is fixed and the genus goes to the infinity.

Ciet et al.(2006) proposed an elegant method for trading inversions for multiplications when computing [2] P+Q from two given points P and Q on elliptic curves of Weierstrass form. Motivated by their work, this paper proposes a fast algorithm for computing [4] P with only one inversion in affine coordinates. Our algorithm that requires 1I+ 8S+ 8M, is faster than two repeated doublings whenever the cost of one field inversion is more expensive than the cost of four field multiplications plus four field squarings (ie I> 4M+ 4S). It saves one field multiplication and one field squaring in comparison with the Sakai-Sakurai method (2001). Even better, for special curves that allow" a= 0"(or" b= 0") speedup, we obtain [4] P in affine coordinates using just 1I+ 5S+ 9M (or 1I+ 5S+ 6M, respectively).

Delegation of signing rights can be useful to promote effective resource sharing and smooth cooperation among participants in distributed systems, and in many situations, we often need restricted delegation such as one-timeness and unlinkability rather than simple full delegation. Particularly, one-timesness cannot be achieved just by deploying cryptographic measures, and one needs to resort to some form of tamper-proofness or the assistance from external cloud servers for ``key-disabling''. In this work, we extend the latter such that a delegatee can sign a message without the delegator's involvement with the assumption that there exists at least one honest cloud server with secure erasure to achieve one-timeness. In this setting, if the delegator just shares their signing key between the delegatee and cloud servers, it may be problematic. It is because in the worst case, the delegator cannot know whether or not a signing key theft occurred because the signatures generated illegally are indistinguishable from the ones generated legally. To solve this, first we propose an efficient one-time delegation scheme of Okamoto-Schnorr signing. Further we combine the basic delegation scheme with anonymous credentials such that the delegator can detect the signing key theft even if one-time delegation is broken while also achieving unlinkability for both the delegator and cloud servers. Further we show its application to an e-cash scheme, which can prevent double-spending.

This paper proposes various optimizations for lattice-based key-encapsulation mechanisms (KEM) using the Number Theoretic Transform (NTT) on the popular ARM Cortex-M4 microcontroller. Improvements come in the form of a faster code using more efficient modular reductions, small polynomial multiplications and more aggressive layer merging in the NTT but also reduced stack usage. We test those optimizations in software implementations of Kyber and NewHope, both round 2 candidates in the NIST post-quantum project and also NewHope-Compact, a recently proposed derivative of NewHope with smaller parameters. Our software is the first implementation of NewHope-Compact on Cortex-M4 and shows speed improvements over previous high-speed implementations on the same platform for Kyber and NewHope . Moreover, it gives a common framework to compare those algorithms with the same level of optimization. Our results show that NewHope-Compact is the faster algorithm, followed by Kyber and finally NewHope that seems to suffer from its large modulus and error distribution for small dimensions.

I describe a non-interactive transaction scheme for Mimblewimble protocol, so as to overcome the usability issue of the Mimblewimble wallet. With the Diffie–Hellman, we can use an Ephemeral Key shared between the sender and the receiver, a public nonce R is added to the output for that, removing the interactive cooperation procedure. And an additional one-time public key P' is used to lock the output to make it only spendable for the receiver, i.e. the owner of P'. Furtherly, to keep Mimblewimble privacy character, the Stealth Address is used in this new transaction scheme.

With the NIST Post quantum cryptography competition in final round, the importance of implementation security is highlighted in the latest call. In this regard, we report practical side-channel assisted message recovery attacks over embedded implementations of several post-quantum public key encryption (PKE) and key encapsulation mechanisms (KEM) based on the Learning With Errors (LWE) and Learning With Rounding (LWR) problem, which include three finalists and three semi-finalist candidates of the NIST standardization process. The proposed attacks target storage of the decrypted message in memory, a basic operation found in all libraries and typically unavoidable in any embedded implementation. We also identify interesting ciphertext malleability properties for LWE/LWR-based PKEs and exploit them to generalise proposed attack to different implementation choices as well as implementations protected with side-channel countermeasures such as shuffling and masking. All proposed attacks are validated on ARM Cortex-M4 microcontroller, targeting optimized open source implementations of PQC schemes using electromagnetic side-channel measurements.

Recently, Li and Micciancio (ePrint 2020/1533) have proposed a passive attack on the CKKS approximate homomorphic encryption (HE) scheme, which allows an adversary to query decryption on valid ciphertexts. In this paper, we discuss for which applications such attack is applicable, and introduce an extension of the HEaaN library. In addition, we investigate the mitigation strategies of other HE libraries that support the CKKS scheme including HElib, PALISADE, Lattigo and SEAL.

This paper presents an IND-CCA2 attack against the 1st- and 2nd-round versions of NTS-KEM, i.e., the versions before the update in December 2019. Our attack works against the 1st- and 2nd-round specifications, with a number of decapsulation queries upper-bounded by n &#8722; k and an advantage lower-bounded by roughly 0.5(n &#8722; k)t/n^2 , where n, k, and t stand for the code length, code dimension, and the designed decoding capacity, for all the three parameter sets of NTS-KEM. We found that the non-reference implementations are also vulnerable to our attack, even though there are bugs. There are also bugs in the reference implementations, but in a way invulnerable to our attack.

Smart grid has improved the security, efficiency of the power system and balanced the supply and demand by intelligent management, which enhanced stability and reliability of power grid. The key point to achieve them is real-time data and consume data sharing by using fine-grained policies. But it will bring the leakage of the privacy of the users and losing of control over data for data owners. The reported solutions can not give the best trade-off among the privacy protection, control over the data shared and confidentiality. In addition, they can not solve the problems of large computation overhead and dynamic management such as users’ revocation. This paper aims at these problems and proposes a decentralized attribute-based data sharing scheme. The proposed scheme ensures the secure sharing of data while removing the central authority and hiding user’s identity information. It uses attribute-based signcryption(ABSC) to achieve data confidentiality and authentication. Under this model, attribute-based encryption gives the access policies for users and keeps the data confidentiality, and the attribute-based signature is used for authentication of the primary ciphertextintegrity. It is more efficient than ”encrypt and then sign” or ”sign and then encrypt”. In addition, the proposed scheme enables user’s revocation and public verifiability. Under the random oracle model, the security and the unforgeability against adaptive chosen message attack are demonstrated.

Logical cryptanalysis, first introduced by Massacci in 2000, is a viable alternative to common algebraic cryptanalysis techniques over boolean fields. With XOR operations being at the core of many cryptographic problems, recent research in this area has focused on handling XOR clauses efficiently. In this paper, we investigate solving the point decomposition step of the index calculus method for prime degree extension fields $\mathbb{F}_{2^n}$, using SAT solving methods. We experimented with different SAT solvers and decided on using WDSat, a solver dedicated to this specific problem. We extend this solver by adding a novel breaking symmetry technique and optimizing the time complexity of the point decomposition step by a factor of $m!$ for the $(m+1)$\textsuperscript{th} Semaev's summation polynomial. While asymptotically solving the point decomposition problem with this method has exponential worst time complexity in the dimension $l$ of the vector space defining the factor base, experimental running times show that the the presented SAT solving technique is significantly faster than current algebraic methods based on Gröbner basis computation. For the values $l$ and $n$ considered in the experiments, the WDSat solver coupled with our breaking symmetry technique is up to 300 times faster then MAGMA's F4 implementation, and this factor grows with $l$ and $n$.

We propose single-trace side-channel attacks against lattice-based KEMs, the current candidates of the NIST's standardization project. More specifically, we analyze the message encoding in the encapsulation of lattice-based KEMs to obtain the ephemeral session keys, concluding that a single trace leakage allows a whole key recovery: our implementation on a ChipWhisperer UFO STM32F3 target board shows 100% success rates for Crystals-Kyber and Saber regardless of optimization level, and more than a 79% success rate for FrodoKEM. We further show that our attack methodologies are not restricted to the above algorithms but widely applicable to other NIST PQC candidates, including LAC, NewHope, NTRU Prime, and NTRU.

Paillier's scheme is a homomorphic public key encryption scheme which is widely used in practical. For instance, Paillier's scheme can be used in the data aggregation in smart grid. Damg$\mathring{a}$rd and Jurik generalized Paillier's scheme to reduce the ciphertext expansion factor. However, the decryption scheme of Damg$\mathring{a}$rd and Jurik's scheme is more complicated than Paillier's original scheme. In this paper, we propose a new generalization of Paillier's scheme and all the Paillier's schemes to our knowledge are special cases of our scheme. We propose a very simple decryption algorithm which is more efficient than other generalization algorithms. We prove that our generalized Paillier's scheme is IND-CPA secure. Our generalized Paillier's scheme can be used in smart grid instead of Paillier's scheme for higher flexibility.

Hardware security tokens have now been used for several decades to store cryptographic keys. When deployed, the security of the corresponding schemes fundamentally relies on the tamper-resistance of the tokens – a very strong assumption in practice. Moreover, even secure tokens, which are expensive and cumbersome, can often be subverted. We introduce a new cryptographic primitive called Encryption schemes with Password-protected Assisted Decryption (EPAD schemes), in which a user’s decryption key is shared between a user device (or token) on which no assumption is made, and an online server. The user shares a human-memorizable password with the server. To decrypt a ciphertext, the user launches, from a public computer, a distributed protocol with the device and the server, authenticating herself to the server with her password (unknown to the device); in such a way that her secret key is never reconstructed during the interaction. We propose a strong security model which guarantees that (1) for an efficient adversary to infer any information about a user’s plaintexts, it must know her password and have corrupted her device (secrecy is guaranteed if only one of the two conditions is fulfilled), (2) the device and the server are unable to infer any information about the ciphertexts they help to decrypt (even though they could together reconstruct the secret key), and (3) the user is able to verify that device and server both performed the expected computations. These EPAD schemes are in the password-only model, meaning that the user is not required to remember a trusted public key, and her password remains safe even if she is led to interact with a wrong server and a malicious device. We then give a practical pairing-based EPAD scheme. Our construction is provably secure under standard computational assumptions, using non-interactive proof systems which can be efficiently instantiated in the standard security model, i.e., without relying on the random oracle heuristic.

We present a principled technique for reducing the lattice and matrix size in some applications of Coppersmith's lattice method for finding roots of modular polynomial equations. Motivated by ideas from machine learning, it relies on extrapolating patterns from the actual behavior of Coppersmith's attack for smaller parameter sizes, which can be thought of as ``focus group'' testing. When applied to the small-exponent RSA problem, our technique reduces lattice dimensions and consequently running times, and hence can be applied to a wider range of exponents. Moreover, in many difficult examples our attack is not only faster but also more successful in recovering the RSA secret key. We include a discussion of subtleties concerning whether or not existing metrics (such as enabling condition bounds) are decisive in predicting the true efficacy of attacks based on Coppersmith's method. Finally, indications are given which suggest certain lattice basis reduction algorithms (such as Nguyen-Stehlé's L2) may be particularly well-suited for Coppersmith's method.

We present a sub-exponential forger by using a $k$-sum algorithm against the aggregate $\Gamma$-signature, which was proposed at AsiaCCS 2019 by Zhao. Our forger is a universal forger under a key-only attack and effective in the knowledge of secret key model. We also discuss the real impact of this attack in reality with Bitcoin applications. The discussions on the real impact of the attack also highlight the significant differences between the usage of individual signatures like EC-DSA and that of aggregate signatures in the blockchain systems like Bitcoin, which might be of independent interest and could bring forth interesting questions for future investigations.

We introduce Vetted Encryption (VE), a novel cryptographic primitive, which addresses the following scenario: a receiver controls, or vets, who can send them encrypted messages. We model this as a filter publicly checking ciphertext validity, where the overhead does not grow with the number of senders. The filter receives one public key for verification, and every user receives one personal encryption key. We present three versions: Anonymous, Identifiable, and Opaque VE (AVE, IVE and OVE), and concentrate on formal definitions, security notions and examples of instantiations based on preexisting primitives of the latter two. For IVE, the sender is identifiable both to the filter and the receiver, and we make the comparison with identity-based signcryption. For OVE, a sender is anonymous to the filter, but is identified to the receiver. OVE is comparable to group signatures with message recovery, with the important additional property of confidentiality of messages.

This article explores the use of elliptic curves with order 2r = 2 mod 4, which we call double-odd elliptic curves. This is a very large class, comprising about 1/4th of all curves over a given field. On such curves, we manage to define a prime order group with appropriate characteristics for building cryptographic protocols: - Element encoding is canonical, and verified upon decoding. For a 2n-bit group (with n-bit security), encoding size is 2n + 1 bits, i.e. as good as compressed points on classic prime order curves. - Unified and complete formulas allow secure and efficient computations in the group. - Efficiency is on par with twisted Edwards curves, and in some respects slightly better; e.g. half of double-odd curves have formulas for computing point doublings with only six multiplications (down to 1M+5S per doubling on some curves). We describe here various formulas and discuss implementations. We also define two specific parameter choices for curves with 128-bit security, called do255e and do255s. Our own implementations on 64-bit x86 (Coffee Lake) and low-end ARM Cortex M0+ achieve generic point multiplication in 76696 and 2.19 million cycles, respectively, with curve do255e.

Our main result is a quantum public-key encryption scheme based on the Extrapolated Di- hedral Coset problem (EDCP) which is equivalent, under quantum polynomial-time reductions, to the Learning With Errors (LWE) problem. For limited number of public keys (roughly linear in the security parameter), the proposed scheme is information-theoretically secure. For poly- nomial number of public keys, breaking the scheme is as hard as solving the LWE problem. The public keys in our scheme are quantum states of size Õ(n) qubits. The key generation and decryption algorithms require Õ(n) qubit operations while the encryption algorithm takes O(1) qubit operations.

Following recent comments in a NIST document related to threshold cryptographic standards, we examine the case of thresholdizing the HashEdDSA signature scheme. This is a deterministic signature scheme based on Edwards elliptic curves. Unlike DSA, it has a Schnorr like signature equation, which is an advantage for threshold implementations, but it has the disadvantage of having the ephemeral secret obtained by hashing the secret key and the message. We show that one can obtain relatively efficient implementations of threshold HashEdDSA with no modifications to the behaviour of the signing algorithm; we achieve this using a doubly-authenticated bit (daBit) generation protocol tailored for Q2 access structures, that is more efficient than prior work. However, if one was to modify the standard algorithm to use an MPC-friendly hash function, such as Rescue, the performance becomes very fast indeed.

Nowadays, information is known as the main asset of each organization, which causes data generation to be exponentially increasing. Hence, different capacity issues and requirements show up with it, e.g. storage and maintenance of generating data, searching among them, and analyzing them. Cloud computing is one of the common technologies used to meet these requirements. Popularity of this technology is extremely growing as it can be used to handle high amount of data in a cost efficient and highly available (anytime and anywhere) manner. However, there are still extensive security challenges (e.g. data confidentiality) with this technology. Cryptography is one of the main methods used to fulfill privacy preserving of people and organizations. Encryption methods can impressively keep data private, so it is not possible to search among encrypted messages in order to retrieve information, after applying traditional encryption. Searchable encryption can enable searching among encrypted data and overcome this shortage. However, much more research is required to enable whole data searching while proper level of security would be achieved for these systems. In this paper, a technique to perform searching by the third party is introduced. When a number of nodes are interacting and some of them may upload malicious documents, this technique can be useful. Furthermore, document categorization is another application of the referred scheme.

This paper aims to address the open problem, namely, to find new techniques to design and prove security of supersingular isogeny-based authenticated key exchange (AKE) protocols against the widest possible adversarial attacks, raised by Galbraith in 2018. Concretely, we present two AKEs based on a double-key PKE in the supersingular isogeny setting secure in the sense of CK$^+$, one of the strongest security models for AKE. Our contributions are summarised as follows. Firstly, we propose a strong $\textsf{OW-CPA}$ secure PKE, $\mathsf{2PKE_{sidh}}$, based on SI-DDH assumption. By applying modified Fujisaki-Okamoto transformation, we obtain a $[\textsf{OW-CCA}, \textsf{OW-CPA}]$ secure KEM, $\mathsf{2KEM_{sidh}}$. Secondly, we propose a two-pass AKE, $\textsf{SIAKE}_2$, based on SI-DDH assumption, using $\mathsf{2KEM_{sidh}}$ as a building block. Thirdly, we present a modified version of $\mathsf{2KEM_{sidh}}$ that is secure against leakage under the 1-Oracle SI-DH assumption. Using the modified $\mathsf{2KEM_{sidh}}$ as a building block, we then propose a three-pass AKE, $\textsf{SIAKE}_3$, based on 1-Oracle SI-DH assumption. Finally, we prove that both $\textsf{SIAKE}_2$ and $\textsf{SIAKE}_3$ are CK$^+$ secure in the random oracle model and supports arbitrary registration. We also provide an implementation to illustrate the efficiency of our schemes. Our schemes compare favourably against existing isogeny-based AKEs. To the best of our knowledge, they are the first of its kind to offer security against arbitrary registration, wPFS, KCI and MEX simultaneously. Regarding efficiency, our schemes outperform existing schemes in terms of bandwidth as well as CPU cycle count.

Side-channel attacks targeting cryptography may leak only partial or indirect information about the secret keys. There are a variety of techniques in the literature for recovering secret keys from partial information. In this tutorial, we survey several of the main families of partial key recovery algorithms for RSA, (EC)DSA, and (elliptic curve) Diffie-Hellman, the public-key cryptosystems in common use today. We categorize the known techniques by the structure of the information that is learned by the attacker, and give simplified examples for each technique to illustrate the underlying ideas.

In this work various approaches for constant time conditional branching in Montgomery ladder have been studied. A previous method appearing in a code for implementing X25519 has been formalized algorithmically. This algorithm is based on a conditional select operation. We consider a variant of this algorithm which groups together operations in a more convenient manner. Further, we provide a new implementation of the conditional select operation using the cmov operation such that cmov works only on registers. This provides a better guarantee of constant time behavior.

We present a generalized inner product argument and demonstrate its applications to pairing-based languages. We apply our generalized argument to proving that an inner pairing product is correctly evaluated with respect to committed vectors of $n$ source group elements. With a structured reference string (SRS), we achieve a logarithmic-time verifier whose work is dominated by $6 \log n$ target group exponentiations. Proofs are of size $6 \log n$ target group elements, computed using $6n$ pairings and $4n$ exponentiations in each source group. We apply our inner product arguments to build the first polynomial commitment scheme with succinct (logarithmic) verification, $O(\sqrt{d})$ prover complexity for degree $d$ polynomials (not including the cost to evaluate the polynomial), and a CRS of size $O(\sqrt{d})$. Concretely, this means that for $d=2^{28}$, producing an evaluation proof in our protocol is $76\times$ faster than doing so in the KZG commitment scheme, and the CRS in our protocol is $1,000\times$ smaller: $13$MB vs $13$GB for KZG. This gap only grows as the degree increases. Our polynomial commitment scheme is applicable to both univariate and bivariate polynomials. As a second application, we introduce an argument for aggregating $n$ $\mathsf{Groth16}$ zkSNARKs into an $O(\log n)$ sized proof. Our protocol is significantly more efficient than aggregating these SNARKs via recursive composition (BCGMMW20): we can aggregate about $130,000$ proofs in $25$min, while in the same time recursive composition aggregates just $90$ proofs. Finally, we show how to apply our aggregation protocol to construct a low-memory SNARK for machine computations. For a computation that requires time $T$ and space $S$, our SNARK produces proofs in space $\tilde{\mathcal{O}}(S+T)$, which is significantly more space efficient than a monolithic SNARK, which requires space $\tilde{\mathcal{O}}(S \cdot T)$.

This paper presents the first attribute-based signature (ABS) scheme supporting signing policies representable by Turing machines (TM), based on well-studied computational assumptions. Our work supports arbitrary TMs as signing policies in the sense that the TMs can accept signing attribute strings of unbounded polynomial length and there is no limit on their running time, description size, or space complexity. Moreover, we are able to achieve input-specific running time for the signing algorithm. All other known expressive ABS schemes could at most support signing policies realizable by either arbitrary polynomial-size circuits or TMs having a pre-determined upper bound on the running time. Consequently, those schemes can only deal with signing attribute strings whose lengths are a priori bounded, as well as suffers from the worst-case running time problem. On a more positive note, for the first time in the literature, the signature size of our ABS scheme only depends on the size of the signed message and is completely independent of the size of the signing policy under which the signature is generated. This is a significant achievement from the point of view of communication efficiency. Our ABS construction makes use of indistinguishability obfuscation (IO) for polynomial-size circuits and certain IO-compatible cryptographic tools. Note that, all of these building blocks including IO for polynomial-size circuits are currently known to be realizable under well-studied computational assumptions.

Cloud computing and cloud storage are among the most efficient technologies for storing and processing metadata. But there are many privacy concerns within this domain. Most of the challenges are coming from trusted or semi trusted cloud servers where some computations must be applied to high confidential data. Data encryption can solve some confidentiality issues on the cloud but it is not easy to provide privacy preserving data processing services such as searching a query over encrypted data. On the other hand implementing searchable encryption algorithms in cloud infrastructure helps providing data confidentiality and privacy preserving data processing and can provide searching capability as well, which is the most important step of selecting a document. First in this article, some injection attacks against searchable public key encryption schemes are described. To be more specific message injection attack and index injection attack are applied against PEKS and PERKS schemes. Afterwards, two new schemes are proposed that are secure against them and are based of dPEKS and SAE-I. Finally, efficiency and security of proposed schemes are analyzed, and some implementation issues were discussed.

In this short note, we explain how to reduce the time to compute all $N$ proofs in the Pointproofs vector commitment (VC) scheme by Gorbunov et al., from $O(N^2)$ time to $O(N\log{N})$. The key ingredient is representing the computation of all proofs as a product between a Toeplitz matrix and the committed vector, which can be computed fast using Discrete Fourier Transforms (DFTs). We quickly prototype our algorithm in C++ and show it is much faster than the naive algorithm for computing all proofs in Pointproofs.

In the past few years, significant progresses on homomorphic encryption (HE) have been made toward both theory and practice. The most promising HE schemes are based on the hardness of the Learning With Errors (LWE) problem or its ring variant (RLWE). In this work, we present new conversion algorithms which switch between different (R)LWE-based HE schemes to take advantages of them. Specifically, we present and combine three ideas to improve the key-switching procedure between LWE ciphertexts, transformation from LWE to RLWE, as well as packing of multiple LWE ciphertexts in a single RLWE encryption. Finally, we demonstrate an application of building a secure channel between a client and a cloud server with lightweight encryption, low communication cost, and capability of homomorphic computation.

Bernstein et al. recently introduced a system ``Elligator'' for steganographic key distribution. At the heart of their construction are invertible maps between a finite field $\mathbb{F}$ and an elliptic curve $\mathcal{E}$ over $\mathbb{F}$. There are two such maps, called $\phi$ in the ``Elligator 1'' system, and $\psi$ in the ``Elligator 2'' system. Here we show two ways to construct hash functions from $\psi$ which are indifferentiable from a random oracle. Because $\psi$ is relatively simple, our analyses are also simple. One of our constructions uses a novel ``wallpapering'' approach, whereas the other uses the hash-twice-and-add approach of Brier et al.

In this paper we construct and consider a signature scheme with evolving secret key, where there is used Type 3 pairing. The idea is based on some properties of binary trees, with a number of leaves being the same as a number of time periods in the scheme. This lets us to gain such conditions, that allows to prove the forward-security of the considered scheme in the random oracle model. The proof is conducted by reducing the security of the scheme to the difficulty of solving a certain counterpart of the Weak $\ell$-th Bilinear Diffie-Hellman Inversion problem. In addition to that, we construct an interactive signature scheme with evolving private key and justify that it is forward-secure blind scheme.

Multi-signatures are used to attest that a fixed collection of $n$ parties, represented by their respective public keys, have all signed a given message. An emerging application of multi-signatures is to be found in consensus protocols to attest that a qualified subset of a global set of $n$ validators have reached agreement. In this paper, we point out that the traditional security model for multi-signatures is insufficient for this new application, as it assumes that every party in the set participates in the multi-signature computation phase and is honest. None of these assumptions hold in the typical adversarial scenarios in consensus protocols (aka. byzantine agreement). We address this by introducing a new multi-signature variant called robust subgroup multi-signatures, whereby any eligible subgroup of signers from the global set can produce a multi-signature on behalf of the group, even in the presence of a byzantine adversary. We provide syntax and security definitions for the new variant. We argue that existing unforgeability security proofs for multi-signatures do not carry over to the consensus setting; a consequence of this observation is that many multi-signature based consensus protocols lack a rigorous security proof for correctness. To remedy this we propose several constructions which we prove secure under widely held cryptographic assumptions using our newly introduced formal definitions and also improve upon multi-signature computation time. Finally, we report on benchmarks from a proof-of-concept implementation.

Trapdoor DDH groups are an appealing cryptographic primitive where DDH instances are hard to solve unless provided with additional information (i.e., a trapdoor). In this paper, we introduce a new trapdoor DDH group construction using pairings and isogenies of supersingular elliptic curves. The construction solves all shortcomings of previous constructions as identified by Seurin (RSA 2013). We also present partial attacks on a previous construction due to Dent--Galbraith, and we provide a formal security definition of the related notion of ``trapdoor pairings''.

There are lots of applications of inner-product functional encryption (IPFE). In this paper, we consider two important extensions of it. One is to enhance IPFE with access control such that only users with a pre-defined identity are allowed to compute the inner product, referred as identity-based inner-product functional encryption (IBIPFE). We formalize the definition of IBIPFE, and propose the first adaptive-secure IBIPFE scheme from Decisional Bilinear Diffie-Hellman (DBDH) assumption. In an IBIPFE scheme, the ciphertext is related to a vector $\vec{x}$ and a new parameter, identity ID. Each secret key is also related to a vector $\vec{y}$ and an identity ID'. The decryption algorithm will output the inner-product value $<\vec{x}, \vec{y}>$ only if ID $=$ ID'. The other extension is to make IBIPFE leakage resilient. We consider the bounded-retrieval model (BRM) in which an adversary can learn at most $l$ bits information from each secret key. Here, $l$ is the leakage bound determined by some external parameters, and it can be set arbitrarily large. After giving the security definition of leakage-resilient IBIPFE, we extend our IBIPFE scheme into a leakage-resilient IBIPFE scheme in the BRM by hash proof system (HPS).

A Gr¥"{o}bner basis algorithm computes a good basis for an ideal of a polynomial ring and appears in various situations of cryptography. In particular, it has been used in the security analysis of multivariate public key cryptography (MPKC), and has been studied for a long time; however, it is far from a complete understanding. We consider the algebraic attack using a Gr¥"{o}bner basis algorithm for a new multivariate encryption scheme proposed by Jiahui Chen et al. at Theoretical Computer Science 2020. Their idea to construct a new scheme was to use the minus and plus modifiers to prevent known attacks, such as linearization attack. Moreover, they discussed to have a resistance to the algebraic attack using a Gr¥"{o}bner basis algorithm. However, in our experiments, the algebraic attack breaks their claimed 80- and 128-bit security parameters in reasonable times. It is necessary to understand whether their scheme can avoid such an attack by introducing a slight modification. In this paper, we theoretically describe why the algebraic attack breaks their scheme and give a precise complexity of the algebraic attack. As a result, we demonstrate that the algebraic attack can break the claimed 80- and 128-bit security parameters in the complexities of approximately 25 and 32 bits, respectively. Moreover, based on our complexity estimation of the algebraic attack, we conclude that Chen et al.'s scheme is not practical.