Cryptography and Coding

A key problem with the original implementation of the Gentry Fully Homomorphic Encryption scheme was the slow key generation process. Gentry and Halevi provided a fast technique for 2-power cyclotomic fields. We present an extension of the Gentry–Halevi key generation technique for arbitrary cyclotomic fields. Our new method is roughly twice as efficient as the previous best methods. Our estimates are backed up with experimental data.

As a concrete example, we present an instantiation based on Reed-Muller codes where for μ = 2 and μ = 3 and security levels between 80 and 128 bits, all operations take less than a second (after some pre-computation). However, our analysis reveals also limitations on this approach. For structural reasons, such schemes cannot be public-key, allow for a limited number of fresh encryptions only, and cannot be combined with the bootstrapping technique. We argue why such schemes are nonetheless useful in certain application scenarios and discuss possible directions on how to overcome these issues.

Kloosterman sums have recently become the focus of much research, most notably due to their applications in cryptography and their relations to coding theory.

Very recently Mesnager has showed that the value 4 of binary Kloosterman sums gives rise to several infinite classes of bent functions, hyper-bent functions and semi-bent functions in even dimension.

In this paper we analyze the different strategies used to find zeros of binary Kloosterman sums to develop and implement an algorithm to find the value 4 of such sums. We then present experimental results showing that the value 4 of binary Kloosterman sums gives rise to bent functions for small dimensions, a case with no mathematical solution so far.

We consider a class of 3-error-correcting cyclic codes of length 2 ^m  − 1 over the two-element field \(\mathbb{F}_2\). The generator polynomial of a code of this class has zeroes \(\alpha, \alpha^{2^i+1}\) and \(\alpha^{2^j+1}\), where α is a primitive element of the field \({\mathbb{F}_{2^m}}\). In short, {1, 2 ⁱ  + 1, 2 ^j  + 1} refers to the zero set of these codes. Kasami in 1971 and Bracken and Helleseth in 2009, showed that cyclic codes with zeroes {1, 2^ℓ + 1, 2^3ℓ + 1} and {1, 2^ℓ + 1, 2^2ℓ + 1} respectively are 3-error correcting, where \(\gcd(\ell,m) = 1\). We present a sufficient condition so that the zero set {1, 2^ℓ + 1, 2 ^pℓ + 1}, \(\gcd(\ell,m)=1\) gives a 3-error-correcting cyclic code. The question for p > 3 is open. In addition, we determine all the 3-error-correcting cyclic codes in the class {1, 2 ⁱ  + 1, 2 ^j  + 1} for m < 20. We investigate their weight distribution via their duals and observe that they have the same weight distribution as 3-error-correcting BCH codes for m < 14. Further our experiment shows that these codes are not equivalent to the 3-error-correcting BCH code in general. We also study the Schaub algorithm which determines a lower bound of the minimum distance of a cyclic code. We introduce a pruning strategy to improve the Schaub algorithm. Finally we study the cryptographic property of a Boolean function, called spectral immunity which is directly related to the minimum distance of cyclic codes over \({\mathbb{F}_{2^m}}\). We apply the improved Schaub algorithm in order to find a lower bound of the spectral immunity of a Boolean function related to the zero set {1, 2 ⁱ  + 1, 2 ^j  + 1}.

A new range proof scheme is proposed in this paper. We study a related technique, range test, and show how its idea can be used to design a more advanced range proof technique. The main advantage of the new range proof technique over the existing solutions is that it achieves the best trade-off between soundness, privacy and efficiency. Is achieves information-theoretic and absolutely precise soundness and thus is more secure than those range proof schemes with conditional soundness. It achieves formally provable zero knowledge in privacy and thus is more secure than those range proof schemes without formally proven zero knowledge. It only needs a small constant number of computations and employs normal-length parameters and thus is more efficient than those range proof schemes needing super-linear cost or extra large integers.

In this paper, we study bit commitment in the bounded storage model (BSM). Specifically, in this paper we derive the tight lower bound on the memory size of honest players of bit commitment in the BSM. The tightness of our lower bound is shown by the fact that a certain bit commitment scheme obtained from the oblivious transfer by Ding et al. meets the bound with equality. We also give a simple and optimal construction of the bit commitment in this paper. We emphasize that our construction is simpler and easier to implement than already known any other bit commitment in the BSM.

A self-corrector for a function f is an efficient machine that computes f correctly using any untrusted black-box that computes f correctly only with a certain probability. The design of self-correctors for non-verifiable functions, typically decryption functions of public-key cryptographies, was investigated. We present a design method for self-correctors that works even when the black-box returns correct output with probability of less than 1/2. For a practical demonstration of the method, we also present examples of self-correctors for the decryption functions of public-key cryptosystems, such as the ElGamal, the Pailler, and the GHV cryptosystems, and for hidden pairings with trapdoors.

We revisit the definitions of preimage resistance, focussing on the question of finding a definition that is simple enough to prove security against, yet flexible enough to be of use for most applications. We give an in-depth analysis of existing preimage resistance notions, introduce several new notions, and establish relations and separations between the known and new preimage notions. This establishes a clear separation between domain-oriented and range-oriented preimage resistance notions. For the former an element is chosen from the domain and hashed to form the target digest; for the latter the target digest is chosen directly from the range.

This paper extends and improves known results on finite symmetric functions: \(f:E_{a}^{n}\longrightarrow E_{b}\), to any a and any b, where E _a (respectively E _b ) stands for the set of a (respectively b) elements. It also generalises them to alternating functions. The main motivation is that for actual implementation in ciphers a and b are required to be powers of 2 instead of a prime. Another driver is the ease of implementation of these functions especially for very large n.

Search algorithms for these functions were defined and implemented with relevant improvements and significant new counting results. Our main theorem gives a new enumeration formula thanks to two theoretical enhancements. We provide exact enumeration values where only lower bounds were previously known. The non existence of balanced finite symmetric or alternating functions is proven under some conditions on a, b, and n. We also exhibit new results for new values of a and b, giving very large numbers of functions.

We propose a new type of hidden vector encryption (HVE) schemes that we call a ciphertext-policy delegatable hidden vector encryption (CP-dHVE) scheme. Several HVE or delegatable HVE schemes have already been proposed and used for achieving searchable encryption which is capable of conjunctive, subset, and range queries on ciphertexts. Those schemes, however, could be categorized as key-policy HVEs because vectors corresponding to secret keys can contain arbitrary number of wildcards (which specify an access policy) whereas vectors corresponding to ciphertexts cannot contain any wildcards. Nonetheless, its dual concept, CP-dHVE, has not been formalized thus far, which leaves the theory of HVE incomplete and potential applications veiled. We therefore formalize CP-dHVE, clarify its security requirements, and propose a concrete scheme which satisfies our security requirements. Our scheme is based on an anonymous hierarchical identity-based encryption (AHIBE) scheme and a wildcard-applicable HIBE (or simply WIBE) scheme. We utilize our “half-baked” methodology to transform an AHIBE scheme into a WIBE scheme, and a well known linear-splitting methodology to make our scheme anonymous. Finally, we show as one of applications of our CP-dHVE scheme a public-key encryption with conjunctive keyword search scheme in the multi-user setting. The ciphertext size of our scheme grows logarithmically to the number of uses while that of a conventional scheme grows linearly, which makes our scheme attractive.

In this paper, we propose a new framework for constructing hybrid encryption. Specifically, we propose an authenticated key encapsulation mechanism (AKEM) which plays a role of the public-key part, and show that it is possible to construct IND-CCA secure hybrid encryption by combining AKEM and traditional DEM (data encapsulation mechanism). The feature of AKEM worthy of mention is that it has the function of authenticity in addition to that of KEM and that it effectively uses additional information in its decryption process. The main contribution of our framework AKEM/DEM lies in simply and systematically providing a wide range of constructions for hybrid encryption by extending the idea of tag-KEM/DEM so that several well-known constructions, such as Fujisaki-Okamoto conversion and REACT, which have not been captured within existing frameworks can be successfully captured. In the AKEM/DEM framework, we propose the following three types of constructions for hybrid encryption, and show a sufficient condition on security of AKEM and DEM to prove that the resulting hybrid encryption meets IND-CCA: (i) the first construction uses only a plaintext of DEM as additional information, and it includes Fujisaki-Okamoto conversion; (ii) the second construction uses both a plaintext and a ciphertext of DEM as additional information, and it includes REACT; and (iii) the third construction uses only a ciphertext of DEM as additional information, and it includes almost all constructions of tag-KEM/DEM. Furthermore, we show that the basic ideas behind constructions of Fujisaki-Okamoto conversion, REACT and tag-KEM can be successfully extended to all types of AKEM by slightly modifying them if necessary.

In [4], starting from an automorphism θ of a finite field \({\mathbb F}_q\) and a skew polynomial ring \(R={\mathbb F}_q[X;\theta]\), module θ-codes are defined as left R-submodules of R/Rf where f ∈ R. In [4] it is conjectured that an Euclidean self-dual module θ-code is a θ-constacyclic code and a proof is given in the special case when the order of θ divides the length of the code. In this paper we prove that this conjecture holds in general by showing that the dual of a module θ-code is a module θ-code if and only if it is a θ-constacyclic code. Furthermore, we establish that a module θ-code which is not θ-constacyclic is a shortened θ-constacyclic code and that its dual is a punctured θ-constacyclic code. This enables us to give the general form of a parity-check matrix for module θ-codes and for module (θ,δ)-codes over \({\mathbb F}_q[X;\theta,\delta]\) where δ is a derivation over \({\mathbb F}_q\). We also prove the conjecture for module θ-codes who are defined over a ring A[X;θ] where A is a finite ring. Lastly we construct self-dual θ-cyclic codes of length 2 ^s over \({\mathbb F}_4\) for s ≥ 3 which are asymptotically bad and conjecture that there exists no other self-dual module θ-code of this length over \({\mathbb F}_4\).

We study the stability of m-sequences in the sense of determining the number of errors needed for decreasing the period of the sequences, as well as giving lower bounds on the k-error linear complexity of the sequences. For prime periods the results are straightforward so we concentrate on composite periods. We give exact results for the case when the period is reduced by a factor which is a Mersenne number and for the case when it is reduced by a prime p such that the order of 2 modulo p equals p − 1. The general case is believed to be difficult due to its similarity to a well studied problem in coding theory. We also provide results about the relative frequencies of the different cases. We formulate a conjecture regarding the minimum number of errors needed for reducing the period at all. Finally we apply our results to the LFSR components of several well known stream ciphers.

In the past year, the speed record for pairing implementations on desktop-class machines has been broken several times. The speed records for asymmetric pairings were set on a single processor. In this paper, we describe our parallel implementation of the optimal ate pairing over Barreto-Naehrig (BN) curves that is about 1.23 times faster using two cores of an Intel Core i5 or Core i7 machine, and 1.45 times faster using 4 cores of the Core i7 than the state-of-the-art implementation on a single core. We instantiate Hess’s general Weil pairing construction and introduce a new optimal Weil pairing tailored for parallel execution. Our experimental results suggest that the new Weil pairing is 1.25 times faster than the optimal ate pairing on 8-core extensions of the aforementioned machines. Finally, we combine previous techniques for parallelizing the eta pairing on a supersingular elliptic curve with embedding degree 4, and achieve an estimated 1.24-fold speedup on an 8-core extension of an Intel Core i7 over the previous best technique.

The advent of Pairing-based protocols has had a major impact on the applicability of cryptography to the solution of more complex real-world problems. However there has always been a question mark over the performance of such protocols. In response much work has been done to optimize pairing implementation, and now it is generally accepted that being pairing-based does not preclude a protocol from consideration as a practical proposition. However although a lot of effort has gone into the optimization of the stand-alone pairing, in many protocols the pairing calculation appears in a particular context within which further optimizations may be possible. It is the purpose of this paper to bridge the gap between theory and practice, and to show that even complex protocols may have a surprisingly efficient implementation. We also point out that in some cases the usually recommended pairing friendly curves may not in fact be optimal. We claim a new record with our implementation of a pairing at the AES-256 bit level.

In pairing-based cryptography, most researches are focused on elliptic curves of embedding degrees greater than six, but less on curves of small embedding degrees, although they are important for pairing-based cryptography over composite-order groups. This paper analyzes efficient pairings on ordinary elliptic curves of embedding degree 1 and 2 from the point of shortening Miller’s loop. We first show that pairing lattices presented by Hess can be redefined on composite-order groups. Then we give a simpler variant of the Weil pairing lattice which can also be regarded as an Omega pairing lattice, and extend it to ordinary curves of embedding degree 1. In our analysis, the optimal Omega pairing, as the super-optimal pairing on elliptic curves of embedding degree 1 and 2, could be more efficient than Weil and Tate pairings. On the other hand, elliptic curves of embedding degree 2 are also very useful for pairings on elliptic curves over RSA rings proposed by Galbraith and McKee. So we analyze the construction of such curves over RSA rings, and redefine pairing lattices over RSA rings. Specially, modified Omega pairing lattices over RSA rings can be computed without knowing the RSA trapdoor. Furthermore, for keeping the trapdoor secret, we develop an original idea of evaluating pairings without leaking the group order.

Precomputation is essential for window-based scalar multiplications which are the most important operation of elliptic curve cryptography. This precomputation stage may require a significant amount of time due to the expensive inversions over finite fields of large characteristic. Hence, the existing state-of-the-art precomputation schemes try to reduce the number of inversions as much as possible. However, our analysis show that the performance of precomputation schemes not only depends on the cost of field inversions, but also on the cost ratio of inversion to multiplication (i.e. I/M).

In this paper, we present a new scheme to precompute all odd multiples [3]P, …, [2k − 1]P, k ≥ 2 on standard elliptic curves in affine coordinates. Our precomputation scheme strikes a balance between the number of inversions and multiplications. We show that our scheme requiring only 2(k − 1) registers, offers the best performance in the case of k ≥ 8 if the I/M-ratio is around 10.

We provide an analysis of the widely deployed SSH protocol’s key exchange mechanism. We exploit the design of the SSH key exchange to perform our analysis in a modular manner. First, a shared secret key is obtained via a Diffie-Hellman key exchange. Next, a transform is applied to obtain the application keys used by later stages of SSH. We define models, following well-established paradigms, that clarify the security provided by each type of key. Previously, there has been no formal analysis of the SSH key exchange protocol. We provide a modular proof of security for the SSH shared secret and application keys. We show that although the shared secret key exchanged by SSH is not indistinguishable, the transformation then applied yields indistinguishable application keys. Our proofs use random oracles to model the hash function used within SSH.

In recent years, light-weight cryptography has received a lot of attention. Many primitives suitable for resource-restricted hardware platforms have been proposed. In this paper, we present a cryptanalysis of the new stream cipher A2U2 presented at IEEE RFID 2011 [9] that has a key length of 56 bit. We start by disproving and then repairing an extremely efficient attack presented by Chai et al. [8], showing that A2U2 can be broken in less than a second in the chosen-plaintext case. We then turn our attention to the more challenging known-plaintext case and propose a number of attacks. A guess-and-determine approach combined with algebraic cryptanalysis yields an attack that requires about 2⁴⁹ internal guesses. We also show how to determine the 5-bit counter key and how to reconstruct the 56-bit key in about 2³⁸ steps if the attacker can freely choose the IV. Furthermore, we investigate the possibility of exploiting the knowledge of a “noisy keystream” by solving a Max-PoSSo problem. We conclude that the cipher needs to be repaired and point out a number of simple measures that would prevent the above attacks.

This paper extends the provably-secure blockcipher construction proposed at FSE 2009 by Minematsu. Unlike the classical Luby-Rackoff cipher and its variants, the scheme is based on tweakable blockciphers. An advantage of the scheme is that it provides the beyond-birthday-bound security quite efficiently. While FSE 2009 proposal was the case of building a 2n-bit blockcipher using an n-bit tweakable blockcipher, we extend it to shorter and longer block lengths than 2n bits, keeping the security of beyond the birthday bound.

Key wrapping schemes are used to encrypt data of high entropy, such as cryptographic keys. There are two known security definitions for key wrapping schemes. One captures the security against chosen plaintext attacks (called DAE-security), and the other captures known plaintext attacks (called AKW-security). In this paper, we revisit the security of Hash-then-CBC key wrapping schemes. At SKEW 2011, Osaki and Iwata showed that the U _CC -then-CBC key wrapping scheme, a key wrapping scheme that uses the U _CC hash function and the CBC mode, has provable AKW-security. In this paper, we show that the scheme achieves the stronger notion of DAE-security. We also show our proof in the variable input length setting, where the adversary is allowed making queries of varying lengths. To handle such a setting, we generalize the previous definition of the U _CC hash function to the variable input length setting, and show an efficient construction that meets the definition. We next consider linear-then-CBC, 2nd-preimage-resistant-then-CBC, and universal-then-CBC schemes. At SAC 2009, Gennaro and Halevi noted that these schemes do not achieve DAE-security. However, details were not presented, and we show concrete and efficient chosen plaintext attacks on these schemes, and confirm that they do not achieve DAE-security.

Anonymous credentials are protocols in which users obtain certificates from organizations and subsequently demonstrate their possession in such a way that transactions carried out by the same user cannot be linked. We present an anonymous credential scheme with non-interactive proofs of credential possession where credentials are associated with a number of attributes. Following recent results of Camenisch and Groß (CCS 2008), the proof simultaneously convinces the verifier that certified attributes satisfy a certain predicate. Our construction relies on a new kind of P-signature, termed block-wise P-signature, that allows a user to obtain a signature on a committed vector of messages and makes it possible to generate a short witness that serves as a proof that the signed vector satisfies the predicate. A non-interactive anonymous credential is obtained by combining our block-wise P-signature scheme with the Groth-Sahai proof system. It allows efficiently proving possession of a credential while simultaneously demonstrating that underlying attributes satisfy a predicate corresponding to the evaluation of inner products (and therefore disjunctions or polynomial evaluations). The security of our scheme is proved in the standard model under non-interactive assumptions.

Most one-round key exchange protocols provide only weak forward secrecy at best. Furthermore, one-round protocols with strong forward secrecy often break badly when faced with an adversary who can obtain ephemeral keys. We provide a characterisation of how strong forward secrecy can be achieved in one-round key exchange. Moreover, we show that protocols exist which provide strong forward secrecy and remain secure with weak forward secrecy even when the adversary is allowed to obtain ephemeral keys. We provide a compiler to achieve this for any existing secure protocol with weak forward secrecy.

After the introduction of designated confirmer signatures (DCS) by Chaum in 1994, considerable researches have been done to build generic schemes from standard digital signatures and construct efficient concrete solutions. In DCS schemes, a signature cannot be verified without the help of either the signer or a semi-trusted third party, called the designated confirmer. If necessary, the confirmer can further convert a DCS into an ordinary signature that is publicly verifiable. However, there is one limit in most existing schemes: the signer is not given the ability to disavow invalid DCS signatures. Motivated by this observation, in this paper we first propose a new variant of DCS model, called designated confirmer signatures with unified verification, in which both the signer and the designated confirmer can run the same protocols to confirm a valid DCS or disavow an invalid signature. Then, we present the first DCS scheme with unified verification and prove its security in the random oracle (RO) model and under a new computational assumption, called Decisional Co-efficient Linear (D-co-L) assumption, whose intractability in pairing settings is analyzed in generic group model. The proposed scheme is constructed by encrypting Boneh, Lynn and Shacham’s pairing based short signatures with signed ElGamal encryption. The resulting solution is efficient in both aspects of computation and communication. In addition, we point out that the proposed concept can be generalized by allowing the signer to run different protocols for confirming and disavowing signatures.