We present a cryptanalysis of the ASASA public key cipher introduced at Asiacrypt 2014. This scheme alternates three layers of affine transformations A with two layers of quadratic substitutions S. We show that the partial derivatives of the public key polynomials contain information about the intermediate layer. This enables us to present a very simple distinguisher between an ASASA public key and random polynomials. We then expand upon the ideas of the distinguisher to achieve a full secret key recovery. This method uses only linear algebra and has a complexity dominated by the cost of computing the kernels of $2^{26}$ small matrices with entries in $\mathbb F_{16}$.

We show a framework for constructing identity-based encryption (IBE) schemes that are (almost) tightly secure in the multi-challenge and multi-instance setting. In particular, we formalize a new notion called broadcast encoding, analogously to encoding notions by Attrapadung (Eurocrypt '14) and Wee (TCC '14). We then show that it can be converted into such an IBE. By instantiating the framework using several encoding schemes (new or known ones), we obtain the following: - We obtain (almost) tightly secure IBE in the multi-challenge, multi-instance setting, both in composite and prime-order groups. The latter resolves the open problem posed by Hofheinz et al (PKC '15). - We obtain the first (almost) tightly secure IBE with sub-linear size public parameters (master public keys). In particular, we can set the size of the public parameters to constant at the cost of longer ciphertexts. This gives a partial solution to the open problem posed by Chen and Wee (Crypto '13). By applying (a variant of) the Canetti-Halevi-Katz transformation to our schemes, we obtain several CCA-secure PKE schemes with tight security in the multi-challenge, multi-instance setting. One of our schemes achieves very small ciphertext overhead, consisting of less than 12 group elements. This significantly improves the state-of-the-art construction by Libert et al.~(in ePrint Archive) which requires 47 group elements. Furthermore, by modifying one of our IBE schemes obtained above, we can make it anonymous. This gives the first anonymous IBE whose security is almost tightly shown in the multi-challenge setting.

An Attribute-Based Signcryption (ABSC) is a natural extension of Attribute-Based Encryption (ABE) and Attribute-Based Signature (ABS), where we have the message confidentiality and authenticity together. Since the signer privacy is captured in security of ABS, it is quite natural to expect that the signer privacy will also be preserved in ABSC. In this paper, first we propose an ABSC scheme which is \textit{weak existential unforgeable, IND-CCA2} secure in \textit{adaptive-predicates} attack and achieves \textit{signer privacy}. Secondly, by applying strongly unforgeable one-time signature (OTS), the above scheme is lifted to an ABSC scheme to attain \textit{strong existential unforgeability} in \textit{adaptive-predicates} model. Both the ABSC schemes are constructed on common setup, i.e the public parameters and key are same for both the encryption and signature modules. Our first construction is in the flavor of $\mathcal{C}{t}\mathcal{E}\&\mathcal{S}$ paradigm, except one extra component that will be computed using both signature components and ciphertext components. The second proposed construction follows a new paradigm (extension of $\mathcal{C}{t}\mathcal{E}\&\mathcal{S}$), we call it ``Commit then Encrypt and Sign then Sign" ($\mathcal{C}{t}\mathcal{E}\&\mathcal{S}{t}\mathcal{S}$). The last signature is done using a strong OTS scheme. Since the non-repudiation is achieved by $\mathcal{C}{t}\mathcal{E}\&\mathcal{S}$ paradigm, our systems also achieve the same.

We propose a new generic framework for achieving fully secure attribute based encryption (ABE) in prime-order bilinear groups. It is generic in the sense that it can be applied to ABE for arbitrary predicate. All previously available frameworks that are generic in this sense are given only in composite-order bilinear groups. These consist of the frameworks proposed by Wee (TCC'14) and Attrapadung (Eurocrypt'14). Both frameworks provide abstractions of dual-system encryption techniques introduced by Waters (Crypto'09). Our framework can be considered as a prime-order version of Attrapadung's framework and works in a similar manner: it relies on a main component called pair encodings, and it generically compiles any secure pair encoding scheme for a predicate in consideration to a fully secure ABE scheme for that predicate. One feature of our new compiler is that although the resulting ABE schemes will be newly defined in prime-order groups, we require essentially the same security notions of pair encodings as before. Beside the security of pair encodings, our framework assumes only the Matrix Diffie-Hellman assumption, introduced by Escala et al. (Crypto'13), which is a weak assumption that includes the Decisional Linear assumption as a special case. As for its applications, we can plug in available pair encoding schemes and automatically obtain the first fully secure ABE realizations in prime-order groups for predicates of which only fully secure schemes in composite-order groups were known. These include ABE for regular languages, ABE for monotone span programs (and hence Boolean formulae) with short ciphertexts or keys, and completely unbounded ABE for monotone span programs. As a side result, we establish the first generic implication from ABE for monotone span programs to ABE for branching programs. Consequently, we obtain fully-secure ABE for branching programs in some new variants, namely, unbounded, short-ciphertext, and short-key variants. Previous ABE schemes for branching programs are bounded and require linear-size ciphertexts and keys.

We show a generic conversion that converts an attribute based encryption (ABE) scheme for arbitrary predicate into an ABE scheme for its dual predicate. In particular, it can convert key-policy ABE (KP-ABE) into ciphertext-policy ABE (CP-ABE), and vice versa, for dually related predicates. It is generic in the sense that it can be applied to arbitrary predicates. On the other hand, it works only within the generic ABE framework recently proposed by Attrapadung (Eurocrypt'14), which provides a generic compiler that compiles a simple primitive called pair encodings into fully secure ABE. Inside this framework, Attrapadung proposed the first generic dual conversion that works only for subclass of encodings, namely, perfectly secure encodings. However, there are many predicates for which realizations of such encodings are not known, and hence the problems of constructing fully secure ABE for their dual predicates were left unsolved. In this paper, we revisit the dual conversion of Attrapadung, and show that, somewhat surprisingly, the very same conversion indeed also works for broader classes of encodings, namely, computationally secure encodings. Consequently, we thus solve the above open problems as we obtain the first fully secure realizations of completely-unbounded CP-ABE and CP-ABE with short keys for Boolean formulae, via applying the conversion to previously proposed KP-ABE. Moreover, we provide a generic conversion that converts ABE into its dual-policy variant. Dual-policy ABE (DP-ABE) conjunctively combines both KP-ABE and CP-ABE into one primitive, and hence can be useful in general-purpose applications. As for instantiations, we obtain the first realizations of fully secure DP-ABE for formulae, unbounded DP-ABE for formulae, and DP-ABE for regular languages. The latter two systems are the first to realize such functionalities, let alone are fully secure.

In 2004, Canetti-Halevi-Katz and later Boneh-Katz showed generic CCA-secure PKE constructions from a CPA-secure IBE. Goyal et al. in 2006 further extended the aforementioned idea implicitly to provide a specific CCA-secure KP-ABE with policies represented by monotone access trees. Later, Yamada et al. in 2011 generalized the CPA to CCA conversion to all those ABE, where the policies are represented by either monotone access trees (MAT) or monotone span programs (MSP), but not the others like sets of minimal sets. Moreover, the underlying CPA-secure constructions must satisfy one of the two features called key-delegation and verifiability. Along with ABE, many other different encryptions schemes, such as inner-product, hidden vector, spatial encryption schemes etc. can be studied under an unified framework, called functional encryption (FE), as introduced by Boneh-Sahai-Waters in 2011. The generic conversions, due to Yamada et al., can not be applied to all these functional encryption schemes. On the other hand, to the best of our knowledge, there is no known CCA-secure construction beyond ABE over MSP and MAT. This paper provides different ways of obtaining CCA-secure functional encryptions of almost all categories. In particular, we provide a generic conversion from a CPA-secure functional encryption into a CCA-secure functional encryption provided the underlying CPA-secure encryption scheme has either restricted delegation or verifiability feature. We observe that almost all functional encryption schemes have this feature. The KP-FE schemes of Waters (proposed in 2012) and Attrapadung (proposed in 2014) for regular languages do not possess the usual delegation property. However, they can be converted into corresponding CCA-secure schemes as they satisfy the restricted delegation.

Recently, IACR ePrint archive posted two fully homomorphic encryption schemes without bootstrapping. In this note, we show that these schemes are trivially insecure. Furthermore, we also show that the encryption schemes of Liu and Wang in CCS 2012 and the encryption scheme of Liu, Bertino, and Xun in ASIACCS 2014 are insecure either.

Multivariate Quadratic polynomial (MQ) problem serve as the basis of security for potentially post-quantum cryptosystems. The hardness of solving MQ problem depends on a number of parameters, most importantly the number of variables and the degree of the polynomials, as well as the number of equations, the size of the base field etc. We investigate the relation among these parameters and the hardness of solving MQ problem, in order to construct hard instances of MQ problem. These instances are used to create a challenge, which may be helpful in determining appropriate parameters for multivariate public key cryptosystems, and stimulate further the research in solving MQ problem.

An alleged theorem of Neven, Smart and Warinschi (NSW) about the security of Schnorr signatures seems to have a flaw described in this report. Schnorr signatures require representation of an element in a discrete logarithm group as a hashable bit string. This report describes a defective bit string representation of elliptic curve points. Schnorr signatures are insecure when used with this defective representation. Nevertheless, the defective representation meets all the conditions of the NSW theorem. Of course, a natural representation of an elliptic curve group element would not suffer from this major defect. So, the NSW theorem can probably be fixed.

The security of pairing-based crypto-systems relies on the difficulty to compute discrete logarithms in finite fields GF(p^n) where n is a small integer larger than 1. The state-of-art algorithm is the number field sieve (NFS) together with its many variants. When p has a special form (SNFS), as in many pairings constructions, NFS has a faster variant due to Joux and Pierrot. We present a new NFS variant for SNFS computations, which is better for some cryptographically relevant cases, according to a precise comparison of norm sizes. The new algorithm is an adaptation of Schirokauer's variant of NFS based on tower extensions, for which we give a middlebrow presentation.

In this work we define multiple relaxations to the definition of correctness in secure obfuscation. While still remaining meaningful, these relaxations provide ways to obfuscate many primitives in a more direct and efficient way. In particular, we first show how to construct a secure obfuscator for the re-encryption primitive from the Decisional Learning with Errors (DLWE) assumption, without going through fully homomorphic encryption. This can be viewed as a meaningful way to trade correctness for efficiency. Next, we show how our tools can be used to construct secure obfuscators for the functional re-encryption and multi-hop unidirectional re-encryption primitives. In the former case, we improve upon the efficiency of the only previously known construction that satisfies the stronger notion of collusion-resistant obfuscation (due to Chandran et al. - TCC 2012) and obtain a construction with input ciphertexts of constant length. In the latter case, we provide the first known obfuscation-based definition and construction; additionally, our scheme is the first scheme where the size of the ciphertexts does not grow with every hop.

Fully homomorphic encryption (FHE) has important applications in cloud computing. However, almost all fully homomorphic encryption schemes share two common flaws that they all use large-scale secret keys and some operations inefficient. In this paper, the “special b” variant of the Learning With Errors problem (bLWE) is presented, and helps us construct the first circularly secure key switching process which can replace the key switching process and similar re-linearization process used by the existing FHE schemes. Then, we present an efficient FHE. Compared with Brakerski’s scheme, our scheme reduces L secret keys to one and is more efficient. Finally, we prove the chosen-plaintext attack (CPA) security of the fully homomorphic scheme and the circular security of key switching process in standard model under the learning with errors problem (LWE) assumption.

In the last few years, cryptographic multilinear maps have proved their tremendous potential as building blocks for new constructions, in particular the first viable approach to general program obfuscation. After the first candidate construction by Garg, Gentry and Halevi (GGH) based on ideal lattices, a second construction over the integers was described by Coron, Lepoint and Tibouchi (CLT). However the CLT scheme was recently broken by Cheon et al.; the attack works by computing the eigenvalues of a diagonalizable matrix over Q derived from the multilinear map. In this paper we describe a new candidate multilinear map over the integers. Our construction is based on CLT but with a new arithmetic technique that makes the zero-testing element non-linear in the encoding, which prevents the Cheon et al. attack. Our new construction is relatively practical as its efficiency is comparable to the original CLT scheme. Moreover the subgroup membership and decisional linear assumptions appear to hold in the new setting.

Motivated by the problem of avoiding duplication in storage systems, Bellare, Keelveedhi, and Ristenpart have recently put forward the notion of Message-Locked Encryption (MLE) schemes which subsumes convergent encryption and its variants. Such schemes do not rely on permanent secret keys, but rather encrypt messages using keys derived from the messages themselves. We strengthen the notions of security proposed by Bellare et al. by considering plaintext distributions that may depend on the public parameters of the schemes. We refer to such inputs as lock-dependent messages. We construct two schemes that satisfy our new notions of security for message-locked encryption with lock-dependent messages. Our main construction deviates from the approach of Bellare et al. by avoiding the use of ciphertext components derived deterministically from the messages. We design a fully randomized scheme that supports an equality-testing algorithm defined on the ciphertexts. Our second construction has a deterministic ciphertext component that enables more efficient equality testing. Security for lock-dependent messages still holds under computational assumptions on the message distributions produced by the attacker. In both of our schemes the overhead in the length of the ciphertext is only additive and independent of the message length.

We present a modular framework for the design of efficient adaptively secure attribute-based encryption (ABE) schemes for a large class of predicates under the standard k-Lin assumption in prime-order groups; this is the first uniform treatment of dual system ABE across different predicates and across both composite and prime-order groups. Via this framework, we obtain concrete efficiency improvements for several ABE schemes. Our framework has three novel components over prior works: (i) new techniques for simulating composite-order groups in prime-order ones, (ii) a refinement of prior encodings framework for dual system ABE in composite-order groups, (iii) an extension to weakly attribute-hiding predicate encryption (which includes anonymous identity-based encryption as a special case).

We present three attacks on the Prime Power RSA with modulus $N=p^rq$. In the first attack, we consider a public exponent $e$ satisfying an equation $ex-\phi(N)y=z$ where $\phi(N)=p^{r-1}(p-1)(q-1)$. We show that one can factor $N$ if the parameters $|x|$ and $|z|$ satisfy $|xz|<N^\frac{r(r-1)}{(r+1)^2}$ thereby extending the recent results of Sakar~\cite{SARKAR}. In the second attack, we consider two public exponents $e_1$ and $e_2$ and their corresponding private exponents $d_1$ and $d_2$. We show that one can factor $N$ when $d_1$ and $d_2$ share a suitable amount of their most significant bits, that is $|d_1-d_2|<N^{\frac{r(r-1)}{(r+1)^2}}$. The third attack enables us to factor two Prime Power RSA moduli $N_1=p_1^rq_1$ and $N_2=p_2^rq_2$ when $p_1$ and $p_2$ share a suitable amount of their most significant bits, namely, $|p_1-p_2|<\frac{p_1}{2rq_1q_2}$.

In this paper we present an identity-set-based broadcast encryption scheme with three working modes: positive membership (Select-mode), all member (All-mode), and negative membership (Cut-mode) over the user identity set, simultaneously.The core of our scheme is the implementation of cryptographic representation of subset by using two aggregation functions: Zeros-based aggregation and Poles-based aggregation. These two aggregation functions are capable of compressing any subset into one element in a bilinear map group for determining the membership between an element and a subset. Our scheme achieves the optimal bound of O(1)-size for either ciphertext (consisting of just two elements) or decryption key (one element) for an identity set of large size. We prove that our scheme is secure under the General Diffie-Hellman Exponent (GDHE) assumption.

We select a set of elliptic curves for cryptography and analyze our selection from a performance and security perspective. This analysis complements recent curve proposals that suggest (twisted) Edwards curves by also considering the Weierstrass model. Working with both Montgomery-friendly and pseudo-Mersenne primes allows us to consider more possibilities which help to improve the overall efficiency of base field arithmetic. Our Weierstrass curves are backwards compatible with current implementations of prime order NIST curves, while providing improved efficiency and stronger security properties. We choose algorithms and explicit formulas to demonstrate that our curves support constant-time, exception-free scalar multiplications, thereby offering high practical security in cryptographic applications. Our implementation shows that variable-base scalar multiplication on the new Weierstrass curves at the 128-bit security level is about 1.4 times faster than the recent implementation record on the corresponding NIST curve. For practitioners who are willing to use a different curve model and sacrifice a few bits of security, we present a collection of twisted Edwards curves with particularly efficient arithmetic that are up to 1.42, 1.26 and 1.24 times faster than the new Weierstrass curves at the 128-, 192- and 256-bit security levels, respectively. Finally, we discuss how these curves behave in a real-world protocol by considering different scalar multiplication scenarios in the transport layer security (TLS) protocol. The proposed curves and the results of the analysis are intended to contribute to the recent efforts towards recommending new elliptic curves for Internet standards.

The first fall degree assumption provides a complexity approximation of Gröbner basis algorithms when the degree of regularity of a polynomial system cannot be precisely evaluated. Most importantly, this assumption was recently used by Petit and Quisquater's to conjecture that the elliptic curve discrete logarithm problem can be solved in subexponential time for binary fields (binary ECDLP). The validity of the assumption may however depend on the systems in play. In this paper, we theoretically and experimentally study the first fall degree assumption for a class of polynomial systems including those considered in Petit and Quisquater's analysis. In some cases, we show that the first fall degree assumption seems to hold and we deduce complexity improvements on previous binary ECDLP algorithms. On the other hand, we also show that the assumption is unlikely to hold in other cases where it would have very unexpected consequences. Our results shed light on a Gröbner basis assumption with major consequences on several cryptanalysis problems, including binary ECDLP.

The Learning With Error problem (LWE) is becoming more and more used in cryptography, for instance, in the design of some fully homomorphic encryption schemes. It is thus of primordial importance to find the best algorithms that might solve this problem so that concrete parameters can be proposed. The BKW algorithm was proposed by Blum et al. as an algorithm to solve the Learning Parity with Noise problem (LPN), a subproblem of LWE. This algorithm was then adapted to LWE by Albrecht et al. In this paper, we improve the algorithm proposed by Albrecht et al. by using multidimensional Fourier transforms. Our algorithm is, to the best of our knowledge, the fastest LWE solving algorithm. Compared to the work of Albrecht et al. we greatly simplify the analysis, getting rid of integrals which were hard to evaluate in the final complexity. We also remove some heuristics on rounded Gaussians. Some of our results on rounded Gaussians might be of independent interest. Moreover, we also analyze algorithms solving LWE with discrete Gaussian noise. Finally, we apply the same algorithm to the Learning With Rounding problem (LWR) for prime q, a deterministic counterpart to LWE. This problem is getting more and more attention and is used, for instance, to design pseudorandom functions. To the best of our knowledge, our algorithm is the first algorithm applied directly to LWR. Furthermore, the analysis of LWR contains some technical results of independent interest.

This paper presents new speed records for 128-bit secure elliptic-curve Diffie-Hellman key-exchange software on three different popular microcontroller architectures. We consider a 255-bit curve proposed by Bernstein known as Curve25519, which has also been adopted by the IETF. We optimize the X25519 key-exchange protocol proposed by Bernstein in 2006 for AVR ATmega 8-bit microcontrollers, MSP430X 16-bit microcontrollers, and for ARM Cortex-M0 32-bit microcontrollers. Our software for the AVR takes only 13 900 397 cycles for the computation of a Diffe-Hellman shared secret, and is the first to perform this computation in less than a second if clocked at 16 MHz for a security level of 128 bits. Our MSP430X software computes a shared secret in 5 301 792 cycles on MSP430X microcontrollers that have a 32-bit hardware multiplier and in 7 933 296 cycles on MSP430X microcontrollers that have a 16-bit multiplier. It thus outperforms previous constant-time ECDH software at the 128-bit security level on the MSP430X by more than a factor of 1.2 and 1.15, respectively. Our implementation on the Cortex-M0 runs in only 3 589 850 cycles and outperforms previous 128-bit secure ECDH software by a factor of 3.

By applying a quantum search algorithm to various heuristic and provable sieve algorithms from the literature, we obtain improved asymptotic quantum results for solving the shortest vector problem on lattices. With quantum computers we can provably find a shortest vector in time $2^{1.799n + o(n)}$, improving upon the classical time complexities of $2^{2.465n + o(n)}$ of Pujol and Stehlé and the $2^{2n + o(n)}$ of Micciancio and Voulgaris, while heuristically we expect to find a shortest vector in time $2^{0.286n + o(n)}$, improving upon the classical time complexity of $2^{0.337n + o(n)}$ of Laarhoven. These quantum complexities will be an important guide for the selection of parameters for post-quantum cryptosystems based on the hardness of the shortest vector problem.

In cryptography, forward secrecy is a well-known property for key agreement protocols. It ensures that a session key will remain private even if one of the long-term secret keys is compromised in the future. In this paper, we investigate some forward security properties for Public-key Encryption with Keyword Search (PEKS) schemes, which allow a client to store encrypted data and delegate search operations to a server. The proposed properties guarantee that the client's privacy is protected to the maximum extent even if his private key is compromised in the future. Motivated by the generic transformation from anonymous Identity-Based Encryption (IBE) to PEKS, we correspondingly propose some forward security properties for IBE, in which case we assume the attacker learns the master secret key. We then study several existing PEKS and IBE schemes, including a PEKS scheme by Nishioka, an IBE scheme by Boneh, Raghunathan and Segev, and an IBE scheme by Arriaga, Tang and Ryan. Our analysis indicates that the proposed forward security properties can be achieved by some of these schemes if the attacker is RO-non-adaptive (the attacker does not define its distributions based on the random oracle). Finally, we propose the concept of correlated-input indistinguishable hash function and show how to extend the Boyen-Waters anonymous IBE scheme to achieve the forward security properties against adaptive attackers.

Divisible e-cash systems allow a user to withdraw a wallet containing K coins and to spend k < K + 1 coins in a single operation, respectively. Independent of the new work of Canard, Pointcheval, Sanders and Traoré (Proceedings of PKC ’15) we present a practical and secure divisible e-cash system in which the bandwidth of each protocol is constant while the system fulfills the standard security requirements (especially which is unforgeable and truly anonymous) in the random oracle model. In other existing divisible e-cash systems that are truly anonymous, either the bandwidth of withdrawing depends on K or the bandwidth of spending depends on k. Moreover, using some techniques of the work of Canard, Pointcheval, Sanders and Traoré we are also able to prove the security in the standard model. Furthermore, we show an efficient attack against the unforgeability of Canard and Gouget’s divisible e-cash scheme (FC ’10). Finally, we extend our scheme to a divisible e-cash system that provides withdrawing and spending of an arbitrary value of coins (not necessarily a power of two) and give an extension to a fair e-cash scheme.

Certificate-based encryption (CBE) is an important class of public key encryption but the existing schemes are secure only under the premise that the decryption key (or private key) and master private key are absolutely secret. In fact, a lot of side channel attacks and cold boot attacks can leak secret information of a cryptographic system. In this case, the security of the cryptographic system is destroyed, so a new model called leakage-resilient (LR) cryptography is introduced to solve this problem. While some traditional public key encryption and identity-based encryption with resilient-leakage schemes have been constructed, as far as we know, there is no leakage-resilient scheme in certificate-based cryptosystems. This paper puts forward the first certificate-based encryption scheme which can resist not only the decryption key leakage but also the master secret key leakage. Based on composite order bilinear group assumption, the security of the scheme is proved by using dual system encryption. The relative leakage rate of key is close to 1/3.

In this work, we revisit the notion of Decentralized Traceable Attribute-Based Signatures (DTABS) introduced by El Kaafarani et al. (CT-RSA 2014) and improve the state-of-the-art in three dimensions: Firstly, we provide a new stronger security model which circumvents some shortcomings in existing models. Our model minimizes the trust placed in attribute authorities and hence provides, among other things, a stronger definition for non-frameability. In addition, unlike previous models, our model captures the notion of tracing soundness which is important for many applications of the primitive, and which ensures that even if all parties in the system are fully corrupt, no one but the actual signer can claim authorship of the signature. Secondly, we provide a generic construction that is secure w.r.t.\ our strong security model and show two example instantiations in the standard model which are more efficient than existing constructions (secure under weaker security definitions). Finally, unlike existing constructions, we dispense with the need for the expensive zero-knowledge proofs required for proving tracing correctness by the tracing authority. As a result, tracing a signature in our constructions is significantly more efficient than existing constructions, both in terms of the size of the tracing proof and the computational cost required to generate and verify it. For instance, verifying tracing correctness in our constructions requires only 4 pairings compared to 34 pairings in the most efficient existing construction.

This work extends the line of research on the hidden number problem. Motivated by studying bit security in finite fields, we define the multivariate hidden number problem. Here, the secret and the multiplier are vectors, and partial information about their dot product is given. Using tools from discrete Fourier analysis introduced by Akavia, Goldwasser and Safra, we show that if one can find the significant Fourier coefficients of some function, then one can solve the multivariate hidden number problem for that function. This allows us to generalise the work of Akavia on the hidden number problem with (non-adaptive) chosen multipliers to all finite fields. We give two further applications of our results, both of which generalise previous works to all (finite) extension fields. The first considers the general (random samples) hidden number problem in F_{p^m} and assumes an advice is given to the algorithm. The second considers a model that allows changing representations, where we show hardness of individual bits for elliptic curve and pairing based functions for elliptic curves over extension fields, as well as hardness of any bit of any component of the Diffie-Hellman secret in F_{p^m} (m>1).

A revocation mechanism in cryptosystems for a large number of users is absolutely necessary for maintaining the security of whole systems. A revocable identity-based encryption (RIBE) provides an efficient revocation method in IBE in which a trusted authority periodically broadcasts an update key for non-revoked users and a user can decrypt a ciphertext if his private key is not revoked in the update key. Boldyreva, Goyal, and Kumar (CCS 2008) defined RIBE and proposed an RIBE scheme that uses a tree-based revocation encryption scheme to revoke users' private keys. However, this approach has an inherent limitation in that the number of private key elements and update key elements cannot be constant. In this paper, to overcome this limitation, we devise a new technique for RIBE and propose RIBE schemes with a constant number of private key elements. We achieve the following results: - We first devise a new technique for RIBE that combines a hierarchical IBE (HIBE) scheme and a public-key broadcast encryption (PKBE) scheme by using multilinear maps. In contrast to the previous technique for RIBE, our technique uses a PKBE scheme in bilinear maps for revocation to achieve short private keys and update keys. - Following our new technique for RIBE, we propose an RIBE scheme in three-leveled multilinear maps that combines the HIBE scheme of Boneh and Boyen (EUROCRYPT 2004) and the PKBE scheme of Boneh, Gentry, and Waters (CRYPTO 2005). The private key and update key of our scheme possess a constant number of group elements. We introduce a new complexity assumption in multilinear maps and prove the security of our scheme in the selective revocation list model. - Next, we propose another RIBE scheme with reduced public parameters by combining the HIBE scheme of Boneh and Boyen and the PKBE scheme of Boneh, Waters, and Zhandry (CRYPTO 2014), which uses multilinear maps. Compared with our first RIBE scheme, our second RIBE scheme requires high-leveled multilinear maps since the underlying PKBE scheme is based on high-leveled multilinear maps.

Security against selective opening attack (SOA) requires that in a multi-user setting, even if an adversary has access to all ciphertexts from users, and adaptively corrupts some fraction of the users by exposing not only their messages but also the random coins, the remaining unopened messages retain their privacy. Recently, Bellare, Waters and Yilek considered SOA-security in the identity-based setting, and presented the first identity-based encryption (IBE) schemes that are proven secure against selective opening chosen plaintext attack (SO-CPA). However, how to achieve SO-CCA security for IBE is still open. In this paper, we introduce a new primitive called extractable IBE, which is a hybrid of one-bit IBE and identity-based key encapsulation mechanism (IB-KEM), and define its IND-ID-CCA security notion. We present a generic construction of SO-CCA secure IBE from an IND-ID-CCA secure extractable IBE with ``One-Sided Public Openability''(1SPO), a collision-resistant hash function and a strengthened cross-authentication code. Finally, we propose two concrete constructions of extractable 1SPO-IBE schemes, resulting in the first simulation-based SO-CCA secure IBE schemes without random oracles.

We introduce the notion of predicate encodings, an information-theoretic primitive reminiscent of linear secret-sharing that in addition, satisfies a novel notion of reusability. Using this notion, we obtain a unifying framework for adaptively-secure public-index predicate encryption schemes for a large class of predicates. Our framework relies on Waters’ dual system encryption methodology (Crypto ’09), and encompass the identity-based encryption scheme of Lewko and Waters (TCC ’10), and the attribute-based encryption scheme of Lewko et al. (Eurocrypt ’10). In addition, we obtain several concrete improvements over prior works. Our work offers a novel interpretation of dual system encryption as a methodology for amplifying a one-time private-key primitive (i.e. predicate encodings) into a many-time public-key primitive (i.e. predicate encryption).

In AsiaCrypt~2013, Qin and Liu proposed a new approach to CCA-security of Public-Key Encryption (PKE) in the presence of bounded key-leakage, from any universal hash proof system (due to Cramer and Shoup) and any one-time lossy filter (a simplified version of lossy algebraic filters, due to Hofheinz). They presented two instantiations under the DDH and DCR assumptions, which result in leakage rate (defined as the ratio of leakage amount to the secret-key length) of $1/2-o(1)$. In this paper, we extend their work to broader assumptions and to flexible leakage rate, more specifically to leakage rate of $1-o(1)$. \begin{itemize} \item We introduce the Refined Subgroup Indistinguishability (RSI) assumption, which is a subclass of subgroup indistinguishability assumptions, including many standard number-theoretical assumptions, like the quadratic residuosity assumption, the decisional composite residuosity assumption and the subgroup decision assumption over a group of known order defined by Boneh et al. \item We show that universal hash proof (UHP) system and one-time lossy filter (OT-LF) can be simply and efficiently constructed from the RSI assumption. Applying Qin and Liu's paradigm gives simple and efficient PKE schemes under the RSI assumption. \item With the RSI assumption over a specific group (free of pairing), public parameters of UHP and OT-LF can be chosen in a flexible way, resulting in a leakage-flexible CCA-secure PKE scheme. More specifically, we get the first CCA-secure PKE with leakage rate of $1-o(1)$ without pairing. \end{itemize}

Divisible E-cash systems allow users to withdraw a unique coin of value $2^n$ from a bank, but then to spend it in several times to distinct merchants. In such a system, whereas users want anonymity of their transactions, the bank wants to prevent, or at least detect, double-spending, and trace the defrauders. While this primitive was introduced two decades ago, quite a few (really) anonymous constructions have been introduced. In addition, all but one were just proven secure in the random oracle model, but still with either weak security models or quite complex settings and thus costly constructions. The unique proposal, secure in the standard model, appeared recently and is unpractical. As evidence, the authors left the construction of an efficient scheme secure in this model as an open problem.

PGP-based encryption systems use a network of key servers to share public keys. These key server operate on an add only basis, thus the data gives us access to PGP public keys from over 20 years of PGP usage. Analyzing this data allows searching for cryptographic weaknesses in large scale. I created a parser script that puts the raw cryptographic data of the PGP keys into a database. Doing this allows large scale searches for well-known vulnerabilities. DSA signatures with a duplicate $k$ value due to bad random numbers allow the calculation of the private key. Similarly analyzing RSA keys for shared prime factors allows factoring the modulus and thus also regenerating the private key. A small number of breakable keys due to these weaknesses were found.

A procedure for sampling lattice vectors is at the heart of many lattice constructions, and the algorithm of Klein (SODA 2000) and Gentry, Peikert, Vaikuntanathan (STOC 2008) is currently the one that produces the shortest vectors. But due to the fact that its most time-efficient (quadratic-time) variant requires the storage of the Gram-Schmidt basis, the asymptotic space requirements of this algorithm are the same for general and ideal lattices. The main result of the current work is a series of algorithms that ultimately lead to a sampling procedure producing the same outputs as the Klein/GPV one, but requiring only linear-storage when working on lattices used in ideal-lattice cryptography. The reduced storage directly leads to a reduction in key-sizes by a factor of $\Omega(d)$, and makes cryptographic constructions requiring lattice sampling much more suitable for practical applications. At the core of our improvements is a new, faster algorithm for computing the Gram-Schmidt orthogonalization of a set of vectors that are related via a linear isometry. In particular, for a linear isometry r:R^d --> R^d which is computable in time $O(d)$ and a d-dimensional vector $b$, our algorithm for computing the orthogonalization of $(b,r(b),r^2(b),...,r^{d-1}(b))$ uses $O(d^2)$ floating point operations. This is in contrast to $O(d^3)$ such operations that are required by the standard Gram-Schmidt algorithm. This improvement is directly applicable to bases that appear in ideal-lattice cryptography because those bases exhibit such ``isometric structure''. The above-mentioned algorithm improves on a previous one of Gama, Howgrave-Graham, Nguyen (EUROCRYPT 2006) which used different techniques to achieve only a constant-factor speed-up for similar lattice bases. Interestingly, our present ideas can be combined with those from Gama et al. to achieve an even an larger practical speed-up. We next show how this new Gram-Schmidt algorithm can be applied towards lattice sampling in quadratic time using only linear space. The main idea is that rather than pre-computing and storing the Gram-Schmidt vectors, one can compute them ``on-the-fly'' while running the sampling algorithm. We also rigorously analyze the required arithmetic precision necessary for achieving negligible statistical distance between the outputs of our sampling algorithm and the desired Gaussian distribution. The results of our experiments involving NTRU lattices show that the practical performance improvements of our algorithms are as predicted in theory.

Side channel attacks take advantage from the fact that the behavior of crypto implementations can be observed and provides hints that simplify revealing keys. The energy consumption of the chip that performs a cryptographic operation depends on its inputs, on the used cryptographic key and on the circuit that realizes the cryptographic algorithm. An attacker can experiment with different inputs and key candidates: he studies the influence of these parameters on the shape of measured traces with the goal to extract the key. The main assumption is here that the circuit of the attacked devices is constant. In this paper we investigated the influence of variable circuits on the shape of electromagnetic traces. We changed only a part of the cryptographic designs i.e. the partial multiplier of our ECC designs. This part calculates always the same function in a single clock cycle. The rest of the design was kept unchanged. So, we obtained designs with significantly different circuits: in our experiments the number of used FPGAs LUTs differs up to 15%. These differences in the circuits caused a big difference in the shape of electromagnetic traces even when the same data and the same key are processed. Our experiments show that the influence of different circuits on the shape of traces is comparable with the influence of different inputs. We assume that this fact can be used as a protection means against side channel attacks, especially if the cryptographic circuit can be changed before the cryptographic operation is executed or dynamically, i.e. while the cryptographic operation is processed.

Inner-product encryption (IPE) provides fine-grained access control and has attractive applications. Agrawal, Freeman, and Vaikuntanathan~(Asiacrypt 2011) proposed the first IPE scheme from lattices by twisting the identity-based encryption (IBE) scheme by Agrawal, Boneh, and Boyen~(Eurocrypt 2010). Their IPE scheme supports inner-product predicates over $R^{\mu}$, where the ring is $R = \mathbb{Z}_q$. Several applications require the ring $R$ to be exponentially large and, thus, they set $q = 2^{O(n)}$ to implement such applications. This choice results in the AFV IPE scheme with public parameters of size $O(\mu n^2 \lg^3{q}) = O(\mu n^5)$ and ciphertexts of size $O(\mu n \lg^3{q}) = O(\mu n^4)$, where $n$ is the security parameter. Hence, this makes the scheme impractical, as they noted. We address this efficiency issue by ``untwisting'' their twist and providing another twist. Our scheme supports inner-product predicates over $R^\mu$ where $R = \mathrm{GF}(q^n)$ instead of $\mathbb{Z}_q$. Our scheme has public parameters of size $O(\mu n^2 \lg^2{q})$ and ciphertexts of size $O(\mu n \lg^2{q})$. Since the cardinality of $\mathrm{GF}(q^n)$ is inherently exponential in $n$, we have no need to set $q$ as the exponential size for applications. As side contributions, we extend our IPE scheme to a hierarchical IPE (HIPE) scheme and propose a fuzzy IBE scheme from IPE. Our HIPE scheme is more efficient than that developed by Abdalla, De Caro, and Mochetti (Latincrypt 2012). Our fuzzy IBE is secure under a much weaker assumption than that employed by Agrawal et al.~(PKC 2012), who constructed the first lattice-based fuzzy IBE scheme.

The construction of a verifiable random function (VRF) with large input space and full adaptive security from a static, non-interactive complexity assumption, like decisional Diffie-Hellman, has proven to be a challenging task. To date it is not even clear that such a VRF exists. Most known constructions either allow only a small input space of polynomially-bounded size, or do not achieve full adaptive security under a static, non-interactive complexity assumption. The only known constructions without these restrictions are based on non-static, so-called "q-type" assumptions, which are parametrized by an integer q. Since q-type assumptions get stronger with larger q, it is desirable to have q as small as possible. In current constructions, q is either a polynomial (e.g., Hohenberger and Waters, Eurocrypt 2010) or at least linear (e.g., Boneh et al., CCS 2010) in the security parameter. We show that it is possible to construct relatively simple and efficient verifiable random functions with full adaptive security and large input space from non-interactive q-type assumptions, where q is only logarithmic in the security parameter. Interestingly, our VRF is essentially identical to the verifiable unpredictable function (VUF) by Lysyanskaya (Crypto 2002), but very different from Lysyanskaya’s VRF from the same paper. Thus, our result can also be viewed as a new, direct VRF-security proof for Lysyanskaya’s VUF. As a technical tool, we introduce and construct balanced admissible hash functions.

We investigate the hardness of finding solutions to bivariate polynomial congruences modulo RSA composites. We establish necessary conditions for a bivariate polynomial to be one-way, second preimage resistant, and collision resistant based on arithmetic properties of the polynomial. From these conditions we deduce a new computational assumption that implies an efficient algebraic collision-resistant hash function. We explore the assumption and relate it to known computational problems. The assumption leads to (i) a new statistically hiding commitment scheme that composes well with Pedersen commitments, (ii) a conceptually simple cryptographic accumulator, and (iii) an efficient chameleon hash function.

We build the first public-key broadcast encryption systems that simultaneously achieve adaptive security against arbitrary number of colluders, have small system parameters, and have security proofs that do not rely on knowledge assumptions or complexity leveraging. Our schemes are built from either composite order multilinear maps or obfuscation and enjoy a ciphertext overhead, private key size, and public key size that are all poly-logarithmic in the total number of users. Previous broadcast schemes with similar parameters are either proven secure in a weaker static model, or rely on non-falsifiable knowledge assumptions.

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

The main bottleneck affecting the efficiency of all known fully homomorphic encryption (FHE) schemes is Gentry’s bootstrapping procedure, which is required to refresh noisy ciphertexts and keep computing on encrypted data. Bootstrapping in the latest implementation of FHE, the HElib library of Halevi and Shoup (Crypto 2014), requires about six minutes per batch. We present a new method to homomorphically compute simple bit operations, and refresh (bootstrap) the resulting output, which runs on a personal computer in just about half a second. We present a detailed technical analysis of the scheme (based on the worst-case hardness of standard lattice problems) and report on the performance of our prototype implementation.

The calculation of the Tate pairing on ordinary curves involves two major steps: the Miller Loop (ML) followed by the Final Exponentiation (FE). The first step for achieving a full pairing inversion would be to invert this FE, which in itself is a mathematically difficult problem. To our best knowledge, most fault attack schemes proposed against pairing algorithms have mainly focussed on the ML. They solved, if at all, the inversion of the FE in some special `easy' cases or even showed that the complexity of the FE is an intrinsic countermeasure against a successful full fault attack on the Tate pairing. In this paper, we present a fault attack on the FE whereby the inversion of the final exponentiation becomes feasible using $3$ independent faults.

Neven, Smart and Warinschi (NSW) proved, in the generic group model, that full-length Schnorr signatures require only random-prefix resistant hash functions to resist passive existential forgery. Short Schnorr signatures halve the length of the hash function, and have been conjectured to provide a similar level of security. The NSW result is too loose to provide a meaningful security for short Schnorr signatures, but Neven, Smart and Warinschi conjecture that this is mere artefact of the proof technique, and not an essential deficiency of the short Schnorr signatures. In particular, this amounts to a conjecture that short Schnorr signature are secure under the same set of assumptions, namely random-prefix resistance of the hash function. This report provides a counterexample to the latter conjecture, in other words, a separation result. It finds a hash function that seems to suggest random-prefix resistance does not suffice for short Schnorr signatures. In other words, the loose reduction implicit in the NSW theorem is as tight as possible. Obviously, this result does not preclude the possibility of another proof for short Schnorr signatures, based on different hash function security properties such as preimage resistance.

Injective one-way trapdoor functions are one of the most fundamental cryptographic primitives. In this work we show how to derandomize lossy encryption (with long messages) to obtain lossy trapdoor functions, and hence injective one-way trapdoor functions. Bellare, Halevi, Sahai and Vadhan (CRYPTO '98) showed that if E is an IND-CPA secure cryptosystem, and $H$ is a random oracle, then $x \mapsto E(x,H(x))$ is an injective trapdoor function. In this work, we show that if E is a lossy encryption with messages at least 1-bit longer than randomness, and $h$ is a pairwise independent hash function, then $x \mapsto E(x,h(x))$ is a lossy trapdoor function, and hence also an injective trapdoor function. The works of Peikert, Vaikuntanathan and Waters and Hemenway, Libert, Ostrovsky and Vergnaud showed that statistically-hiding 2-round Oblivious Transfer (OT) is equivalent to Lossy Encryption. In their construction, if the sender randomness is shorter than the message in the OT, it will also be shorter than the message in the lossy encryption. This gives an alternate interpretation of our main result. In this language, we show that any 2-message statistically sender-private semi-honest oblivious transfer (OT) for strings longer than the sender randomness implies the existence of injective one-way trapdoor functions. This is in contrast to the black box separation of injective trapdoor functions from many common cryptographic protocols, e.g. IND-CCA encryption.

A self-bilinear map is a bilinear map where the domain and target groups are identical. In this paper, we introduce a self-bilinear map with auxiliary information which is a weaker variant of a self-bilinear map, construct it based on indistinguishability obfuscation and prove that a useful hardness assumption holds with respect to our construction under the factoring assumption. From our construction, we obtain a multilinear map with interesting properties: the level of multilinearity is not bounded in the setup phase, and representations of group elements are compact, i.e., their size is independent of the level of multilinearity. This is the first construction of a multilinear map with these properties. Note, however, that to evaluate the multilinear map, auxiliary information is required. As applications of our multilinear map, we construct multiparty non-interactive key-exchange and distributed broadcast encryption schemes where the maximum number of users is not fixed in the setup phase. Besides direct applications of our self-bilinear map, we show that our technique can also be used for constructing somewhat homomorphic encryption based on indistinguishability obfuscation and the Phi-hiding assumption.

In this paper we present adaptive key recovery attacks on NTRU-based somewhat homomorphic encryption schemes. Among such schemes, we study the proposal by Bos et al [BLLN13] in 2013. Given access to a decryption oracle, the attack allows us to compute the private key for all parameter choices. Such attacks show that one must be very careful about the use of homomorphic encryption in practice. The existence of a key recovery attack means that the scheme is not CCA1-secure. Indeed, almost every somewhat homomorphic construction proposed till now in the literature is vulnerable to an attack of this type. Hence our result adds to a body of literature that shows that building CCA1-secure homomorphic schemes is not trivial.

We construct an identity-based encryption (IBE) scheme that is tightly secure in a very strong sense. Specifically, we consider a setting with many instances of the scheme and many encryptions per instance. In this setting, we reduce the security of our scheme to a variant of a simple assumption used for a similar purpose by Chen and Wee (Crypto 2013). The security loss of our reduction is O(k) (where k is the security parameter). Our scheme is the first IBE scheme to achieve this strong flavor of tightness under a simple assumption. Technically, our scheme is a variation of the IBE scheme by Chen and Wee. However, in order to “lift” their results to the multi-instance, multi-ciphertext case, we need to develop new ideas. In particular, while we build on (and extend) their high-level proof strategy, we deviate significantly in the low-level proof steps.

Using the Pohlig--Hellman algorithm, den Boer reduced the discrete logarithm problem to the Diffie--Hellman problem in groups of an order whose prime factors were each one plus a smooth number. This report reviews some related general conjectural lower bounds on the Diffie-Hellman problem in elliptic curve groups that relax the smoothness condition into a more commonly true condition. This report focuses on some elliptic curve parameters defined over a prime field size of size 9+55(2^288), whose special form may provide some efficiency advantages over random fields of similar sizes. The curve has a point of Proth prime order 1+55(2^286), which helps to nearly optimize the den Boer reduction. This curve is constructed using the CM method. It has cofactor 4, trace 6, and fundamental discriminant -55. This report also tries to consolidate the variety of ways of deciding between elliptic curves (or other algorithms) given the efficiency and security of each.

In this paper, we introduce and study a new cryptographic primitive that we call "puncturable key encapsulation mechanism" (PKEM), which is a special class of KEMs that satisfy some functional and security requirements that, combined together, imply chosen ciphertext security (CCA security). The purpose of introducing this primitive is to capture certain common patterns in the security proofs of the several existing CCA secure public key encryption (PKE) schemes and KEMs based on general cryptographic primitives which (explicitly or implicitly) use the ideas and techniques of the Dolev-Dwork-Naor (DDN) construction (STOC'91), and "break down" the proofs into smaller steps, so that each small step is easier to work with/verify/understand than directly tackling CCA security. To see the usefulness of PKEM, we show (1) how several existing constructions of CCA secure PKE/KEM constructed based on general cryptographic primitives can be captured as a PKEM, which enables us to understand these constructions via a unified framework, (2) its connection to detectable CCA security (Hohenberger et al. EUROCRYPT'12), and (3) a new security proof for a KEM-analogue of the DDN construction from a set of assumptions: "sender non-committing encryption" (SNCE) and non-interactive witness indistinguishable proofs. Then, as our main technical result, we show how to construct a PKEM satisfying our requirements (and thus a CCA secure KEM) from a new set of general cryptographic primitives: "SNCE" and "symmetric key encryption secure for key-dependent messages" (KDM secure SKE). Our construction realizes the "decrypt-then-re-encrypt"-style validity check of a ciphertext which is powerful but in general has a problem of the circularity between a plaintext and a randomness.We show how SNCE and KDM secure SKE can be used together to overcome the circularity. We believe that the connection among three seemingly unrelated notions of encryption primitives, i.e. CCA security, the sender non-committing property, and KDM security, to be of theoretical interest.

In this paper, we introduce a new functionality for proxy re-encryption (PRE) that we call re-encryption verifiability. In a PRE scheme with re-encryption verifiability (which we simply call verifiable PRE, or VPRE), a receiver of a re-encrypted ciphertext can verify whether the received ciphertext is correctly transformed from an original ciphertext by a proxy, and thus can detect illegal activities of the proxy. We formalize the security model for a VPRE scheme, and show that the single-hop uni-directional PRE scheme by Hanaoka et al. (CT-RSA 2012) can be extended to a secure VPRE scheme.

In view of the expiration or reveal of user's private credential (or private key) in a realistic scenario, identity-based encryption (IBE) schemes with an efficient key revocation mechanism, or for short, revocable identity-based encryption (RIBE) schemes, become prominently significant. In this paper, we present an RIBE scheme from lattices by combining two Agrawal et al.'s IBE schemes with the subset difference (SD) method. Our scheme is secure against adaptive identity-time attacks in the standard model under the learning with errors (LWE) assumption. In particular, our scheme serves as one solution to the challenge posed by Chen et al.(ACISP '12).

We discuss how to apply Gaudry’s index calculus algorithm for abelian varieties to solve the discrete logarithm problem in the trace zero variety of an elliptic curve. We treat in particular the practically relevant cases of field extensions of degree 3 or 5. Our theoretical analysis is compared to other algorithms present in the literature, and is complemented by results from a prototype implementation.

Group signatures are a class of digital signatures with enhanced privacy. By using this type of signature, a user can sign a message on behalf of a specific group without revealing his identity, but in the case of a dispute, an authority can expose the identity of the signer. However, in some situations it is only required to know whether a specific user is the signer of a given signature. In this case, the use of a standard group signature may be problematic since the specified user might not be the signer of the given signature, and hence, the identity of the actual signer will be exposed. Inspired by this problem, we propose the notion of a deniable group signature, where, with respect to a signature and a user, the authority can issue a proof showing that the specified user is NOT the signer of the signature, without revealing the actual signer. We also describe a fairly practical construction by extending the Groth group signature scheme (ASIACRYPT 2007). In particular, a denial proof in our scheme consists of 96 group elements, which is about twice the size of a signature in the Groth scheme. The proposed scheme is provably secure under the same assumptions as those of the Groth scheme.

Related key attacks (RKAs) are powerful cryptanalytic attacks where an adversary can change the secret key and observe the effect of such changes at the output. The state of the art in RKA security protects against an a-priori unbounded number of certain algebraic induced key relations, e.g., affine functions or polynomials of bounded degree. In this work, we show that it is possible to go beyond the algebraic barrier and achieve security against arbitrary key relations, by restricting the number of tampering queries the adversary is allowed to ask for. The latter restriction is necessary in case of arbitrary key relations, as otherwise a generic attack of Gennaro et al. (TCC 2004) shows how to recover the key of almost any cryptographic primitive. We describe our contributions in more detail below. 1) We show that standard ID and signature schemes constructed from a large class of $\Sigma$-protocols (including the Okamoto scheme, for instance) are secure even if the adversary can arbitrarily tamper with the prover’s state a bounded number of times and obtain some bounded amount of leakage. Interestingly, for the Okamoto scheme we can allow also independent tampering with the public parameters. 2) We show a bounded tamper and leakage resilient CCA secure public key cryptosystem based on the DDH assumption. We first define a weaker CPA-like security notion that we can instantiate based on DDH, and then we give a general compiler that yields CCA-security with tamper and leakage resilience. This requires a public tamper-proof common reference string. 3) Finally, we explain how to boost bounded tampering and leakage resilience (as in 1. and 2. above) to continuous tampering and leakage resilience, in the so-called floppy model where each user has a personal hardware token (containing leak- and tamper-free information) which can be used to refresh the secret key. We believe that bounded tampering is a meaningful and interesting alternative to avoid known impossibility results and can provide important insights into the security of existing standard cryptographic schemes.

The GHS attack is known to map the discrete logarithm problem(DLP) in the Jacobian of a curve $C_{0}$ defined over the $d$ degree extension $k_{d}$ of a finite field $k$ to the DLP in the Jacobian of a new curve $C$ over $k$ which is a covering curve of $C_0$, then solve the DLP of curves $C/k$ by variations of index calculus algorithms. It is therefore important to know which curve $C_0/k_d$ is subjected to the GHS attack, especially those whose covering $C/k$ have the smallest genus $g(C)=dg(C_0)$, which we called satisfying the isogeny condition. Until now, 4 classes of such curves were found by Thériault and 6 classes by Diem. In this paper, we present a classification i.e. a complete list of all elliptic curves and hyperelliptic curves $C_{0}/k_{d}$ of genus 2, 3 which possess $(2,...,2)$ covering $C/k$ of $\Bbb{P}^1$ under the isogeny condition (i.e. $g(C)=d \cdot g(C_{0})$) in odd characteristic case. In particular, classification of the Galois representation of $\Gal(k_{d}/k)$ acting on the covering group $\cov(C/\Bbb{P}^1)$ is used together with analysis of ramification points of these coverings. Besides, a general existential condition of a model of $C$ over $k$ is also obtained. As the result, a complete list of all defining equations of curves $C_0/k_d$ with covering $C/k$ are provided explicitly. Besides the 10 classes of $C_0/k_d$ already known, 17 classes are newly found.

In a functional encryption (FE) scheme, the owner of the secret key can generate restricted decryption keys that allow users to learn specific functions of the encrypted messages and nothing else. In many known constructions of FE schemes, security is guaranteed only for messages that are fixed ahead of time (i.e., before the adversary even interacts with the system). This so-called selective security is too restrictive for many realistic applications. Achieving adaptive security (also called full security), where security is guaranteed even for messages that are adaptively chosen at any point in time, seems significantly more challenging. The handful of known adaptively-secure schemes are based on specifically tailored techniques that rely on strong assumptions (such as obfuscation or multilinear maps assumptions). We show that any sufficiently-expressive selectively-secure FE scheme can be transformed into an adaptively-secure one without introducing any additional assumptions. We present a black-box transformation, for both public-key and private-key schemes, making novel use of hybrid encryption, a classical technique that was originally introduced for improving the efficiency of encryption schemes. We adapt the hybrid encryption approach to the setting of functional encryption via a technique for embedding a "hidden execution thread'' in the decryption keys of the underlying scheme, which will only be activated within the proof of security of the resulting scheme. As an additional application of this technique, we show how to construct functional encryption schemes for arbitrary circuits starting from ones for shallow circuits (NC1 or even TC0).

This paper presents three curious findings about deterministic public-key encryption (D-PKE) that further our understanding of its security, in particular because of the contrast with standard, randomized public-key encryption (R-PKE): (1) It would appear to be a triviality, for any primitive, that security in the standard model implies security in the random-oracle model, and it is certainly true, and easily proven, for R-PKE. For D-PKE it is not clear and depends on details of the definition. In particular we can show it in the non-uniform case but not in the uniform case. (2) The power of selective-opening attacks (SOA) comes from an adversary's ability, upon corrupting a sender, to learn not just the message but also the coins used for encryption. For R-PKE, security is achievable. For D-PKE, where there are no coins, one's first impression may be that SOAs are vacuous and security should be easily achievable. We show instead that SOA-security is impossible, meaning no D-PKE scheme can achieve it. (3) For R-PKE, single-user security implies multi-user security, but we show that there are D-PKE schemes secure for a single user and insecure with two users.

Fully homomorphic is an encryption scheme that allows for data to be stored and processed in an encrypted format, which gives the cloud provider a solution to host and process data without even knowing what the message is. In previous identity-based homomorphic encryption scheme, computing efficiency is complicated and expensive. In this work, based on Regev’s work, we propose a sampling trapdoor one-way function in arbitrary cyclotomic rings . Then construct a leveled identity-based homomorphic encryption scheme from ring learning with errors, which has advantage in computational efficiency and key management, by using user’s identity as the unique public key. This scheme is proved IND-CPA secure in the random oracle model, relied to hardness of decision ring learning with errors problem.

Structure-preserving signatures are schemes in which public keys, messages, and signatures are all collections of source group elements of some bilinear groups. In this paper, we introduce fully structure-preserving signature schemes, with the additional requirement that even secret keys should be group elements. This new type of structure-preserving signatures allows for efficient non-interactive proofs of knowledge of the secret key and is useful in designing cryptographic protocols with strong security guarantees based on the simulation paradigm where the simulator has to extract the secret keys on-line. To gain efficiency, we construct shrinking structure-preserving trapdoor commitments. This is by itself an important primitive and of independent interest as it appears to contradict a known impossibility result. We argue that a relaxed binding property lets us circumvent the impossibility result while still retaining the usefulness of the primitive in important applications as mentioned above.

Proxy Re-Encryption was introduced by Blaze, Bleumer and Strauss to efficiently solve the problem of delegation of decryption rights. In proxy re-encryption, a semi-honest proxy transforms a ciphertext intended for Alice to a ciphertext of the same message for Bob without learning anything about the underlying message. From its introduction, several proxy re-encryption schemes in the Public Key Infrastructure (PKI) and Identity (ID) based setting have been proposed. In practice, systems in the public key infrastructure suffer from the \textit{certificate management problem} and those in identity based setting suffer from the \textit{key escrow problem}. Certificateless Proxy Re-encryption schemes enjoy the advantages provided by ID-based constructions without suffering from the key escrow problem. In this work, we construct the \textit{first} unidirectional, single-hop CCA-secure certificateless proxy re-encryption scheme \textit{without} \textit{pairing} by extending the PKI based construction of Chow et al. proposed in 2010. We prove its security in the random oracle model under the Computational Diffie-Hellman (CDH) assumption. Prior to this work, the only secure certificateless proxy re-encryption scheme is due to Guo et al. proposed in 2013 using bilinear pairing. They proved their construction is RCCA-secure under $q$-weak Decisional Bilinear Diffie-Hellman assumption. The construction proposed in this work is more efficient than that system and its security relies on more standard assumptions. We also show that the recently proposed construction of Yang et al. is insecure with respect to the security model considered in this work.

Often, in privacy-sensitive cryptographic protocols, a party commits to a secret message m and later needs to prove that $m$ belongs to a language L or that m does not belong to L (but this party does not want to reveal any further information). We present a method to prove in a non-interactive way that a committed value does not belong to a given language L. Our construction is generic and relies on the corresponding proof of membership to L. We present an efficient realization of our proof system by combining {smooth projective hash functions} and the Groth-Sahai proof system. In 2009, Kiayias and Zhou introduced {zero-knowledge proofs with witness elimination} which enable to prove that a committed message $m$ belongs to a language L (with a witness w) in such a way that the verifier accepts the interaction only if w does not belong to a set determined by a public relation Q and some private input w' of the verifier. We show that the protocol they proposed is flawed and that a dishonest prover can actually make a verifier accept a proof for any message m in L even if (w,w') in Q. Using our non-interactive proof of non-membership of committed values, we are able to fix their protocol and improve its efficiency. Our approach finds also efficient applications in other settings, e.g. in anonymous credential systems and privacy-preserving authenticated identification and key exchange protocols.

This paper introduces a high-security post-quantum stateless hash-based signature scheme that signs hundreds of messages per second on a modern 4-core 3.5GHz Intel CPU. Signatures are 41 KB, public keys are 1 KB, and private keys are 1 KB. The signature scheme is designed to provide long-term $2^{128}$ security even against attackers equipped with quantum computers. Unlike most hash-based designs, this signature scheme is stateless, allowing it to be a drop-in replacement for current signature schemes.

Side-channel attacks allow the adversary to gain partial knowledge of the secret key when cryptographic protocols are implemented in real-world hardware. The goal of leakage resilient cryptography is to design crytosystems that withstand such attacks. In the auxiliary input model an adversary is allowed to see a computationally hard-to-invert function of the secret key. The auxiliary input model weakens the bounded leakage assumption commonly made in leakage resilient cryptography as the hard-to-invert function may information-theoretically reveal the entire secret key. In this work, we propose the first constructions of digital signature schemes that are secure in the auxiliary input model. Our main contribution is a digital signature scheme that is secure against chosen message attacks when given any exponentially hard-to-invert function of the secret key. As a second contribution, we construct a signature scheme that achieves security for random messages assuming that the adversary is given a polynomial-time hard-to-invert function (where both the challenge as well as the signatures seen prior to that are computed on random messages). Here, polynomial-hardness is required even when given the entire public-key. We further show that such signature schemes readily give us auxiliary input secure identification schemes.

We design a linearly homomorphic encryption scheme whose security relies on the hardness of the decisional Diffie-Hellman problem. Our approach requires some special features of the underlying group. In particular, its order is unknown and it contains a subgroup in which the discrete logarithm problem is tractable. Therefore, our instantiation holds in the class group of a non maximal order of an imaginary quadratic field. Its algebraic structure makes it possible to obtain such a linearly homomorphic scheme whose message space is the whole set of integers modulo a prime p and which supports an unbounded number of additions modulo p from the ciphertexts. A notable difference with previous works is that, for the first time, the security does not depend on the hardness of the factorization of integers. As a consequence, under some conditions, the prime p can be scaled to fit the application needs.

Cloud storage is very popular since it has many advantages, but there is a new threat to cloud storage that was not considered before. {\it Self-updatable encryption} that updates a past ciphertext to a future ciphertext by using a public key is a new cryptographic primitive introduced by Lee, Choi, Lee, Park, and Yung (Asiacrypt 2013) to defeat this threat such that an adversary who obtained a past-time private key can still decrypt a (previously unread) past-time ciphertext stored in cloud storage. Additionally, an SUE scheme can be combined with an attribute-based encryption (ABE) scheme to construct a powerful revocable-storage ABE (RS-ABE) scheme introduced by Sahai, Seyalioglu, and Waters (Crypto 2012) that provides the key revocation and ciphertext updating functionality for cloud storage. In this paper, we propose an efficient SUE scheme and its extended schemes. First, we propose an SUE scheme with short public parameters in prime-order bilinear groups and prove its security under a $q$-type assumption. Next, we extend our SUE scheme to a time-interval SUE (TI-SUE) scheme that supports a time interval in ciphertexts. Our TI-SUE scheme has short public parameters and also secure under the $q$-type assumption. Finally, we propose the first large universe RS-ABE scheme with short public parameters in prime-order bilinear groups and prove its security in the selective revocation list model under a $q$-type assumption.

A multiparty computation protocol is said to be adaptively secure if it retains its security even in the presence of an adversary who can corrupt participants as the protocol proceeds. This is in contrast to the static corruption model where the adversary is forced to choose which participants to corrupt before the protocol begins. A central tool for constructing adaptively secure protocols is non-committing encryption (Canetti, Feige, Goldreich and Naor, STOC '96). The original protocol of Canetti et al. had ciphertext expansion that was quadratic in the security parameter, and prior to this work, the best known constructions had ciphertext expansion that was linear in the security parameter. In this work, we present the first non-committing encryption scheme that achieves ciphertext expansion that is logarithmic in the message length. Our construction has optimal round complexity (2-rounds), where (just as in all previous constructions) the first message consists of a public-key of size $\tilde{\bigoh}(n \secpar)$ where $n$ is the message length and $\secpar$ is the security parameter. The second message consists of a ciphertext of size $\bigoh( n \log n + \secpar )$. The security of our scheme is proved based on the $\Phi$-hiding problem.

Lattice-based encryption schemes still suffer from a low message throughput per ciphertext. This is mainly due to the fact that the underlying schemes do not tap the full potentials of LWE. Many constructions still follow the one-time-pad approach considering LWE instances as random vectors added to a message, most often encoded bit vectors. Recently, at Financial Crypto 2015 El Bansarkhani et al. proposed a novel encryption scheme based on the A-LWE assumption (Augmented LWE), where data is embedded into the error term without changing its target distributions. By this novelty it is possible to encrypt much more data as compared to the traditional one-time-pad approach and it is even possible to combine both concepts. In this paper we revisit this approach and propose amongst others several algebraic techniques in order to significantly improve the message throughput per ciphertext. Furthermore, we give a thorough security analysis as well as an efficient implementation of the CCA1-secure encryption scheme instantiated with the most efficient trapdoor construction. In particular, we attest that it even outperforms the CPA-secure encryption scheme from Lindner and Peikert presented at CT-RSA 2011.

We provide new bounds on how close to regular the map x |--> x^e is on arithmetic progressions in Z_N, assuming e | Phi(N) and N is composite. We use these bounds to analyze the security of natural cryptographic problems related to RSA, based on the well-studied Phi-Hiding assumption. For example, under this assumption, we show that RSA PKCS #1 v1.5 is secure against chosen-plaintext attacks for messages of length roughly (log N)/4 bits, whereas the previous analysis, due to Lewko et al (2013), applies only to messages of length less than (log N)/32. In addition to providing new bounds, we also show that a key lemma of Lewko et al. is incorrect. We prove a weaker version of the claim which is nonetheless sufficient for most, though not all, of their applications. Our technical results can be viewed as showing that exponentiation in Z_N is a deterministic extractor for every source that is uniform on an arithmetic progression. Previous work showed this type of statement only on average over a large class of sources, or for much longer progressions (that is, sources with much more entropy).

A group signature allows a group member to anonymously sign messages on behalf of the group. In the past few years, new group signatures based on lattice problems have appeared: the most efficient lattice-based constructions are due to Laguillaumie {\it et al.} (Asiacrypt '13) and Langlois {\it et al.} (PKC '14). Both have at least $O(n^2\log^2 n \log N)$-bit group public key and $O(n\log^3 n\log N)$-bit signature, where $n$ is the security parameter and $N$ is the maximum number of group members. In this paper, we present a simpler lattice-based group signature, which is more efficient by a $O(\log N)$ factor in both the group public key and the signature size. We achieve this by using a new non-interactive zero-knowledge (NIZK) proof corresponding to a simple identity-encoding function. The security of our group signature can be reduced to the hardness of SIS and LWE in the random oracle model.

Cryptographic schemes based on the Learning Parity with Noise (LPN) problem have several very desirable aspects: Low computational overhead, simple implementation and conjectured post-quantum hardness. Choosing the LPN noise parameter sufficiently low allows for public key cryptography. In this work, we construct the first standard model public key encryption scheme with key dependent message security based solely on the low noise LPN problem. Additionally, we establish a new connection between LPN with a bounded number of samples and LPN with an unbounded number of samples. In essence, we show that if LPN with a small error and a small number of samples is hard, then LPN with a slightly larger error and an unbounded number of samples is also hard. The key technical ingredient to establish both results is a variant of the LPN problem called the extended LPN problem.

Recent work on structure-preserving signatures studies optimality of these schemes in terms of the number of group elements needed in the verification key and the signature, and the number of pairing-product equations in the verification algorithm. While the size of keys and signatures is crucial for many applications, another important aspect to consider for performance is the time it takes to verify a given signature. By far, the most expensive operation during verification is the computation of pairings. However, the concrete number of pairings that one needs to compute is not captured by the number of pairing-product equations considered in earlier work. To fill this gap, we consider the question of what is the minimal number of pairings that one needs to compute in the verification of structure-preserving signatures. First, we prove lower bounds for schemes in the Type~II setting that are secure under chosen message attacks in the generic group model, and we show that three pairings are necessary and that at most one of these pairings can be precomputed. We also extend our lower bound proof to schemes secure under random message attacks and show that in this case two pairings are still necessary. Second, we build an automated tool to search for schemes matching our lower bounds. The tool can generate automatically and exhaustively all valid structure-preserving signatures within a user-specified search space, and analyze their (bounded) security in the generic group model. Interestingly, using this tool, we find a new randomizable structure-preserving signature scheme in the Type~II setting that is optimal with respect to the lower bound on the number of pairings, and also minimal with respect to the number of group operations that have to be computed during verification.

We propose an efficient large-universe multi-authority ciphertext - policy attribute-based encryption system. In a large-universe ABE scheme, any string can be used as an attribute of the system, and these attributes are not necessarily enumerated during setup. In a multi-authority ABE scheme, there is no central authority that distributes the keys to users. Instead, there are several authorities, each of which is responsible for the authorized key distribution of a specific set of attributes. Prior to our work, several schemes have been presented that satisfy one of these two properties but not both. Our construction achieves maximum versatility by allowing multiple authorities to control the key distribution for an exponential number of attributes. In addition, the ciphertext policies of our system are sufficiently expressive and overcome the restriction that ``each attribute is used only once'' that constrained previous constructions. Besides versatility, another goal of our work is to increase efficiency and practicality. As a result, we use the significantly faster prime order bilinear groups rather than composite order groups. The construction is non-adaptively secure in the random oracle model under a non-interactive q-type assumption, similar to one used in prior works. Our work extends existing ``program-and-cancel'' techniques to prove security and introduces two new techniques of independent interest for other ABE constructions. We provide an implementation and some benchmarks of our construction in Charm, a programming framework developed for rapid prototyping of cryptographic primitives.

One-round authenticated key exchange (ORKE) is an established research area, with many prominent protocol constructions like HMQV (Krawczyk, CRYPTO 2005) and Naxos (La Macchia et al., ProvSec 2007), and many slightly different, strong security models. Most constructions combine ephemeral and static Diffie-Hellman Key Exchange (DHKE), in a manner often closely tied to the underlying security model. We give a generic construction of ORKE protocols from general assumptions, with security in the standard model, and in a strong security model where the attacker is even allowed to learn the randomness or the long-term secret of either party in the target session. The only restriction is that the attacker must not learn both the randomness and the long-term secret of one party of the target session, since this would allow him to recompute all internal states of this party, including the session key. This is the first such construction that does not rely on random oracles. The construction is intuitive, relatively simple, and efficient. It uses only standard primitives, namely non-interactive key exchange, a digital signature scheme, and a pseudorandom function, with standard security properties, as building blocks.

Related-Key Attacks (RKAs) allow an adversary to observe the outcomes of a cryptographic primitive under not only its original secret key e.g., $s$, but also a sequence of modified keys $\phi(s)$, where $\phi$ is specified by the adversary from a class $\Phi$ of so-called Related-Key Derivation (RKD) functions. This paper extends the notion of non-malleable Key Derivation Functions (nm-KDFs), introduced by Faust et al. (EUROCRYPT'14), to \emph{continuous} nm-KDFs. Continuous nm-KDFs have the ability to protect against any a-priori \emph{unbounded} number of RKA queries, instead of just a single time tampering attack as in the definition of nm-KDFs. Informally, our continuous non-malleability captures the scenario where the adversary can tamper with the original secret key repeatedly and adaptively. We present a novel construction of continuous nm-KDF for any polynomials of bounded degree over a finite field. Essentially, our result can be extended to richer RKD function classes possessing properties of \emph{high output entropy and input-output collision resistance}. The technical tool employed in the construction is the one-time lossy filter (Qin et al. ASIACRYPT'13) which can be efficiently obtained under standard assumptions, e.g., DDH and DCR. We propose a framework for constructing $\Phi$-RKA-secure IBE, PKE and signature schemes, using a continuous nm-KDF for the same $\Phi$-class of RKD functions. Applying our construction of continuous nm-KDF to this framework, we obtain the first RKA-secure IBE, PKE and signature schemes for a class of polynomial RKD functions of bounded degree under \emph{standard} assumptions. While previous constructions for the same class of RKD functions all rely on non-standard assumptions, e.g., $d$-extended DBDH assumption.

We propose the first construction for achieving adaptively secure functional encryption (FE) for poly-sized circuits (without complexity leveraging) from indistinguishability obfuscation (iO). Our reduction has polynomial loss to the underlying primitives. We develop a "punctured programming'' approach to constructing and proving systems where outside of obfuscation we rely only on primitives realizable from pseudo random generators. Our work consists of two constructions. Our first FE construction is provably secure against any attacker that is limited to making all of its private key queries after it sees the challenge ciphertext. (This notion implies selective security.) Our construction makes use of an we introduce called puncturable deterministic encryption (PDE) which may be of independent. With this primitive in place we show a simpleconstruction FE construction. We then provide a second construction that achieves adaptive security from indistinguishability obfuscation. Our central idea is to achieve an adaptively secure functional encryption by bootstrapping from a one-bounded FE scheme that is adaptively secure. By using bootstrapping we can use "selective-ish'' techniques at the outer level obfuscation level and push down the challenge of dealing with adaptive security is then FE scheme, where it has been already been solved. We combine our bootstrapping framework with a new "key signaling'' technique to achieve our construction and proof.

In this work, we aim to make attribute-based encryption (ABE) more suitable for access control to data stored in the cloud. For this purpose, we concentrate on giving to the encryptor full control over the access rights, providing feasible key management even in case of multiple independent authorities, and enabling viable user revocation, which is essential in practice. Our main result is an extension of the decentralized CP-ABE scheme of Lewko and Waters with identity-based user revocation. Our revocation system is made feasible by removing the computational burden of a revocation event from the cloud service provider, at the expense of some permanent, yet acceptable overhead of the encryption and decryption algorithms run by the users. Thus, the computation overhead is distributed over a potentially large number of users, instead of putting it on a single party (e.g., a proxy server), which would easily lead to a performance bottleneck. Besides describing our scheme, we also give a formal proof of its security in the generic bilinear group and random oracle models.

At the center of many lattice-based constructions is an algorithm that samples a short vector $s$, satisfying $[A|AR-HG]s=t\bmod q$ where $A,AR, H, G$ are public matrices and $R$ is a trapdoor. Although the algorithm crucially relies on the knowledge of the trapdoor $R$ to perform this sampling efficiently, the distribution it outputs should be independent of $R$ given the public values. We present a new, simple algorithm for performing this task. The main novelty of our sampler is that the distribution of $s$ does not need to be Gaussian, whereas all previous works crucially used the properties of the Gaussian distribution to produce such an $s$. The advantage of using a non-Gaussian distribution is that we are able to avoid the high-precision arithmetic that is inherent in Gaussian sampling over arbitrary lattices. So while the norm of our output vector $s$ is on the order of $\sqrt{n}$ to $n$ - times larger (the representation length, though, is only a constant factor larger) than in the samplers of Gentry, Peikert, Vaikuntanathan (STOC 2008) and Micciancio, Peikert (EUROCRYPT 2012), the sampling itself can be done very efficiently. This provides a useful time/output trade-off for devices with constrained computing power. In addition, we believe that the conceptual simplicity and generality of our algorithm may lead to it finding other applications.

Side channel and fault attacks take advantage from the fact that the behavior of crypto implementations can be observed and provide hints that simplify revealing keys. These attacks use identical devices either for preparation of attacks or for measurements. By the preparation of attacks the structure and the electrical circuit of devices, that are identical to the target, is analyzed. By side channel attacks usually the same device is used many times for measurements, i.e. measurements on the identical device are made serially in time. Another way is to exploit the difference of side channel leakages; here two identical devices are used parallel, i.e. at the same time. In this paper we investigate the influence of the electrical circuit of a cryptographic implementation on the shape of the resulting power trace, because individualizing of circuits of cryptographic devices can be a new means to prevent attacks that use identical devices. We implemented three different designs that provide exactly the same cryptographic function, i.e. an ECC kP multiplication. For our evaluation we use two different FPGAs. The visualization of the routed design and measurement results show clear differences in the resources consumed as well as in the power traces.

The function field sieve, a subexponential algorithm of complexity L(1/3) that computes discrete logarithms in finite fields, has recently been improved to an algorithm of complexity L(1/4) and subsequently to a quasi-polynomial time algorithm. We investigate whether the new ideas also apply to index calculus algorithms for computing discrete logarithms in Jacobians of algebraic curves. While we do not give a final answer to the question, we discuss a number of ideas, experiments, and possible conclusions.

We present new constructions of leakage-resilient cryptosystems, which remain provably secure even if the attacker learns some arbitrary partial information about their internal secret key. For any polynomial $\ell$, we can instantiate these schemes so as to tolerate up to $\ell$ bits of leakage. While there has been much prior work constructing such leakage-resilient cryptosystems under concrete number-theoretic and algebraic assumptions, we present the first schemes under general and minimal assumptions. In particular, we construct: - Leakage-resilient public-key encryption from any standard public-key encryption. - Leakage-resilient weak pseudorandom functions, symmetric-key encryption}, and message-authentication codes from any one-way function. These are the first constructions of leakage-resilient symmetric-key primitives that do not rely on public-key assumptions. We also get the first constructions of leakage-resilient public-key encryption from ``search assumptions'', such as the hardness of factoring or CDH. Although our schemes can tolerate arbitrarily large amounts of leakage, the tolerated rate of leakage (defined as the ratio of leakage-amount to key-size) is rather poor in comparison to prior results under specific assumptions. As a building block of independent interest, we study a notion of weak hash-proof systems in the public-key and symmetric-key settings. While these inherit some of the interesting security properties of standard hash-proof systems, we can instantiate them under general assumptions.

In this paper, we propose a new phase-based enumeration algorithm based on two interesting and useful observations for y-sparse representations of short lattice vectors in lattices from SVP challenge benchmarks. Experimental results show that the phase-based algorithm greatly outperforms other famous enumeration algorithms in running time and achieves higher dimensions, like the Kannan-Helfrich enumeration algorithm. Therefore, the phase-based algorithm is a practically excellent solver for the shortest vector problem (SVP).

It has been an open problem for a number of years to construct an identity-based fully homomorphic encryption (IBFHE) scheme (first mentioned by Naccache at CHES/CRYPTO 2010). At CRYPTO 2013, Gentry, Sahai and Waters largely settled the problem by presenting leveled IBFHE constructions based on the Learning With Errors problem. However their constructions are not bootstrappable, and as a result, are not ``pure'' IBFHE schemes. The major challenge with bootstrapping in the identity-based setting is that it must be possible to non-interactively derive from the public parameters an ``encryption'' of the secret key for an arbitrary identity. All presently-known leveled IBFHE schemes only allow bootstrapping if such an ``encryption'' of the secret key is supplied out-of-band. In this work, we present a ``pure'' IBFHE scheme from indistinguishability obfuscation, and extend the result to the attribute-based setting. Our attribute-based scheme is the first to support homomorphic evaluation on ciphertexts with different attributes. Finally, we characterize presently-known leveled IBFHE schemes with a view to developing a ``compiler'' from a leveled IBFHE scheme to a bootstrappable IBFHE scheme, and sufficient conditions are identified.

Shortly following Cheon, Han, Lee, Ryu and Stehle attack against the multilinear map of Coron, Lepoint and Tibouchi (CLT), two independent approaches to thwart this attack have been proposed on the cryptology ePrint archive, due to Garg, Gentry, Halevi and Zhandry on the one hand, and Boneh, Wu and Zimmerman on the other. In this short note, we show that both countermeasures can be defeated in polynomial time using extensions of the Cheon et al. attack.

The concept of multivariate bijective map of an affine space $K^n$ over commutative Ring $K$ was already used in Cryptography. We consider the idea of nonbijective multivariate polynomial map $F_n$ of $K^n$ into $K^n$ represented as ''partially invertible decomposition'' $F^{(1)}_nF^{(2)}_n \dots F^{(k)}_n$, $k=k(n)$, such that knowledge on the decomposition and given value $u=F(v)$ allow to restore a special part $v'$ of reimage $v$. We combine an idea of ''oil and vinegar signatures cryptosystem'' with the idea of linguistic graph based map with partially invertible decomposition to introduce a new cryptosystem. The decomposition will be induced by pseudorandom walk on the linguistic graph and its special quotient (homomorphic image). We estimate the complexity of such general algorithm in case of special family of graphs with quotients, where both graphs form known families of Extremal Graph Theory. The map created by key holder (Alice) corresponds to pseudorandom sequence of ring elements. The postquantum version of the algorithm can be obtained simply by the usage of random strings instead of pseudorandom.

Cryptographic primitives based on infinite families of progressively weaker assumptions have been proposed by Hofheinz-Kiltz and by Shacham (the n-Linear assumptions) and by Escala et al. (the Matrix Diffie-Hellman assumptions). All of these assumptions are extensions of the decisional Diffie-Hellman (DDH) assumption. In contrast, in this paper, we construct (additive) homomorphic encryption (HE) schemes based on a new infinite family of assumptions extending the decisional Composite Residuosity (DCR) assumption. This is the first result on a primitive based on an infinite family of progressively weaker assumptions not originating from the DDH assumption. Our assumptions are indexed by rooted trees, and provides a completely different structure compared to the previous extensions of the DDH assumption. Our construction of a HE scheme is generic; based on a tree structure, we recursively combine copies of building-block HE schemes associated to each leaf of the tree (e.g., the Paillier cryptosystem, for our DCR-based result mentioned above). Our construction for depth-one trees utilizes the "share-then-encrypt" multiple encryption paradigm, modified appropriately to ensure security of the resulting HE schemes. We prove several separations between the CPA security of our HE schemes based on different trees; for example, the existence of an adversary capable of breaking all schemes based on depth-one trees, does not imply an adversary against our scheme based on a depth-two tree (within a computational model analogous to the generic group model). Moreover, based on our results, we give an example which reveals a type of "non-monotonicity" for security of generic constructions of cryptographic schemes and their building-block primitives; if the building-block primitives for a scheme are replaced with other ones secure under stronger assumptions, it may happen that the resulting scheme becomes secure under a weaker assumption than the original.

Dual system encryption techniques introduced by Waters in Crypto'09 are powerful approaches for constructing fully secure functional encryption (FE) for many predicates. However, there are still some FE for certain predicates to which dual system encryption techniques seem inapplicable, and hence their fully-secure realization remains an important problem. A notable example is FE for regular languages, introduced by Waters in Crypto'12. \\ We propose a generic framework that abstracts the concept of dual system encryption techniques. We introduce a new primitive called \emph{pair encoding} scheme for predicates and show that it implies fully secure functional encryption (for the same predicates) via a generic construction. Using the framework, we obtain the first fully secure schemes for functional encryption primitives of which only selectively secure schemes were known so far. Our three main instantiations include FE for regular languages, unbounded attribute-based encryption (ABE) for large universes, and ABE with constant-size ciphertexts. \\ Our main ingredient for overcoming the barrier of inapplicability for the dual system techniques to certain predicates is a computational security notion of the pair encoding scheme which we call \emph{doubly selective security}. This is in contrast with most of the previous dual system based schemes, where information-theoretic security are implicitly utilized. The doubly selective security notion resembles that of selective security and its complementary notion, co-selective security, and hence its name. Our framework can be regarded as a method for boosting doubly selectively security (of encoding) to full security (of functional encryption). \\ Besides generality of our framework, we remark that improved security is also obtained, as our security proof enjoys tighter reduction than previous schemes, notably the reduction cost does not depend on the number of all queries, but only that of \emph{pre-challenged} queries.

In CRYPTO 2012, Sahai et al. raised the concern that in a cloud control system revocation of past keys should also be accompanied by updation of previously generated ciphertexts in order to prevent unread ciphertexts from being read by revoked users. Self-updatable encryption (SUE), introduced by Lee et al. in ASIACRYPT 2013, is a newly developed cryptographic primitive that realizes ciphertext update as an inbuilt functionality and thus improves the efficiency of key revocation and time evolution in cloud management. In SUE, a user can decrypt a ciphertext associated with a specific time if and only if the user possesses a private key corresponding to either the same time as that of the ciphertext or some future time. Furthermore, a ciphertext attached to a certain time can be updated to a new one attached to a future time using only public information. The SUE schemes available in the literature are either (a) fully secure but developed in a composite order bilinear group setting under highly non-standard assumptions or (b) designed in prime order bilinear groups but only selectively secure. This paper presents the first fully secure SUE scheme in prime order bilinear groups under standard assumptions, namely, the Decisional Linear and the Decisional Bilinear Diffie-Hellman assumptions. As pointed out by Freeman (EUROCRYPT 2010)and Lewko (EUROCRYPT 2012), the communication and storage, as well as, computational efficiency of prime order bilinear groups are much higher compared to that of composite order bilinear groups with an equivalent level of security. Consequently, our SUE scheme is highly cost-effective than the existing fully secure SUE.

We extend the recent zeroizing attacks of Cheon et al. on multilinear maps to some settings where no encodings of zero below the maximal level are available. Some of the new attacks apply to the CLT scheme (resulting in total break) while others apply to the GGH scheme (resulting in a weak-DL attack).

Public key infrastructures (PKIs) enable users to look up and verify one another's public keys based on identities. Current approaches to PKIs are vulnerable because they do not offer sufficiently strong guarantees of \emph{identity retention}; that is, they do not effectively prevent one user from registering a public key under another's already-registered identity. In this paper, we leverage the consistency guarantees provided by cryptocurrencies such as Bitcoin and Namecoin to build a PKI that ensures identity retention. Our system, called Certcoin, has no central authority and thus requires the use of secure distributed dictionary data structures to provide efficient support for key lookup.

In this paper, we revisit the recent small characteristic discrete logarithm algorithms. We show that a simplified description of the algorithm, together with some additional ideas, permits to obtain an improved complexity for the polynomial time precomputation that arises during the discrete logarithm computation. With our new improvements, this is reduced to O(q^6), where q is the cardinality of the basefield we are considering. This should be compared to the best currently documented complexity for this part, namely O(q^7). With our simplified setting, the complexity of the precomputation in the general case becomes similar to the complexity known for Kummer (or twisted Kummer) extensions.

This paper shows, assuming standard heuristics regarding the number-field sieve, that a "batch NFS" circuit of area L^{1.181...+o(1)} factors L^{0.5+o(1)} separate B-bit RSA keys in time L^{1.022...+o(1)}. Here L=exp((log 2^B)^{1/3}(log log 2^B)^{2/3}). The circuit's area-time product (price-performance ratio) is just L^{1.704...+o(1)} per key. For comparison, the best area-time product known for a single key is L^{1.976...+o(1)}. This paper also introduces new "early-abort" heuristics implying that "early-abort ECM" improves the performance of batch NFS by a superpolynomial factor, specifically exp((c+o(1))(log 2^B)^{1/6}(log log 2^B)^{5/6}) where c is a positive constant.

In this paper, the authors give the definitions of a coprime sequence and a lever function, and describe the five algorithms and six characteristics of a prototypal public key cryptosystem which is used for encryption and signature, and based on three new problems and one existent problem: the multivariate permutation problem (MPP), the anomalous subset product problem (ASPP), the transcendental logarithm problem (TLP), and the polynomial root finding problem (PRFP). Prove by reduction that MPP, ASPP, and TLP are computationally at least equivalent to the discrete logarithm problem (DLP) in the same prime field, and meanwhile find some evidence which inclines people to believe that the new problems are harder than DLP each, namely unsolvable in DLP subexponential time. Demonstrate the correctness of the decryption and the verification, deduce the probability of a plaintext solution being nonunique is nearly zero, and analyze the exact securities of the cryptosystem against recovering a plaintext from a ciphertext, extracting a private key from a public key or a signature, and forging a signature through known signatures, public keys, and messages on the assumption that IFP, DLP, and LSSP can be solved. Studies manifest that the running times of effectual attack tasks are greater than or equal to O(2^n) so far when n = 80, 96, 112, or 128 with lg M = 696, 864, 1030, or 1216. As viewed from utility, it should be researched further how to decrease the length of a modulus and to increase the speed of the decryption.

In a homomorphic signature scheme, a user Alice signs some large data $x$ using her secret signing key and stores the signed data on a server. The server can then run some computation $y=g(x)$ on the signed data and homomorphically produce a short signature $\sigma$. Anybody can verify the signature using Alice's public verification key and become convinced that $y$ is the correct output of the computation $g$ over Alice's data, without needing to have the underlying data itself. In this work, we construct the first leveled fully homomorphic signature schemes that can evaluate arbitrary circuits over signed data, where only the maximal depth $d$ of the circuit needs to be fixed a priori. The size of the evaluated signature grows polynomially in $d$, but is otherwise independent of the circuit size or the data size. Our solutions are based on the hardness of the small integer solution (SIS) problem, which is in turn implied by the worst-case hardness of problems in standard lattices. We get a scheme in the standard model, albeit with large public parameters whose size must exceed the total size of all signed data. In the random-oracle model, we get a scheme with short public parameters. These results offer a significant improvement in capabilities and assumptions over the best prior homomorphic signature scheme due to Boneh and Freeman (Eurocrypt '11). As a building block of independent interest, we introduce a new notion called homomorphic trapdoor functions (HTDF). We show to how construct homomorphic signatures using HTDFs as a black box. We construct HTDFs based on the SIS problem by relying on a recent technique developed by Boneh et al. (Eurocrypt '14) in the context of attribute based encryption.

We show how to compute an existential forgery after querying 4 signatures on chosen messages for a signature scheme presented at Asiacrypt 2014.

In this work, we present the first definitions and constructions for functional encryption supporting randomized functionalities. The setting of randomized functionalities require us to revisit functional encryption definitions by, for the first time, explicitly adding security requirements for dishonest encryptors, to ensure that they cannot improperly tamper with the randomness that will be used for computing outputs. Our constructions are built using indistinguishability obfuscation.

The signature scheme Bliss proposed by Ducas, Durmus, Lepoint and Lyubashevsky at Crypto’13, is currently the most compact and efficient lattice-based signature scheme that is provably secure under lattice assumptions. It does compare favourably with the standardized schemes RSA and ECDSA on both Software and Hardware. In this work, we introduce a new technique that improves the above scheme, offering an acceleration factor up to 2.8, depending on the set of parameters. Namely, we improve the unnatural geometric bound used in Bliss to a tighter and much more natural bound by using some extra degree of freedom: the ternary representations of binary challenges. Precisely, we efficiently choose a ternary representation that makes the result deterministically shorter than the expected length for a random challenges. Our modified scheme Bliss-b is rather close to the original scheme, and both versions are compatible. The patch has been implemented on the Open-Source Software implementation of Bliss, and will be released under similar license.

Proxy re-encryption (PRE) schemes are cryptosystems which allow a proxy who has a re-encryption key to convert a ciphertext originally encrypted for one party into a ciphertext which can be decrypted by another party. In IWSEC 2011, Hayashi et al. proposed the new security notion for PRE called ``unforgeability of re-encryption keys against collusion attacks,'' UFReKey-CA for short. They proposed the PRE schemes and claimed that their schemes meet UFReKey-CA. However, Isshiki et al. pointed out that the schemes do not meet UFReKey-CA in IWSEC 2013. It is an open problem of constructing the scheme which meets UFReKey-CA. In this paper, we propose new PRE schemes which meet confidentiality (RCCA security) assuming that the q-wDBDHI problem is hard and meet UFReKey-CA assuming that the 2-DHI problem is hard.

Given two integers $N_1 = p_1q_1$ and $N_2 = p_2q_2$ with $\alpha$-bit primes $q_1,q_2$, suppose that the $t$ least significant bits of $p_1$ and $p_2$ are equal. May and Ritzenhofen (PKC 2009) developed a factoring algorithm for $N_1,N_2$ when $t \geq 2\alpha + 3$; Kurosawa and Ueda (IWSEC 2013) improved the bound to $t \geq 2\alpha + 1$. In this paper, we propose a polynomial-time algorithm in a parameter $\kappa$, with an improved bound $t = 2\alpha - O(\log \kappa)$; it is the first non-constant improvement of the bound. Both the construction and the proof of our algorithm are very simple; the worst-case complexity of our algorithm is evaluated by an easy argument, without any heuristic assumptions. We also give some computer experimental results showing the efficiency of our algorithm for concrete parameters, and discuss potential applications of our result to security evaluations of existing factoring-based primitives.

The paper is about the discrete logarithm problem for elliptic curves over characteristic 2 finite fields F_2^n of prime degree n. We consider practical issues about index calculus attacks using summation polynomials in this setting. The contributions of the paper include: a choice of variables for binary Edwards curves (invariant under the action of a relatively large group) to lower the degree of the summation polynomials; a choice of factor base that “breaks symmetry” and increases the probability of finding a relation; an experimental investigation of the use of SAT solvers rather than Gröbner basis methods for solving multivariate polynomial equations over F2. We show that our choice of variables gives a significant improvement to previous work in this case. The symmetry breaking factor base and use of SAT solvers seem to give some benefits in practice, but our experimental results are not conclusive. Our work indicates that Pollard rho is still much faster than index calculus algorithms for the ECDLP (and even for variants such as the oracle-assisted static Diffie-Hellman problem of Granger and Joux-Vitse) over prime extension fields F_2^n of reasonable size.

Demands for lawful access to encrypted data are a long standing obstacle to integrating cryptographic protections into communication systems. A common approach is to allow a trusted third party (TTP) to gain access to private data. However, there is no way to verify that this trust is well place as the TTP may open all messages indiscriminately. Moreover, existing approaches do not scale well when, in addition to the content of the conversation, one wishes to hide ones identity. Given the importance of metadata this is a major problem. We propose a new signature scheme as an accountable replacement for group signatures, accountable forward and backward tracing signatures.