KyungKeun LEE YoungHo PARK SangJae MOON
Recently, Yoon et al. exhibited the vulnerability of the smart-card-equipped password based authentication protocol proposed by Chien et al. to the Denning-Sacco attack. Furthermore, they also pointed out that the protocol does not provide the perfect forward secrecy. Accordingly, they presented an enhanced protocol to strengthen the security. This letter, however, demonstrates an interleaving attack on the Yoon et al.'s improved protocol and also discusses how to defend the protocol from the attack presented here.
Taiichi SAITO Fumitaka HOSHINO Shigenori UCHIYAMA Tetsutaro KOBAYASHI
This paper proposes new candidate one-way functions constructed with a certain type of endomorphisms on non-supersingular elliptic curves. We can show that the one-wayness of our proposed functions is equivalent to some special cases of the co-Diffie-Hellman assumption. Also a digital signature scheme is explicitly described using our proposed functions.
Chisato KONOMA Masahiro MAMBO Hiroki SHIZUYA
To examine the computational complexity of cryptographic primitives such as the discrete logarithm problem, the factoring problem and the Diffie-Hellman problem, we define a new problem called square-root exponent, which is a problem to compute a value whose discrete logarithm is a square root of the discrete logarithm of a given value. We analyze reduction between the discrete logarithm problem modulo a prime and the factoring problem through the square-root exponent. We also examine reductions among the computational version and the decisional version of the square-root exponent and the Diffie-Hellman problem and show that the gap between the computational square-root exponent and the decisional square-root exponent partially overlaps with the gap between the computational Diffie-Hellman and the decisional Diffie-Hellman under some condition.
Chik-How TAN Xun YI Chee-Kheong SIEW
In this paper, we examine the computational Diffie-Hellman problem and decisional Diffie-Hellman problem in 3-rd order linear feedback shift register and show that the shift register based Diffie-Hellman problems are equivalent to the Diffie-Hellman problems over prime subgroup of GF(p3e) respectively. This result will be useful in constructing new cryptographic primitives based on the hardness of the shift register based Diffie-Hellman problems.
Goldwasser and Sipser proved that every interactive proof system can be transformed into a public-coin one (a.k.a. an Arthur-Merlin game). Unfortunately, the applicability of their transformation to cryptography is limited because it does not preserve the computational complexity of the prover's strategy. Vadhan showed that this deficiency is inherent by constructing a promise problem Π with a private-coin interactive proof that cannot be transformed into an Arthur-Merlin game such that the new prover can be implemented in polynomial-time with oracle access to the original prover. However, the transformation formulated by Vadhan has a restriction, i.e., it does not allow the new prover and verifier to look at common input. This restriction is essential for the proof of Vadhan's negative result. This paper considers an unrestricted transformation where both the new prover and verifier are allowed to access and analyze common input. We show that an analogous negative result holds even in this unrestricted case under a non-standard computational assumption.
Kaoru KUROSAWA Quang Viet DUONG
In this paper, we first show a multiple-use protocol under the Diffie-Hellman assumption such that the initialization phase is much more efficient than the previous one. We next present an efficient multiple-use protocol whose security is equivalent to breaking RSA. The securities of our protocols are all formally proved.
Koji CHIDA Kunio KOBAYASHI Hikaru MORITA
A new approach for electronic sealed-bid auctions that preserve the privacy of losing bids is presented. It reduces the number of operations performed by the auctioneers to O(log
This paper describes simple and efficient (linear-preserving) reductions between the Decision Diffie-Hellman problem and related problems.
Shouichi HIROSE Kanta MATSUURA
In this manuscript, two key agreement protocols which are resistant to a denial-of-service attack are constructed from a key agreement protocol in [9] provably secure against passive and active attacks. The denial-of-service attack considered is the resource-exhaustion attack on a responder. By the resource-exhaustion attack, a malicious initiator executes a key agreement protocol simultaneously as many times as possible to exhaust the responder's resources and to disturb executions of it between honest initiators and the responder. The resources are the storage and the CPU. The proposed protocols are the first protocols resistant to both the storage-exhaustion attack and the CPU-exhaustion attack. The techniques used in the construction are stateless connection, weak key confirmation, and enforcement of heavy computation. The stateless connection is effective to enhancing the resistance to the storage-exhaustion attack. The weak key confirmation and the enforcement of heavy computation are effective to enhancing the resistance to the CPU-exhaustion attack.
Taiichi SAITO Takeshi KOSHIBA Akihiro YAMAMURA
This paper examines similarities between the Decision Diffie-Hellman (DDH) assumption and the Quadratic Residuosity (QR) assumption. In addition, we show that many cryptographic protocols based on the QR assumption can be reconstructed using the DDH assumption.
The rigorous security of Okamoto-Tanaka identity-based key exchange scheme has been open for a decade. In this paper, we show that (1) breaking the scheme is equivalent to breaking the Diffie-Hellman key exchange scheme over Zn, and (2) impersonation is easier than breaking. The second result is obtained by proving that breaking the RSA public-key cryptosystem reduces to breaking the Diffie-Hellman scheme over Zn with respect to the polynomial-time many-one reducibility.
Secret sharing schemes are good for protecting the important secrets. They are, however, inefficient if the secret shadow held by the shadowholder cannot be reused after recovering the shared secret. Traditionally, the (t, n) secret sharing scheme can be used only once, where t is the threshold value and n is the number of participants. To improve the efficiency, we propose an efficient dynamic secret sharing scheme. In the new scheme, each shadowholder holds a secret key and the corresponding public key. The secret shadow is constructed from the secret key in our scheme, while in previously proposed secret sharing schemes the secret key is the shadow. In addition, the shadow is not constructed by the shadowholder unless it is necessary, and no secure delivery channel is needed. Morever, this paper will further discuss how to change the shared secret, the threshold policy and cheater detection. Therefore, this scheme provides an efficient way to maintain important secrets.