The problem we consider in this paper is whether the Menezes-Okamoto-Vanstone (MOV) reduction for attacking elliptic curve cryptosystems can be realized for genera elliptic curves. In realizing the MOV reduction, the base field Fq is extended so that the reduction to the discrete logarithm problem in a finite field is possible. Recent results by Balasubramanian and Koblitz suggest that, if l q-1, such a minimum extension degree is the minimum k such that l|qk-1, which is equivalent to the condition under which the Frey-Ruck (FR) reduction can be applied, where l is the order of the group in the elliptic curve discrete logarithm problem. Our point is that the problem of finding an l-torsion point required in evaluating the Weil pairing should be considered as well from an algorithmic point of view. In this paper, we actually propose a method which leads to a solution of the problem. In addition, our contribution allows us to draw the conclusion that the MOV reduction is indeed as powerful as the FR reduction under l q-1 not only from the viewpoint of the minimum extension degrees but also from that of the effectiveness of algorithms.

The security of biometric authentication systems against impersonation attack is usually evaluated by the false accept rate, FAR. The false accept rate FAR is a metric for zero-effort impersonation attack assuming that the attacker attempts to impersonate a user by presenting his own biometric sample to the system. However, when the attacker has some information about algorithms in the biometric authentication system, he might be able to find a “strange” sample (called a wolf) which shows high similarity to many templates and attempt to impersonate a user by presenting a wolf. Une, Otsuka, Imai [22],[23] formulated such a stronger impersonation attack (called it wolf attack), defined a new security metric (called wolf attack probability, WAP), and showed that WAP is extremely higher than FAR in a fingerprint-minutiae matching algorithm proposed by Ratha et al. [19] and in a finger-vein-patterns matching algorithm proposed by Miura et al. [15]. Previously, we constructed secure matching algorithms based on a feature-dependent threshold approach [8] and showed that if the score distribution is perfectly estimated for each input feature data, then the proposed algorithms can lower WAP to a small value almost the same as FAR. In this paper, in addition to reintroducing the results of our previous work [8], we show that the proposed matching algorithm can keep the false reject rate (FRR) low enough without degrading security, if the score distribution is normal for each feature data.

The code length of Tardos's collusion-secure fingerprint code is of theoretically minimal order with respect to the number of adversarial users (pirates). However, the constant factor should be further reduced for practical implementation. In this article, we improve the tracing algorithm of Tardos's code and propose a 2-secure and short random fingerprint code, which is secure against collusion attacks by two pirates. Our code length is significantly shorter than that of Tardos's code and its tracing error probability is practically small.

So far, in almost all of the practical public key encryption schemes, hash functions which are dependent on underlying cyclic groups are necessary, e.g., H:{0,1}* → Zp where p is the order of the underlying cyclic group, and it could be required to construct a dedicated hash function for each public key. The motivation of this note is derived from the following two facts: 1). there is an important technical gap between hashing to a specific prime-order group and hashing to a certain length bit sequence, and this could cause a security hole; 2). surprisingly, to our best knowledge, there is no explicit induction that one could use the simple construction, instead of tailor-made hash functions. In this note, we investigate this issue and provide the first rigorous discussion that in many existing schemes, it is possible to replace such hash functions with a target collision resistant hash function H:{0,1}* → {0,1}k, where k is the security parameter. We think that it is very useful and could drastically save the cost for the hash function implementation in many practical cryptographic schemes.

An algorithm for cryptanalysis of certain keystream generators is proposed. The developed algorithm has the following two advantages over other reported ones: it is more powerful, and it can be implemented by a high-speed software or a simple hardware suitable for high parallel architectures. The algorithm is based on error-correction of information bits only (of the corresponding binary block code) with a novel method for construction of the parity-checks, and the employed error-correction procedure is an APP based threshold decoding. Experimental and theoretical analyses of the algorithm performance are presented, and its complexity is evaluated. The proposed algorithm is compared with recently proposed improved fast correlation attacks based on convolutional codes and turbo decoding. The underlying principles, performance and complexity are compared, and the gain obtained with the novel approach is pointed out.

Internet Key Exchange (IKE) is very important as an entrance to secure communication over the Internet. The first phase of IKE is based on Diffie-Hellman (DH) key-agreement protocol. Since DH protocol on its own is vulnerable to man-in-the-middle (MIM) attack, IKE provides authentication to protect the protocol from MIM. This authentication owes a lot to public-key primitives whose implementation includes modular exponentiation. Since modular exponentiation is computationally expensive, attackers are motivated to abuse it for Denial-of-Service (DoS) attacks; computational burden caused by malicious requests may exhaust the CPU resource of the target. DoS attackers can also abuse inappropriate use of Cookies in IKE; as an anti-clogging token, Cookie must eliminate the responder's state during initial exchanges of the protocol while IKE Cookies do not. Thus a large number of malicious requests may exhaust the memory resource of the target. In search of resistance against those DoS attacks, this paper first reviews DoS-resistance of the current version of IKE and basic ideas on DoS-protection. The paper then proposes a DoS-resistant version of three-pass IKE Phase 1 where attackers are discouraged by heavy stateful computation they must do before the attack really burdens the target. DoS-resistance is evaluated in terms of the computational cost and the memory cost caused by bogus requests. The result shows that the proposed version gives the largest ratio of the attacker's cost to the responder's cost.

A function can be represented in many ways. A representation O of a function f is called 'obscure' if O is different from the representation D used as the definition of f and if it is (or, seems to be) computationally infeasible to get D from O. Such an obscure representation is useful for cryptographic techniques so that it is important to estimate its descriptive and executive complexity. We present a complexity-estimation method for certain functions used to constructing asymmetric cryptosystems. Let m be a positive integer and let K, Km, and L denote the field {0, 1}, the set of all m-tuples over K, and an extention field or order m over K, respectively. The objective function is a composit g:Km Km of three functions s, e, and t, where s:Km L and t:L Km are affine and e:L L is defined by a univariate polynomial e over L. The obscure representation of g is an m-tuple g of m-variate polynomials over K. The complexity respect to g is well measured by its degree. So we give a theorem for estimating the degree of g in terms of a characteristic quantity of the polynomial e.