The existing discrete-logarithm-based two-round multi-signature schemes without using the idealized model, i.e., the Algebraic Group Model (AGM), have quite large reduction loss. This means that an implementation of these schemes requires an elliptic curve (EC) with a very large order for the standard 128-bit security when we consider concrete security. Indeed, the existing standardized ECs have orders too small to ensure 128-bit security of such schemes. Recently, Pan and Wagner proposed two two-round schemes based on the Decisional Diffie-Hellman (DDH) assumption (EUROCRYPT 2023). For 128-bit security in concrete security, the first scheme can use the NIST-standardized EC P-256 and the second can use P-384. However, with these parameter choices, they do not improve the signature size and the communication complexity over the existing non-tight schemes. Therefore, there is no two-round scheme that (i) can use a standardized EC for 128-bit security and (ii) has high efficiency. In this paper, we construct a two-round multi-signature scheme achieving both of them from the DDH assumption. We prove that an EC with at least a 321-bit order is sufficient for our scheme to ensure 128-bit security. Thus, we can use the NIST-standardized EC P-384 for 128-bit security. Moreover, the signature size and the communication complexity per one signer of our proposed scheme under P-384 are 1152 bits and 1535 bits, respectively. These are most efficient among the existing two-round schemes without using the AGM including Pan-Wagner’s schemes and non-tight schemes which do not use the AGM. Our experiment on an ordinary machine shows that for signing and verification, each can be completed in about 65 ms under 100 signers. This shows that our scheme has sufficiently reasonable running time in practice.

This paper describes an attack that allows plural verifiers to check the validity of a signature simultaneously in Chaum's zero knowledge undeniable signature scheme, where if a malicious person takes part in the attack procedure as one verifier, the non-transitivity of a signature is suspect, and also proposes countermeasures to the attack.

The well-known closure tests, the cycling closure test (CCT) and the meet-in-the-middle closure test (MCT), were introduced by Kaliski, Rivest and Sherman to analyze the algebraic properties of cryptosystems, and CCT indicates that DES is not closed. Though Coppersmith presented that DES can be proved not to be closed by a particular way, the closure tests can check various kinds of cryptosystems generally. Thus, successors to MCT and CCT have been proposed at CRYPTO. This paper expands the MCT successor, the switching closure test (SCT), to apply to the DES-like cryptosystems, and shows that this SCT variant is more efficient than the closure test proposed at CRYPTO'92, because the SCT variant establishes a better relationship between the computation cost and the probability of error (the evaluation index). The MCT successors are more important than the CCTs, because the MCTs can directly break closed cryptosystemes. Therefore, if you want to detect the closure property of cryptosystems generally, the SCT variant is better.

Since the Merkle-Damgård hash function (denoted by MDFH) that uses a fixed input length random oracle as a compression function is not indifferentiable from a random oracle (denoted by RO) due to the extension attack, there is no guarantee for the security of cryptosystems, which are secure in the RO model, when RO is instantiated with MDHF. This fact motivates us to establish a criteria methodology for confirming cryptosystems security when RO is instantiated with MDHF. In this paper, we confirm cryptosystems security by using the following approach: 1.Find a weakened random oracle (denoted by WRO) which leaks values needed to realize the extension attack. 2.Prove that MDHF is indifferentiable from WRO. 3.Prove cryptosystems security in the WRO model. The indifferentiability framework of Maurer, Renner and Holenstein guarantees that we can securely use the cryptosystem when WRO is instantiated with MDHF. Thus we concentrate on such finding WRO. We propose Traceable Random Oracle (denoted by TRO) which leaks values enough to permit the extension attack. By using TRO, we can easily confirm the security of OAEP encryption scheme and variants of OAEP encryption scheme. However, there are several practical cryptosystems whose security cannot be confirmed by TRO (e.g. RSA-KEM). This is because TRO leaks values that are irrelevant to the extension attack. Therefore, we propose another WRO, Extension Attack Simulatable Random Oracle (denoted by ERO), which leaks just the value needed for the extension attack. Fortunately, ERO is necessary and sufficient to confirm the security of cryptosystems under MDHF. This means that the security of any cryptosystem under MDHF is equivalent to that under the ERO model. We prove that RSA-KEM is secure in the ERO model.

In this paper, we discuss the collision search for hash functions, mainly in terms of their advanced message modification. The advanced message modification is a collision search tool based on Wang et al.'s attacks. Two advanced message modifications have previously been proposed: cancel modification for MD4 and MD5, and propagation modification for SHA-0. In this paper, we propose a new concept of advanced message modification, submarine modification. As a concrete example combining the ideas underlying these modifications, we apply submarine modification to the collision search for SHA-0. As a result, we show that this can reduce the collision search attack complexity from 239 to 236 SHA-0 compression operations.

At EUROCRYPT 2012, Libert, Peters and Yung (LPY) proposed the first scalable revocable group signature (R-GS) scheme in the standard model which achieves constant signing/verification costs and other costs regarding signers are at most logarithmic in N, where N is the maximum number of group members. However, although the LPY R-GS scheme is asymptotically quite efficient, this scheme is not sufficiently efficient in practice. For example, the signature size of the LPY scheme is roughly 10 times larger than that of an RSA signature (for 160-bit security). In this paper, we propose a compact R-GS scheme secure in the random oracle model that is efficient not only in the asymptotic sense but also in practical parameter settings. We achieve the same efficiency as the LPY scheme in an asymptotic sense, and the signature size is nearly equal to that of an RSA signature (for 160-bit security). It is particularly worth noting that our R-GS scheme has the smallest signature size compared to those of previous R-GS schemes which enable constant signing/verification costs. Our technique, which we call parallel Boneh-Boyen-Shacham group signature technique, helps to construct an R-GS scheme without following the technique used in LPY, i.e., we directly apply the Naor-Naor-Lotspiech framework without using any identity-based encryption.

This paper shows two power analysis attacks against a software implementation of a first-order DPA resistant S-box algorithm that is based on the discrete Fourier Transform (DFT). The DPA resistant S-box algorithm based on DFT was proposed by Prouff et al. in 2006 and improved by Coron et al. in 2008, respectively. In our attacks against the improved one, we pre-process the power traces by separating them into two subgroups, so that each has a biased mask. For the separated power traces, two post analysis methods are proposed to identify the key. One is based on DPA attack against one subgroup, and the other utilizes the difference of means for two subgroups and a pattern matching. Finally, we compare these two attack methods and propose an algorithm-level countermeasure to enhance the security of S-box calculation based on the DFT.

In this paper, we propose password recovery attacks against challenge-response authentication protocols. Our attacks use a message difference for a MD5 collision attack proposed in IEICE 2008. First, we show how to efficiently find a message pair that collides with the above message difference. Second, we show that a password used in authenticated post office protocol (APOP) can be recovered practically. We also show that the password recovery attack can be applied to a session initiation protocol (SIP) and digest authentication. Our attack can recover up to the first 31 password characters in a short time and up to the first 60 characters faster than the naive search method. We have implemented our attack and confirmed that 31 characters can be successfully recovered.

The PayWord Scheme, invented by Rivest and Shamir, is an efficient micropayment scheme utilizing a hash function. We point out that the scheme has the following problem: a malicious customer can damage the bank by purchasing in excess of the customer's credit which the bank has guaranteed by issuing a certificate. Generally, there are two positions of the bank with regard to the certificate. Position 1: the bank takes full responsibility for the certificate and compensates all payments created by the customer's purchases; and Position 2: the bank does not redeem payments exceeding a limit set for the customer and shares the loss with the shop if trouble occurs. In the PayWord Scheme, the bank can reduce its risk by adopting Position 2 rather than Position 1. However, this paper points out that the bank can damage the shop in Position 2 by impersonating an imaginary customer and making the shop share the loss with the bank. We propose a micropayment scheme (countermeasure) that overcomes these problems.

This paper proposes a new algorithm for evaluating the number of chaining variable conditions (CVCs) in the selecting step of a disturbance vector (DV) for the analysis of SHA-1 collision search. The algorithm is constructed by combining four strategies, that can evaluate the number of CVCs more strictly compared with the previous approach. By using our method, we found some DVs that have 57 (or 59) essential CVCs for 1st (or 2nd) block in the case if we assume that we can modify messages up to step 25, which we have not confirmed the practicability of the assumption.

GPS is an efficient identification (ID) scheme based on Schnorr ID scheme designed for applications where low cost devices with limited resources are used and a very-short authentication time is required. Let P and V be a prover and a verifier in GPS and < g > be a multiplicative group. P holds a secret key S∈[0,S) and publishes I=g-s. In each elementary round: (1) P sends to Vx=gr where r is chosen randomly from [0,A), (2) V sends to P a random C∈[0,B), and (3) P sends y=r+cs (no modulus computation). Since there is no modular reduction on y, a key issue is whether GPS leaks information about s. It has been proved that GPS is statistical zero-knowledge, if in asymptotic sense, BS/A is negligible, where is the number of elementary rounds in one complete identification trial. In this paper, first we will show the followings. (1) We can construct a concrete attack procedure which reveals one bit of secret key s from the specified value range of y unless BS/A is negligible. We reconfirm that we must set A extremely large compared to BS. (2) This drawback can be avoided by modifying GPS into a new scheme, GPS+, in which P does not send the value of y in the specified range where y reveals some information about s. GPS+ ensures perfect ZK only by requiring both A > BS and A being a multiple of the order of g, while it allows an honest P to be rejected with probability at most BS/(2A) in one elementary round. Under the standard recommended parameters for 80-bit security where =1, |S|=160, and |B|=35, |A|=275 is recommended for GPS in GPS' paper. On the other hand, GPS+ can guarantee 80-bit security and less than one false rejection on average in 100 identifications with only |A|=210 with the same parameters as above. In practice, this implies 275-210=65 bits (≈24%) reductions on storage requirement. We have confirmed that the reduce of A also reduces approximately 4% of running time for online response using a certain implementation technique for GPS+ by machine experiment.

The most widely used hash functions from MD4 family have been broken, which lead to a public competition on designing new hash functions held by NIST. This paper focuses on one concept called near-collision resistance: computationally difficult to find a pair of messages with hash values differing in only few bits, which new hash functions should satisfy. In this paper, we will give a model of near-collisions on MD4, and apply it to attack protocols including HMAC/NMAC-MD4 and MD4(Password||Challenge). Our new outer-key recovery attacks on HMAC/NMAC-MD4 has a complexity of 272 online queries and 277 MD4 computations, while previous result was 288 online queries and 295 MD4 computations. Our attack on MD4(Password||Challenge) can recover 16 password characters with a complexity of 237 online queries and 221 MD4 computations, which is the first approach to attack such protocols.

We discuss the security of Message Authentication Code (MAC) schemes from the viewpoint of differential attack, and propose an attack that is effective against DES-MAC and FEAL-MAC. The attack derives the secret authentication key in the chosen plaintext scenario. For example, DES(8-round)-MAC can be broken with 234 pairs of plaintext, while FEAL8-MAC can be broken with 222 pairs. The proposed attack is applicable to any MAC scheme, even if the 32-bits are randomly selected from among the 64-bits of ciphertext generated by a cryptosystem vulnerable to differential attack in the chosen plaintext scenario.

This paper proposes the first provably secure multi-signature schemes under the random oracle model. The security of our schemes can be proven in the sense of concrete security in Ref. [13]. The proposed schemes are efficient if the random oracle is replaced by practical hash functions. The essential techniques in our proof of security are the optimal reduction from breaking the corresponding identification to breaking signatures (ID Reduction Technique), and the hierarchical heavy row lemmas used in the concrete reduction from solving the primitive problem to breaking the identification scheme.

Ring signature scheme enables a signer to sign a message anonymously. In the ring signature scheme, the signer who wants to sign a document anonymously first chooses some public keys of entities (signers) and then generates a signature which ensures that one of the signer or entities signs the document. In some situations, however, the ring signature scheme allows the signer to shift the blame to victims because of the anonymity. The group signature scheme may be a solution for the problem; however, it needs an electronic big brother, called a group manager, who can violate the signer anonymity by himself, and a complicated key setting. This paper introduces a new notion of a signature scheme with signer anonymity, a deniable ring signature scheme (DRS), in which no group manager exists, and the signer should be involved in opening the signer anonymity. We also propose a concrete scheme proven to be secure under the assumption of the DDH (decision Diffie Hellman) problem in the random oracle model.

In this paper, we present practical password recovery attacks against two challenge and response authentication protocols using MD4. For attacks on protocols, the number of queries is one of the most important factors because the opportunity where an attacker can ask queries is very limited in real protocols. When responses are computed as MD4(Password||Challenge), which is called prefix approach, previous work needs to ask 237 queries to recover a password. Asking 237 queries in real protocols is almost impossible. In our attack, to recover up to 8-octet passwords, we only need 1 time the amount of eavesdropping, 17 queries, and 234 MD4 off-line computations. To recover up to 12-octet passwords, we only need 210 times the amount of eavesdropping, 210 queries, and 241 off-line MD4 computations. When responses are computed as MD4(Password||Challenge||Password), which is called hybrid approach, previous work needs to ask 263 queries, while in our attack, up to 8-octet passwords are practically recovered by 28 times the amount of eavesdropping, 28 queries, and 239 off-line MD4 computations. Our idea is guessing a part of passwords so that we can simulate values of intermediate chaining variables from observed hash values. This enables us to use a short local collision that occurs with a very high probability, and thus the number of queries becomes practical.

In this paper, we propose a new type of authentication system, one-time zero-knowledge authentication system. Informally speaking, in this authentication system, double usage of the same authentication is prevented. Based on these one-time zero-knowledge authentication systems, we propose a new untraceable electronic cash scheme satisfying both untraceability and unreusablity. This scheme overcomes the problems of the previous scheme proposed by Chaum, Fiat and Naor through its greater efficiency and provable security under reasonable cryptographic assumptions. We also propose a scheme, transferable untraceable electronic cash scheme, satisfying transferability as well as the above two criteria. Moreover, we also propose a new type of electronic cash, untraceable electronic coupon ticket, in which the value of one piece of the electronic cash can be subdivided into many pieces.

This paper proposes to apply random mapping methods of a pseudo random function to find collisions of a hash function. We test a hash function including a block cipher (see ISO/IEC 10118-2) with computers, where users can select its initial vector. In particular, the paper shows that a hash function with multiple stages generates a lot of collision hash values, so our probabilistic consideration of a small model for the hash function well explains the computational results. We show that it's feasible to find collisions between the selected messages in advance for 64-bit-size hash functions with WSs linked via an ordinary LAN (Local Area Network). Thus, it is dangerous to use the hash function -- single block mode -- defined in [6] and [7].

Secret Handshake protocol allows members of the same group to authenticate each other secretly. That is, two members who belong to the same group can learn counterpart is in the same group, while non-member of the group cannot determine whether the counterpart is a member of the group or not. Yamashita and Tanaka proposed Secret Handshake Scheme with Multiple Groups (SHSMG). They extended a single group setting to a multiple groups setting where two members output "accept" iff both member's affiliations of the multiple groups are identical. In this paper, we first show the flaw of their SHSMG, and we construct a new secure SHSMG. Second, we introduce a new concept of Secret Handshake scheme, "monotone condition Secret Handshake with Multiple Groups (mc-SHSMG)," in order to extend the condition of "accept." In our new setting of handshake protocol, members can authenticate each other in monotone condition (not only both member's affiliations are identical but also the affiliations are not identical). The communication costs and computational costs of our proposed mc-SHSMG are fewer than the trivial construction of mc-SHSMG.

Many hash-based authentication protocols have been proposed, and proven secure assuming that underlying hash functions are secure. On the other hand, if a hash function compromises, the security of authentication protocols based on this hash function becomes unclear. Therefore, it is significantly important to verify the security of hash-based protocols when a hash function is broken. In this paper, we will re-evaluate the security of two MD5-based authentication protocols based on a fact that MD5 cannot satisfy a required fundamental property named collision resistance. The target protocols are APOP (Authenticated Post Office Protocol) and NMAC (Nested Message Authentication Code), since they or their variants are widely used in real world. For security evaluation of APOP, we will propose a modified password recovery attack procedure, which is twice as fast as previous attacks. Moreover, our attack is more realistic, as the probability of being detected is lower than that of previous attacks. For security evaluation of MD5-based NMAC, we will propose a new key-recovery attack procedure, which has a complexity lower than that of previous attack. The complexity of our attack is 276, while that of previous attack is 2100.** Moreover, our attack has another interesting point. NMAC has two keys: the inner key and the outer key. Our attack can recover the outer key partially without the knowledge of the inner key.