Recently, Coron presented an attack of GGH15 multilinear maps, which breaks the multipartite Diffie-Hellman key exchange protocol based on GGH15. In this paper, we describe a variation of GGH15, which seems to thwart known attacks.

Qin, Liu, Yuen, Deng, and Chen (PKC 2015) gave a new security notion of key-derivation function (KDF), continuous non-malleability with respect to $\Phi$-related-key attacks ($\Phi$-CNM), and its application to RKA-secure public-key cryptographic primitives. They constructed a KDF from cryptographic primitives and showed that the obtained KDF is $\Phi_{hoe\&iocr}$-CNM, where $\Phi_{hoe\&iocr}$ contains the identity function, the constant functions, and functions that have high output-entropy (HOE) and input-output collision-resistance (IOCR) simultaneously. This short note disproves the security of their KDF by giving $\Phi_{hoe\&iocr}$-RKAs by exploiting the components of their KDF. We note that their proof is still correct for $\Phi$-CNM for a subset of $\Phi_{hoe\&iocr}$; for example the KDF satisfies $\Phi_{poly(d)}$-CNM, in which an adversary can tamper with a secret by using polynomials of degree at most $d$.

Designing attribute-based systems supporting highly expressive access policies has been one of the principal focus of research in attribute-based cryptography. While attribute-based encryption (ABE) enables fine-grained access control over encrypted data in a multi-user environment, attribute-based signature (ABS) provides a powerful tool for preserving signer anonymity. Attributebased signcryption (ABSC), on the other hand, is a combination of ABE and ABS into a unified cost-effective primitive. In this paper, we start by presenting a key-policy ABE supporting general polynomial-size circuit realizable decryption policies and featuring compactness. More specifically, our ABE construction exhibits short ciphertexts and shorter decryption keys compared to existing similar works. We then proceed to design a key-policy ABSC scheme which enjoys several interesting properties that were never achievable before. It supports arbitrary polynomial-size circuits, thereby handles highly sophisticated control over signing and decryption rights. Besides, it generates short ciphertext as well. Our ABE construction employs multilinear map of level $n + l + 1$, while that used for our ABSC scheme has level $n + n' + l + 1$, where $n$, $n'$, and $l$ represent respectively the input length of decryption policy circuits, input size of signing policy circuits, and depth of both kinds of circuits. Selective security of our constructions are proven in the standard model under the Multilinear Decisional Diffie-Hellman and Multilinear Computational Diffie-Hellman assumptions which are standard complexity assumptions in the multilinear map setting. Our key-policy constructions can be converted to the corresponding ciphertext-policy variants achieving short ciphertext by utilizing the technique of universal circuits.

This paper introduces a new central trapdoor for multivariate quadratic (MQ) public-key cryptosystems that allows for encryption, in contrast to time-tested MQ primitives such as Unbalanced Oil and Vinegar or Hidden Field Equations which only allow for signatures. Our construction is a mixed-field scheme that exploits the commutativity of the extension field to dramatically reduce the complexity of the extension field polynomial implicitly present in the public key. However, this reduction can only be performed by the user who knows concise descriptions of two simple polynomials, which constitute the private key. After applying this transformation, the plaintext can be recovered by solving a linear system. We use the minus and projection modifiers to inoculate our scheme against known attacks. A straightforward C++ implementation confirms the efficient operation of the public key algorithms.

The Learning Parity with Noise problem (LPN) is appealing in cryptography as it is considered to remain hard in the post-quantum world. It is also a good candidate for lightweight devices due to its simplicity. In this paper we provide a comprehensive analysis of the existing LPN solving algorithms, both for the general case and for the sparse secret scenario. In practice, the LPN-based cryptographic constructions use as a reference the security parameters proposed by Levieil and Fouque. But, for these parameters, there remains a gap between the theoretical analysis and the practical complexities of the algorithms we consider. The new theoretical analysis in this paper provides tighter bounds on the complexity of LPN solving algorithms and narrows this gap between theory and practice. We show that for a sparse secret there is another algorithm that outperforms BKW and its variants. Following from our results, we further propose practical parameters for different security levels.

The security of pairing-based cryptography is based on the hardness of solving the discrete logarithm problem (DLP) over extension field F_{p^n} of characteristic p and degree n. Joux et al. proposed an asymptotically fastest algorithm for solving DLP over F_{p^n} (JLSV06-NFS) as the extension of the number field sieve over prime field F _p (JL03-NFS). The lattice sieve is often used for a large-scaled experiment of solving DLP over F_p by the number field sieve. Franke and Kleinjung proposed a 2-dimensional lattice sieve which efficiently enumerates all the points in a given sieve region of the lattice. However, we have to consider a sieve region of more than 2 dimensions in the lattice sieve of JLSV06-NFS. In this paper, we extend the Franke-Kleinjung method to 3-dimensional sieve region. We construct an appropriate basis using the Hermite normal form, which can enumerate the points in a given sieve region of the 3-dimensional lattice. From our experiment on F_{p^{12}} of 303 bits, we are able to enumerate more than 90\% of the points in a sieve region in the lattice generated by special-q. Moreover, we implement the number field sieve using the proposed 3-dimensional lattice sieve. Our implementation of the JLSV06 over F_{p^6} of 240 bits is about as efficient as that of the current record over F_{p^6} using 3-dimensional line sieve by Zajac.

In this paper we consider a two party key-exchange protocol proposed by Grigoriev and Shpilrain which uses tropical matrix algebra as a platform. Our analysis shows that the scheme is not secure.

Software Watermarking is the process of transforming a program into a functionally equivalent ``marked'' program in such a way that it is computationally hard to remove the mark without destroying functionality. Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan and Yang (CRYPTO 2001) defined software watermarking and showed that the existence of indistinguishability obfuscation implies that software watermarking is impossible. Given the recent candidate constructions of indistinguishability obfuscation, this result paints a bleak picture for the possibility of meaningful watermarking. We show that slightly relaxing the functionality requirement gives us strong positive results for watermarking. Namely, instead of requiring the marked program to agree with the original unmarked program on {\em all inputs}, we require only that they agree on a large fraction of inputs. With this relaxation in mind, our contributions are as follows. 1. We define publicly verifiable watermarking where marking a program requires a secret key, but anyone can verify that a program is marked. The handful of existing watermarking schemes are secretly verifiable, and moreover, satisfy only a weak definition where the adversary is restricted in the type of unmarked programs it is allowed to produce (Naccache, Shamir and Stern, PKC 1999; Nishimaki, EUROCRYPT 2013). Moreover, our definition requires security against chosen program attacks, where an adversary has access to an oracle that marks programs of her choice. 2. We construct a publicly verifiable watermarking scheme for any family of puncturable pseudo-random functions (PPRF), assuming indistinguishability obfuscation and injective one-way functions. Complementing our positive result, we show that there are pseudo-random functions which cannot be watermarked, even in a very weak setting. As a corollary, we demonstrate the first family of PRFs that are not point-puncturable.

The encryption scheme NTRU is designed over a quotient ring of a polynomial ring. Basically, if the ring is changed to any other ring, NTRU-like cryptosystem is constructible. In this paper, we propose a variant of NTRU using group ring, which is called GR-NTRU. GR-NTRU includes NTRU as a special case. Moreover, we analyze and compare the security of GR-NTRU for several concrete groups. It is easy to investigate the algebraic structure of group ring by using group representation theory. We apply this fact to the security analysis of GR-NTRU. We show that the original NTRU and multivariate NTRU are most secure among several GR-NTRUs which we investigated.

In early 2000's, Rivest~\cite{CambridgeTalk-Rivest,TSS-Micali} and Micali~\cite{TSS-Micali} introduced the notion of \emph{transitive signature}, which allows a third party to generate a valid signature for a composed edge $(v_i, v_k)$, from the signatures for two edges $(v_i, v_j)$ and $(v_j, v_k)$, and using the public key only. Since then, a number of works, including \cite{TSS-Micali,transig-fac-rsa-Bellare,hohenberger-masters,TSS-BilinearGroup-Shahandashti,transig-Bellare}, have been devoted on transitive signatures. Most of them address the undirected transitive signature problem, and the directed transitive signature is still an open problem. S.~Hohenberger~\cite{hohenberger-masters} even showed that a directed transitive signature implies a complex mathmatical group, whose existence is still unkown. Recently, a few directed transitive signature schemes~\cite{DirectedTSS-Yi,dtts-Neven} on directed trees are proposed. The drawbacks of these schemes include: the size of composed signature increases linearly with the number of recursive applications of composition and the creating history of composed edge is not hidden properly. This paper presents {\DTTS}---a \emph{Directed}-Tree-Transitive Signature scheme, to address these issues. Like previous works~\cite{DirectedTSS-Yi,dtts-Neven}, {\DTTS} is designed only for directed trees, however, it features with constant (composed) signature size and privacy preserving property. %oblivious composition history G.~Neven~\cite{dtts-Neven} pointed out constant signature size is an essential requirement of the original directed transitive signature problem raised by Rivest and Micali. In this sense, our scheme {\DTTS} is the \emph{first} transitive signature scheme on a directed tree. We also prove that {\DTTS} is transitively unforgeable under adaptive chosen message attack in the standard model.

Previously known functional encryption (FE) schemes for general circuits relied on indistinguishability obfuscation, which in turn either relies on an exponential number of assumptions (basically, one per circuit), or a polynomial set of assumptions, but with an exponential loss in the security reduction. Additionally these schemes are proved in the weaker selective security model, where the adversary is forced to specify its target before seeing the public parameters. For these constructions, full security can be obtained but at the cost of an exponential loss in the security reduction. In this work, we overcome the above limitations and realize a fully secure functional encryption scheme without using indistinguishability obfuscation. Specifically the security of our scheme relies only on the polynomial hardness of simple assumptions on multilinear maps. As a separate technical contribution of independent interest, we show how to add to existing graded encoding schemes a new \emph{extension function}, that can be though of as dynamically introducing new encoding levels.

Multi-HFE (Chen et al., 2009) is one of cryptosystems whose public key is a set of multivariate quadratic forms over a finite field. Its quadratic forms are constructed by a set of multivariate quadratic forms over an extension field. Recently, Bettale et al. (2013) have studied the security of HFE and multi-HFE against the min-rank attack and found that multi-HFE is not more secure than HFE of similar size. In the present paper, we propose a new attack on multi-HFE by using a diagonalization approach. As a result, our attack can recover equivalent secret keys of multi-HFE in polynomial time for odd characteristic case. In fact, we experimentally succeeded to recover equivalent secret keys of several examples of multi-HFE in about fifteen seconds on average, which was recovered in about nine days by the min-rank attack.

Myers and Shelat (FOCS 2009) showed how to convert a chosen ciphertext secure (CCA secure) PKE scheme that can encrypt only $1$-bit plaintexts into a CCA secure scheme that can encrypt arbitrarily long plaintexts (via the notion of key encapsulation mechanism (KEM) and hybrid encryption), and subsequent works improved efficiency and simplicity. In terms of efficiency, the best known construction of a CCA secure KEM from a CCA secure 1-bit PKE scheme, has the public key size $\Omega(k) \cdot |pk|$ and the ciphertext size $\Omega(k^2) \cdot |c|$, where $k$ is a security parameter, and $|pk|$ and $|c|$ denote the public key size and the ciphertext size of the underlying $1$-bit scheme, respectively. In this paper, we show a new CCA secure KEM based on a CCA secure $1$-bit PKE scheme which achieves the public key size $2 \cdot |pk|$ and the ciphertext size $(2k + o(k)) \cdot |c|$. These sizes are asymptotically optimal in the sense that they are (except for a constant factor) the same as those of the simplest \lq\lq bitwise-encrypt'' construction (seen as a KEM by encrypting a $k$-bit random session-key) that works for the chosen plaintext attack and non-adaptive chosen ciphertext attack settings. We achieve our main result by developing several new techniques and results on the \lq\lq double-layered'' construction (which builds a KEM from an inner PKE/KEM and an outer PKE scheme) by Myers and Shelat and on the notion of detectable PKE/KEM by Hohenberger, Lewko, and Waters (EUROCRYPT 2012).

In 2010, van Dijk, Gentry, Halevi, and Vaikuntanathan described the first fully homomorphic encryption over the integers, called DGHV. The scheme is based on a set of $m$ public integers $c_i=pq_i+r_i$, $i=1,\cdots,m$, where the integers $p$, $q_i$ and $r_i$ are secret. In this paper, we describe two lattice-based attacks on DGHV. The first attack is applicable when $r_1=0$ and the public integers $c_i$ satisfy a linear equation $a_2c_2+\ldots+a_mc_m=a_1q_1$ for suitably small integers $a_i$, $i=2,\ldots,m$. The second attack works when the positive integers $q_i$ satisfy a linear equation $a_1q_1+\ldots+a_mq_m=0$ for suitably small integers $a_i$, $i=1,\ldots,m$. We further apply our methods for the DGHV recommended parameters as specified in the original work of van Dijk, Gentry, Halevi, and Vaikuntanathan.

In security proofs of lattice based cryptography, bounding the closeness of two probability distributions is an important procedure. To measure the closeness, the Rényi divergence has been used instead of the classical statistical distance. Recent results have shown that the Rényi divergence offers security reductions with better parameters, e.g. smaller deviations for discrete Gaussian distributions. However, since previous analyses used a fixed order Rényi divergence, i.e., order two, they lost tightness of reductions. To overcome the deficiency, we adaptively optimize the orders based on the advantages of the adversary for several lattice-based schemes. The optimizations enable us to prove the security with both improved efficiency and tighter reductions. Indeed, our analysis offers security reductions with smaller parameters than the statistical distance based analysis and the reductions are tighter than those of previous Rényi divergence based analyses. As applications, we show tighter security reductions for sampling discrete Gaussian distributions with smaller precomputed tables for Bimodal Lattice Signature Scheme (BLISS), and the variants of learning with errors (LWE) problem and the small integer solution (SIS) problem called k-LWE and k-SIS, respectively.

The Modular Inversion Hidden Number Problem (MIHNP) was introduced by Boneh, Halevi and Howgrave-Graham in Asiacrypt 2001 (BHH’01). They provided two heuristics - in Method I, two-third of the output bits are required to solve the problem, whereas the more efficient heuristic (Method II) requires only one-third of the bits of the output. After more than a decade, here Sarkar in [28] identified that the claim in Method II is actually not correct and a detailed calculation justified that this method too requires two-third of the bits of the output, contrary to the claim in BHH’01. He reconstructed the lattice and give a bound which heuristically solve with half of the output bits. Although J.Xu et al in [29] solved it with only one-third of the output bits asymptotically but that technique is difficult to understand and implement. Here we essentially use similar idea of [28] but in a clever way such that it is a better bound although we solve the problem heuristically with only half of the output bits in asymptotic sense. This is lot easier to understand and implement. Also experimental results support the claim corresponding to our heuristics. In the last section we actually talk about a variant of this which seems to be hard to solve under lattice attack.

The notion of multi-input functional encryption (MI-FE) was recently introduced by Goldwasser et al. [EUROCRYPT’14] as a means to non-interactively compute aggregate information on the joint private data of multiple users. A fundamental limitation of their work, however, is that the total number of users (which corresponds to the arity of the functions supported by the MI-FE scheme) must be a priori bounded and fixed at the system setup time. In this work, we overcome this limitation by introducing the notion of unbounded input MI-FE that supports the computation of functions with unbounded arity. We construct such an MI-FE scheme with indistinguishability security in the selective model based on the existence of public-coin differing-inputs obfuscation for turing machines and collision-resistant hash functions. Our result enables several new exciting applications, including a new paradigm of on-the-fly secure multiparty computation where new users can join the system dynamically.

In the ordinary security model for signature schemes, we consider an adversary that may forge a signature on a new message using only his knowledge of other valid message and signature pairs. To take into account side channel attacks such as tampering or fault-injection attacks, Bellare and Kohno (Eurocrypt 2003) formalized related-key attacks (RKA), where stronger adversaries are considered. In RKA for signature schemes, the adversary can also manipulate the signing key and obtain signatures for the modified key. This paper considers RKA security of two established signature schemes: the Schnorr signature scheme and (a well-known variant of) DSA. First, we show that these signature schemes are secure against a weak notion of RKA. Second, we demonstrate that, on the other hand, neither the Schnorr signature scheme nor DSA achieves the standard notion of RKA security, by showing concrete attacks on these. Lastly, we show that a slight modification of both the Schnorr signature scheme and (the considered variant of) DSA yields fully RKA secure schemes.

We construct a new structure-preserving signature scheme in the efficient Type-III asymmetric bilinear group setting with signatures shorter than all existing schemes. Our signatures consist of 3 group elements from the first source group and therefore have shorter size than all existing schemes as existing ones have at least one component of the signature in the second source group whose elements bit size is at least double their first group counterparts. Besides enjoying short signatures, our scheme is fully re-randomizable which is a useful property for many applications. Our result also constitutes a proof that the impossibility of unilateral structure-preserving signatures in the Type-III setting result of Abe et al.~(Crypto 2011) does not apply to constructions in which the message space is dual in both source groups. Besides checking the well-formedness of the message, verifying a signature in our scheme requires checking $2$ Pairing Product Equations (PPE) and require the evaluation of only $5$ pairings in total which matches the best existing scheme and outperforms many other existing ones. Reducing the number of pairings in the verification equations is very important when combining structure-preserving signature schemes with Groth-Sahai proofs as the number of pairings required for verifying Groth-Sahai proofs for PPE equations grows linearly with the number of pairing monomials in the source equations. We give some examples of how using our new scheme instead of existing ones improves the efficiency of some existing cryptographic protocols such as direct anonymous attestation and group signature related constructions.

About three decades ago it was realized that implementing private channels between parties which can be adaptively corrupted requires an encryption scheme that is secure against selective opening attacks. Whether standard (IND-CPA) security implies security against selective opening attacks has been a major open question since. The only known reduction from selective opening to IND-CPA security loses an exponential factor. A polynomial reduction is only known for the very special case where the distribution considered in the selective opening security experiment is a product distribution, i.e., the messages are samples independent from each other. In this paper we give a reduction whose loss is quantified via the dependence graph (where message dependencies correspond to edges) of the underlying message distribution. In particular, for some concrete distributions including Markov distributions, our reduction is polynomial.

Boneh et al. showed at Crypto 99 that moduli of the form N=p^r q can be factored in polynomial time when r=log p. Their algorithm is based on Coppersmith's technique for finding small roots of polynomial equations. In this paper we show that N=p^r q^s can also be factored in polynomial time when r or s is at least (log p)^3; therefore we identify a new class of integers that can be efficiently factored. We also generalize our algorithm to moduli N with k prime factors; we show that a non-trivial factor of N can be extracted in polynomial-time if one of the k exponents is large enough.

The purpose of this paper is to compare side-by-side the NTRU and BGV schemes in their non-scale invariant (messages in the lower bits), and their scale invariant (message in the upper bits) forms. The scale invariant versions are often called the FV and YASHE schemes. As an additional optimization, we also investigate the affect of modulus reduction on the scale-invariant schemes. We compare the schemes using the ``average case'' noise analysis presented by Gentry et al. In addition we unify notation and techniques so as to show commonalities between the schemes. We find that the BGV scheme appears to be more efficient for large plaintext moduli, whilst YASHE seems more efficient for small plaintext moduli (although the benefit is not as great as one would have expected).

In this paper, we analyze the security of cryptosystems using short generators over ideal lattices such as candidate multilinear maps by Garg, Gentry and Halevi and fully homomorphic encryption by Smart and Vercauteren. Our approach is based on a recent work by Cramer, Ducas, Peikert and Regev on analysis of recovering a short generator of an ideal in the $q$-th cyclotomic field for a prime power $q$. In their analysis, implicit lower bounds of the special values of Dirichlet $L$-functions at 1 are essentially used for estimating some sizes of the dual basis in the log-unit lattice of the $q$-th cyclotomic field. Our main contribution is to improve Cramer et al.'s analysis by giving explicit lower and upper bounds of the special values of Dirichlet $L$-functions at 1 for any non-trivial even Dirichlet characters modulo $q$. Moreover, we give various experimental evidence that recovering short generators of principle ideals in $2k$-th cyclotomic fields for $k \geq 10$ is succeeded with high probability. As a consequence, our analysis suggests that the security of the above cryptosystems based on the difficulty of recovering a short generator is reduced to solving the principal ideal problem under the number theoretical conjecture so-called Weber's class number problem.

Goldwasser and Micali (1984) highlighted the importance of randomizing the plaintext for public-key encryption and introduced the notion of semantic security. They also realized a cryptosystem meeting this security notion under the standard complexity assumption of deciding quadratic residuosity modulo a composite number. The Goldwasser-Micali cryptosystem is simple and elegant but is quite wasteful in bandwidth when encrypting large messages. A number of works followed to address this issue and proposed various modifications. This paper revisits the original Goldwasser-Micali cryptosystem using 2^k-th power residue symbols. The so-obtained cryptosystems appear as a very natural generalization for k >= 2 (the case k = 1 corresponds exactly to the Goldwasser-Micali cryptosystem). Advantageously, they are efficient in both bandwidth and speed; in particular, they allow for fast decryption. Further, the cryptosystems described in this paper inherit the useful features of the original cryptosystem (like its homomorphic property) and are shown to be secure under a similar complexity assumption. As a prominent application, this paper describes an efficient lossy trapdoor function based thereon.

We show how to garble a large persistent database and then garble, one by one, a sequence of adaptively and adversarially chosen RAM programs that query and modify the database in arbitrary ways. Still, it is guaranteed that the garbled database and programs reveal only the outputs of the programs when run in sequence on the database. The runtime, space requirements and description size of the garbled programs are proportional only to those of the plaintext programs and the security parameter. We assume indistinguishability obfuscation for circuits and poly-to-one collision-resistant hash functions. The latter can be constructed based on standard algebraic assumptions such as the hardness of discrete log or factoring. In contrast, all previous garbling schemes with persistent data were shown secure only in the static setting where all the programs are known in advance. As an immediate application, our scheme is the first to provide a way to outsource large databases to untrusted servers, and later query and update the database over time in a private and verifiable way, with complexity and description size proportional to those of the unprotected queries. Our scheme extends the non-adaptive RAM garbling scheme of Canetti and Holmgren [ITCS 2016]. We also define and use a new primitive, called adaptive accumulators, which is an adaptive alternative to the positional accumulators of Koppula et al [STOC 2015] and somewhere statistical binding hashing of Hubacek and Wichs [ITCS 2015]. This primitive might well be useful elsewhere.

To accomplish effective privacy protection in smart grid systems, various approaches were proposed combining information security technology with the smart grid's new features. Diao et al. proposed a privacy-preserving scheme using linkable anonymous credential based on CL signature, and demonstrated its identity anonymity, message authentication and traceability of broken smart meters. In this paper, a forgery attack is presented to point out the protocol dissatisfies message authentication and unforgeability. We hold the idea that this scheme doesn't have basic safety requirements and application value.

Deniable encryption (Canetti et al. CRYPTO '97) is an intriguing primitive that provides a security guarantee against not only eavesdropping attacks as required by semantic security, but also stronger coercion attacks performed after the fact. The concept of deniability has later demonstrated useful and powerful in many other contexts, such as leakage resilience, adaptive security of protocols, and security against selective opening attacks. Despite its conceptual usefulness, our understanding of how to construct deniable primitives under standard assumptions is restricted. In particular, from standard assumptions such as Learning with Errors (LWE), we have only multi-distributional or non-negligible advantage deniable encryption schemes, whereas with the much stronger assumption of indistinguishable obfuscation, we can obtain at least fully-secure sender-deniable PKE and computation. How to achieve deniability for other more advanced encryption schemes under standard assumptions remains an interesting open question. In this work, we construct a bi-deniable inner product encryption (IPE) in the multi-distributional model without relying on obfuscation as a black box. Our techniques involve new ways of manipulating Gaussian noise, and lead to a significantly tighter analysis of noise growth in Dual Regev type encryption schemes. We hope these ideas can give insight into achieving deniability and related properties for further, advanced cryptographic constructions under standard assumptions.

In this note we provide a more-or-less unified framework to talk about the functionality and security of graded encoding schemes, describe some variations of recent schemes, and discuss their security. In particular we describe schemes that combine elements from both the GGH13 scheme of Garg, Gentry and Halevi (EUROCRYPT 2013) and the GGH15 scheme of Gentry, Gorbunov and Halevi (TCC 2015). On one hand, we show how to use techniques from GGH13 in the GGH15 construction to enable encoding of arbitrary plaintext elements (as opposed to only small ones) and to introduce "levels/subsets" (e.g., as needed to implement straddling sets). On the other hand, we show how to modify the GGH13 scheme to support graph-induced constraints (either instead of, or in addition to, the levels from GGH13). Turning to security, we describe zeroizing attacks on the GGH15 scheme, similar to those described by Cheon et al. (EUROCRYPT 2015) and Coron et al. (CRYPTO 2015) on the CLT13 and GGH13 constructions. As far as we know, however, these attacks to not break the GGH15 multi-partite key-agreement protocol. We also describe a new multi-partite key-agreement protocol using the GGH13 scheme, which also seems to resist known attacks. That protocol suggests a relatively simple hardness assumption for the GGH13 scheme, that we put forward as a target for cryptanalysis.

We put forward the concept of a reconfigurable cryptosystem. Intuitively, a reconfigurable cryptosystem allows to increase the security of the system at runtime, by changing a single central parameter we call common reference string (CRS). In particular, e.g., a cryptanalytic advance does not necessarily entail a full update of a large public-key infrastructure; only the CRS needs to be updated. In this paper we focus on the reconfigurability of encryption and signature schemes, but we believe that this concept and the developed techniques can also be applied to other kind of cryptosystems. Besides a security definition, we offer two reconfigurable encryption schemes, and one reconfigurable signature scheme. Our first reconfigurable encryption scheme uses indistinguishability obfuscation (however only in the CRS) to adaptively derive short-term keys from long-term keys. The security of long-term keys can be based on a one-way function, and the security of both the indistinguishability obfuscation and the actual encryption scheme can be increased on-the-fly, by changing the CRS. We stress that our scheme remains secure even if previous short-term secret keys are leaked. Our second reconfigurable encryption scheme has a similar structure (and similar security properties), but relies on a pairing-friendly group instead of obfuscation. Its security is based on the recently introduced hierarchy of \(k\)-SCasc assumptions. Similar to the \(k\)-Linear assumption, it is known that \(k\)-SCasc implies \((k+1)\)-SCasc, and that this implication is proper in the generic group model. Our system allows to increase \(k\) on-the-fly, just by changing the CRS. In that sense, security can be increased without changing any long-term keys. We also offer a reconfigurable signature scheme based on the same hierarchy of assumptions.

In this paper, we study the discrete logarithm problem in medium and high characteristic finite fields. We propose a variant of the Number Field Sieve (NFS) based on numerous number fields. Our improved algorithm computes discrete logarithms in $\mathbb{F}_{p^n}$ for the whole range of applicability of NFS and lowers the asymptotic complexity from $L_{p^n}(1/3, (128/9)^{1/3})$ to $L_{p^n}(1/3, (2^{13} /3^6)^{1/3})$ in the medium characteristic case, and from $L_{p^n} (1/3, (64/9)^{1/3})$ to $L_{p^n}(1/3,((92 + 26\sqrt{13})/27))^{1/3})$ in the high characteristic case. Version 2 contains an erratum.

In PQCrypto 2013 Yasuda, Takagi and Sakurai proposed an interesting signature scheme of efficiency $O(n^2)$ with parameter $(q=6781, n=121)$ claimed to have 140-bit security level. Later on almost at the same time two independent and different attacks were then proposed by Y. Hashimoto in PQCrypto 2014 and by the authors in ICISC 2014. Hashimoto's attack has complexity $O(n^4)$ and breaks $(q=6781, n=121)$ in several minutes. In this paper, we make an essential extension of our work in ICISC 2014. We develop for the our previous method a thorough and rigorous mathematical theory by applying intensively the theory of invariant subspaces, then work out a much better attack with complexity $O(n^4)$, and especially implement it successfully. Our new attack efficiently recovers equivalent private keys of many randomly generated instances, especially breaking $(q=6781, n=121)$ in only about 14.77 seconds, much faster than Y. Hashimoto's attack. The approach developed here might have further applications.

In a traitor tracing scheme, each user is given a different decryption key. A content distributor can encrypt digital content using a public encryption key and each user in the system can decrypt it using her decryption key. Even if a coalition of users combines their decryption keys and constructs some ``pirate decoder'' that is capable of decrypting the content, there is a public tracing algorithm that is guaranteed to recover the identity of at least one of the users in the coalition given black-box access to such decoder. In prior solutions, the users are indexed by numbers $1,\ldots,N$ and the tracing algorithm recovers the index $i$ of a user in a coalition. Such solutions implicitly require the content distributor to keep a record that associates each index $i$ with the actual identifying information for the corresponding user (e.g., name, address, etc.) in order to ensure accountability. In this work, we construct traitor tracing schemes where all of the identifying information about the user can be embedded directly into the user's key and recovered by the tracing algorithm. In particular, the content distributor does not need to separately store any records about the users of the system, and honest users can even remain anonymous to the content distributor. The main technical difficulty comes in designing tracing algorithms that can handle an exponentially large universe of possible identities, rather than just a polynomial set of indices $i \in [N]$. We solve this by abstracting out an interesting algorithmic problem that has surprising connections with seemingly unrelated areas in cryptography. We also extend our solution to a full ``broadcast-trace-and-revoke'' scheme in which the traced users can subsequently be revoked from the system. Depending on parameters, some of our schemes can be based only on the existence of public-key encryption while others rely on indistinguishability obfuscation.

Three recent proposals for standardization of next-generation ECC signatures have included "key prefixing" modifications to Schnorr's signature system. Bernstein, Duif, Lange, Schwabe, and Yang stated in 2011 that key prefixing is "an inexpensive way to alleviate concerns that several public keys could be attacked simultaneously". However, a 2002 theorem by Galbraith, Malone-Lee, and Smart states that, for the classic Schnorr signature system, single-key security tightly implies multi-key security. Struik and then Hamburg, citing this theorem, argued that key prefixing was unnecessary for multi-user security and should not be standardized. This paper identifies an error in the 2002 proof, and an apparently insurmountable obstacle to the claimed theorem. The proof idea does, however, lead to a different theorem, stating that single-key security of the classic Schnorr signature system tightly implies multi-key security of the key-prefixed variant of the system. This produces exactly the opposite conclusion regarding standardization.

Cryptographic multilinear map is a useful tool for constructing numerous secure protocols and Graded Encoding System (GES) is an {\em approximate} concept of multilinear map. In multilinear map context, there are several important issues, mainly about security and efficiency. All early stage candidate multilinear maps are recently broken by so-called zeroizing attack, so that it is highly required to develop reliable mechanisms to prevent zeroizing attacks. Moreover, the encoding size in all candidate multilinear maps grows quadratically in terms of multilinearity parameter $\kappa$ and it makes them less attractive for applications requiring large $\kappa$. In this paper, we propose a new integer-based multilinear map that has several advantages over previous schemes. In terms of security, we expect that our construction is resistant to the zeroizing attack. In terms of efficiency, the bit-size of an encoding grows sublinearly with $\kappa$, more precisely $O((\log_2\kappa)^2)$. To this end, we essentially utilize a technique of the multiplication procedure in {\em scale-invariant} fully homomorphic encryption (FHE), which enables to achieve sublinear complexity in terms of multilinearity and at the same time security against the zeroizing attacks (EUROCRYPT 2015, IACR-Eprint 2015/934, IACR-Eprint 2015/941), which totally broke Coron, Lepoint, and Tibouchi's integer-based construction (CRYPTO 2013, CRYPTO2015). We find that the technique of scale-invariant FHE is not very well harmonized with previous approaches of making GES from (non-scale-invariant) FHE. Therefore, we first devise a new approach for approximate multilinear maps, called {\em Ring Encoding System (RES)}, and prove that a multilinear map built via RES is generically secure. Next, we propose a new efficient scale-invariant FHE with special properties, and then construct a candidate RES based on a newly proposed scale-invariant FHE. It is worth noting that, contrary to the CLT multilinear map (CRYPTO 2015), multiplication procedure in our construction does not add hidden constants generated by ladders of zero encodings, but mixes randoms in encodings in non-linear ways without using ladders of zero encodings. This feature is obtained by using the scale-invariant FHE and essential to prevent the Cheon et al.'s zeroizing attack.

The challenge of maintaining confidentiality of stored data in cloud is of utmost importance to realize the potential of cloud computing. Storing data in encrypted form may solve the problem, but increases the security issues and diminishes the essence of cloud while performing operations on cloud data by repeated decryption-encryption. Hence, Fully homomorphic encryption (FHE) is an effective scheme to support arbitrary operations directly on encrypted data. Further, cloud mostly acts as storage database, hence secured sorting and searching of FHE cloud data can be an effective field of research. We have investigated the feasibility of performing comparison as well as partition based sort on CPA resistant FHE data and highlight an important observation that time requirement of partition based sort on FHE data is no better than comparison based sort owing to the security of the cryptosystem. We identify the recrypt operation, which is the denoising step of FHE as the main reason of costly timing requirement of such operations. Finally, we propose a two stage sorting technique termed as Lazy sort with reduced recrypt operation, which proves to be better in terms of performance on FHE data in comparison to partition as well as comparison sort.

We describe a new technique for conducting ``partitioning arguments''. Partitioning arguments are a popular way to prove the security of a cryptographic scheme. For instance, to prove the security of a signature scheme, a partitioning argument could divide the set of messages into ``signable'' messages for which a signature can be simulated during the proof, and ``unsignable'' ones for which any signature would allow to solve a computational problem. During the security proof, we would then hope that an adversary only requests signatures for signable messages, and later forges a signature for an unsignable one. In this work, we develop a new class of partitioning arguments from simple assumptions. Unlike previous partitioning strategies, ours is based upon an algebraic property of the partitioned elements (e.g., the signed messages), and not on their bit structure. This allows to perform the partitioning efficiently in a ``hidden'' way, such that already a single ``slot'' for a partitioning operation in the scheme can be used to implement many different partitionings sequentially, one after the other. As a consequence, we can construct complex partitionings out of simple basic (but algebraic) partitionings in a very space-efficient way. As a demonstration of our technique, we provide the first signature and public-key encryption schemes that achieve the following properties simultaneously: they are (almost) tightly secure under a simple assumption, and they are fully compact (in the sense that parameters, keys, and signatures, resp.~ciphertexts only comprise a constant number of group elements).

The paper presented an identity based encryption (IBE) under selective opening attack (SOA) whose security is almost-tightly related to a set of computational assumptions. Our result is a combination of Bellare, Waters, and Yilek's method [TCC, 2011] for constructing (not tightly) SOA secure IBE and Hofheinz, Koch, and Striecks' technique [PKC, 2015] on building almost-tightly secure IBE in the multi-ciphertext setting. In particular, we first tuned Bellare et al.'s generic construction for SOA secure IBE to show that a one-bit IBE achieving ciphertext indistinguishability under chosen plaintext attack in the multi-ciphertext setting (with one-sided publicly openability) tightly implies a multi-bit IBE secure under selective opening attack. Next, we almost-tightly reduced such a one-bit IBE to static assumptions in the composite-order bilinear groups employing the technique of Hofheinz et al. This yielded the first SOA secure IBE with almost-tight reduction.

In the paper about the cryptosystem MST3, Svaba and Trung pro- posed a way to build a cryptosystem based on the concept of logarithmic signa- tures, and they choose Suzuki's group, which is not abelian for implementing. Recently, to reason why these methods cannot be applied to abelian groups; Sv- aba, Trung and Wolf developed some algorithms to factorize the fused transver- sal logarithmic signatures (FTLS). Their attacks can be avoided by some mod- ications, which is the aim of this paper, where we will use the weakness of the discrete logarithm problem (DLP) to propose two cryptosystems. The rst one is based on the new concept about quasi-logarithmic signature of nite solvable groups, which is the generalization of logarithmic signatures. The second is built on the logarithmic signatures of nite cyclic 2-groups, which include two interesting examples on Pell's curves and elliptic curves over nite elds.

Bilinear maps are popular cryptographic primitives which have been commonly used in various modern cryptographic protocols. However, the cost of computation for bilinear maps is expensive because of their realization using variants of Weil and Tate pairings of elliptic curves. Due to increasing availability of cloud computing services, devices with limited computational resources can outsource this heavy computation to more powerful external servers. Currently, the checkability probability of the most efficient outsourcing algorithm is $1/2$ and the overall computation requires $4$ point addition in the preimage and $3$ multiplications in the image of the bilinear map under the one-malicious version of a two-untrusted-program model. In this paper, we propose two efficient new algorithms which decrease not only the memory requirement but also the overall communication overhead.

Hash Proof Systems were first introduced by Cramer and Shoup (Eurocrypt'02) as a tool to construct efficient chosen-ciphertext-secure encryption schemes. Since then, they have found many other applications, including password authenticated key exchange, oblivious transfer, and zero-knowledge arguments. One of the aspects that makes hash proof systems so interesting and powerful is that they can be seen as implicit proofs of membership for certain languages. As a result, by extending the family of languages that they can handle, one often obtains new applications or new ways to understand existing schemes. In this paper, we show how to construct hash proof systems for the disjunction of languages defined generically over cyclic, bilinear, and multilinear groups. Among other applications, this enables us to construct the most efficient one-time simulation-sound (quasi-adaptive) non-interactive zero-knowledge arguments for linear languages over cyclic groups, the first one-round group password-authenticated key exchange without random oracles, the most efficient threshold structure-preserving chosen-ciphertext-secure encryption scheme, and the most efficient one-round password authenticated key exchange in the UC framework.

Signatures with partially message recovery in which some parts of messages are not transmitted with signatures to make them shorter are useful where bandwidth is one of the crucial concern and especially in case of signing short messages in applications such as time stamping, certified email services and identitybased cryptosystems. In this paper, to have quantum-attackresistant short signatures, a signature scheme with partially message recovery from coding theory is proposed. The security of the proposed scheme is proved under Goppa Parametrized Bounded Decoding and the Goppa Code Distinguishing assumptions in the random oracle model. Relying on the partially message recovery property, the proposal is shorter than the Dallot signature scheme, the only provably secure and practical code-based signature scheme. We should highlight that our scheme can be used as a building block of code-based signature schemes with additional properties since it compared to Dallot signature scheme not only improves its communication overhead but also it preserves its signature efficiency.

Group signatures are a central cryptographic primitive which allows users to sign messages while hiding their identity within a crowd of group members. In the standard model (without the random oracle idealization), the most efficient constructions rely on the Groth-Sahai proof systems (Eurocrypt'08). The structure-preserving signatures of Abe et al. (Asiacrypt'12) make it possible to design group signatures based on well-established, constant-size number theoretic assumptions (a.k.a. ``simple assumptions'') like the Symmetric eXternal Diffie-Hellman or Decision Linear assumptions. While much more efficient than group signatures built on general assumptions, these constructions incur a significant overhead w.r.t. constructions secure in the idealized random oracle model. Indeed, the best known solution based on simple assumptions requires 2.8 kB per signature for currently recommended parameters. Reducing this size and presenting techniques for shorter signatures are thus natural questions. In this paper, our first contribution is to significantly reduce this overhead. Namely, we obtain the first fully anonymous group signatures based on simple assumptions with signatures shorter than 2 kB at the 128-bit security level. In dynamic (resp. static) groups, our signature length drops to 1.8 kB (resp. 1 kB). This improvement is enabled by two technical tools. As a result of independent interest, we first construct a new structure-preserving signature based on simple assumptions which shortens the best previous scheme by 25%. Our second tool is a new method for attaining anonymity in the strongest sense using a new CCA2-secure encryption scheme which is simultaneously a Groth-Sahai commitment.

We provide a framework for constructing leakage-resilient identification(ID) protocols in the bounded retrieval model (BRM) from proofs of storage(PoS) that hide partial information about the file. More precisely, we describe a generic transformation from any zero-knowledge PoS to a leakage-resilient ID protocol in the BRM. We then describe a ZK-PoS based on RSA which, under our transformation, yields the first ID protocol in the BRM based on RSA (in the ROM). The resulting protocol relies on a different computational assumption and is more efficient than previously-known constructions.

The recent advent of cloud computing and the IoT has made it imperative to have efficient and secure cryptographic schemes for online data sharing. Data owners would ideally want to store their data/files online in an encrypted manner, and delegate decryption rights for some of these to users with appropriate credentials. An efficient and recently proposed solution in this regard is to use the concept of aggregation that allows users to decrypt multiple classes of data using a single key of constant size. In this paper, we propose a secure and dynamic key aggregate encryption scheme for online data sharing that operates on elliptic curve subgroups while allowing dynamic revocation of user access rights. We augment this basic construction to a generalized two-level hierarchical structure that achieves optimal space and time complexities, and also efficiently accommodates extension of data classes. Finally, we propose an extension to the generalized scheme that allows use of efficiently computable bilinear pairings for encryption and decryption operations. Each scheme is formally proven to be semantically secure. Practical experiments have been conducted to validate all claims made in the paper.

Cloud data owners encrypt their documents before outsourcing to provide their privacy. They could determine a search control policy and delegate the ability of search token generation to the users whose attributes satisfy the search control policy. Verifiable attribute-based keyword search (VABKS) where the users can also verify the accuracy of cloud functionality is one of such schemes. In this paper, the first generic construction for VABKS is proposed. To this end, the notion of hierarchical identity-based multi-designated verifier signature (HIB-MDVS) has been introduced and existential forgery under chosen message attack (EF-CMA) is formally defined for its unforgeability. Furthermore, anonymity against chosen identity vector set and chosen plaintext attack (Anon-CIVS-CPA) has been defined as the security definition of hierarchical identity-based broadcast encryption (HIBBE) in a formal way. The proposed construction is built in a modular structure by using HIBBE, HIB-MDVS, and Bloom filter as the building blocks. We prove that the security of proposed construction is based on the unforgeability of HIB-MDVS and the anonymity of HIBBE. Finally, the concept of verifiable ranked keyword search will be introduced and a construction of this primitive will be presented which is based on proposed VABKS.

Functional encryption (FE) enables sophisticated control over decryption rights in a multi-user scenario, while functional signature (FS) allows to enforce complex constraints on signing capabilities. This paper introduces the concept of functional signcryption (FSC) that aims to provide the functionalities of both FE and FS in an unified cost-effective primitive. FSC provides a solution to the problem of achieving confidentiality and authenticity simultaneously in digital communication and storage systems involving multiple users with better efficiency compared to a sequential implementation of FE and FS. We begin by providing formal definition of FSC and formulating its security requirements. Next, we present a generic construction of this challenging primitive that supports arbitrary polynomial-size signing and decryption functions from known cryptographic building blocks, namely, indistinguishability obfuscation (IO) and statistically simulation-sound noninteractive zero-knowledge proof of knowledge (SSS-NIZKPoK). Finally, we exhibit a number of representative applications of FSC: (I) We develop the first construction of attribute-based signcryption (ABSC) supporting signing and decryption policies representable by general polynomial-size circuits from FSC. (II) We show how FSC can serve as a tool for building SSS-NIZKPoK system and IO, a result which in conjunction with our generic FSC construction can also be interpreted as establishing an equivalence between FSC and the other two fundamental cryptographic primitives.

The ring and polynomial learning with errors problems (Ring-LWE and Poly-LWE) have been proposed as hard problems to form the basis for cryptosystems, and various security reductions to hard lattice problems have been presented. So far these problems have been stated for general (number) rings but have only been closely examined for cyclotomic number rings. In this paper, we state and examine the Ring-LWE problem for general number rings and demonstrate provably weak instances of Ring-LWE. We construct an explicit family of number fields for which we have an efficient attack. We demonstrate the attack in both theory and practice, providing code and running times for the attack. The attack runs in time linear in q, where q is the modulus. Our attack is based on the attack on Poly-LWE which was presented in [EHL]. We extend the EHL-attack to apply to a larger class of number fields, and show how it applies to attack Ring-LWE for a heuristically large class of fields. Certain Ring-LWE instances can be transformed into Poly-LWE instances without distorting the error too much, and thus provide the first weak instances of the Ring-LWE problem. We also provide additional examples of fields which are vulnerable to our attacks on Poly-LWE, including power-of-2 cyclotomic fields, presented using the minimal polynomial of $\zeta_{2^n} \pm 1$.

The GHS attack is known to solve discrete logarithm problems (DLP) in the Jacobian of a curve C_0 defined over the d degree extension field k_d of k:=GF(q) by mapping it to the DLP in the Jacobian of a covering curve C of C_0 over k. Recently, classifications for all elliptic curves and hyperelliptic curves C_0/k_d of genus 2,3 which possess (2,...,2)-covering C/k of P^1 were shown under an isogeny condition (i.e. when g(C) = d * g(C_0)). This paper presents a systematic classification procedure for hyperelliptic curves in the odd characteristic case. In particular, we show a complete classification of elliptic curves C_0 over k_d which have (2,...,2)-covering C/k of P^1 for d=2,3,5,7. It has been reported by Diem that the GHS attack fails for elliptic curves C_0 over odd characteristic definition field k_d with prime extension degree d greater than or equal to 11 since g(C) become very large. Therefore, for elliptic curves over k_d with prime extension degree d, it is sufficient to analyze cases of d=2,3,5,7. As a result, a complete list of all elliptic curves C_0/k which possess (2,...,2)-covering C/k of P^1 thus are subjected to the GHS attack with odd characteristic and prime extension degree d is obtained.

Attribute Based Encryption (ABE) is a promising public-key cryptographic primitive that can be used for cryptographically enforced access control in untrusted storage. Storing data on untrusted storage not only requires data security for data owners but also poses data protection from untrusted storage server. To address this important requirement, Anonymous Attribute Based Encryption (AABE) is a suitable primitive that provides users to access data from untrusted storage without revealing their identities. At the same time user data can be stored in untrusted storage in an encrypted form. While storing data in an encrypted form, keyword-based query search (and data retrieval) is a challenging research problem. In this paper we present an anonymous attribute based searchable encryption (A2SBE) scheme which facilitates user to retrieve only a subset of documents pertaining to his chosen keyword(s). User can upload documents in public cloud in an encrypted form, search documents based on keyword(s) and retrieve documents without revealing his identity. The scheme is proven secure under the selective ciphertext- policy and chosen plaintext attack (IND-sCP-CPA) model and selective ciphertext-policy and chosen keyword attack (IND-sCP-CKA) model. The scheme requires small storage for user's decryption key and reduced computation for decryption in comparison to other schemes.

This paper revisits related randomness attacks against public key encryption schemes as introduced by Paterson, Schuldt and Sibborn (PKC 2014). We present a general transform achieving security for public key encryption in the related randomness setting using as input any secure public key encryption scheme in combination with an auxiliary-input reconstructive extractor. Specifically, we achieve security in the function-vector model introduced by Paterson et al., obtaining the first constructions providing CCA security in this setting. We consider instantiations of our transform using the Goldreich-Levin extractor; these outperform the previous constructions in terms of public-key size and reduction tightness, as well as enjoying CCA security. Finally, we also point out that our approach leads to an elegant construction for Correlation Input Secure hash functions, which have proven to be a versatile tool in diverse areas of cryptography.

In this paper, we propose a new multivariate signature scheme named MI-T-HFE as a competitor of QUARTZ. The core map of MI-T-HFE is of an HFEv type but more importantly has a specially designed trapdoor. This special trapdoor makes MI-T-HFE have several attractive advantages over QUARTZ. First of all, the core map and the public map of MI-T-HFE are both surjective. This surjectivity property is important for signature schemes because any message should always have valid signatures; otherwise it may be troublesome to exclude those messages without valid signatures. However this property is missing for a few major signature schemes, including QUARTZ. A practical parameter set is proposed for MI-T-HFE with the same length of message and same level of security as QUARTZ, but it has smaller public key size, and is more efficient than (the underlying HFEv- of) QUARTZ with the only cost that its signature length is twice that of QUARTZ.

In a selective opening (SO) attack an adversary breaks into a subset of honestly created ciphertexts and tries to learn information on the plaintexts of some untouched (but potentially related) ciphertexts. Contrary to intuition, standard security notions do not always imply security against this type of adversary, making SO security an important standalone goal. In this paper we study {\em receiver security}, where the attacker is allowed to obtain the decryption keys corresponding to some of the ciphertexts. First we study the relation between two existing security definitions, one based on simulation and the other based on indistinguishability, and show that the former is strictly stronger. We continue with feasibility results for both notions which we show can be achieved from (variants of) non-committing encryption schemes. In particular, we show that indistinguishability-based SO security can be achieved from a tweaked variant of non-committing encryption which, in turn, can be instantiated from a variety of basic, well-established, assumptions. We conclude our study by showing that SO security is however strictly weaker than all variants of non-committing encryption that we consider, leaving potentially more efficient constructions as an interesting open problem.

This paper demonstrates new technique for managing revocation in the context of attribute-based encryption (ABE) and presents two selectively secure directly revocable ABE (RABE) constructions – supporting decryption policies realizable by polynomial size Boolean circuits of arbitrary fan-out and – featuring compactness in the sense that the number of revocation controlling components in ciphertexts and decryption keys are constant. In fact, our RABE schemes are the first to achieve these parameters. Both our constructions utilize multilinear maps. The size of public parameter in our first construction is linear to the maximum number of users supported by the system while in the second construction we reduce it to logarithmic.

The security of many cryptographic schemes and protocols rests on the conjectured computational intractability of the discrete logarithm problem in some group <g> of prime order. Such schemes and protocols require domain parameters that specify <g> and a specific generator g. In this paper we consider the problem of computing information on the domain parameters from public keys selected uniformly at random from <g>. We show that it is not possible to compute any information on the generator g regardless of the number of public keys observed. In the case of elliptic curves E(GF(p)) or E(GF(2^n)) on short Weierstrass form, or E(K) on Edwards form, twisted Edwards form or Montgomery form, where K is a non-binary field, we show how to compute the domain parameters excluding the generator from four keys on affine form. Hence, if the domain parameters excluding the generator are to be kept private, points may not be transmitted on affine form. It is an open question whether point compression is a sufficient requirement. Regardless of whether points are transmitted on affine or compressed form, it is in general possible to create a distinguisher for the domain parameters, excluding the generator, both in the case of the elliptic curve groups previously mentioned, and in the case of multiplicative subgroups of GF(p). We propose that a good method for preventing all of the above attacks may be to use blinding schemes, and suggest new applications for existing blinding schemes originally designed for steganographic applications.

Strongly unforgeable signature schemes provide a more stringent security guarantee than the standard existential unforgeability. It requires that not only forging a signature on a new message is hard, it is infeasible as well to produce a new signature on a message for which the adversary has seen valid signatures before. Strongly unforgeable signatures are useful both in practice and as a building block in many cryptographic constructions. This work investigates a generic transformation that compiles any existential-unforgeable scheme into a strongly unforgeable one, which was proposed by Teranishi et al. and was proven in the classical random-oracle model. Our main contribution is showing that the transformation also works against quantum adversaries in the quantum random-oracle model. We develop proof techniques such as adaptively programming a quantum random-oracle in a new setting, which could be of independent interest. Applying the transformation to an existential-unforgeable signature scheme due to Cash et al., which can be shown to be quantum-secure assuming certain lattice problems are hard for quantum computers, we get an efficient quantum-secure strongly unforgeable signature scheme in the quantum random-oracle model.

In this short paper, we propose a variant of the Number Field Sieve to compute discrete logarithms in medium characteristic finite fields. We propose an algorithm that combines two recent ideas, namely the Multiple variant of the Number Field Sieve taking advantage of a large number of number fields in the sieving phase and the Conjugation Method giving a new polynomial selection for the classical Number Field Sieve. The asymptotic complexity of our improved algorithm is L_Q (1/3, (8 (9+4 \sqrt{6})/15)^1/3), where F_Q is the target finite field and (8 (9+4 \sqrt{6})/15)^1/3) is approximately equal to 2.156. This has to be compared with the complexity of the previous state-of-the-art algorithm for medium characteristic finite fields, the Number Field Sieve with Conjugation Method, that has a complexity of approximately L_Q(1/3, 2.201).

We present an efficient structure-preserving tagged one-time signature scheme with tight security reductions to the decision-linear assumption. Our scheme features short tags consisting of a single group element and gives rise to the currently most efficient structure-preserving signature scheme based on the decision-liner assumption with constant-size signatures of only 14 group elements, where the record-so-far was 17 elements. To demonstrate the advantages of our scheme, we revisit the work by Hofheinz and Jager (CRYPTO 2012) and present the currently most efficient tightly secure public-key encryption scheme. We also obtain the first structure-preserving public-key encryption scheme featuring both tight security and public verifiability.

Functional encryption (FE) is a powerful generalization of various types of encryption. We investigate how FE can be used by a trusted authority to enforce access-control policies to data stored in an untrusted repository. Intuitively, if (functionally) encrypted data items are put in a publicly-readable repository, the effect of the encryption should be that every user has access to exactly (and only) those functions of the data items for which he has previously received the corresponding decryption key. That is, in an ideal-world view, the key authority can flexibly manage read access of users to the repository. This appears to be exactly what FE is supposed to achieve, and most natural applications of FE can be understood as specific uses of such a repository with access control. However, quite surprisingly, it is unclear whether known security definitions actually achieve this goal and hence whether known FE schemes can be used in such an application. In fact, there seems to be agreement in the cryptographic community that identifying the right security definitions for FE remains open. To resolve this problem, we treat FE in the constructive cryptography framework and propose a new conventional security definition, called composable functional encryption security (CFE-security), which exactly matches the described ideal-world interpretation. This definition (and hence the described application) is shown to be unachievable in the standard model but achievable in the random oracle model. Moreover, somewhat weaker definitions, which are achievable in the standard model, can be obtained by certain operational restrictions of the ideal-world repository, making explicit how schemes satisfying such a definition can (and cannot) meaningfully be used. Finally, adequate security definitions for generalizations of FE (such as multi-input, randomized functions, malicious ciphertext generation, etc.) can be obtained by straight-forward operational extensions of the repository and extracting the corresponding security definitions. This leads towards a unified treatment of the security of FE.

We formalize the standard application of identity-based encryption (IBE), namely non-interactive secure communication, as realizing an ideal system which we call delivery controlled channel (DCC). This system allows users to be registered (by a central authority) for an identity and to send messages securely to other users only known by their identity. Quite surprisingly, we show that existing security definitions for IBE are not sufficient to realize DCC. In fact, it is impossible to do so in the standard model. We show, however, how to adjust any IBE scheme that satisfies the standard security definition IND-ID-CPA to achieve this goal in the random oracle model. We also show that the impossibility result can be avoided in the standard model by considering a weaker ideal system that requires all users to be registered in an initial phase before any messages are sent. To achieve this, a weaker security notion, which we introduce and call IND-ID1-CPA, is actually sufficient. This justifies our new security definition and might open the door for more efficient schemes. We further investigate which ideal systems can be realized with schemes satisfying the standard notion and variants of selective security. As a contribution of independent interest, we show how to model features of an ideal system that are potentially available to dishonest parties but not guaranteed, and which such features arise when using IBE.

In this paper, we survey the status of attacks on the ring and polynomial learning with errors problems (RLWE and PLWE). Recent work on the security of these problems [EHL, ELOS] gives rise to interesting questions about number fields. We extend these attacks and survey related open problems in number theory, including spectral distortion of an algebraic number and its relationship to Mahler measure, the monogenic property for the ring of integers of a number field, and the size of elements of small order modulo q.

Gentry, Sahai and Waters recently presented the first (leveled) identity-based fully homomorphic (IBFHE) encryption scheme (CRYPTO 2013). Their scheme however only works in the single-identity setting; that is, homomorphic evaluation can only be performed on ciphertexts created with the same identity. In this work, we extend their results to the multi-identity setting and obtain a multi-identity IBFHE scheme that is selectively secure in the random oracle model under the hardness of Learning with Errors (LWE). We also obtain a multi-key fully-homomorphic encryption (FHE) scheme that is secure under LWE in the standard model. This is the first multi-key FHE based on a well-established assumption such as standard LWE. The multi-key FHE of López-Alt, Tromer and Vaikuntanathan (STOC 2012) relied on a non-standard assumption, referred to as the Decisional Small Polynomial Ratio assumption.

In this short note, we analyze the security of the quadratic zero-testing procedure for the GGH13 graded encoding scheme, which was recently proposed by Gentry, Halevi and Lepoint. We show that this modification fails to immunize the GGH13 construction against zeroizing attacks, and that the modified scheme is susceptible to the same attacks as the original one.

We give a theoretical description of a new homomorphic encryption scheme DA-Encrypt that is based on (non-archimedean) Diophantine Approximation.

The energy cost of asymmetric cryptography is a vital component of modern secure communications, which inhibits its wide spread adoption within the ultra-low energy regimes such as Implantable Medical Devices (IMDs) and Radio Frequency Identification (RFID) tags. The ciphertext-policy attribute-based encryption (CP-ABE) is a promising cryptographic tool, where an encryptor can decide the access policy that who can decrypt the data. Thus, the data will be protected from the unauthorized users. However, most of the existing CP-ABE schemes require huge storage and computational overheads. Moreover, CP-ABE schemes based on bilinear map loose the high efficiency over the elliptic curve cryptography because of the requirement of the security parameters of larger size. These drawbacks prevent the use of ultra-low energy devices in practice. In this paper, we aim to propose a novel expressive AND-gate access structured CP-ABE scheme with constant-size secret keys (CSSK) with the cost efficient solutions for the encryption and decryption using ECC, called the CP-ABE-CSSK scheme. In the proposed CP-ABE-CSSK, the size of secret key is as small as 320 bits. In addition, ECC is efficient and more suitable for the lightweight devices as compared to the bilinear pairing based cryptosystem. Thus, the proposed CP-ABE-CSSK scheme provides the low computation and storage overheads with an expressive AND-gate access structure as compared to the related existing schemes in the literature. As a result, our scheme is very suitable for CP-ABE key storage and computation cost in the ultra-low energy devices.

Broadcasting is a very efficient way to securely transmit information to a large set of geographically scattered receivers, and in practice, it is often the case that these receivers can be grouped in sets sharing common characteristics (or attributes). We describe in this paper an efficient ciphertext-policy attribute-based broadcast encryption scheme (CP-ABBE) supporting negative attributes and able to handle access policies in conjunctive normal form (CNF). Essentially, our scheme is a combination of the Boneh-Gentry-Waters broadcast encryption and of the Lewko-Sahai-Waters revocation schemes; the former is used to express attribute-based access policies while the latter is dedicated to the revocation of individual receivers. Our scheme is the first one that involves a public key and private keys having a size that is independent of the number of receivers registered in the system. Its selective security is proven with respect to the Generalized Diffie-Hellman Exponent (GDHE) problem on bilinear groups.

After four decades of public key cryptography, both the industry and academia seek better solutions for the public key infrastructure. A recent proposal, the certificate transparency concept, tries to enable untrusted servers act as public key servers, such that any key owner can verify that her key is kept properly at those servers. Unfortunately, due to high computation and communication requirements, existing certificate transparency proposals fail to address the problem as a whole. We propose a new efficient key authentication service (KAS). It uses server-side gossiping as the source of trust, and assumes servers are not all colluding. KAS stores all keys of each user in a separate hash chain, and always shares the last ring of the chain among the servers, ensuring the users that all servers provide the same view about them (i.e., no equivocation takes place). Storing users’ keys separately reduces the server and client computation and communication dramatically, making our KAS a very efficient way of public key authentication. The KAS handles a key registration/change operation in O(1) time using only O(1) proof size; independent of the number of users. While the previous best proposal, CONIKS, requires the client to download 100 KB of proof per day, our proposal needs less than 1 KB of proof per key lifetime, while obtaining the same probabilistic guarantees as CONIKS.

Hierarchical identity-based encryption (HIBE) is an extension of identity-based encryption (IBE) where an identity of a user is organized as a hierarchical structure and a user can delegate the private key generation to another user. Providing a revocation mechanism for HIBE is highly necessary to keep a system securely. Revocable HIBE (RHIBE) is an HIBE scheme that can revoke a user's private key if his credential is expired or revealed. In this paper, we first propose an unbounded HIBE scheme where the maximum hierarchy depth is not limited and prove its selective security under a q-type assumption. Next, we propose an efficient unbounded RHIBE scheme by combining our unbounded HIBE scheme and a binary tree structure, and then we prove its selective security. By presenting the unbounded RHIBE scheme, we solve the open problem of Seo and Emura in CT-RSA 2015.

We construct both randomizable and strongly existentially unforgeable structure-preserving signatures for messages consisting of many group elements. To sign a message consisting of N=mn group elements we have a verification key size of $m$ group elements and signatures contain n+2 elements. Verification of a signature requires evaluating n+1 pairing product equations. We also investigate the case of fully structure-preserving signatures where it is required that the secret signing key consists of group elements only. We show a variant of our signature scheme allowing the signer to pick part of the verification key at the time of signing is still secure. This gives us both randomizable and strongly existentially unforgeable fully structure-preserving signatures. In the fully structure preserving scheme the verification key is a single group element, signatures contain m+n+1 group elements and verification requires evaluating n+1 pairing product equations.

We give a simple heuristic sieving algorithm for the $m$-dimensional exact shortest vector problem (SVP) which runs in time $2^{0.3112m +o(m)}$. Unlike previous time-memory trade-offs, we do not increase the memory, which stays at its bare minimum $2^{0.2075m +o(m)}$. To achieve this complexity, we borrow a recent tool from coding theory, known as nearest neighbor search for binary code words. We simplify its analysis, and show that it can be adapted to solve this variant of the fixed-radius nearest neighbor search problem: Given a list of exponentially many unit vectors of $\mR^m$, and an angle $\gamma\pi$, find all pairs of vectors whose angle $\leq\gamma\pi$. The complexity is sub-quadratic which leads to the improvement for lattice sieves.

In an Attribute-Based Encryption (ABE) scheme the ciphertext encrypting a message $\mu$, is associated with a public attribute vector $\vecx$ and a secret key $\sk_P$ is associated with a predicate $P$. The decryption returns $\mu$ if and only if $P(\vecx) = 1$. ABE provides efficient and simple mechanism for data sharing supporting fine-grained access control. Moreover, it is used as a critical component in constructions of succinct functional encryption, reusable garbled circuits, token-based obfuscation and more. In this work, we describe a new efficient ABE scheme for a family of branching programs with short secret keys and from a mild assumption. In particular, in our construction the size of the secret key for a branching program $P$ is $|P| + \poly(\secp)$, where $\secp$ is the security parameter. Our construction is secure assuming the standard Learning With Errors (LWE) problem with approximation factors $n^{\omega(1)}$. Previous constructions relied on $n^{O(\log n)}$ approximation factors of LWE (resulting in less efficient parameters instantiation) or had large secret keys of size $|P| \times \poly(\secp)$. We rely on techniques developed by Boneh et al. (EUROCRYPT'14) and Brakerski et al. (ITCS'14) in the context of ABE for circuits and fully-homomorphic encryption.

Deterministic public-key encryption, introduced by Bellare, Boldyreva, and O’Neill (CRYPTO 2007), is an important technique for searchable encryption; it allows quick, logarithmic-time, search over encrypted data items. The technique is most effective in scenarios where frequent search queries are performed over a huge database of unpredictable data items. We initiate the study of deterministic public-key encryption (D-PKE) in the presence of leakage. We formulate appropriate security notions for leakage-resilient D-PKE, and present constructions that achieve them in the standard model. We work in the continual leakage model, where the secret-key is updated at regular intervals and an attacker can learn arbitrary but bounded leakage on the secret key during each time interval. We, however, do not consider leakage during the updates. Our main construction is based on the (standard) linear assumption in bilinear groups, tolerat- ing up to 0.5 - o(1) fraction of arbitrary leakage. The leakage rate can be improved to 1 - o(1) by relying on the SXDH assumption. At a technical level, we propose and construct a “continual leakage resilient” version of the all-but-one lossy trapdoor functions, introduced by Peikert and Waters (STOC 2008). Our formulation and construction of leakage-resilient lossy-TDFs is of independent general interest for leakage-resilient cryptography.

This paper shows how scalar blinding can provide protection against side channel attacks when performing elliptic curve operations with modest cost, even if the characteristic of the field has a sparse representation. This may indicate that, for hardware implementations, random primes might not have as large of an advantage over special primes as previously claimed.

Modular multiplication and modular reduction are the atomic constituents of most public-key cryptosystems. Amongst the numerous algorithms for performing these operations, a particularly elegant method was proposed by Barrett. This method builds the operation $a \bmod b$ from bit shifts, multiplications and additions in $\mathbb{Z}$. This allows building modular reduction at very marginal code or silicon costs by leveraging existing hardware or software multipliers. This paper presents a method allowing doubling the speed of Barrett’s algorithm by using specific composite moduli. This is particularly useful for lightweight devices where such an optimization can make a difference in terms of power consumption, cost and processing time. The generation of composite moduli with a predetermined portion is a well-known technique and the use of such moduli is considered, in statu scientae, as safe as using randomly generated composite moduli.

In this paper we present a very simple scheme for strengthening the conventional product-sum type PKC which has been long considered insecure against the various attacks such as the secret key attack, LLL attack, etc. We show that with the proposed strengthening scheme, the securities of the conventional product-sum type PKC's can be much improved.

Recently Sarkar (DCC 2014) has proposed a new attack on small decryption exponent when RSA Modulus is of the form N=p^rq for r>=2. This variant is known as Prime Power RSA. The work of Sarkar improves the result of May (PKC 2004) when r<=5. In this paper, we improve the existing results for r=3,4. We also study partial key exposure attack on Prime Power RSA. Our result improves the work of May (PKC 2004) for certain parameters.

One approach towards basing public-key encryption (PKE) schemes on weak and credible assumptions is to build ``stronger'' or more general schemes generically from ``weaker'' or more restricted ones. One particular line of work in this context was initiated by Myers and shelat (FOCS '09) and continued by Hohenberger, Lewko, and Waters (Eurocrypt '12), who provide constructions of multi-bit CCA-secure PKE from single-bit CCA-secure PKE. It is well-known that encrypting each bit of a plaintext string independently is not CCA-secure---the resulting scheme is *malleable*. We therefore investigate whether this malleability can be dealt with using the conceptually simple approach of applying a suitable non-malleable code (Dziembowski et al., ICS '10) to the plaintext and subsequently encrypting the resulting codeword bit-by-bit. We find that an attacker's ability to ask multiple decryption queries requires that the underlying code be *continuously* non-malleable (Faust et al., TCC '14). Since, as we show, this flavor of non-malleability can only be achieved if the code is allowed to ``self-destruct,'' the resulting scheme inherits this property and therefore only achieves a weaker variant of CCA security. We formalize this new notion of so-called *self-destruct CCA security (SD-CCA)* as CCA security with the restriction that the decryption oracle stops working once the attacker submits an invalid ciphertext. We first show that the above approach based on non-malleable codes yields a solution to the problem of domain extension for SD-CCA-secure PKE, provided that the underlying code is continuously non-malleable against a *reduced* form of bit-wise tampering. Then, we prove that the code of Dziembowski et al.\ is actually already continuously non-malleable against (even *full*) bit-wise tampering; this constitutes the first *information-theoretically* secure continuously non-malleable code, a technical contribution that we believe is of independent interest. Compared to the previous approaches to PKE domain extension, our scheme is more efficient and intuitive, at the cost of not achieving full CCA security. Our result is also one of the first applications of non-malleable codes in a context other than memory tampering.

In this paper, we first present a new class of code based public key cryptosystem(PKC) based on Reed-Solomon code over extension field of less than m=9, referred to as K(XVI)SE(1)PKC. We then present a new class of quadratic multivariate PKC, K(XVI)SE(2)PKC, based on binary cyclic code. We show that both K(XVI)SE(1)PKC and K(XVI)SE(2)PKC can be secure against the various linear transformation attacks such as Grobner bases attack due to a non-linear structure introduced when constructing the ciphertexts. Namely, thanks to a non-linear transformation introduced in the construction of K(XVI)SE(1)PKC and K(XVI)SE(2)PKC the ciphertexts can be made very secure against the various sort of linear transformation attacks such as Grobner bases attack, although the degree of any multivariate polynomial used for public key is 1. A new scheme presented in this paper that transforms message variables in order to realize a non-linear transformation, K(II)TS, would yield a brand-new technique in the field of both code based PKC and multivariate PKC, for much improving the security. We shall show that the K(XVI)SE(1)PKC can be effectively constructed based on the Reed-Solomon code of m=8, extensively used in the present day storage systems or the various digital transmission systems.

We describe a methods for generating parameter sets and calculating security estimates for NTRUEncrypt. Analyses are provided for the standardized product-form parameter sets from IEEE 1363.1-2008 and for the NTRU Challenge parameter sets.

Attribute-based signatures, introduced by Maji \emph{et al.}, are signatures that prove that an authority has issued the signer ``attributes'' that satisfy some specified predicate. In existing attribute-based signature schemes, keys are valid indefinitely once issued. In this paper, we initiate the study of incorporating time into attribute-based signatures, where a time instance is embedded in every signature, and attributes are restricted to producing signatures with times that fall in designated validity intervals. We provide three implementations that vary in granularity of assigning validity intervals to attributes, including a scheme in which each attribute has its own independent validity interval, a scheme in which all attributes share a common validity interval, and a scheme in which sets of attributes share validity intervals. All of our schemes provide anonymity to a signer, hide the attributes used to create the signature, and provide collusion-resistance between users.

This report describes the design and implementation results in FPGAs of a scalable hardware architecture for computing modular multiplication in prime fields GF($p$), based on the Montgomery multiplication (MM) algorithm. Starting from an existing digit-serial version of the MM algorithm, a novel {\it digit-digit} based MM algorithm is derived and two hardware architectures that compute that algorithm are described. In the proposed approach, the input operands (multiplicand, multiplier and modulus) are represented using as radix $\beta = 2^k$. Operands of arbitrary size can be multiplied with modular reduction using almost the same hardware since the multiplier's kernel module that performs the modular multiplication depends only on $k$. The novel hardware architectures proposed in this paper were verified by modeling them using VHDL and implementing them in the Xilinx FPGAs Spartan and Virtex5. Design trade-offs are analyzed considering different operand sizes commonly used in cryptography and different values for $k$. The proposed designs for MM are well suited to be implemented in modern FPGAs, making use of available dedicated multiplier and memory blocks reducing drastically the FPGA's standard logic while keeping an acceptable performance compared with other implementation approaches. From the Virtex5 implementation, the proposed MM multiplier reaches a throughput of 242Mbps using only 219 FPGA slices and achieving a 1024-bit modular multiplication in 4.21$\mu$secs.

Multi-server authentication is going to be an integral part of remote authentication with the passage of time. The remote authentication has been part and parcel of internet based communication. In the last decade several multi-server authentication techniques has been presented. However there is still a need of more efficient and robust techniques. Lately, Saraswathi et al., presented a multi-server authentication scheme that has been found under much vulnerability like stolen card attack, misrepresentation attack, and forward secrecy attacks. This paper presents the cryptanalysis for Saraswathi et al. scheme and shows the review analysis.

For $q$ a prime power, the discrete logarithm problem (DLP) in $\mathbb{F}_{q}^{\times}$ consists in finding, for any $g \in \mathbb{F}_{q}^{\times}$ and $h \in \langle g \rangle$, an integer $x$ such that $g^x = h$. For each prime $p$ we exhibit infinitely many extension fields $\mathbb{F}_{p^n}$ for which the DLP in $\mathbb{F}_{p^n}^{\times}$ can be solved in expected quasi-polynomial time.

This paper explores some attacks that someone with a Quantum Computer may be able to perform against NTRUEncrypt, and in particular NTRUEncrypt as implemented by the publicly available library from Security Innovation. We show four attacks that an attacker with a Quantum Computer might be able to perform against encryption performed by this library. Two of these attacks recover the private key from the public key with less effort than expected; in one case taking advantage of how the published library is implemented, and the other, an academic attack that works against four of the parameter sets defined for NTRUEncrypt. In addition, we also show two attacks that are able to recover plaintext from the ciphertext and public key with less than expected effort. This has potential implications on the use of NTRU within TOR, as suggested by Whyte and Schanck

The original specification of EdDSA was suitable only for finite fields Fq with q mod 4 = 1. The main purpose of this document is to extend EdDSA to allow finite fields Fq with any odd q. This document also extends EdDSA to support prehashing, i.e., signing the hash of a message.

We propose a new unified point compression format for Edwards, Twisted Edwards and Montgomery curves over large-characteristic fields, which effectively divides the curve's cofactor by 4 at very little cost to performance. This allows cofactor-4 curves to efficiently implement prime-order groups.

Generating and standardizing elliptic curves to use them in a cryptographic context is a hard task. In this note, we don’t make an explicit proposal for an elliptic curve, but we deal with the following issues. Security: We give a list of criteria that should be satisfied by a secure elliptic curve. Although a few of these criteria are incompatible, we detail what we think are the best choices for optimal security. Transparency: We sketch a way to generate a curve in a fully transparent way so that it can be trusted and not suspected to belong to a (not publicly known to be) vulnerable class. In particular, since the computational cost of verifying the output of such a process may be quite high, we sketch out the format of a certificate that eases the computations. We think that this format might deserve being standardized.

Secure multicast communication has application in growing number of applications. Forward secrecy is of prime importance and insures message confidentiality even long-term private key compromised. We present an efficient construction of multi message multi receiver signcryption with forward secrecy on elliptic curves. It provides confidentiality, integrity, authenticity, non-repudiation, public verifiability, unforgeability and forward secrecy of multi message multicast. It is efficient in computation cost and communication overhead and suitable for resource constrained IP-based secure multi message multicast systems.

We show how any pair of authenticated users can on-the-fly agree on an el- liptic curve group that is unique to their communication session, unpredictable to outside observers, and secure against known attacks. Our proposal is suitable for deployment on constrained devices such as smartphones, allowing them to efficiently generate ephemeral parameters that are unique to any single cryptographic application such as symmetric key agreement. For such applications it thus offers an alternative to long term usage of stan- dardized or otherwise pre-generated elliptic curve parameters, obtaining security against cryptographic attacks aimed at other users, and eliminating the need to trust elliptic curves generated by third parties.

Many papers have proposed elliptic curves which are faster and easier to implement than the NIST prime-order curves. Most of these curves have had fields of size around $2^256$, and thus security estimates of around 128 bits. Recently there has been interest in a stronger curve, prompting designs such as Curve41417 and Microsoft’s pseudo-Mersenne-prime curves. Here I report on the design of another strong curve, called Ed448-Goldilocks. Implementations of this curve can perform very well for its security level on many architectures. As of this writing, this curve is favored by IRTF CFRG for inclusion in future versions of TLS along with Curve25519.

An important attack on multi-power RSA ($N=p^rq$) was introduced by Sarkar in 2014, by extending the small private exponent attack of Boneh and Durfee on classical RSA. In particular, he showed that $N$ can be factored efficiently for $r=2$ with private exponent $d$ satisfying $d<N^{0.395}$. In this paper, we generalize this work by introducing a new partial key exposure attack for finding small roots of polynomials using Coppersmith's algorithm and Gröbner basis computation. Our attack works for all multi-power RSA exponents $e$ (resp. $d$) when the exponent $d$ (resp. $e$) has full size bit length. The attack requires prior knowledge of least significant bits (LSBs), and has the property that the required known part of LSB becomes smaller in the size of $e$. For practical validation of our attack, we demonstrate several computer algebra experiments.

Round-optimal blind signatures are notoriously hard to construct in the standard model, especially in the malicious-signer model, where blindness must hold under adversarially chosen keys. This is substantiated by several impossibility results. The only construction that can be termed theoretically efficient, by Garg and Gupta (Eurocrypt'14), requires complexity leveraging, inducing an exponential security loss. We present a construction of practically efficient round-optimal blind signatures in the standard model. It is conceptually simple and builds on the recent structure-preserving signatures on equivalence classes (SPS-EQ) from Asiacrypt'14. While the traditional notion of blindness follows from standard assumptions, we prove blindness under adversarially chosen keys under an interactive variant of DDH. However, we neither require non-uniform assumptions nor complexity leveraging. We then show how to extend our construction to partially blind signatures and to blind signatures on message vectors, which yield a construction of one-show anonymous credentials à la "anonymous credentials light" (CCS'13) in the standard model. Furthermore, we give the first SPS-EQ construction under non-interactive assumptions and show how SPS-EQ schemes imply conventional structure-preserving signatures, which allows us to apply optimality results for the latter to SPS-EQ.

Asymmetric-key cryptographic algorithms when implemented on systems with branch predictors, are subjected to side-channel attacks exploiting the deterministic branch predictor behavior due to their key-dependent input sequences. We show that branch predictors can also leak information through the hardware performance monitors which are accessible by an adversary at the user-privilege level. This paper presents an iterative attack which target the key-bits of 1024 bit RSA, where in offline phase, the system’s underlying branch predictor is approximated by a theoretical predictor in literature. Subsimulations are performed to classify the message-space into distinct partitions based on the event branch misprediction and the target key bit value. In online phase, we ascertain the secret key bit using branch mispredictions obtained from the hardware performance monitors which reflect the information of branch miss due to the underlying predictor hardware. We theoretically prove that the probability of success of the attack is equivalent to the accurate modelling of the theoretical predictor to the underlying system predictor. Experimentations reveal that the success-rate increases with message-count and reaches such a significant value so as to consider side-channel from the performance counters as a real threat to RSA-like ciphers due to the underlying branch predictors and needs to be considered for developing secured-systems.

The Diffie-Hellman problem as a cryptographic primitive plays an important role in modern cryptology. The Bit Security or Hard-Core Bits of Diffie-Hellman problem in arbitrary finite cyclic group is a long-standing open problem in cryptography. Until now, only few groups have been studied. Hyperelliptic curve cryptography is an alternative to elliptic curve cryptography. Due to the recent cryptanalytic results that the best known algorithms to attack hyperelliptic curve cryptosystems of genus $g<3$ are the generic methods and the recent implementation results that hyperelliptic curve cryptography in genus 2 has the potential to be competitive with its elliptic curve cryptography counterpart. In this paper, we generalize Boneh and Shparlinksi's method and result about elliptic curve to the case of Jacobians of hyperelliptic curves. We prove that the least significant bit of each coordinate of hyperelliptic curves Diffie-Hellman secret value in genus 2 is hard as the entire Diffie-Hellman value, and then we also show that any bit is hard as the entire Diffie-Hellman value. Finally, we extend our techniques and results to hyperelliptic curves of any genus.

Structure-preserving signatures (SPS) are pairing-based signatures where all the messages, signatures and public keys are group elements, with numerous applications in public-key cryptography. We present new, simple and improved SPS constructions under standard assumptions via a conceptually different approach. Our constructions significantly narrow the gap between existing constructions from standard assumptions and optimal schemes in the generic group model.

Two alternating vector operations on a cubic hypersurface are given simple expressions. Direct use of the first operation's expression seems less efficient than state-of-the-art elliptic curve cryptography. The second expression seems mainly interesting towards an elementary exposition about elliptic curve theory.

Trace and revoke is broadcast encryption with the traitor tracing functionality. It is a very powerful primitive since it can revoke users whose private keys are compromised by finding them using a tracing algorithm if a pirate decoder is given. Public-key trace and revoke (PKTR) is a special type of trace and revoke such that anyone can run the tracing algorithm and anyone can create an encrypted message by using a public key. Although public-key trace and revoke schemes are attractive tools, the currently known PKTR schemes are a little bit inefficient in terms of the private key size and the public key size compared with public-key broadcast encryption schemes. In this paper, we propose a new technique to construct an efficient PKTR scheme by using the subset cover framework. First, we introduce a new concept of public-key encryption named single revocation encryption (SRE) and propose an efficient SRE scheme in the random oracle model. The universe of SRE consists of many groups and each group consists of many members. A user in SRE is represented as a group that he belongs and a member in the group. In SRE, a sender can create a ciphertext for a specified group where one member in the group is revoked, and a receiver can decrypt the ciphertext if he belongs to the group in the ciphertext and he is not revoked in the group. Second, we show that the subset difference (SD) scheme (or the layered subset difference (LSD) scheme) and a SRE scheme can be combined to construct a PKTR scheme. Our PKTR scheme using the LSD scheme and our SRE scheme has the ciphertext size of $O(r)$, the private key size of $O(\log^{1.5} N)$, and the public key size of $O(1)$ where $N$ is the total number of users in the system and $r$ is the size of a revoked set. Our PKTR scheme is the first one that achieves the private key size of $O(\log^{1.5} N)$ and the public key size of $O(1)$.

We extend the recent zeroizing attacks of Cheon, Han, Lee, Ryu and Stehlé (Eurocrypt'15) on multilinear maps to settings where no encodings of zero below the maximal level are available. Some of the new attacks apply to the CLT13 scheme (resulting in a total break) while others apply to (a variant of) the GGH13 scheme (resulting in a weak-DL attack). We also note the limits of these zeroizing attacks.

In this work, we first formalize the notion of dynamic group signatures with distributed traceability, where the capability to trace signatures is distributed among $n$ managers without requiring any interaction. This ensures that only the participation of all tracing managers permits tracing a signature, which reduces the trust placed in a single tracing manager. The threshold variant follows easily from our definitions and constructions. Our model offers strong security requirements. Our second contribution is a generic construction for the notion which has a concurrent join protocol, meets strong security requirements, and offers efficient traceability, i.e.\ without requiring tracing managers to produce expensive zero-knowledge proofs for tracing correctness. To dispense with the expensive zero-knowledge proofs required in the tracing, we deploy a distributed tag-based encryption with public verifiability. Finally, we provide some concrete instantiations, which, to the best of our knowledge, are the first efficient provably secure realizations in the standard model simultaneously offering all the aforementioned properties. To realize our constructions efficiently, we construct an efficient distributed (and threshold) tag-based encryption scheme that works in the efficient Type-III asymmetric bilinear groups. Our distributed tag-based encryption scheme yields short ciphertexts (only 1280 bits at 128-bit security), and is secure under an existing variant of the standard decisional linear assumption. Our tag-based encryption scheme is of independent interest and is useful for many applications beyond the scope of this paper. As a special case of our distributed tag-based encryption scheme, we get an efficient tag-based encryption scheme in Type-III asymmetric bilinear groups that is secure in the standard model.

Several authors suggest that the use of twist secure Elliptic Curves automatically leads to secure implementations. We argue that even for twist secure curves a point validation has to be performed. We illustrate this with examples where the security of EC-algorithms is strongly degraded, even for twist secure curves. We show that the usual blindig countermeasures against SCA are insufficient (actually they introduce weaknesses) if no point validation is performed, or if an attacker has access to certain intermediate points. In this case the overall security of the system is reduced to the length of the blinding parameter. We emphazise that our methods work even in the case of a very high identification error rate during the SCA-phase.

Several well-known public key encryption schemes, including those of Alekhnovich (FOCS 2003), Regev (STOC 2005), and Gentry, Peikert and Vaikuntanathan (STOC 2008), rely on the conjectured intractability of inverting noisy linear encodings. These schemes are limited in that they either require the underlying field to grow with the security parameter, or alternatively they can work over the binary field but have a low noise entropy that gives rise to sub-exponential attacks. Motivated by the goal of efficient public key cryptography, we study the possibility of obtaining improved security over the binary field by using different noise distributions. Inspired by an abstract encryption scheme of Micciancio (PKC 2010), we consider an abstract encryption scheme that unifies all the three schemes mentioned above and allows for arbitrary choices of the underlying field and noise distributions. Our main result establishes an unexpected connection between the power of such encryption schemes and additive combinatorics. Concretely, we show that under the ``approximate duality conjecture" from additive combinatorics (Ben-Sasson and Zewi, STOC 2011), every instance of the abstract encryption scheme over the binary field can be attacked in time $2^{O(\sqrt{n})}$, where $n$ is the maximum of the ciphertext size and the public key size (and where the latter excludes public randomness used for specifying the code). On the flip side, counter examples to the above conjecture (if false) may lead to candidate public key encryption schemes with improved security guarantees. We also show, using a simple argument that relies on agnostic learning of parities (Kalai, Mansour and Verbin, STOC 2008), that any such encryption scheme can be {\em unconditionally} attacked in time $2^{O(n/\log n)}$, where $n$ is the ciphertext size. Combining this attack with the security proof of Regev's cryptosystem, we immediately obtain an algorithm that solves the {\em learning parity with noise (LPN)} problem in time $2^{O(n/\log \log n)}$ using only $n^{1+\epsilon}$ samples, reproducing the result of Lyubashevsky (Random 2005) in a conceptually different way. Finally, we study the possibility of instantiating the abstract encryption scheme over constant-size rings to yield encryption schemes with no decryption error. We show that over the binary field decryption errors are inherent. On the positive side, building on the construction of matching vector families (Grolmusz, Combinatorica 2000; Efremenko, STOC 2009; Dvir, Gopalan and Yekhanin, FOCS 2010), we suggest plausible candidates for secure instances of the framework over constant-size rings that can offer perfectly correct decryption.