One-time signatures (OTS) are called one-time, because the accompanying reductions only guarantee security under single-message attacks. However, this does not imply that efficient attacks are possible under two-message attacks. Especially in the context of hash-based OTS (which are basic building blocks of recent standardization proposals) this leads to the question if accidental reuse of a one-time key pair leads to immediate loss of security or to graceful degradation. In this work we analyze the security of the most prominent hash-based OTS, Lamport's scheme, its optimized variant, and WOTS, under different kinds of two-message attacks. Interestingly, it turns out that the schemes are still secure under two message attacks, asymptotically. However, this does not imply anything for typical parameters. Our results show that for Lamport's scheme, security only slowly degrades in the relevant attack scenarios and typical parameters are still somewhat secure, even in case of a two-message attack. As we move on to optimized Lamport and its generalization WOTS, security degrades faster and faster, and typical parameters do not provide any reasonable level of security under two-message attacks.

We investigate the subset-resilience problem, defined in 2002 by Reyzin and Reyzin to analyze their HORS signature scheme. We show that textbook HORS is insecure against adaptive attacks, and present a practical attack based on a greedy algorithm. We also describe weak messages for HORS, that map to smaller subsets than expected, and are thus easier to cover. This leads to an improved attack against HORS and to an improved classical attack against the signature scheme SPHINCS, of complexity $2^{270}$ instead of $2^{277}$. We propose the PRNG to obtain a random subset construction (PORS), which avoids weak messages, for a tiny computational overhead. We adapt PORS to SPHINCS to also deterministically select the HORST instance that is used to sign the input message. This new construction reduces the attack surface and increases the security level, improving the security of SPHINCS by 67 bits against classical attacks and 33 bits against quantum attacks. A version of SPHINCS using our PORS construction can work with smaller parameters that reduce the signature size by 4616 bytes and speed up signature and verification, for the same 128-bit post-quantum security as the original SPHINCS.

Structure-Preserving Signatures (SPSs) are an important tool for the design of modular cryptographic protocols. It has been proven that such schemes in the most efficient Type-3 bilinear group setting have a lower bound of 3-element signatures, which must include elements from both base groups, and a verification overhead of at least 2 Pairing-Product Equations (PPEs). Very recently, Ghadafi (ESORICS 2017) showed that by restricting the message space to the set of Diffie-Hellman pairs (which does not hinder applicability of the schemes), some of the existing lower bounds for the single message case can be circumvented. However, the case of signing multiple messages, which is required for many applications, was left as an open problem since the techniques used for signing single messages do not seem to lend themselves to the multi-message setting. In this work we investigate this setting and answer the question in the affirmative. We construct schemes that sign vectors of messages and which yield shorter signatures than optimal schemes for vectors of unilateral messages. More precisely, we construct 2 fully randomiazble schemes that sign vectors of Diffie-Hellman pairs yielding signatures consisting of only 2 elements regardless of the size of the vector signed. We also construct a unilateral scheme that signs a pair of messages yielding signatures consisting of 3 elements from the shorter base group. All of our schemes require a single PPE for verification (not counting the cost of verifying the well-formedness of the messages). Thus, all of our schemes compare favourably to all existing schemes with respect to signature size and verification overhead. Even when considering single messages, our first 2 schemes compare favourably to the best existing schemes in many aspects including the verification overhead and the key size.

The American signature standards DSA and ECDSA, as well as their Russian and Chinese counterparts GOST 34.10 and SM2, are of utmost importance in the current security landscape. The mentioned schemes are all rooted in the Elgamal signature scheme and use a hash function and a cyclic group as building blocks. Unfortunately, authoritative security guarantees for the schemes are still due: All existing positive results on their security use aggressive idealization approaches, like the generic group model, leading to debatable overall results. In this work we conduct security analyses for a set of classic signature schemes, including the ones mentioned above, providing positive results in the following sense: If the hash function is modeled as a random oracle, and the signer issues at most one signature per message, then the schemes are unforgeable if and only if they are key-only unforgeable, where the latter security notion captures that the adversary has access to the verification key but not to sample signatures. Put differently, for the named signature schemes, in the one-signature-per-message setting the signature oracle is redundant.

We propose two optimal representations for the elements of trace zero subgroups of twisted Edwards curves. For both representations, we provide efficient compression and decompression algorithms. The efficiency of the algorithm is compared with the efficiency of similar algorithms on elliptic curves in Weierstrass form.

We consider trace-zero subgroups of elliptic curves over a degree three field extension. The elements of these groups can be represented in compressed coordinates, i.e. via the two coefficients of the line that passes through the point and its two Frobenius conjugates. In this paper we give the first algorithm to compute scalar multiplication in the degree three trace-zero subgroup using these coordinates.

There is a recent trend in cryptography to construct protocols based on the hardness of computing isogenies between supersingular elliptic curves. Two prominent examples are Jao-De Feo's key exchange protocol and the resulting encryption scheme by De Feo-Jao-Plût. One particularity of the isogeny problems underlying these protocols is that some additional information is given in input, namely the image of some torsion points with order coprime to the isogeny. This additional information was used in several active attacks against the protocols but the current best passive attacks on the protocols make no use of it at all. In this paper, we provide new algorithms that exploit the additional information provided in isogeny protocols to speed up the resolution of the underlying problems. Our techniques lead to a heuristic polynomial-time key recovery on a non-standard variant of De Feo-Jao-Plût's protocols in a plausible attack model. This shows that at least some isogeny problems are easier to solve when additional information is leaked.

Selective opening (SO) security refers to adversaries that receive a number of ciphertexts and, after having corrupted a subset of the senders (thus obtaining the plaintexts and the senders' random coins), aim at breaking the security of remaining ciphertexts. So far, very few public-key encryption schemes are known to provide simulation-based selective opening (SIM-SO-CCA2) security under chosen-ciphertext attacks and most of them encrypt messages bit-wise. The only exceptions to date rely on all-but-many lossy trapdoor functions (as introduced by Hofheinz; Eurocrypt'12) and the Composite Residuosity assumption. In this paper, we describe the first all-but-many lossy trapdoor function with security relying on the presumed hardness of the Learning-With-Errors problem (LWE) with standard parameters. Our construction exploits homomorphic computations on lattice trapdoors for lossy LWE matrices. By carefully embedding a lattice trapdoor in lossy public keys, we are able to prove SIM-SO-CCA2 security under the LWE assumption. As a result of independent interest, we describe a variant of our scheme whose multi-challenge CCA2 security tightly relates to the hardness of LWE and the security of a pseudo-random function.

Revoking corrupted users is a desirable functionality for cryptosystems. Since Boldyreva, Goyal, and Kumar (ACM CCS 2008) proposed a notable result for scalable revocation method in identity-based encryption (IBE), several works have improved either the security or the efficiency of revocable IBE (RIBE). Currently, all existing scalable RIBE schemes that achieve adaptively security against decryption key exposure resistance (DKER) can be categorized into two groups; either with long public parameters or over composite-order bilinear groups. From both practical and theoretical points of views, it would be interesting to construct adaptively secure RIBE scheme with DKER and short public parameters in prime-order bilinear groups. In this paper, we address this goal by using Seo and Emura's technique (PKC 2013), which transforms the Waters IBE to the corresponding RIBE. First, we identify necessary requirements for the input IBE of their transforming technique. Next, we propose a new IBE scheme having several desirable properties; satisfying all the requirements for the Seo-Emura technique, constant-size public parameters, and using prime-order bilinear groups. Finally, by applying the Seo-Emura technique, we obtain the first adaptively secure RIBE scheme with DKER and constant-size public parameters in prime-order bilinear groups. We also discuss some extensions of the proposed RIBE scheme.

Beyond their security guarantees under well-studied assumptions, algebraic pseudo-random functions are motivated by their compatibility with efficient zero-knowledge proof systems, which is useful in a number of privacy applications like digital cash. We consider the problem of proving the correct evaluation of lattice-based PRFs based on the Learning-With-Rounding (LWR) problem introduced by Banerjee et al. (Eurocrypt'12). Namely, we are interested zero-knowledge arguments of knowledge of triples $(y,k,x)$ such that $y=F_k(x)$ is the correct evaluation of a PRF for a secret input $x$ and a committed key $k$. While analogous statements admit efficient zero-knowledge protocols in the discrete logarithm setting, they have never been addressed in lattices so far. We provide such arguments for the key homomorphic PRF of Boneh et al. (Crypto'13) and the generic PRF implied by the LWR-based pseudo-random generator. As an application of our ZK arguments, we design the first compact e-cash system based on lattice assumptions. By ``compact'', we mean that the complexity is at most logarithmic in the value of withdrawn wallets. Our system can be seen as a lattice-based analogue of the first compact e-cash construction due to Camenisch, Hohenberger and Lysyanskaya (Eurocrypt'05).

The Rényi divergence is a measure of divergence between distributions. It has recently found several applications in lattice-based cryptography. The contribution of this paper is twofold. First, we give theoretic results which renders it more efficient and easier to use. This is done by providing two lemmas, which give tight bounds in very common situations { for distributions that are tailcut or have a bounded relative error. We then connect the Rényi divergence to the max-log distance. This allows the Rényi divergence to indirectly benefit from all the advantages of a distance. Second, we apply our new results to five practical usecases. It allows us to claim 256 bits of security for a floating-point precision of 53 bits, in cases that until now either required more than 150 bits of precision or were limited to 100 bits of security: rejection sampling, trapdoor sampling (61 bits in this case) and a new sampler by Micciancio and Walter. We also propose a new and compact approach for table-based sampling, and squeeze the standard deviation of trapdoor samplers by a factor that provides a gain of 30 bits of security in practice.

This paper considers efficient scalar multiplication of elliptic curves over binary fields with a twofold purpose. Firstly, we derive the most efficient $3P$ formula in $\lambda$-projective coordinates and $5P$ formula in both affine and $\lambda$-projective coordinates. Secondly, extensive experiments have been conducted to test various multi-base scalar multiplication methods (e.g., greedy, ternary/binary, multi-base NAF, and tree-based) by integrating our fast formulas. The experiments show that our $3P$ and $5P$ formulas had an important role in speeding up the greedy, the ternary/binary, the multi-base NAF, and the tree-based methods over the NAF method. We also establish an efficient $3P$ formula for Koblitz curves and use it to construct an improved set for the optimal pre-computation of window TNAF.

Time and again, attribute-based encryption has been shown to be the natural cryptographic tool for building various types of conditional access systems with far-reaching applications, but the deployment of such systems has been very slow. A central issue is the lack of an encryption scheme that can operate on sensitive data very efficiently and, at the same time, provides features that are important in practice. This paper proposes the first fully secure ciphertext-policy and key-policy ABE schemes based on a standard assumption on Type-III pairing groups, which do not put any restriction on policy type or attributes. We implement our schemes along with several other prominent ones using the Charm library, and demonstrate that they perform better on almost all parameters of interest.

Predicates are used in cryptography as a fundamental tool to control the disclosure of secrets. However, how to embed a particular predicate into a cryptographic primitive is usually not given much attention. In this work, we formalize the idea of encoding predicates as arithmetic circuits and observe that choosing the right encoding of a predicate may lead to an improvement in many aspects such as the efficiency of a scheme or the required hardness assumption. In particular, we develop two predicate encoding schemes with different properties and construct cryptographic primitives that benefit from these: verifiable random functions (VRFs) and predicate encryption (PE) schemes. - We propose two VRFs on bilinear maps. Both of our schemes are secure under a non-interactive $Q$-type assumption where $Q$ is only poly-logarithmic in the security parameter, and they achieve either a poly-logarithmic verification key size or proof size. This is a significant improvement over prior works, where all previous schemes either require a strong hardness assumption or a large verification key and proof size. - We propose a lattice-based PE scheme for the class of \emph{multi-dimensional equality} (MultEq) predicates. This class of predicate is expressive enough to capture many of the appealing applications that motivates PE schemes. Our scheme achieves the best in terms of the required approximation factor for LWE (we only require $\poly(\lambda)$) and the decryption time. In particular, all existing PE schemes that support the class of MultEq predicates either require a subexponential LWE assumption or an exponential decryption time (in the dimension of the MultEq predicates).

In light of security challenges that have emerged in a world with complex networks and cloud computing, the notion of functional encryption has recently emerged. In this work, we show that in several applications of functional encryption (even those cited in the earliest works on functional encryption), the formal notion of functional encryption is actually \emph{not} sufficient to guarantee security. This is essentially because the case of a malicious authority and/or encryptor is not considered. To address this concern, we put forth the concept of \emph{verifiable functional encryption}, which captures the basic requirement of output correctness: even if the ciphertext is maliciously generated (and even if the setup and key generation is malicious), the decryptor is still guaranteed a meaningful notion of correctness which we show is crucial in several applications. We formalize the notion of verifiable function encryption and, following prior work in the area, put forth a simulation-based and an indistinguishability-based notion of security. We show that simulation-based verifiable functional encryption is unconditionally impossible even in the most basic setting where there may only be a single key and a single ciphertext. We then give general positive results for the indistinguishability setting: a general compiler from any functional encryption scheme into a verifiable functional encryption scheme with the only additional assumption being the Decision Linear Assumption over Bilinear Groups (DLIN). We also give a generic compiler in the secret-key setting for functional encryption which maintains both message privacy and function privacy. Our positive results are general and also apply to other simpler settings such as Identity-Based Encryption, Attribute-Based Encryption and Predicate Encryption. We also give an application of verifiable functional encryption to the recently introduced primitive of functional commitments. Finally, in the context of indistinguishability obfuscation, there is a fundamental question of whether the correct program was obfuscated. In particular, the recipient of the obfuscated program needs a guarantee that the program indeed does what it was intended to do. This question turns out to be closely related to verifiable functional encryption. We initiate the study of verifiable obfuscation with a formal definition and construction of verifiable indistinguishability obfuscation.

Server-Aided Verification (SAV) is a method that can be employed to speed up the process of verifying signatures by letting the verifier outsource part of its computation load to a third party. Achieving fast and reliable verification under the presence of an untrusted server is an attractive goal in cloud computing and internet of things scenarios. In this paper, we describe a simple framework for SAV where the interaction between a verifier and an untrusted server happens via a single-round protocol. We propose a security model for SAV that refines existing ones and includes the new notions of SAV-anonymity and extended unforgeability. In addition, we apply our definitional framework to provide the first generic transformation from any signature scheme to a single-round SAV scheme that incorporates verifiable computation. Our compiler identifies two independent ways to achieve SAV-anonymity: computationally, through the privacy of the verifiable computation scheme, or unconditionally, through the adaptibility of the signature scheme. Finally, we define three novel instantiations of SAV schemes obtained through our compiler. Compared to previous works, our proposals are the only ones which simultaneously achieve existential unforgeability and soundness against collusion.

This work deals with the energy-efficient, high-speed and high-security implementation of elliptic curve scalar multiplication, elliptic curve Diffie-Hellman (ECDH) key exchange and elliptic curve digital signatures on embedded devices using FourQ and incorporating strong countermeasures to thwart a wide variety of side-channel attacks. First, we set new speed records for constant-time curve-based scalar multiplication, DH key exchange and digital signatures at the 128-bit security level with implementations targeting 8, 16 and 32-bit microcontrollers. For example, our software computes a static ECDH shared secret in 6.9 million cycles (or 0.86 seconds @8MHz) on a low-power 8-bit AVR microcontroller which, compared to the fastest Curve25519 and genus-2 Kummer implementations on the same platform, offers 2x and 1.4x speedups, respectively. Similarly, it computes the same operation in 496 thousand cycles on a 32-bit ARM Cortex-M4 microcontroller, achieving a factor-2.9 speedup when compared to the fastest Curve25519 implementation targeting the same platform. A similar speed performance is observed in the case of digital signatures. Second, we engineer a set of side-channel countermeasures taking advantage of FourQ's rich arithmetic and propose a secure implementation that offers protection against a wide range of sophisticated side-channel attacks, including differential power analysis (DPA). Despite the use of strong countermeasures, the experimental results show that our FourQ software is still efficient enough to outperform implementations of Curve25519 that only protect against timing attacks. Finally, we perform a differential power analysis evaluation of our software running on an ARM Cortex-M4, and report that no leakage was detected with up to 10 million traces. These results demonstrate the potential of deploying FourQ on low-power applications such as protocols for the Internet of Things.

Most Multivariate Quadratic (MQ) signature schemes have a very large public key, which makes them unsuitable for many applications, despite attractive features such as speed and small signature sizes. In this paper we introduce a modification of the Unbalanced Oil and Vinegar (UOV) signature scheme that has public keys which are an order of magnitude smaller than other MQ signature schemes. The main idea is to choose UOV keys over the smallest field F2 in order to achieve small keys, but to lift the keys to a large extension field, where solving the MQ problem is harder. The resulting Lifted UOV signature scheme is very competitive with other post-quantum signature schemes in terms of key sizes, signature sizes and speed.

We show how to obfuscate a large and expressive class of programs, which we call compute-and-compare programs, under the learning-with-errors (LWE) assumption. Each such program $CC[f,y]$ is parametrized by an arbitrary polynomial-time computable function $f$ along with a target value $y$ and we define $CC[f,y](x)$ to output $1$ if $f(x)=y$ and $0$ otherwise. In other words, the program performs an arbitrary computation $f$ and then compares its output against a target $y$. Our obfuscator satisfies distributional virtual-black-box security, which guarantees that the obfuscated program does not reveal any partial information about the function $f$ or the target value $y$, as long as they are chosen from some distribution where $y$ has sufficient pseudo-entropy given $f$. We also extend our result to multi-bit compute-and-compare programs $MBCC[f,y,z](x)$ which output a message $z$ if $f(x)=y$. Compute-and-compare programs are powerful enough to capture many interesting obfuscation tasks as special cases. This includes obfuscating conjunctions, and therefore we improve on the prior work of Brakerski et al. (ITCS '16) which constructed a conjunction obfuscator under a non-standard "entropic" ring-LWE assumption, while here we obfuscate a significantly broader class of programs under standard LWE. We show that our obfuscator has several interesting applications. For example, we can take any encryption scheme and publish an obfuscated plaintext equality tester that allows users to check whether an arbitrary ciphertext encrypts some target value $y$; as long as $y$ has sufficient pseudo-entropy this will not harm semantic security. We can also use our obfuscator to generically upgrade attribute-based encryption to predicate encryption with one-sided attribute-hiding security, as well as witness encryption to indistinguishability obfuscation which is secure for all null circuits. Furthermore, we show that our obfuscator gives new circular-security counter-examples for public-key bit encryption and for unbounded length key cycles. Our result uses the graph-induced multi-linear maps of Gentry, Gorbunov and Halevi (TCC '15), but only in a carefully restricted manner which is provably secure under LWE. Our technique is inspired by ideas introduced in a recent work of Goyal, Koppula and Waters (EUROCRYPT '17) in a seemingly unrelated context.

Proxy re-encryption (PRE) is a cryptographic primitive introduced by Blaze, Bleumer and Strauss to provide delegation of decryption rights. PRE allows re-encryption of a ciphertext intended for Alice (delegator) to a ciphertext for Bob (delegatee) via a semi-honest proxy, who should not learn anything about the underlying message. In 2003, Al-Riyami and Patterson introduced the notion of certificateless public key cryptography which offers the advantage of identity-based cryptography without suffering from the key escrow problem. The existing certificateless PRE (CLPRE) schemes rely on costly bilinear pairing operations. In ACM ASIA-CCS SCC 2015, Srinivasan et al. proposed the first construction of a certificateless PRE scheme without resorting to pairing in the random oracle model. However, in this work, we demonstrate a flaw in the CCA-security proof of their scheme. Also, we present the first construction of a CLPRE scheme without pairing which meets CCA security under the computational Diffie-Hellman hardness assumption in the random oracle model.

Gentry’s bootstrapping technique is the most famous method of obtaining fully homomorphic encryption. In previous work I proposed a fully homomorphic encryption without bootstrapping which has the weak point in the enciphering function. In this paper I propose the improved fully homomorphic public-key encryption scheme on non-associative octonion ring over finite field without bootstrapping technique. The plaintext p consists of two sub-plaintext u and v. The proposed fully homomorphic public-key encryption scheme is immune from the “p and -p attack”. The cipher text consists of three sub-cipher texts. As the scheme is based on computational difficulty to solve the multivariate algebraic equations of high degree while the almost all multivariate cryptosystems proposed until now are based on the quadratic equations avoiding the explosion of the coefficients. Because proposed fully homomorphic encryption scheme is based on multivariate algebraic equations with high degree or too many variables, it is against the Gröbner basis attack, the differential attack, rank attack and so on.

Digital signatures constructed solely from hash functions offer competitive signature sizes and fast signing and verifying times. Moreover, the security of hash functions against a quantum adversary is believed to be well understood. This means that hash-based signatures are strong candidates for standard use in a post-quantum world. The Leighton-Micali signature scheme (LMS) is one such scheme being considered for standardization. However all systematic analyses of LMS have only considered a classical adversary. In this work we close this gap by showing a proof of the security of LMS in the quantum random-oracle model. Our results match the bounds imposed by Grover's search algorithm within a constant factor, and remain tight in the multi-user setting.

Commonly used digital signature schemes have a limited lifetime because their security is based on computational assumptions that will potentially break in the future when more powerful computers are available. In 1993, Bayer et al.\ proposed to renew a digital signature by time-stamping the signature together with the signed document. Based on their idea long-term timestamp schemes have been proposed and standardized that allow to protect data integrity over long periods of time. To minimize the risk of a design failure that affects the security of these schemes, it is important to formally analyze their security. However, many of the proposed schemes have not been subject to a formal security analysis yet. In this paper, we address this issue by formally analyzing the security of a hash-based long-term timestamp scheme that is based on the ideas of Bayer et al. Our analysis shows that the security level of this scheme degrades cubic over time, a security loss that needs to be taken into account when the scheme is used in practice.

The number field sieve is the best-known algorithm for factoring integers and solving the discrete logarithm problem in prime fields. In this paper, we present some new improvements to various steps of the number field sieve. We apply these improvements on the current 768-bit discrete logarithm record and show that we are able to perform the overall computing time in about 1260 core$\cdot$years using these improvements instead of 2350 core$\cdot$years using the best known parameters for this problem. Moreover, we show that the pre-computation phase for a 768-bit discrete logarithm problem, that allows for example to build a massive decryption tool of IPsec traffic protected by the Oakley group~1, was feasible in reasonable time using technologies available before the year 2000.

Verifiable random functions are pseudorandom functions producing publicly verifiable proofs for their outputs, allowing for efficient checks of the correctness of their computation. In this work, we introduce a new computational hypothesis, the n-Eigen-Value assumption, which can be seen as a relaxation of the U_n-MDDH assumption, and prove its equivalence with the n-Rank assumption. Based on the newly introduced computational hypothesis, we build the core of a verifiable random function having an exponentially large input space and reaching adaptive security under a static assumption. The final construction achieves shorter public and secret keys compared to the existing schemes reaching the same properties.

In this paper, we revisit the security of factoring-based signature schemes built via the Fiat-Shamir transform and show that they can admit tighter reductions to certain decisional complexity assumptions such as the quadratic-residuosity, the high-residuosity, and the $\phi$-hiding assumptions. We do so by proving that the underlying identification schemes used in these schemes are a particular case of the lossy identification notion recently introduced by Abdalla et al. at Eurocrypt 2012. Next, we show how to extend these results to the forward-security setting based on ideas from the Itkis-Reyzin forward-secure signature scheme. Unlike the original Itkis-Reyzin scheme, our construction can be instantiated under different decisional complexity assumptions and has a much tighter security reduction. Moreover, we also show that the tighter security reductions provided by our proof methodology can result in concrete efficiency gains in practice, both in the standard and forward-security setting, as long as the use of stronger security assumptions is deemed acceptable. Finally, we investigate the design of forward-secure signature schemes whose security reductions are fully tight.

In their foundational paper on pseudorandom bit generation, Blum and Micali showed that the discrete logarithm problem could be solved efficiently given a ``magic box'' oracle that computes the most significant bit of the discrete logarithm with a slight advantage over guessing. This magic box can be realized on a quantum computer with a new, simplified variant of Shor's algorithm. The resulting combination of Blum and Micali's reduction and this new quantum magic box offers an intriguing hybrid approach to solving the discrete logarithm problem with a quantum computer. Because the only requirement on the quantum portion of the algorithm is that it provide an approximate estimate of a single bit of the discrete logarithm, the new algorithm may be easier to implement, more resilient to errors, and more amenable to optimization than previous approaches. Further analysis is needed to quantify the extent of these benefits in practice. The result applies to the discrete logarithm problem over both finite fields and elliptic curves. (The views expressed are my own and do not necessarily reflect those of my employer.)

As an invited speaker of the ACISP 2017 conference, Dongxi Liu recently introduced a new lattice-based encryption scheme (joint work with Li, Kim and Nepal) designed for lightweight IoT applications, and announced plans to submit it to the NIST postquantum competition. The new scheme is based on a variant of standard LWE called Compact-LWE, but is claimed to achieve high security levels in considerably smaller dimensions than usual lattice-based schemes. In fact, the proposed parameters, allegedly suitable for 138-bit security, involve the Compact-LWE assumption in dimension only 13. In this note, we show that this particularly aggressive choice of parameters fails to achieve the stated security level. More precisely, we show that ciphertexts in the new encryption scheme can be decrypted using the public key alone with >99.9% probability in a fraction of a second on a standard PC, which is not quite as fast as legitimate decryption, but not too far off.

Structure-preserving signatures are an important cryptographic primitive that is useful for the design of modular cryptographic protocols. It has been proven that structure-preserving signatures (in the most efficient Type-III bilinear group setting) have a lower bound of 3 group elements in the signature (which must include elements from both source groups) and require at least 2 pairing-product equations for verification. In this paper, we show that such lower bounds can be circumvented. In particular, we define the notion of Unilateral Structure-Preserving Signatures on Diffie-Hellman pairs (USPSDH) which are structure-preserving signatures in the efficient Type-III bilinear group setting with the message space being the set of Diffie-Hellman pairs, in the terminology of Abe et al. (Crypto 2010). The signatures in these schemes are elements of one of the source groups, i.e. unilateral, whereas the verification key elements' are from the other source group. We construct a number of new structure-preserving signature schemes which bypass the Type-III lower bounds and hence they are much more efficient than all existing structure-preserving signature schemes. We also prove optimality of our constructions by proving lower bounds and giving some impossibility results. Our contribution can be summarized as follows: \begin{itemize} \item We construct two optimal randomizable CMA-secure schemes with signatures consisting of only 2 group elements from the first short source group and therefore our signatures are at least half the size of the best existing structure-preserving scheme for unilateral messages in the (most efficient) Type-III setting. Verifying signatures in our schemes requires, besides checking the well-formedness of the message, the evaluation of a single Pairing-Product Equation (PPE) and requires a fewer pairing evaluations than all existing structure-preserving signature schemes in the Type-III setting. Our first scheme has a feature that permits controlled randomizability (combined unforgeability) where the signer can restrict some messages such that signatures on those cannot be re-randomized which might be useful for some applications. \item We construct optimal strongly unforgeable CMA-secure one-time schemes with signatures consisting of 1 group element, and which can also sign a vector of messages while maintaining the same signature size. \item We give a one-time strongly unforgeable CMA-secure structure-preserving scheme that signs unilateral messages, i.e. messages in one of the source groups, whose efficiency matches the best existing optimal one-time scheme in every respect. \item We investigate some lower bounds and prove some impossibility results regarding this variant of structure-preserving signatures. \item We give an optimal (with signatures consisting of 2 group elements and verification requiring 1 pairing-product equation) fully randomizable CMA-secure partially structure-preserving scheme that simultaneously signs a Diffie-Hellman pair and a vector in $\Z^k_p$. \item As an example application of one of our schemes, we obtain efficient instantiations of randomizable weakly blind signatures which do not rely on random oracles. The latter is a building block that is used, for instance, in constructing Direct Anonymous Attestation (DAA) protocols, which are protocols deployed in practice. \end{itemize} Our results offer value along two fronts: On the practical side, our constructions are more efficient than existing ones and thus could lead to more efficient instantiations of many cryptographic protocols. On the theoretical side, our results serve as a proof that many of the lower bounds for the Type-III setting can be circumvented.

The LLL algorithm (from Lenstra, Lenstra and Lovász) and its generalization BKZ (from Schnorr and Euchner) are widely used in cryptanalysis, especially for lattice-based cryptography. Precisely understanding their behavior is crucial for deriving appropriate key-size for cryptographic schemes subject to lattice-reduction attacks. Current models, e.g. the Geometric Series Assumption and Chen-Nguyen's BKZ-simulator, have provided a decent first-order analysis of the behavior of LLL and BKZ. However, they only focused on the average behavior and were not perfectly accurate. In this work, we initiate a second order analysis of this behavior. We confirm and quantify discrepancies between models and experiments ---in particular in the head and tail regions--- and study their consequences. We also provide variations around the mean and correlations statistics, and study their impact. While mostly based on experiments, by pointing at and quantifying unaccounted phenomena, our study sets the ground for a theoretical and predictive understanding of LLL and BKZ performances at the second order.

Proxy re-encryption (PRE) is a cryptographic primitive in which a proxy can transform Alice's ciphertexts into ones decryptable by Bob. Key-private PRE specifies an additional level of security, requiring that proxy keys leak no information on the identities of Alice and Bob. In this paper, we build two key-private PRE schemes: (1) we propose a CPA-secure key-private PRE scheme in the standard model, and (2) we then transform it into a CCA-secure scheme in the random oracle model. Both schemes enjoy following properties: both are uni-directional and the CPA-secure one is a multi-hop scheme. In addition, the security of our schemes is based on the hardness of the standard Learning-With-Errors (LWE) problem, itself reducible from worst-case lattice hard problems that are conjectured immune to quantum cryptanalysis, or ``post-quantum''. We implement the CPA-secure scheme and point out that, among many applications, it can be sufficiently used for the practical task of key rotation over encrypted data.

Given a well-chosen additively homomorphic cryptosystem and a $\Sigma$ protocol with a linear answer, Damgård, Fazio, and Nicolosi proposed a non-interactive designated-verifier zero knowledge argument in the registered public key model that is sound under non-standard complexity-leveraging assumptions. In 2015, Chaidos and Groth showed how to achieve the weaker yet reasonable culpable soundness notion under standard assumptions but only if the plaintext space order is prime. It makes use of $\Sigma$ protocols that satisfy what we call the \emph{optimal culpable soundness}. Unfortunately, most of the known additively homomorphic cryptosystems (like the Paillier Elgamal cryptosystem that is secure under the standard Decisional Composite Residuosity Assumption) have composite-order plaintext space. We construct optimally culpable sound $\Sigma$ protocols and thus culpably sound non-interactive designated-verifier zero knowledge protocols for NP under standard assumptions given that the least prime divisor of the plaintext space order is large.

In this work the first linearly homomorphic authenticated encryption scheme with public verifiability and provable correctness, called LEPCoV, is presented. It improves the initial proposal by avoiding false negatives during the verification algorithm. This work provides a detailed description of LEPCoV, a comparison with the original scheme, a security and correctness proof, and a performance analysis showing that all algorithms run in reasonable time for parameters that are currently considered secure. The scheme presented here allows a user to outsource computations on encrypted data to the cloud, such that any third party can verify the correctness of the computations without having access to the original data. This makes this work an important contribution to cloud computing and applications where operations on sensitive data have to be performed, such as statistics on medical records and tallying of electronically cast votes.

In this short report, we study the security of the new multivariate signature scheme HMFEv proposed at PQCrypto 2017.

Leveled authentication allows resource-constrained IoT devices to be authenticated at different strength levels according to the particular types of communication. To achieve efficient leveled authentication, we propose a lightweight public key encryption scheme that can produce very short ciphertexts without sacrificing its security. The security of our scheme is based on the Learning With Secretly Scaled Errors in Dense Lattice (referred to as Compact-LWE) problem. We prove the hardness of Compact-LWE by reducing Learning With Errors (LWE) to Compact-LWE. However, unlike LWE, even if the closest vector problem (CVP) in lattices can be solved, Compact-LWE is still hard, due to the high density of lattices constructed from Compact-LWE samples and the relatively longer error vectors. By using a lattice-based attack tool, we verify that the attacks, which are successful on LWE instantly, cannot succeed on Compact-LWE, even for a small dimension parameter like $n=13$, hence allowing small dimensions for short ciphertexts. On the Contiki operating system for IoT, we have implemented our scheme, with which a leveled Needham-Schroeder-Lowe public key authentication protocol is implemented. On a small IoT device with 8MHZ MSP430 16-bit processor and 10KB RAM, our experiment shows that our scheme can complete 50 encryptions and 500 decryptions per second at a security level above 128 bits, with a public key of 2368 bits, generating 176-bit ciphertexts for 16-bit messages. With two small IoT devices communicating over IEEE 802.15.4 and 6LoWPAN, the total time of completing an authentication varies from 640ms (the 1st authentication level) to 8373ms (the 16th authentication level), in which the execution of our encryption scheme takes only a very small faction from 46ms to 445ms.

We perform a special number field sieve discrete logarithm computation in a 1024-bit prime field. To our knowledge, this is the first kilobit-sized discrete logarithm computation ever reported for prime fields. This computation took a little over two months of calendar time on an academic cluster using the open-source CADO-NFS software. Our chosen prime $p$ looks random, and $p-1$ has a 160-bit prime factor, in line with recommended parameters for the Digital Signature Algorithm. However, our $p$ has been trapdoored in such a way that the special number field sieve can be used to compute discrete logarithms in $\mathbb{F}_p^*$, yet detecting that $p$ has this trapdoor seems out of reach. Twenty-five years ago, there was considerable controversy around the possibility of backdoored parameters for DSA. Our computations show that trapdoored primes are entirely feasible with current computing technology. We also describe special number field sieve discrete log computations carried out for multiple weak primes found in use in the wild.

In this work, we introduce a novel technique for secure computation over large inputs. Specifically, we provide a new oblivious transfer (OT) protocol with a laconic receiver. Laconic OT allows a receiver to commit to a large input $D$ (of length $M$) via a short message. Subsequently, a single short message by a sender allows the receiver to learn $m_{D[L]}$, where the messages $m_0, m_1$ and the location $L \in [M]$ are dynamically chosen by the sender. All prior constructions of OT required the receiver's outgoing message to grow with $D$. Our key contribution is an instantiation of this primitive based on the Decisional Diffie-Hellman (DDH) assumption in the common reference string (CRS) model. The technical core of this construction is a novel use of somewhere statistically binding (SSB) hashing in conjunction with hash proof systems. Next, we show applications of laconic OT to non-interactive secure computation on large inputs and multi-hop homomorphic encryption for RAM programs.

Extending bilinear elliptic curve pairings to multilinear maps is a long-standing open problem. The first plausible construction of such multilinear maps has recently been described by Garg, Gentry and Halevi, based on ideal lattices. In this paper we describe a different construction that works over the integers instead of ideal lattices, similar to the DGHV fully homomorphic encryption scheme. We also describe a different technique for proving the full randomization of encodings: instead of Gaussian linear sums, we apply the classical leftover hash lemma over a quotient lattice. We show that our construction is relatively practical: for reasonable security parameters a one-round 7-party Diffie-Hellman key exchange requires about $25$ seconds per party.

How is it possible to prevent the sharing of cryptographic functions? This question appears to be fundamentally hard to address since in this setting the owner of the key {\em is} the adversary: she wishes to share a program or device that (potentially only partly) implements her main cryptographic functionality. Given that she possesses the cryptographic key, it is impossible for her to be {\em prevented} from writing code or building a device that uses that key. She may though be {\em deterred} from doing so. We introduce {\em leakage-deterring} public-key cryptographic primitives to address this problem. Such primitives have the feature of enabling the embedding of owner-specific private data into the owner's public-key so that given access to {\em any} (even partially functional) implementation of the primitive, the recovery of the data can be facilitated. We formalize the notion of leakage-deterring in the context of encryption, signature, and identification and we provide efficient generic constructions that facilitate the recoverability of the hidden data while retaining privacy as long as no sharing takes place.

Predicate encodings (Wee, TCC 2014; Chen, Gay, Wee, EUROCRYPT 2015), are symmetric primitives that can be used for building predicate encryption schemes. We give an algebraic characterization of the notion of privacy from predicate encodings, and explore several of its consequences. Specifically, we propose more efficient predicate encodings for boolean formulae and arithmetic span programs, and generic optimizations of predicate encodings. We define new constructions to build boolean combination of predicate encodings. We formalize the relationship between predicate encodings and pair encodings (Attrapadung, EUROCRYPT 2014), another primitive that can be transformed generically into predicate encryption schemes, and compare our constructions for boolean combinations of pair encodings with existing similar constructions from pair encodings. Finally, we demonstrate that our results carry to tag-based encodings (Kim, Susilo, Guo, and Au, SCN 2016).

The wide number and variety of side-channel attacks against scalar multiplication algorithms makes their security evaluations complex, in particular in case of time constraints making exhaustive analyses impossible. In this paper, we present a systematic way to evaluate the security of such implementations against horizontal attacks. As horizontal attacks allow extracting most of the information in the leakage traces of scalar multiplications, they are suitable to avoid risks of overestimated security levels. For this purpose, we additionally propose to use linear regression in order to accurately characterize the leakage function and therefore approach worst-case security evaluations. We then show how to apply our tools in the contexts of ECDSA and ECDH implementations, and validate them against two targets: a Cortex-M4 and a Cortex-A8 micro-controllers.

To simplify the certificate management procedures, Shamir introduced the concept of identity-based cryptography (IBC). However, the key escrow problem is inherent in IBC. To get rid of it, Al-Riyami and Paterson introduced in 2003 the notion of certificateless cryptography (CLC). However, if a cryptosystem is not perfectly implemented, adversaries would be able to obtain part of the system's secret state via side-channel attacks, and thus may break the system. This is not considered in the security model of traditional cryptographic primitives. Leakage-resilient cryptography was then proposed to prevent adversaries from doing so. There are fruitful works on leakage-resilient encryption schemes, while there are not many on signature schemes in the leakage setting. In this work, we review the folklore generic constructions of identity-based signature and certificateless signature, and show that if the underlying primitives are leakage-resilient, so are the resulting identity-based signature scheme and certificateless signature scheme. The leakage rate follows the minimum one of the underlying primitives. We also show some instantiations of these generic constructions.

We provide a tight security proof for an IND-CCA Ring-LWE based Key Encapsulation Mechanism that is derived from a generic construction of Dent (IMA Cryptography and Coding, 2003). Such a tight reduction is not known for the generic construction. The resulting scheme has shorter ciphertexts than can be achieved with other generic constructions of Dent or by using the well-known Fujisaki-Okamoto constructions (PKC 1999, Crypto 1999). Our tight security proof is obtained by reducing to the security of the underlying Ring-LWE problem, avoiding an intermediate reduction to a CPA-secure encryption scheme. The proof technique maybe of interest for other schemes based on LWE and Ring-LWE.

In recent years several papers have appeared investigating the classical discrete logarithm problem for elliptic curves by means of the multivariate polynomial approach based on the celebrated summation polynomials, introduced by Semaev in 2004. However, with a notable exception by Petit et al. in 2016, all numerous papers have investigated only the composite-field case, leaving apart the laborious prime-field case. In this paper we propose a variation of Semaev's original approach for the prime-field case. Our proposal outperforms both the original Semaev's method and Petit et al. specialized algorithm. The improvement is reached by reducing the necessary Groebner basis computations to only one basis calculation.

Practical hardness results are necessary to select parameters for cryptographic schemes. Cryptographic challenges proved to be useful for determining the practical hardness of computational problems that are used to build public-key cryptography. However, several of these problems have the drawback that it is not known how to create a challenge for them without knowing the solutions. Hence, for these problems the creators of the challenges are excluded from participating. In this work, we present a method to create cryptographic challenges without excluding anyone from participating. This method is based on secure multi-party computation (MPC). We demonstrate that the MPC-based approach is indeed feasible by using it to build a challenge for the learning with errors (LWE) problem. The LWE problem is one of the most important problems in lattice-based cryptography. The security of many cryptographic schemes that have been proposed in the last decade is directly based on it. We identify parameters for LWE instances that provide the appropriate hardness level for a challenge while representing instances used to instantiate encryption schemes as close as possible. The LWE challenge is designed to determine the practical hardness of LWE, to gain an overview of the best known LWE solvers, and to motivate additional research effort in this direction.

A Unlinkable Sanitizable Signature scheme (USS) allows a sanitizer to modify some parts of a signed message such that nobody can link the modified signature to the original one. A Verifiable Ring Signature scheme (VRS) allows the users to sign messages anonymously within a group such that a user can prove a posteriori to a verifier that he is the signer of a given message. In this paper, we first revisit the notion of VRS: we improve the proof capabilities of the users, we give a complete security model for VRS and we give an efficient and secure scheme called EVeR. Our main contribution is GUSS , a generic USS based on a VRS scheme and an unforgeable signature scheme. We show that GUSS instanciated with EVeR and the Schnorr's signature is twice as efficient as the best USS scheme of the literature. Moreover, we propose a stronger definition of accountability: a USS is accountable when the signer can prove whether a signature is sanitized. We formally define the notion of strong accontability when the sanitizer can also prove the origin of a signature. We show that the notion of strong accountability is important in practice. Finally, we prove the security properties of GUSS (including the strong accountability) and EVeR under the Decisional Diffie-Hellman assumption in the random oracle model.

The Naor-Yung paradigm (Naor and Yung, STOC '90) allows to generically boost security under chosen-plaintext attacks (CPA) to security against chosen-ciphertext attacks (CCA) for public-key encryption (PKE) schemes. The main idea is to encrypt the plaintext twice (under independent public keys), and to append a non-interactive zero-knowledge (NIZK) proof that the two ciphertexts indeed encrypt the same message. Later work by Camenisch, Chandran, and Shoup (Eurocrypt '09) and Naor and Segev (Crypto '09 and SIAM J. Comput. '12) established that the very same techniques can also be used in the settings of key-dependent message (KDM) and key-leakage attacks (respectively). In this paper we study the conditions under which the two ciphertexts in the Naor-Yung construction can share the same random coins. We find that this is possible, provided that the underlying PKE scheme meets an additional simple property. The motivation for re-using the same random coins is that this allows to design much more efficient NIZK proofs. We showcase such an improvement in the random oracle model, under standard complexity assumptions including Decisional Diffie-Hellman, Quadratic Residuosity, and Subset Sum. The length of the resulting ciphertexts is reduced by 50\%, yielding truly efficient PKE schemes achieving CCA security under KDM and key-leakage attacks. As an additional contribution, we design the first PKE scheme whose CPA security under KDM attacks can be directly reduced to (low-density instances of) the Subset Sum assumption. The scheme supports key-dependent messages computed via any affine function of the secret key.

We present two practically efficient functional encryption schemes for a large class of quadratic functionalities. Specifically, our constructions enable the computation of so-called bilinear maps on encrypted vectors. This represents a practically relevant class of functions that includes, for instance, multivariate quadratic polynomials (over the integers). Our realizations work over asymmetric bilinear groups and are surprisingly efficient and easy to implement. For instance, in our most efficient scheme the public key and each ciphertext consist of \(2n + 1\) and \(4n + 2\) group elements respectively, where n is the dimension of the encrypted vectors, while secret keys are only two group elements. Our two schemes build on similar ideas, but develop them in a different way in order to achieve distinct goals. Our first scheme is proved (selectively) secure under standard assumptions, while our second construction is concretely more efficient and is proved (adaptively) secure in the generic group model. As a byproduct of our functional encryption schemes, we show new predicate encryption schemes for degree-two polynomial evaluation, where ciphertexts consist of only \(O(n)\) group elements. This significantly improves the \(O(n^2)\) bound one would get from inner product encryption-based constructions.

An internet user wanting to share observed content is typically restricted to primitive techniques such as screenshots, web caches or share button-like solutions. These acclaimed proofs, however, are either trivial to falsify or require trust in centralized entities (e.g., search engine caches). This motivates the need for a seamless and standardized internet-wide non-repudiation mechanism, allowing users to share data from news sources, social websites or financial data feeds in a provably secure manner. Additionally, blockchain oracles that enable data-rich smart contracts typically rely on a trusted third party (e.g., TLSNotary or Intel SGX). A decentralized method to transfer web-based content into a permissionless blockchain without additional trusted third party would allow for smart contract applications to flourish. In this work, we present TLS-N, the first TLS extension that provides secure non-repudiation and solves both of the mentioned challenges. TLS-N generates non-interactive proofs about the content of a TLS session that can be efficiently verified by third parties and blockchain based smart contracts. As such, TLS-N increases the accountability for content provided on the web and enables a practical and decentralized blockchain oracle for web content. TLS-N is compatible with TLS 1.3 and adds a minor overhead to a typical TLS session. When a proof is generated, parts of the TLS session (e.g., passwords, cookies) can be hidden for privacy reasons, while the remaining content can be verified. Practical demonstrations can be found at https://tls-n.org/.

In a recent paper, Aggarwal, Joux, Prakash, and Santha (AJPS) describe an ingenious public-key cryptosystem mimicking NTRU over the integers. This algorithm relies on the properties of Mersenne primes instead of polynomial rings. The security of the AJPS cryptosystem relies on the conjectured hardness of the Mersenne Low Hamming Ratio Assumption, defined in [AJPS]. This work shows that AJPS' security estimates are too optimistic and describes an algorithm allowing to recover the secret key from the public key much faster than foreseen in [AJPS]. In particular, our algorithm is \emph{experimentally practical} (within the reach of the computational capabilities of a large organization), at least for the parameter choice $\{n=1279,h=17\}$ conjectured in [AJPS] as corresponding to a $2^{120}$ security level. The algorithm is fully parallelizable.

We provide the first constructions of identity-based encryption and hierarchical identity-based encryption based on the hardness of the (Computational) Diffie-Hellman Problem (without use of groups with pairings) or Factoring. Our construction achieves the standard notion of identity-based encryption as considered by Boneh and Franklin [CRYPTO 2001]. We bypass known impossibility results using garbled circuits that make a non-black-box use of the underlying cryptographic primitives.

In this work, we design a new lattice encoding structure for vectors. Our encoding can be used to achieve a packed FHE scheme that allows some SIMD operations and can be used to improve all the prior IBE schemes and signatures in the series. In particular, with respect to FHE setting, our method improves over the prior packed GSW structure of Hiromasa et al. (PKC '15), as we do not rely on a circular assumption as required in their work. Moreover, we can use the packing and unpacking method to extract each single element, so that the homomorphic operation supports element-wise and cross-element-wise computation as well. In the IBE scenario, we improves over previous constructions supporting $O(\Lambda)$-bit length identity from lattices substantially, such as Yamada (Eurocrypt '16), Katsumata, Yamada (Asiacrypt '16) and Yamada (Crypto '17), by shrinking the master public key to three matrices from standard Learning With Errors assumption. Additionally, our techniques from IBE can be adapted to construct a compact digital signature scheme, which achieves existential unforgeability under the standard Short Integer Solution (SIS) assumption with small polynomial parameters.

In this paper we describe how to use a secret bug as a trapdoor to design trapped ellliptic curve E(Fp). This trapdoor can be used to mount an invalid curve attack on E(Fp). E(Fp) is designed to respect all ECC security criteria (prime order,high twist order, etc.) but for a secret exponent the point is projected on another unsecure curve. We show how to use this trap with a particular type of time/memory tradeoff to break the ECKCDSA verication process for any public key of the trapped curve. The process is highly undetectable : the chosen defender eort is quadratic in the saboter computational eort. This work provides a concrete hardly detectable and easily deniable example of cryptographic sabotage. While this proof of concept is very narrow, it highlights the necessity of the Full Verifiable Randomness of ECC

We analyze the concrete security of a hash-based signature scheme described in the most recent Internet Draft by McGrew, Fluhrer and Curcio. We perform this analysis in the random-oracle model, where the Merkle-Damgård hash compression function is models as the random oracle. We show that, even with a large number of different keys the attacker can choose from, and a huge computational budget, the attacker succeeds in creating a forgery with negligible probability ($< 2^{-129}$).

If $q$ is a prime and $n$ is a positive integer then any two finite fields of order $q^n$ are isomorphic. Elements of these fields can be thought of as polynomials with coefficients chosen modulo $q$, and a notion of length can be associated to these polynomials. A non-trivial isomorphism between the fields, in general, does not preserve this length, and a short element in one field will usually have an image in the other field with coefficients appearing to be randomly and uniformly distributed modulo $q$. This key feature allows us to create a new family of cryptographic constructions based on the difficulty of recovering a secret isomorphism between two finite fields. In this paper we describe a fully homomorphic encryption scheme based on this new hard problem.

In this paper, we construct {\em subring homomorphic encryption} scheme that is a homomorphic encryption scheme build on the decomposition ring, which is a subring of cyclotomic ring. In the scheme, each plaintext slot contains an integer in $\mathbb{Z}_{p^l}$, rather than an element of $\mathrm{GF}(p^d)$ as in conventional homomorphic encryption schemes on cyclotomic rings. Our benchmark results indicate that the subring homomorphic encryption scheme is several times faster than HElib {\em for mod-$p^l$ plaintexts}, due to its high parallelism of mod-$p^l$ slot structure. We believe in that the plaintext structure composed of mod-$p^l$ slots will be more natural, easy to handle, and significantly more efficient for many applications such as outsourced data mining.

SHA-1 is a widely used 1995 NIST cryptographic hash function standard that was officially deprecated by NIST in 2011 due to fundamental security weaknesses demonstrated in various analyses and theoretical attacks. Despite its deprecation, SHA-1 remains widely used in 2017 for document and TLS certificate signatures, and also in many software such as the GIT versioning system for integrity and backup purposes. A key reason behind the reluctance of many industry players to replace SHA-1 with a safer alternative is the fact that finding an actual collision has seemed to be impractical for the past eleven years due to the high complexity and computational cost of the attack. In this paper, we demonstrate that SHA-1 collision attacks have finally become practical by providing the first known instance of a collision. Furthermore, the prefix of the colliding messages was carefully chosen so that they allow an attacker to forge two distinct PDF documents with the same SHA-1 hash that display different arbitrarily-chosen visual contents. We were able to find this collision by combining many special cryptanalytic techniques in complex ways and improving upon previous work. In total the computational effort spent is equivalent to $2^{63.1}$ calls to SHA-1's compression function, and took approximately 6,500 CPU years and 100 GPU years. While the computational power spent on this collision is larger than other public cryptanalytic computations, it is still more than 100,000 times faster than a brute force search.

In this paper, we focus on the constructions of adaptively secure identity-based encryption (IBE) from lattices and verifiable random function (VRF) with large input spaces. Existing constructions of these primitives suffer from low efficiency, whereas their counterparts with weaker guarantees (IBEs with selective security and VRFs with small input spaces) are reasonably efficient. We try to fill these gaps by developing new partitioning techniques that can be performed with compact parameters and proposing new schemes based on the idea. - We propose new lattice IBEs with poly-logarithmic master public key sizes, where we count the number of the basic matrices to measure the size. Our constructions are proven secure under the LWE assumption with polynomial approximation factors. They achieve the best asymptotic space efficiency among existing schemes that depend on the same assumption and achieve the same level of security. - We also propose several new VRFs on bilinear groups. In our first scheme, the size of the proofs is poly-logarithmic in the security parameter, which is the smallest among all the existing schemes with similar properties. On the other hand, the verification keys are long. In our second scheme, the size of the verification keys is poly-logarithmic, which is the smallest among all the existing schemes. The size of the proofs is sub-linear, which is larger than our first scheme, but still smaller than all the previous schemes.

Guo et al. recently presented a reaction attack against the QC-MDPC McEliece cryptosystem. Their attack is based on the observation that when a bit-flipping decoding algorithm is used in the QC-MDPC McEliece, then there exists a dependence between the secret matrix $H$ and the failure probability of the bit-flipping algorithm. This dependence can be exploited to reveal the matrix $H$ which constitutes the private key in the cryptosystem. It was conjectured that such dependence is present even when a soft-decision decoding algorithm is used instead of a bit-flipping algorithm. This paper shows that a similar dependence between the secret matrix $H$ and the failure probability of a decoding algorithm is also present in the QC-LDPC McEliece cryptosystem. Unlike QC-MDPC McEliece, the secret key in QC-LDPC McEliece also contains matrices $S$ and $Q$ in addition to the matrix $H$. We observe that there also exists a dependence between the failure probability and the matrix $Q$. We show that these dependences leak enough information to allow an attacker to construct a sparse parity-check matrix for the public code. This parity-check matrix can then be used for decrypting ciphertexts. We tested the attack on an implementation of the QC-LDPC McEliece using a soft-decision decoding algorithm. Thus we also confirmed that soft-decision decoding algorithms can be vulnerable to leaking information about the secret key.

To ensure uninterrupted cryptographic security, it is important to begin planning the transition to post-quantum cryptography. In addition to creating post-quantum primitives, we must also plan how to adapt the cryptographic infrastructure for the transition, especially in scenarios such as public key infrastructures (PKIs) with many participants. The use of hybrids — multiple algorithms in parallel — will likely play a role during the transition for two reasons: “hedging our bets” when the security of newer primitives is not yet certain but the security of older primitives is already in question; and to achieve security and functionality both in post-quantum-aware and in a backwards-compatible way with not-yet-upgraded software. In this paper, we investigate the use of hybrid digital signature schemes. We consider several methods for combining signature schemes, and give conditions on when the resulting hybrid signature scheme is unforgeable. Additionally we address a new notion about the inability of an adversary to separate a hybrid signature into its components. For both unforgeability and non-separability, we give a novel security hierarchy based on how quantum the attack is. We then turn to three real-world standards involving digital signatures and PKI: certificates (X.509), secure channels (TLS), and email (S/MIME). We identify possible approaches to supporting hybrid signatures in these standards while retaining backwards compatibility, which we test in popular cryptographic libraries and implementations, noting specially the inability of some software to handle larger certificates.

Proxy re-encryption (PRE) was introduced by Blaze, Bleumer and Strauss [Eurocrypt '98]. Basically, PRE allows a semi-trusted proxy to transform a ciphertext encrypted under one key into an encryption of the same plaintext under another key, without revealing the underlying plaintext. Since then, many interesting applications have been explored, and many constructions in various settings have been proposed. In 2007, Cannetti and Honhenberger [CCS '07] defined a stronger notion -- CCA-security and construct a bi-directional PRE scheme. Later on, several work considered CCA-secure PRE based on bilinear group assumptions. Very recently, Kirshanova [PKC '14] proposed the first single-hop CCA-secure PRE scheme based on learning with errors (LWE) assumption. In this work, we first point out a subtle but serious mistake in the security proof of the work by Kirshanova. This reopens the direction of lattice-based CCA-secure constructions, even in the single-hop setting. Then we propose a new LWE-based single-hop CCA-secure PRE scheme. Finally, we extend the construction to support multi-hop re-encryptions for different levels of security under different settings.

We take a critical look at established security definitions for predicate encryption (PE) with public index under chosen-plaintext attack (CPA) and under chosen-ciphertext attack (CCA). In contrast to conventional public-key encryption (PKE), security definitions for PE have to deal with user collusion which is modeled by an additional key generation oracle. We identify three different formalizations of key handling in the literature implicitly assumed to lead to the same security notion. Contrary to this assumption we prove that the corresponding models result in two different security notions under CPA and three different security notions under CCA. Similarly to the recent results for PKE and conventional key-encapsulation mechanism (KEM) (Journal of Cryptology, 2015) we also analyze subtleties in security definitions for PE and predicate key-encapsulation mechanism (P-KEM) regarding the so-called "no-challenge-decryption" condition. While the results for PE and PKE are similar, the results for P-KEM significantly differ from the corresponding results for conventional KEM. Our analysis is based on appropriate definitions of semantic security and indistinguishability of encryptions for PE under different attacks scenarios. These definitions complement related security definitions for identity-based encryption and functional encryption. As a result of our work we suggest security definitions for PE and P-KEM under different attack scenarios.

The unbalanced oil and vinegar signature scheme (UOV) is one of signature schemes whose public key is a set of multivariate quadratic forms. Recently, a new variant of UOV called Cubic UOV was proposed at Inscrypt 2015. It was claimed that the cubic UOV was more efficient than the original UOV and its security was enough. However, an equivalent secret key of the cubic UOV can be recovered easily. In this note, we describe how to recover it. After we posted the first version of this note, Duong et al. proposed two variants of Cubic UOV at ICISC 2016. We also explain their weakness in the second version.

Lattice-based cryptography is one of the most promising areas within post-quantum cryptography, and offers versatile, efficient, and high performance security services. The aim of this paper is to verify the correctness of the discrete Gaussian sampling component, one of the most important modules within lattice-based cryptography. In this paper, the GLITCH software test suite is proposed, which performs statistical tests on discrete Gaussian sampler outputs. An incorrectly operating sampler, for example due to hardware or software errors, has the potential to leak secret-key information and could thus be a potential attack vector for an adversary. Moreover, statistical test suites are already common for use in pseudo-random number generators (PRNGs), and as lattice-based cryptography becomes more prevalent, it is important to develop a method to test the correctness and randomness for discrete Gaussian sampler designs. Additionally, due to the theoretical requirements for the discrete Gaussian distribution within lattice-based cryptography, certain statistical tests for distribution correctness become unsuitable, therefore a number of tests are surveyed. The final GLITCH test suite provides 11 adaptable statistical analysis tests that assess the exactness of a discrete Gaussian sampler, and which can be used to verify any software or hardware sampler design.

In this paper, we present several methods to improve the evaluation of homomorphic functions, both for fully and for leveled homomorphic encryption. We propose two packing methods, in order to decrease the expansion factor and optimize the evaluation of look-up tables and random functions in TRGSW-based homomorphic schemes. We also extend the automata logic, introduced in [19, 12], to the efficient leveled evaluation of weighted automata, and present a new homomorphic counter called TBSR, that supports all the elementary operations that occur in a multiplication. These improvements speed-up the evaluation of most arithmetic functions in a packed leveled mode, with a noise overhead that remains additive. We finally present a new circuit bootstrapping that converts TLWE into low-noise TRGSW ciphertexts in just 137ms, which makes the leveled mode of TFHE composable, and which is fast enough to speed-up arithmetic functions, compared to the gate-by-gate bootstrapping given in [12]. Finally, we propose concrete parameter sets and timing comparison for all our constructions.

The Naccache–Stern public-key cryptosystem (NS) relies on the conjectured hardness of the modular multiplicative knapsack problem: Given $p,\{v_i\},\prod v_i^{m_i} \bmod p$, find the $\{m_i\}$. Given this scheme's algebraic structure it is interesting to systematically explore its variants and generalizations. In particular it might be useful to enhance NS with features such as semantic security, re-randomizability or an extension to higher-residues. This paper addresses these questions and proposes several such variants.

Finding a short element $g$ of a number field, given the ideal generated by $g$, is a classic problem in computational algebraic number theory. Solving this problem recovers the private key in cryptosystems introduced by Gentry, Smart-Vercauteren, Gentry-Halevi, Garg-Gentry-Halevi, et al. Work over the last few years has shown that for some number fields this problem has a surprisingly low post-quantum security level. This paper shows, and experimentally verifies, that for some number fields this problem has a surprisingly low pre-quantum security level.

We present the first fault attack on cryptosystems based on supersingular isogenies. During the computation of the auxiliary points, the attack aims to change the base point to a random point on the curve via a fault injection. We will show that this would reveal the secret isogeny with one successful perturbation with high probability. We will exhibit the attack by placing it against signature schemes and key-exchange protocols with validations in place. Our paper therefore demonstrates the need to incorporate checks in implementations of the cryptosystem.

We present novel variants of the dual-lattice attack against LWE in the presence of an unusually short secret. These variants are informed by recent progress in BKW-style algorithms for solving LWE. Applying them to parameter sets suggested by the homomorphic encryption libraries HElib and SEAL v2.0 yields revised security estimates. Our techniques scale the exponent of the dual-lattice attack by a factor of \((2\,L)/(2\,L+1)\) when \(\log q = \Theta{\left(L \log n\right)}\), when the secret has constant hamming weight \(h\) and where \(L\) is the maximum depth of supported circuits. They also allow to half the dimension of the lattice under consideration at a multiplicative cost of \(2^{h}\) operations. Moreover, our techniques yield revised concrete security estimates. For example, both libraries promise 80 bits of security for LWE instances with $n=1024$ and $\log_2 q \approx {47}$, while the techniques described in this work lead to estimated costs of 68 bits (SEAL v2.0) and 62 bits (HElib).

We call a simple abelian variety over $\mathbb{F}_p$ super-isolated if its ($\mathbb{F}_p$-rational) isogeny class contains no other varieties. The motivation for considering these varieties comes from concerns about isogeny based attacks on the discrete log problem. We heuristically estimate that the number of super-isolated elliptic curves over $\mathbb{F}_p$ with prime order and $p \leq N$, is roughly $\tilde{\Theta}(\sqrt{N})$. In contrast, we prove that there are only 2 super-isolated surfaces of cryptographic size and near-prime order.

We propose multi target homomorphic attribute-based encryption (MT-HABE) with fully dynamic homomorphic evaluation: it can take as input arbitrary additional ciphertexts during homomorphic computation. In the previous MT-HABE of Brakerski et al. (TCC 2016-B), the output of homomorphic computation, which is related to a policy set, cannot be computed with a fresh ciphertext whose attribute does not satisfy any policy in the set. This is because the underlying multi-key fully homomorphic encryption (MKFHE) is single-hop: some keys are related to the output of homomorphic computation, which cannot be combined with ciphertexts encrypted under other keys. To implement fully dynamic homomorphic evaluations, we construct MT-HABE from the multi-hop MKFHE proposed by Peikert and Shiehian (TCC 2016-B).

This paper gives the first bit security result for the elliptic curve Diffie--Hellman key exchange protocol for elliptic curves defined over prime fields. About $5/6$ of the most significant bits of the $x$-coordinate of the Diffie--Hellman key are as hard to compute as the entire key. A similar result can be derived for the $5/6$ lower bits. The paper also generalizes and improves the result for elliptic curves over extension fields, that shows that computing one component (in the ground field) of the Diffie--Hellman key is as hard to compute as the entire key.

We show how to build a UC-Secure Oblivious Transfer in the presence of Adaptive Corruptions from Quasi-Adaptive Non-Interactive Zero-Knowledge proofs. Our result is based on the work of Jutla and Roy at Asiacrypt 2015, where the authors proposed a constant-size very efficient PAKE scheme. As a stepping stone, we first show how a two-flow PAKE scheme can be generically transformed in an optimized way, in order to achieve an efficient three-flow Oblivious-Transfer scheme. We then compare our generic transformations to existing OT constructions and see that we manage to gain at least a factor 2 to the best known constructions. To the best of our knowledge, our scheme is the first UC-secure Oblivious Transfer with a constant size flow from the receiver, and nearly optimal size for the server.

In this paper, we present a factoring algorithm that, assuming standard heuristics, uses just $(\log N)^{2/3+o(1)}$ qubits to factor an integer $N$ in time $L^{q+o(1)}$ where $L = \exp((\log N)^{1/3}(\log\log N)^{2/3})$ and $q=\sqrt[3]{8/3}\approx 1.387$. For comparison, the lowest asymptotic time complexity for known pre-quantum factoring algorithms, assuming standard heuristics, is $L^{p+o(1)}$ where $p>1.9$. The new time complexity is asymptotically worse than Shor's algorithm, but the qubit requirements are asymptotically better, so it may be possible to physically implement it sooner.

This paper proposes RSA parameters for which (1) key generation, encryption, decryption, signing, and verification are feasible on today's computers while (2) all known attacks are infeasible, even assuming highly scalable quantum computers. As part of the performance analysis, this paper introduces a new algorithm to generate a batch of primes. As part of the attack analysis, this paper introduces a new quantum factorization algorithm that is often much faster than Shor's algorithm and much faster than pre-quantum factorization algorithms. Initial pqRSA implementation results are provided.

Attribute based signature schemes (ABS) constitute important and powerful primitives when it comes to protecting the privacy of the user's identity and signing information. More specifically, ABS schemes provide the advantage of anonymously signing a message once a given policy is satisfied. As opposed to other related privacy preserving signatures, the verifier is not able to deduce from the signature, which attributes have been used to satisfy the (public) signing policy. In this work, we propose the first lattice-based ABS signature scheme for expressive policies. More precisely, the scheme that we propose doesn't follow the traditional approach to build ABS schemes for expressive policies, i.e. using span programs or secret sharing schemes as for classical schemes. In fact, our approach is simpler and does not require such complex subroutines. We first construct a new (t,B)-threshold ABS scheme that allows to anonymously generate signatures, only if $t$ out of p=|B| attributes are covered by valid credentials. Based on this scheme, we propose a lattice-based ABS scheme for expressive (And,Or)-policies. For this, we construct a new credential aggregation system that is built on top of a modified variant of Boyen's signature scheme, which could be of independent interest. Our ABS scheme for expressive policies yields signature sizes that are linear in the number of attributes similar to state-of-the-art classical ABS schemes.

The security of code-based cryptosystems such as the McEliece cryptosystem relies primarily on the difficulty of decoding random linear codes. The best decoding algorithms are all improvements of an old algorithm due to Prange: they are known under the name of information set decoding techniques. It is also important to assess the security of such cryptosystems against a quantum computer. This research thread started in Overbeck and Sendrier's 2009 survey on code-based cryptography, and the best algorithm to date has been Bernstein's quantising of the simplest information set decoding algorithm, namely Prange's algorithm. It consists in applying Grover's quantum search to obtain a quadratic speed-up of Prange's algorithm. In this paper, we quantise other information set decoding algorithms by using quantum walk techniques which were devised for the subset-sum problem by Bernstein, Jeffery, Lange and Meurer. This results in improving the worst-case complexity of 2^{0.06035n} of Bernstein's algorithm to 2^{0.05869n} with the best algorithm presented here (where n is the codelength).

The Learning Parity with Noise (LPN) problem has found many applications in cryptography due to its conjectured post-quantum hardness and simple algebraic structure. Over the years, constructions of different public-key primitives were proposed from LPN, but most of them are based on the LPN assumption with _low noise_ rate rather than _constant noise_ rate. A recent breakthrough was made by Yu and Zhang (Crypto'16), who constructed the first Public-Key Encryption (PKE) from constant-noise LPN. However, the problem of designing a PKE with _Key-Dependent Message_ (KDM) security from constant-noise LPN is still open. In this paper, we present the first PKE with KDM-security assuming certain sub-exponential hardness of constant-noise LPN, where the number of users is predefined. The technical tool is two types of _multi-fold LPN on squared-log entropy_, one having _independent secrets_ and the other _independent sample subspaces_. We establish the hardness of the multi-fold LPN variants on constant-noise LPN. Two squared-logarithmic entropy sources for multi-fold LPN are carefully chosen, so that our PKE is able to achieve correctness and KDM-security simultaneously.

In this paper we present an encoding method for fixed-point numbers tailored for homomorphic function evaluation. The choice of the degree of the polynomial modulus used in all popular somewhat homomorphic encryption schemes is dominated by security considerations, while with the current encoding techniques the correctness requirement allows for much smaller values. We introduce a generic encoding method using expansions with respect to a non-integral base, which exploits this large degree at the benefit of reducing the growth of the coefficients when performing homomorphic operations. In practice this allows one to choose a smaller plaintext coefficient modulus which results in a significant reduction of the running time. We illustrate our approach by applying this encoding in the setting of homomorphic electricity load forecasting for the smart grid which results in a speed-up by a factor 13 compared to previous work, where encoding was done using balanced ternary expansions.

It is well known that multivariate quadratic (MQ) digital signature schemes have small signatures but huge public keys. However, in some settings, such as public key infrastructure (PKI), both variables are important. This paper explains how to transform any MQ signature scheme into one with a much smaller public key at the cost of a larger signature. The transformation aims to reduce the combined size of the public key and signature and this metric is improved significantly. The security of our transformation reduces to that of the underlying MQ signature scheme in the random oracle model. It is possible to decrease signature sizes even further but then its security is related to the conjectured hardness of a new problem, the Approximate MQ Problem (AMQ).

We construct a functional encryption scheme for circuits which simultaneously achieves and improves upon the security of the current best known, and incomparable, constructions from standard assumptions: reusable garbled circuits by Goldwasser, Kalai, Popa, Vaikuntanathan and Zeldovich (STOC 2013) [GKP + 13] and predicate encryption for circuits by Gorbunov, Vaikuntanathan and Wee (CRYPTO 2015) [GVW15]. Our scheme is secure based on the learning with errors (LWE) assumption. Our construction implies: 1. A new construction for reusable garbled circuits that achieves stronger security than the only known prior construction [GKP + 13]. 2. A new construction for bounded collusion functional encryption with substantial efficiency benefits: our public parameters and ciphertext size incur an additive growth of O(Q^2), where Q is the number of permissible queries. Additionally, the ciphertext of our scheme is succinct, in that it does not depend on the size of the circuit. By contrast, the prior best construction [GKP+13, GVW12] incurred a multiplicative blowup of O (Q^4) in both the public parameters and ciphertext size. However, our scheme is secure in a weaker game than GVW12]. Additionally, we show that existing LWE based predicate encryption schemes [AFV11, GVW15] are completely insecure against a general functional encryption adversary (i.e. in the “strong attribute hiding” game). We demonstrate three different attacks, the strongest of which is applicable even to the inner product predicate encryption scheme [AFV11]. Our attacks are practical and allow the attacker to completely recover x from its encryption Enc (x) within a polynomial number of queries. This illustrates that the barrier between predicate and functional encryption is not just a limitation of proof techniques. We believe these attacks shed significant light on the barriers to achieving full fledged functional encryption from LWE, even for simple functionalities such as inner product zero testing [KSW08, AFV11]. Along the way, we develop a new proof technique that permits the simulator to program public parameters based on keys that will be requested in the future. This technique may be of independent interest.

Cryptography is essential for the security of Internet communication, cars, and implanted medical devices. However, many commonly used cryptosystems will be completely broken once big quantum computers exist. Post-quantum cryptography is cryptography under the assumption that the attacker has a large quantum computer; post-quantum cryptosystems strive to remain secure even in this scenario. This relatively young research area has seen some successes in identifying mathematical operations for which quantum algorithms offer little speedup, and then building cryptographic systems around those. The central challenge in post-quantum cryptography is to meet demands for cryptographic usability and flexibility without sacrificing trust.

We present two general constructions that can be used to combine any two functional encryption (FE) schemes (supporting a bounded number of key queries) into a new functional encryption scheme supporting a larger number of key queries. By using these constructions iteratively, we transform any primitive FE scheme supporting a single functional key query (from a sufficiently general class of functions) and has certain weak compactness properties to a collusion-resistant FE scheme with the same or slightly weaker compactness properties. Together with previously known reductions, this shows that the compact, weakly compact, collusion-resistant, and weakly collusion-resistant versions of FE are all equivalent under polynomial time reductions. These are all FE variants known to imply the existence of indistinguishability obfuscation, and were previously thought to offer slightly different avenues toward the realization of obfuscation from general assumptions. Our results show that they are indeed all equivalent, improving our understanding of the minimal assumptions on functional encryption required to instantiate indistinguishability obfuscation.

We put forward a generalization of lossy trapdoor functions (LTFs). Namely, all-but-many lossy trapdoor functions (ABM-LTFs) are LTFs that are parametrized with tags. Each tag can either be injective or lossy, which leads to an invertible or a lossy function. The interesting property of ABM-LTFs is that it is possible to generate an arbitrary number of lossy tags by means of a special trapdoor, while it is not feasible to produce lossy tags without this trapdoor. Our definition and construction can be seen as generalizations of all-but-one LTFs (due to Peikert and Waters) and all-but-N LTFs (due to Hemenway et al.). However, to achieve ABM-LTFs (and thus a number of lossy tags which is not bounded by any polynomial), we have to employ some new tricks. Concretely, we give two constructions that employ ``disguised'' variants of the Waters, resp. Boneh-Boyen signature schemes to make the generation of lossy tags hard without trapdoor. In a nutshell, lossy tags simply correspond to valid signatures. At the same time, tags are disguised (i.e., suitably blinded) to keep lossy tags indistinguishable from injective tags. ABM-LTFs are useful in settings in which there are a polynomial number of adversarial challenges (e.g., challenge ciphertexts). Specifically, building on work by Hemenway et al., we show that ABM-LTFs can be used to achieve selective opening security against chosen-ciphertext attacks. One of our ABM-LTF constructions thus yields the first SO-CCA secure encryption scheme with compact ciphertexts (O(1) group elements) whose efficiency does not depend on the number of challenges. Our second ABM-LTF construction yields an IND-CCA (and in fact SO-CCA) secure encryption scheme whose security reduction is independent of the number of challenges and decryption queries.

The Montgomery ladder is a remarkably simple method of computing scalar multiples of points on a broad class of elliptic curves. This article surveys a wide range of topics related to the Montgomery ladder, both from the historical perspective of Weierstrass curves and from the modern perspective of Edwards curves. New material includes a full proof of a complete constant-time ladder algorithm suitable for cryptographic applications.

We propose practically efficient signature schemes which feature several attractive properties: (a) they only rely on the security of symmetric-key primitives (block ciphers, hash functions), and are therefore a viable candidate for post-quantum security, (b) they have extremely small signing keys, essentially the smallest possible, and, (c) they are highly parametrizable. For this result we take advantage of advances in two very distinct areas of cryptography. The first is the area of primitives in symmetric cryptography, where recent developments led to designs which exhibit an especially low number of multiplications. The second is the area of zero-knowledge proof systems, where significant progress for efficiently proving statements over general circuits was recently made. We follow two different directions, one of them yielding the first practical instantiation of a design paradigm due to Bellare and Goldwasser without relying on structured hardness assumptions. For both our schemes we explore the whole design spectrum to obtain optimal parameter choices for different settings. Within limits, in all cases our schemes allow to trade-off computational effort with signature sizes. We also demonstrate that our schemes are parallelizable to the extent that they can practically take advantage of several cores on a CPU.

This paper reports on the number field sieve computation of a 768-bit prime field discrete logarithm, describes the different parameter optimizations and resulting algorithmic changes compared to the factorization of a 768-bit RSA modulus, and briefly discusses the cryptologic relevance of the result.

The worst-case hardness of finding short vectors in ideals of cyclotomic number fields (Ideal-SVP) is a central matter in lattice based cryptography. Assuming the worst-case hardness of Ideal-SVP allows to prove the Ring-LWE and Ring-SIS assumptions, and therefore to prove the security of numerous cryptographic schemes and protocols --- including key-exchange, digital signatures, public-key encryption and fully-homomorphic encryption. A series of recent works has shown that Principal Ideal-SVP is not always as hard as finding short vectors in general lattices, and some schemes were broken using quantum algorithms --- the Soliloquy encryption scheme, Smart-Vercauteren fully homomorphic encryption scheme from PKC 2010, and Gentry-Garg-Halevi cryptographic multilinear-maps from Eurocrypt 2013. Those broken schemes were using a special class of principal ideals, but these works also showed how to solve SVP for principal ideals in the worst-case in quantum polynomial time for an approximation factor of $\exp(\tilde O(\sqrt n))$. This exposed an unexpected hardness gap between general lattices and some structured ones, and called into question the hardness of various problems over structured lattices, such as Ideal-SVP and Ring-LWE. In this work, we generalize the previous result to general ideals. Precisely, we show how to solve the close principal multiple problem (CPM) by exploiting the classical theorem that the class-group is annihilated by the (Galois-module action of) the so-called Stickelberger ideal. Under some plausible number-theoretical hypothesis, our approach provides a close principal multiple in quantum polynomial time. Combined with the previous results, this solves Ideal-SVP in the worst case in quantum polynomial time for an approximation factor of $\exp(\tilde O(\sqrt n))$. Although it does not seem that the security of Ring-LWE based cryptosystems is directly affected, we contribute novel ideas to the cryptanalysis of schemes based on structured lattices. Moreover, our result shows a deepening of the gap between general lattices and structured ones.

This paper puts forward an efficient broadcast encryption in public key setting employing ternary tree subset difference method for revocation. It provides outsider anonymity disabling the revoked users from getting any information of message and concealing the set of subscribed users from the revoked users. Our approach utilizes composite order bilinear group setting and exhibits significant improvement in the broadcast efficiency. The proposed scheme compares favourably over the existing similar schemes in standard model. The public key and secret key sizes are poly-logarithmic while the ciphertext size is sub linear in total number of users. Our scheme achieves selective security against chosen plaintext attack in the standard model under reasonable assumptions.

We introduce a tag based encoding, a new generic framework for modular design of Predicate Encryption (PE) schemes in prime order groups. Our framework is equipped with a compiler which is adaptively secure in prime order groups under the standard Decisional Linear Assumption (DLIN). Compared with prior encoding frameworks in prime order groups which require multiple group elements to interpret a tuple of an encoding in a real scheme, our framework has a distinctive feature which is that each element of an encoding can be represented with only a group element and an integer. This difference allows us to construct a more efficient encryption scheme. In the current literature, the most efficient compiler was proposed by Chen, Gay and Wee (CGW) in Eurocrypt'15. It features one tuple of an encoding into two group elements under the Symmetric External Diffie-Hellman assumption (SXDH). Compared with their compiler, our encoding construction saves the size of either private keys or ciphertexts up-to 25 percent and reduces decryption time and the size of public key up-to 50 percent in 128 security level. Several new schemes such as inner product encryption with short keys, dual spatial encryption with short keys and hierarchical identity based encryption with short ciphertexts are also introduced as instances of our encoding.

Multivariate Cryptography is one of the main candidates for creating post-quantum cryptosystems. Especially in the area of digital signatures, there exist many practical and secure multivariate schemes. However, there is a lack of more advanced schemes, such as schemes for oblivious transfer and signature schemes with special properties. While, in the last years, a number of multivariate ring signature schemes have been proposed, all of these have weaknesses in terms of security or efficiency. In this paper we propose a simple and efficient technique to extend arbitrary multivariate signature schemes to ring signature schemes and illustrate it using the example of Rainbow. The resulting scheme provides perfect anonymity for the signer (as member of a group), as well as shorter ring signatures than all previously proposed post-quantum ring signature schemes.

We give a new black-box transformation from any semantically secure encryption scheme into a non-malleable one which has a better rate than the best previous work of Coretti et al. (TCC 2016-A). We achieve a better rate by departing from the “matrix encoding” methodology used by previous constructions, and working directly with a single codeword. We also use a Shamir secret-share packing technique to improve the rate of the underlying error-correcting code.

We design a new McEliece-like rank metric based encryption scheme from Gabidulin codes. We explain why it is not affected by the invariant subspace attacks also known as Overbeck's attacks. The idea of the design mixes two existing approaches designing rank metric based encryption schemes. For a given security our public-keys are more compact than for the same security in the Hamming metric based settings.

Wee (TCC'14) and Attrapadung (Eurocrypt'14) introduced predicate and pair encodings, respectively, as a simple way to construct and analyze attribute-based encryption schemes, or more generally predicate encryption. However, many schemes do not satisfy the simple information theoretic property proposed in those works, and thus require much more complicated analysis. In this paper, we propose a new simple property for pair encodings called symbolic security. Proofs that pair encodings satisfy this property are concise and easy to verify. We show that this property is inherently tied to the security of predicate encryption schemes by arguing that any scheme which is not trivially broken must satisfy it. Then we use this property to discuss several ways to convert between pair encodings to obtain encryption schemes with different properties like small ciphertexts or keys. Finally, we show that any pair encoding satisfying our new property can be used to construct a fully secure predicate encryption scheme. The resulting schemes are secure under a new q-type assumption which we show follows from several of the assumptions used to construct such schemes in previous work.

Pair encodings and predicate encodings, recently introduced by Attrapadung (Eurocrypt 2014) and Wee (TCC 2014) respectively, greatly simplify the process of designing and analyzing predicate and attribute-based encryption schemes. However, they are still somewhat limited in that they are restricted to composite order groups, and the information theoretic properties are not sufficient to argue about many of the schemes. Here we focus on pair encodings, as the more general of the two. We first study the structure of these objects, then propose a new relaxed but still information theoretic security property. Next we show a generic construction for predicate encryption in prime order groups from our new property; it results in either semi-adaptive or full security depending on the encoding, and gives security under SXDH or DLIN. Finally, we demonstrate the range of our new property by using it to design the first semi-adaptively secure CP-ABE scheme with constant size ciphertexts.

Passwords bootstrap symmetric and asymmetric cryptography, tying keys to an individual user. Biometrics are intended to strengthen this tie. Unfortunately, biometrics exhibit noise between repeated readings. Fuzzy extractors (Dodis et al., Eurocrypt 2004) derive stable symmetric keys from noisy sources. We ask if it is also possible for noisy sources to directly replace private keys in asymmetric cryptosystems. We propose a new primitive called public-key cryptosystems with noisy keys. Such a cryptosystem functions when the private key varies according to some metric. An intuitive solution is to combine a fuzzy extractor with a public key cryptosystem. Unfortunately, fuzzy extractors need static helper information to account for noise. This helper information creates fundamental limitations on the resulting cryptosytems. To overcome these limitations, we directly construct public-key encryption and digital signature algorithms with noisy keys. The core of our constructions is a computational version of the fuzzy vault (Juels and Sudan, Designs, Codes, and Cryptography 2006). Security of our schemes is based on graded encoding schemes (Garg et al., Eurocrypt 2013, Garg et al., TCC 2016). Importantly, our public-key encryption algorithm is based on a weaker model of grading encoding. If functional encryption or indistinguishable obfuscation exist in this weaker model, they also exist in the standard model. In addition, we use the computational fuzzy vault to construct the first reusable fuzzy extractor (Boyen, CCS 2004) supporting a linear fraction of errors.

In the last few years multivariate public key cryptography has experienced an infusion of new ideas for encryption. Among these new strategies is the ABC Simple Matrix family of encryption schemes which utilize the structure of a large matrix algebra to construct effectively invertible systems of nonlinear equations hidden by an isomorphism of polynomials. One promising approach to cryptanalyzing these schemes has been structural cryptanalysis, based on applying a strategy similar to MinRank attacks to the discrete differential. These attacks however have been significantly more expensive when applied to parameters using fields of characteristic 2, which have been the most common choice for published parameters. This disparity is especially great for the cubic version of the Simple Matrix Encryption Scheme. In this work, we demonstrate a technique that can be used to implement a structural attack which is as efficient against parameters of characteristic 2 as are attacks against analogous parameters over higher characteristic fields. This attack demonstrates that, not only is the cubic simple matrix scheme susceptible to structural attacks, but that the published parameters claiming 80 bits of security are less secure than claimed (albeit only slightly.) Similar techniques can also be applied to improve structural attacks against the original Simple Matrix Encryption scheme, but they represent only a modest improvement over previous structural attacks. This work therefore demonstrates that choosing a field of characteristic 2 for the Simple Matrix Encryption Scheme or its cubic variant will not provide any additional security value.

In this paper I propose fully homomorphic public-key encryption (FHPKE) with the recursive ciphertex. A ciphertext consists of three sub-ciphertexts corresponding to one plaintext. When we execute the additional operation or multiplicative operation, a new three sub-ciphertexts are generated from the three sub-ciphertexts recursively without revealing the plaintexts. The scheme is based on the discrete logarithm assumption (DLA) and computational Diffie–Hellman assumption (CDH) of multivariate polynomials on octonion ring with composite number modulus. The scheme is immune from “m and - m attack”.

This paper introduces the notion of attribute-based concurrent signatures. This primitive can be considered as an interesting extension of concurrent signatures in the attribute-based setting. It allows two parties fairly exchange their signatures only if each of them has convinced the opposite party that he/she possesses certain attributes satisfying a given signing policy. Due to this new feature, this primitive can find useful applications in online contract signing, electronic transactions and so on. We formalize this notion and present a con-struction which is secure in the random oracle model under the Strong Dif-fie-Hellman assumption and the eXternal Diffie-Hellman assumption.

Several recent standards, including NIST SP 800- 56A and RFC 5114, advocate the use of “DSA” parameters for Diffie-Hellman key exchange. While it is possible to use such parameters securely, additional validation checks are necessary to prevent well-known and potentially devastating attacks. In this paper, we observe that many Diffie-Hellman implementations do not properly validate key exchange inputs. Combined with other protocol properties and implementation choices, this can radically decrease security. We measure the prevalence of these parameter choices in the wild for HTTPS, POP3S, SMTP with STARTTLS, SSH, IKEv1, and IKEv2, finding millions of hosts using DSA and other non-“safe” primes for Diffie-Hellman key exchange, many of them in combination with potentially vulnerable behaviors. We examine over 20 open-source cryptographic libraries and applications and observe that until January 2016, not a single one validated subgroup orders by default. We found feasible full or partial key recovery vulnerabilities in OpenSSL, the Exim mail server, the Unbound DNS client, and Amazon’s load balancer, as well as susceptibility to weaker attacks in many other applications.