The notion of aggregator oblivious (AO) security for privacy preserving data aggregation was formalized with a specific construction of AO-secure blinding technique over a cyclic group by Shi et al. Some of proposals of data aggregation protocols use the blinding technique of Shi et al. for BGN cryptosystem, an additive homomorphic encryption. Previously, there have been some security analysis on some of BGN based data aggregation protocols in the context of integrity or authenticity of data. Even with such security analysis, the BGN cryptosystem has been a popular building block of privacy preserving data aggregation protocol. In this paper, we study the privacy issues in the blinding technique of Shi et al. used for BGN cryptosystem. We show that the blinding techniques for the BGN cryptosystem used in several protocols are not privacy preserving against the recipient, the decryptor. Our analysis is based on the fact that the BGN cryptosystem uses a pairing e : G × G → G T and the existence of the pairing makes the DDH problem on G easy to solve. We also suggest how to prevent such privacy leakage in the blinding technique of Shi et al. used for BGN cryptosystem.

In LATTE, a lattice based hierarchical identity-based encryption (HIBE) scheme, each hierarchical level user delegates a trapdoor basis to the next level by solving a generalized NTRU equation of level ℓ ≥ 3. For ℓ = 2, Howgrave-Graham, Pipher, Silverman, and Whyte presented an algorithm using resultant and Pornin and Prest presented an algorithm using a field norm with complexity analysis. Even though their ideas of solving NTRU equations can be conceptually extended for ℓ ≥ 3, no explicit algorithmic extensions with the storage analysis are known so far. In this paper, we interpret the generalized NTRU equation as the determinant of a matrix. By using the mathematical properties of the determinant, we show that how to construct algorithms for solving the generalized NTRU equation either using resultant or a field norm for any ℓ ≥ 3. We also obtain an upper bound of the size of solutions by using the properties of the determinant. From our analysis, the storage requirement of the algorithm using resultant is O(ℓ 2 n 2 log B) and that of the algorithm using a field norm is O(ℓ 2 n log B), where B is an upper bound of the coefficients of the input polynomials of the generalized NTRU equations. We present examples of our algorithms for ℓ = 3 and the average storage requirements for ℓ = 3; 4.

The notion of key substitution security on digital signatures in the multiuser setting has been proposed by Menezes and Smart in 2004. Along with the unforgeability of signature, the key substitution security is very important since it is a critical requirement for the nonrepudiation and the authentication of the signature. Lattice-based signature is a promising candidate for post-quantum cryptography, and the unforgeability of each scheme has been relatively well studied. In this paper, we present key substitution attacks on BLISS, Lyubashevsky’s signature scheme, and GPV and thus show that these signature schemes do not provide nonrepudiation. We also suggest how to avoid key substitution attack on these schemes.

Tian and Huang proposed a lattice-based CLS scheme based on the hardness of the SIS problem and proved, in the random oracle model, that the scheme is existentially unforgeable against strong adversaries. Their security proof uses the general forking lemma under the assumption that the underlying hash function H is a random oracle. We show that the hash function in the scheme is neither one-way nor collision-resistant in the view of a strong Type 1 adversary. We point out flaws in the security arguments and present attack algorithms that are successful in the strong Type 1 adversarial model using the weak properties of the hash function.

The McEliece cryptosystem is defined using a Goppa code, and decoding the Goppa code is a crucial step of its decryption. Patterson's decoding algorithm is the best known algorithm for decoding Goppa codes. Currently, the most efficient implementation of Patterson's algorithm uses a precomputation. In this paper, we modify Patterson's decoding algorithm so that one can remove the precomputation part while sustaining the best efficiency. Precomputations yield additional storage requirement to store the precomputed value which increases as the security level increases in McEliece cryptosystem. In the original decoding algorithm of Patterson, computing square root in a quotient field of polynomial ring over a finite field is necessary. In our modification, the computations are involved only in the arithmetics of polynomial ring over a finite field, not in the quotient field. This achieves better efficiency because one can remove polynomial reductions in the computations of quotient field.

In this paper, we propose a new method for constructing a bilinear pairing over (hyper)elliptic curves, which we call the R-ate pairing. This pairing is a generalization of the Ate and Ateipairing, and can be computed more efficiently. Using the R-ate pairing, the loop length in Miller's algorithm can be as small as log (r1/phi(k)) some pairing-friendly elliptic curves which have not reached this lower bound. Therefore, we obtain savings of between 29% and 69% in overall costs compared to the Ateipairing. On supersingular hyperelliptic curves of genus 2, we show that this approach makes the loop length in Miller's algorithm shorter than that of the Ate pairing.