It is known that a super-pseudorandom permutation can be constructed from a pseudorandom function f and two universal hash functions, h and h′. It is a four round Feistel permutation denoted by φ(h_k,f,f,h′_k′). In this paper, we show how to re-use the secret key for f in this construction. Specifically, we show that (1) the same key can be used for both h and h′, and (2) the key for h and h′can be derived from f. As a result, our construction requires only the key for f as a secret key, and it preserves computational efficiency and security. We show the full security proof of our construction. Also, we derive a similar result for a five round MISTY-type permutation.

This paper proposes novel calculuses of linearizing attack that can be applied to higher order differential attack. Higher order differential attack is a powerful and versatile attack on block ciphers. It can be roughly summarized as follows: (1) Derive an attack equation to estimate the key by using the higher order differential properties of the target cipher, (2) Determine the key by solving an attack equation. Linearizing attack is an effective method of solving attack equations. It linearizes an attack equation and determines the key by solving a system of linearized equations using approaches such as the Gauss-Jordan method. We enhance the derivation algorithm of the coefficient matrix for linearizing attack to reduce computational cost (fast calculus 1). Furthermore, we eliminate most of the unknown variables in the linearized equations by making the coefficient column vectors 0 (fast calculus 2). We apply these algorithms to an attack of the five-round variant of KASUMI and show that the attack complexity is equivalent to 2^28.9 chosen plaintexts and 2^31.2 KASUMI encryptions.

Knudsen and Meier applied the χ²-attack to RC6. The χ²-attack recovers a key by using high correlations measured by χ²-value. Up to the present, the success probability of any χ²-attack has not been evaluated theoretically without using experimental results. In this paper, we discuss the success probability of χ²-attack and give the theorem that evaluates the success probability without using any experimental result, for the first time. We make sure the accuracy of our theorem by demonstrating it on both 4-round RC6 without post-whitening and 4-round RC6-8. We also evaluate the security of RC6 theoretically and show that a variant of the χ²-attack is faster than an exhaustive key search for the 192-bit-key and 256-bit-key RC6 with up to 16 rounds. As a result, we succeed in answering such an open question that a variant of the χ²-attack can be used to attack RC6 with 16 or more rounds.

In the past twenty years, there were only a few constructions for Boolean functions with nonlinearity exceeding the quadratic bound 2^n-1-2^(n-1)/2 when n is odd (we shall call them Boolean functions with very high nonlinearity). The first basic construction was by Patterson and Wiedemann in 1983, which produced unbalanced function with very high nonlinearity. But for cryptographic applications, we need balanced Boolean functions. Therefore in 1993, Seberry, Zhang and Zheng proposed a secondary construction for balanced functions with very high nonlinearity by taking the direct sum of a modified bent function with the Patterson-Wiedemann function. Later in 2000, Sarkar and Maitra constructed such functions by taking the direct sum of a bent function with a modified Patterson-Wiedemann function. In this paper, we propose a new secondary construction for balanced Boolean functions with very high nonlinearity by recursively composing balanced functions with very high nonlinearity with quadratic functions. This is the first construction for balanced function with very high nonlinearity not based on the direct sum approach. Our construction also have other desirable properties like high algebraic degree and large linear span.

At Eurocrypt'05, Wang et al. presented efficient collision attacks on MD5 and MD4 hash functions. They found a collision of MD5 with a complexity of less than 2³⁷ MD5 hash operations, and a collision of MD4 with complexity less than 2⁸ MD4 hash operations. In their attack, the procedure to generate a collision is divided into 4 steps. First, they determine the message differential and output differentials of chaining variables in each step, which generates a collision with small complexity. Second, they construct sufficient conditions that guarantee that the desired differential is always calculated. Third, they find a message modification that can satisfy the sufficient conditions with high probability. Finally, they search for a message that satisfies all sufficient conditions. In this paper, we focus on the message modification of MD5 and MD4, and propose a new message modification. Using our message modification, a collision of MD5 can be found with complexity less than 2²⁹ MD5 hash operations, and a collision of MD4 can be found with complexity less than 3 MD4 hash operations. To improve the complexity from previous attacks, we mainly use two ideas. The first idea is to use message modification that can satisfy more sufficient conditions in the second round than in previous attacks. The second idea is to use message modification that can enable us to search for a collision starting from an intermediate step.

This paper studies the reduction among cyptographic functions. Our main result is that the prime factoring function IF does not reduce to the certified discrete logarithm function modulo a prime nor its variant with respect to some special reducibility, i.e. the range injection reducibility, under the assumption that the Heath-Brown conjecture is true and IFPF. Since there is no known direct relationship between these functions, this is the first result that could separate these functions. Our approach is based on the notion of the preimage functions.

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.

An approach of membership revocation in group signatures is verifier-local revocation (VLR for short). In this approach, only verifiers are involved in the revocation mechanism, while signers have no involvement. Thus, since signers have no load, this approach is suitable for mobile environments. Although Boneh and Shacham recently proposed a VLR group signature scheme from bilinear maps, this scheme does not satisfy the backward unlikability. The backward unlinkability means that even after a member is revoked, signatures produced by the member before the revocation remain anonymous. In this paper, we propose VLR group signature schemes with the backward unlinkability from bilinear maps.

Blind signatures allow a signer to digitally sign a document without being able to glean any information about the document. In this paper, we investigate the symmetric analog of blind signatures, namely blind message authentication codes (blind MACs). One may hope to get the same efficiency gain from blind MAC constructions as is usually obtained when moving from asymmetric to symmetric cryptosystems. Our main result is a negative one however: we show that the natural symmetric analogs of the unforgeability and blindness requirements cannot be simultaneously satisfied. Faced with this impossibility, we show that blind MACs do exist (under the one-more RSA assumption in the random oracle model) in a more restrictive setting where users can share common state information. Our construction, however, is only meant to demonstrate the existence; it uses an underlying blind signature scheme, and hence does not achieve the desired performance benefits. The construction of an efficient blind MAC scheme in this restrictive setting is left as an open problem^*.

Multisignature schemes enable us to integrate multiple signatures into a single short signature. In 2001, Mitomi and Miyaji proposed a general model of multisignatures, in which signed messages are flexible and the signing order is verifiable and flexible. Several schemes that satisfy these properties have been proposed, but to the best of our knowledge, their verifiable orders are limited to only sequential structures unlike some order-verifiable (but not message-flexible) multisignatures. We define a signing structure as a labeled tree, which can represent any natural signing order including series-parallel graphs, and formalize a general model of multisignatures that makes good use of our structure. We present a security model for such signatures, give the construction based on the general aggregate signature developed by Boneh et al., and provide a security proof in the random oracle model.

ID-SP-M4M scheme means ID-based series-parallel multisignature schemes for multi-messages. In this paper, we investigate series-parallel multisignature schemes for multi-messages and propose an ID-SP-M4M scheme based on pairings in which signers in the same subgroup sign the same message, and those in different subgroups sign different messages. Our new scheme is an improvement over the series-parallel multisignature schemes introduced by Doi et al.[6]-[8] and subsequent results such as the schemes proposed by Burmester et al.[4] and the original protocols proposed by Tada [20],[21], in which only one message is to be signed. Furthermore, our ID-SP-M4M scheme is secure against forgery signature attack from parallel insiders under the BDH assumption.

It is known that for any general access structure, a secret sharing scheme (SSS) can be constructed from an (m,m)-threshold scheme by using the so-called cumulative map or from a (t,m)-threshold SSS by a modified cumulative map. However, such constructed SSSs are not efficient generally. In this paper, a new method is proposed to construct a SSS from a (t,m)-threshold scheme for any given general access structure. In the proposed method, integer programming is used to derive the optimal (t,m)-threshold scheme and the optimal distribution of the shares to minimize the average or maximum size of the distributed shares to participants. From the optimality, it can always attain lower coding rate than the cumulative maps because the cumulative maps cannot attain the optimal distribution in many cases. The same method is also applied to construct SSSs for incomplete access structures and/or ramp access structures.

We propose here the first efficient publicly verifiable hybrid mix-net. Previous publicly verifiable mix-net was only efficient for short ciphertexts and was not suitable for mixing long messages. Previous hybrid mix-net can mix long messages but did not have public verifiability. The proposed scheme is efficient enough to treat large scale electronic questionnaires of long messages as well as voting with write-ins, and offers public verifiability of the correctness of the tally. The scheme is provably secure if we assume random oracles, semantic security of a one-time symmetric-key cryptosystem, and intractability of decision Diffie-Hellman problem. This paper is the full version of the extended abstract appeared in FC 2006 [10].

We propose a protocol for implementing secure circuit evaluation (SCE) based on the threshold homomorphic ElGamal encryption scheme and present the implementation results of the protocol. To the best of knowledge of the authors, the proposed protocol is more efficient in terms of computational complexity than previously reported protocols. We also introduce applications using SCE and estimate their practicality based on the implementation results.

Password-based authenticated key exchange protocols are more convenient and practical, since users employ human-memorable passwords that are simpler to remember than cryptographic secret keys or public/private keys. Abdalla, Fouque, and Pointcheval proposed the password-based authenticated key exchange protocol in a 3-party model (GPAKE) in which clients trying to establish a secret do not share a password between themselves but only with a trusted server. On the other hand, Canetti presented a general framework, which is called universally composable (UC) framework, for representing cryptographic protocols and analyzing their security. In this framework, the security of protocols is maintained under a general protocol composition operation called universal composition. Canetti also proved a UC composition theorem, which states that the definition of UC-security achieves the goal of concurrent general composition. A server must manage all the passwords of clients when the 3-party password-based authenticated key exchange protocols are realized in large-scale networks. In order to resolve this problem, we propose a hierarchical hybrid authenticated key exchange protocol (H2AKE). In H2AKE, forwarding servers are located between each client and a distribution server, and the distribution server sends the client an authentication key via the forwarding servers. In H2AKE, public/private keys are used between servers, while passwords are also used between clients and forwarding servers. Thus, in H2AKE, the load on the distribution server can be distributed to the forwarding servers concerning password management. In this paper, we define hierarchical hybrid authenticated key exchange functionality. H2AKE is the universal form of the hierarchical (hybrid) authenticated key exchange protocol, which includes a 3-party model, and it has the characteristic that the construction of the protocol can flexibly change according to the situation. We also prove that H2AKE is secure in the UC framework with the security-preserving composition property.

Cryptosystems using pairing computation on elliptic curves have various applications including ID-based encryption ([19],[29],[30] etc.). Scott [33] proposed a scaling method of security by a change of the embedding degree k. On the other hand, he also presented an efficient pairing computation method on an ordinary (non-supersingular) elliptic curve over a large prime field F_p ([34]). In this paper, we present an implementation method of the pairing computation with both of the security scaling in [33] and the efficiency in [34]. First, we will investigate the mathematical nature of the set of the paremeter r (the order of cyclic group used) so as to support many k's. Then, based on it, we will suggest some modification to the algorithm of Scott in [34] to achieve flexible scalability of security level.

This paper proposes a new countermeasure, Random Switching Logic (RSL), against DPA (Differential Power Analysis) and Second-Order DPA at the logic level. RSL makes a signal transition uniform at each gate and suppresses the propagation of glitch to allow power consumption to be independent of predictable data. Furthermore, we implement basic logic circuits on the FPGA (Field Programmable Gate Array) by using RSL, and evaluate the effectiveness. As a result, we confirm the fact that the secure circuit can be structured against DPA and Second-Order DPA.

In this paper, we propose new models for directly evaluating DPA leakage from logic information in CMOS circuits. These models are based on the transition probability for each gate, and are naturally applicable to various actual devices for simulating power analysis. Furthermore, we demonstrate the weakness of previously known hardware countermeasures for both our model and FPGA and suggest secure conditions for the hardware countermeasure.

We propose a new construct, the Text-Graphics Character (TGC) CAPTCHA, for preventing dictionary attacks against password authentication systems allowing remote access via dumb terminals. Password authentication is commonly used for computer access control. But password authentication systems are prone to dictionary attacks, in which attackers repeatedly attempt to gain access using the entries in a list of frequently-used passwords. CAPTCHAs (Completely Automated Public Turing tests to tell Computers and Humans Apart) are currently being used to prevent automated "bots" from registering for email accounts. They have also been suggested as a means for preventing dictionary attacks. However, current CAPTCHAs are unsuitable for text-based remote access. TGC CAPTCHAs fill this gap. In this paper, we define two TGC CAPTCHAs and incorporate one of them in a prototype based on the SSH (Secure Shell) protocol suite. We also prove that, if a TGC CAPTCHA is easy for humans and hard for machines, then the resulting CAPTCHA is secure. We provide empirical evidence that our TGC CAPTCHAs are indeed easy for humans and hard for machines through a series of experiments. We believe that a system exploiting a TGC CAPTCHA will not only help improve the security of servers allowing remote terminal access, but also encourage a healthy spirit of competition in the fields of pattern recognition, computer graphics, and psychology.

We present generic frameworks for constructing efficient broadcast encryption schemes in the subset-cover paradigm, introduced by Naor et al., based on various key derivation techniques. Our frameworks characterize any instantiation completely to its underlying graph decompositions, which are purely combinatorial in nature. These abstract away the security of each instantiated scheme to be guaranteed by the generic one of the frameworks; thus, give flexibilities in designing schemes. Behind these, we present new techniques based on (trapdoor) RSA accumulators utilized to obtain practical performances. We then give some efficient instantiations from the frameworks, via a new structure called subset-incremental-chain. Our first construction improves the currently best schemes, including the one proposed by Goodrich et al., without any further assumptions (only pseudo-random generators are used) by some factors. The second instantiation, which is the most efficient, is instantiated based on RSA and directly improves the first scheme. Its ciphertext length is of order O(r), the key size is O(1), and its computational cost is O(n^1/klog² n) for any (arbitrary large) constant k; where r and n are the number of revoked users and all users respectively. To the best of our knowledge, this is the first explicit collusion-secure scheme in the literature that achieves both ciphertext size and key size independent of n simultaneously while keeping all other costs efficient, in particular, sub-linear in n. The third scheme improves Gentry and Ramzan's scheme, which itself is more efficient than the above schemes in the aspect of asymptotic computational cost.

Data retrieval is used to obtain a particular data item from a database. A user requests an item in the database from a database server by sending a query, and obtains the item from an answer to the query. Security requirements of data retrieval include protecting the privacy of the user, the secrecy of the database, and the consistency of answers. In this paper, a data retrieval scheme which satisfies all the security requirements is defined and an efficient construction is proposed. In the proposed construction, the size of a query and an answer is O((log N)²), and the size of data published by the database server when the database is updated is only O(1). The proposed construction uses the Merkle tree, a commitment scheme, and Oblivious Transfer. The proof of the security is given under the assumption that the used cryptographic schemes are secure.

A typical watermarking scheme consists of an embedding scheme and a detection scheme. In detecting a watermark, there are two kinds of detection errors, a false positive error (FPE) and a false negative error (FNE). A detection scheme is said to be optimum if the FNE probability is minimized for a given FPE probability. In this paper, we present an optimum watermark detection scheme for an additive embedding scheme with a spatial domain. The key idea of the proposed scheme is to use the differences between two brightnesses for detecting a watermark. We prove that under the same FPE probability the FNE probability of the proposed optimum detection scheme is no more than that of the previous optimum detection scheme for the additive embedding scheme with the spatial domain. Then, it is confirmed that for an actual image, the FNE probability of the proposed optimum detection scheme is much lower than that of the previous optimum detection scheme. Moreover, it is confirmed experimentally that the proposed optimum detection scheme can control the FPE probability strictly so that the FPE probability is close to a given probability.

Kurosawa-Desmedt public-key encryption scheme is a variation of Cramer-Shoup public-key encryption schemes, which are the first practical schemes secure against adaptive chosen ciphertext attack (IND-CCA) in standard model. We introduce some variants of Kurosawa-Desmedt public-key encryption scheme which are also IND-CCA secure. Furthermore, the variants are either more efficient or less cryptographic assumptions than the original version.

Johnston and Gemmell proposed an authenticated key exchange protocol based on the difficulty of the q-th root problem. They showed that it is provably secure against man-in-the-middle attacks. In this paper we show that the protocol is insecure against an unknown key-share attack and does not achieve forward secrecy.

Differential power analysis (DPA) is an effective technique that extracts secret keys from cryptographic systems through statistical analysis of the power traces obtained during encryption and decryption operations. This letter proposes symmetric discharge logic (SDL), a circuit-level countermeasure against DPA, which exhibits uniform power traces for every clock period by maintaining a set of discharge paths independent of input values. This feature minimizes differences in power traces and improves resistance to DPA attacks. HSPICE simulations for the test circuits using 0.18 µm TSMC CMOS process parameters indicate that SDL reduces power differences by an order of magnitude, compared to the existing circuit-level technique.

Using a pair of matched square-root-raised-cosine (SRRC) filters in the transmitter and the receiver in a band-limited digital communication system can theoretically achieve zero inter-symbol interference (ISI). In reality, the ISI cannot be zero when both SRRC filters are approximately implemented because of some numerical precision problems in the design phase as well as in the implementation phase. In this paper, the author proposes an iterative method to design the coefficients of SRRC FIR filters. The required ISI of the system can be specified such that both ISI and frequency domain specifications are monitored in the design phase. Since the ISI can be specified beforehand, the tradeoff between performance and the filter length becomes possible in the proposed design algorithm.

As hardware platforms increase in computation capability, multiple filter coefficient adaptations between two neighboring input signals can be realized to achieve a high convergence rate. This study explores the data-reusing scheme based on the Normalized Least Mean Squared (NLMS) algorithm. Moreover, the impacts of the reusing times and input signal vector's variance to the convergence rate and misadjustment of an adaptive filter are theoretically derived and analyzed. A large number of reusing times was found to raise the convergence rate but also increase misadjustament, while a high variance of an input vector was found to lower misadjustment and expedite the convergence rate. To reduce computational complexity of the data-reusing scheme, this study develops the Fast Data-Reusing NLMS (FDRNLMS) algorithm. The proposed FDRNLMS requires minimal computation for the adaptation scaling factor, and only requires two more multiplication operations than NLMS in calculating each filter output. Additionally, the computation complexity of this FDRNLMS is independent of the number of reusing times. Therefore, the FDRNLMS proposed herein is superior to the NLMS and Least Mean Squared (LMS) algorithms using conventional data-reusing schemes which have computation complexity proportional to the number of reusing times.

We propose a new method of logic synthesis for dual-rail RSFQ (rapid single-flux-quantum) digital circuits. RSFQ circuit technology is one of the strongest candidates for the next generation technology of digital circuits. For representing logic functions, we use a root-shared binary decision diagram (RSBDD) which is a directed acyclic graph constructed from binary decision diagrams. In the method, first we construct an RSBDD from given logic functions, and then reduce the number of nodes in the constructed RSBDD by variable re-ordering. Finally, we synthesize a dual-rail RSFQ circuit from the reduced RSBDD. We have implemented the method and have synthesized benchmark circuits. We have synthesized dual-rail circuits that consist of about 27% fewer logic elements than those synthesized by a Transduction-based method on average.

The voltage island style has been widely accepted as an effective way to design low power high performance chips. This paper proposes an automated voltage island generation flow in standard cell based designs. Two important objectives in voltage island designs are addressed in this flow: 1) reducing power dissipation under given performance constraints; 2) reducing implementation overheads, mainly layout overheads caused by cell clustering to form islands. The first objective is handled with timing and power driven netweighting and timing analysis in voltage assignment. For the second objective, we propose layout aware voltage assignment, i.e., voltage assignment during placement. We iteratively perform the following to adjustments: adjustment on voltage assignment to facilitate voltage island generation, and adjustment on cell locations to cluster cells in voltage islands. These iterations lead to a flow featured with tightly integrated voltage assignment and cell placement. Experimental results have demonstrated the advantages of our approach.

This paper introduces a new graph problem to find an Optimal Euler Circuit (OEC) in an Euler graph. OEC is defined as the Euler circuit that maximizes the sum of contiguous costs along it, where the contiguous cost is assigned for each of the two contiguous edges incident to a vertex. We prove that the OEC problem is NP-complete. A polynomial time algorithm will be presented for the case of a graph without vertex of degree greater than 4, and for the general case, a 1/4-approximation polynomial time algorithm will be proposed.

Sequences with good correlation properties are widely used in engineering applications, especially in the area of communications. Among the known sequences, cyclotomic families have the optimal autocorrelation property. In this paper, we decide the cross-correlation function of the known cyclotomic sequences completely. Moreover, to get our results, the relations between the multiplier group and the decimations of the characteristic sequence are also established for an arbitrary difference set.

In this paper, we present a modified genetic algorithm for solving combinatorial optimization problems. The modified genetic algorithm in which crossover and mutation are performed conditionally instead of probabilistically has higher global and local search ability and is more easily applied to a problem than the conventional genetic algorithms. Three optimization problems are used to test the performances of the modified genetic algorithm. Experimental studies show that the modified genetic algorithm produces better results over the conventional one and other methods.

Recently, Choi et al. proposed an ID-based authenticated group key agreement with bilinear maps. Subsequently, Zhang and Chen showed that the protocol does not provide authenticity as claimed by replaying transcripts of the past session. To prevent those replay attacks, they suggest adding a time parameter to the message being signed. However, despite of such a modification, we show that the protocol is still insecure against insider colluding attacks without replaying transcripts of the past session.

A remote user authentication scheme is a two-party protocol whereby an authentication server in a distributed system confirms the identity of a remote individual logging on to the server over an untrusted, open network. Recently, Lee et al. have proposed an efficient nonce-based scheme for remote user authentication using smart cards. This work reviews Lee et al.'s authentication scheme and provides a security analysis on the scheme. Our analysis shows that Lee et al.'s scheme does not achieve its basic aim of authenticating remote users and furthermore has a very hazardous method for changing passwords. In addition, we recommend some changes to the scheme so that it can attain at least its main security goal.

In this paper, we will show that the status certificate-based encryption scheme proposed by Yum and Lee is insecure against key substitution attacks by two types of attackers.

The letter describes a phase perturbation attack to the Discrete Fourier Transform (DFT) and Phase Shift Keying (PSK) based watermarking scheme which is proposed in [3]. In that paper the watermark information is embedded in the phase of the DFT coefficients. But this kind of PSK based watermarking scheme is very vulnerable to the phase perturbation attack, when some noise is added on the phase of the DFT coefficients, the watermark can't be correctly extracted anymore, while the quality degradation of the attacked watermarked image is visually acceptable.