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.

The baby-step giant-step algorithm, BSGS for short, was proposed by Shanks in order to compute the class number of an imaginary quadratic field. This algorithm is at present known as a very useful tool for computing with respect to finite groups such as the discrete logarithms and counting the number of the elements. Especially, the BSGS is normally made use of counting the rational points on the Jacobian of a hyperelliptic curve over a finite field. Indeed, research on the practical improvement of the BSGS has recently received a lot of attention from a cryptographic viewpoint. In this paper, we explicitly analyze the modified BSGS, which is for non-uniform distributions of the group order, proposed by Blackburn and Teske. More precisely, we refine the Blackburn-Teske algorithm, and also propose a criterion for the decision of the effectiveness of their algorithm; namely, our proposed criterion explicitly shows that what distribution is needed in order that their proposed algorithm is faster than the original BSGS. That is, we for the first time present a necessary and sufficient condition under which the modified BSGS is effective.

In this paper, we describe a technique for optimizing the algebraic method that is applied to higher order differential attack. The higher order differential attack is a well-known attack on block ciphers, in which we derive an attack equation to determine a round key from a property of a higher order differential of a target block cipher. The algebraic method is a linearization of the attack equation and determines the true key by a method such as Gaussian elimination. Our technique is based on linear dependency and can reduce the complexity of that method. We also describe a technique that allows the algebraic method to be used as an attack equation that holds probabilistically. We demonstrate this method by attacking a five-round MISTY1 and show that it needs 2^21.6 chosen plaintexts and 2^28.0 encryption times. The computer simulation took about two minutes to complete.

In this paper, we give a theoretical analysis of χ² attack proposed by Knudsen and Meier on the RC6 block cipher. To this end, we propose a method of security evaluation against χ² attack precisely including key dependency by introducing a method "Transition Matrix Computing." Previously, no theoretical security evaluation against χ² attack was known, it has been done by computer experiments. We should note that it is the first result concerning the way of security evaluation against χ² attack is shown theoretically.

We present a new keystream generator (KSG) MUGI, which is a variant of P_ANAMA proposed at FSE '98. MUGI has a 128-bit secret key and a 128-bit initial vector as parameters and generates a 64-bit string per round. The design is particularly suited for efficient hardware implementations, but the software performance of MUGI is excellent as well. A speed optimized implementation in hardware achieves about 3 Gbps with 26 Kgates, which is several times faster than AES. On the other hand, the security of MUGI has been evaluated by analyzing the applicability of re-synchronization attacks, related-key attacks, and attacks that exploit the linear correlation of an output sequence. Our analysis confirms that MUGI is a secure KSG.

In this paper, we propose TMAC. TMAC is a refinement of XCBC such that it requires only two keys while XCBC requires three keys. More precisely, TMAC requires only (k + n)-bit keys while XCBC requires (k + 2n)-bit keys, where k is the key length of the underlying block cipher E and n is its block length. We achieve this by using a universal hash function and the cost is almost negligible. Similar to XCBC, the domain is {0,1}^* and it requires no extra invocation of E even if the size of the message is a multiple of n.

This paper shows an improvement of square hash function family proposed by Etzel et al. In the new variants, the size of keys is much shorter while the collision probability is slightly larger. Most of the main techniques used to optimize the original square hash functions work on our variants as well. The proposed algorithms are applicable to fast and secure message authentication.

It is known that a super-pseudorandom permutation on 2n bits can be obtained from a random function f on n bits and two bi-symmetric and AXU hash functions h₁ and h₂ on n bits. It has a Feistel type structure which is usually denoted by φ(h₁,f, f, h₂). Bi-symmetric and AXU hash functions h₁,h₂ are much weaker primitives than a random function f and they can be computed much faster than random functions. This paper shows that we can further weaken the condition on h₁.

In this paper, we study variants of the parallel hash function construction of Damgård. We first show an improvement such that the number of processors is almost a half if |M|=(2^s + 1)n for some s, where M is the message to be hashed. We next show that there exists a variant of our parallel hash construction such that it is secure even if the underlying compression function is not necessarily collision-free nor one-way. The cost is that some constant times more processors are required.

The side channel attack (SCA) is a serious attack on wearable devices that have scarce computational resources. Cryptographic algorithms on them should be efficient using small memory--we have to make efforts to optimize the trade-off between efficiency and memory. In this paper we present efficient SCA-resistant scalar multiplications based on window method. Moller proposed an SPA-resistant window method based on 2^w-ary window method, which replaces w-consecutive zeros to 1 plus w-consecutive and it requires 2^w points of table (or 2^w-1 + 1 points if the signed 2^w-ary is used). The most efficient window method with small memory is the width-w NAF, which requires 2^w-2 points of table. In this paper we convert the width-w NAF to an SPA-resistant addition chain. Indeed we generate a scalar sequence with the fixed pattern, e.g. |00x|00x||00x|, where x is positive odd points < 2^w. Thus the size of the table is 2^w-1, which is optimal in the construction of the SPA-resistant chain based on width-w NAF. The table sizes of the proposed scheme are 6% to 50% smaller than those of Moller's scheme for w = 2,3,4,5, which are relevant choices in the sense of efficiency for 160-bit ECC.

The Single Instruction, Multiple Data (SIMD) architecture enables computation in parallel on a single processor. The SIMD operations are implemented on some processors such as Pentium 3/4, Athlon, SPARC, or even on smart cards. This paper proposes efficient algorithms for assembling an elliptic curve addition (ECADD), doubling (ECDBL), and k-iterated ECDBL (k-ECDBL) with SIMD operations. We optimize the number of auxiliary variables and the order of basic field operations used for these addition formulas. If an addition chain has k-bit zero run, we can replace k-time ECDBLs to the proposed faster k-ECDBL and the total efficiency of the scalar multiplication can be improved. Using the singed binary chain, we can compute a scalar multiplication about 10% faster than the previously fastest algorithm proposed by Aoki et al. Combined with the sliding window method or the width-w NAF window method, we also achieve about 10% faster parallelized scalar multiplication algorithms with SIMD operations. For the implementation on smart cards, we establish two fast parallelized scalar multiplication algorithms with SIMD resistant against side channel attacks.

We propose a public-key primitive modulo p^kq based on the RSA primitive. The decryption process of the proposed scheme is faster than those of two variants of PKCS #1 version 2.1, namely the RSA cryptosystem using Chinese remainder theorem (CRT) and the Multi-Prime RSA. The message M of the proposed scheme is decrypted from M mod p^k and M mod q using the CRT, where we apply the Hensel lifting to calculate M mod p^k from M mod p that requires only quadratic complexity ((log₂p)²). Moreover, we propose a trick that avoids modular inversions used for the Hensel lifting, and thus the proposed algorithm can be computed without modular inversion. We implemented in software both the proposed scheme with 1024-bit modulus p²q and the 1024-bit Multi-Prime RSA for modulus p₁p₂p₃, where p,q,p₁,p₂,p₃ are 342 bits. The improvements of the proposed scheme over the Multi-Prime RSA are as follows: The key generation is about 49% faster, the decryption time is about 42% faster, and the total secret key size is 33% smaller.

Extensive studies have been made of the public key cryptosystems based on multivariate polynomials. However most of the proposed public key cryptosystems of rate 1.0 based on multivariate polynomials, are proved not secure. In this paper, we propose several types of new constructions of public key cryptosystems based on two classes of randomly generated simultaneous equations, namely, a class based on bijective transformation and another class based on random transformation. One of the features of the proposed cryptosystems is that the sets of random simultaneous equations significantly improve the utilization factor of the transformation. We show an example of the proposed cryptosystem whose size of the ciphertext is only 100 bits.

The new concept of ES (Encryption-Signature) schemes which realize an encryption scheme and a signature scheme with a unique padding technique and key pair, was proposed by Coron et al. They also gave a proof of PSS-ES. In this paper, first, we discuss the methodology for the construction for ES schemes by using padding techniques of encryption schemes, and propose a new ES scheme, OAEP-ES, adopting this methodology. It is proven that OAEP-ES scheme can be constructed under the assumption of the one-wayness of the encryption permutation, while the security of PSS-ES utilized as an encryption scheme is based on the partial-domain one-wayness; which is a theoretical progress since the one-wayness is more general assumption than the partial-domain one-wayness. It is shown that OAEP-ES attains tighter security than PSS-ES, which is a practical interest.

Digital signatures whose security does not rely on any unproven computational assumption have recently received considerable attention. While these unconditionally secure digital signatures provide a foundation for long term integrity and non-repudiation of data, currently known schemes generally require a far greater amount of memory space for the storage of secret and public keys than a traditional digital signature. The focus of this paper is on methods for reducing memory requirements of unconditionally secure digital signatures. A major contribution of this paper is to propose two novel unconditionally secure digital signature schemes, one called a symmetric construction and other an asymmetric construction, which require a significantly smaller amount of memory. As a specific example, with a typical parameter setting the required memory size for a user is reduced to be approximately of that in a previously known scheme. Another contribution of the paper is to show an attack on a multireceiver authentication code which was proposed by Safavi-Naini and Wang. A simple method to fix the problem of the multireceiver authentication code is also proposed.

This paper addresses how to use public-keys of several different signature schemes to generate 1-out-of-n signatures. Previously known constructions are for either RSA-type keys only or DL-type keys only. We present a widely applicable method to construct a 1-out-of-n signature scheme that allows mixture use of different flavors of keys at the same time. The resulting scheme is more efficient than previous schemes even if it is used only with a single type of keys. With all DL-type keys, it yields shorter signatures than the ones of the previously known scheme based on the witness indistinguishable proofs by Cramer, et al. With all RSA-type keys, it reduces both computational and storage costs compared to that of the Ring signatures by Rivest, et al.

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.

Many oblivious transfer (OT) protocols have been proposed, however, most of them the security is assured in the random oracle model. Naor and Pinkas proposed 1-out-of-n OT which does not need random oracles. In this paper, we extend the 1-out-of-n OT to k-out-of-n OT protocol. Our protocol is efficient in the sense of both communication complexity and computation complexity.

This paper proposes a new concept of Interaction key. An interaction key is a group public key that corresponds to a shared key shared by multiple users, and it has a new feature that an interaction key generator can verify the following: the shared key has been generated now, and the shared key has not existed before. In other words, the multiple users can prove them to the key generator. This feature is different from Time-stamp technology proves that a message existed at a point in time. Here, the key generator is a third party that can observe communications of the multiple users. Present technology only allows a group member or a privileged entity to generate a group public key. We are not presently aware of a technology where a third party can generate the group public key as above. The interaction key technology is useful both for generating public key certificates and for message certification. In a certificate generation, a certificate authority can issue a public key certificate with the shared key (i.e. secret key) to be used by the multiple users. In a message certification, the users can prove the signed message has not existed before, since the message is signed by the shared key corresponds to the interaction key.

Secure distribution of digital goods is now a significantly important issue for protecting publishers' copyrights. In this paper, we study a useful primitive for constructing a secure and efficient digital rights management system (DRM) where a server which encrypts digital content and one which issues the corresponding decryption key works independently, and existing schemes lack this property. We first argue the desired property necessary of an encryption scheme for constructing an efficient DRM, and formally define an encryption scheme as split encryption scheme containing such property. Also, we show that an efficient split encryption scheme can be constructed from any identity-based scheme. More precisely, we show an equivalence result implying that a split encryption scheme for some system parameter setting and an identity-based encryption scheme have the same primitives but for different uses. Since currently there is no identity-based encryption scheme which is based on well-known computational assumption and/or provably secure in the standard model (i.e. without the random oracle model), by reasonably tuning the system parameter, we show another construction of split encryption which is secure against chosen ciphertext attacks in the standard model assuming that decision Diffie-Hellman problem is hard to solve.

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 ); previous protocols require O(N ) or O(N log ) where the number of bidders is N and that of available bidding prices is . Namely, the number of auctioneers' operations in our auction protocol is independent of the number of bidders. This feature offers strong advantages in massive auctions. We also propose a new scheme that checks the equality of two values without disclosing them. The scheme enhances our basic auction protocol, in terms of security and communication costs.

Linking schemes have been proposed assuming the model where the time-stamp issuer need not be trusted. However, in that environment, a fake chain attack and forward or backward dating attacks are still a residual risk in Time-Stamping services (TSS). In this paper, we propose a new time-stamping scheme that focuses on these problems. In our scheme, we use pseudonyms to prevent the time-stamp issuer from dating the time that the specific entity requests. Our scheme doesn't rely on only one trustworthy entity, and uses mutual communication between each entity. Two types of entities, server and clients without any trustworthy entities are configured in our system. The server provides an anonymous communication channel, but doesn't provide TSS, and the clients are not only time-stamp requesters but also issuers. So, when a client requests a time-stamp from the system, it is issued by one of the other clients.

The safety problem in access matrix models determines whether a given subject can eventually obtain access privilege to a given object. Generally speaking, the safety problem is, unfortunately undecidable. Not much is known about protection systems for which the safety problem is decidable, except for strongly constrained systems (e.g., monotonic systems). Therefore, we propose the Dynamic-Typed Access Matrix (DTAM) Model, which extends the Typed Access Matrix model of Sandhu by allowing the type of an object to change dynamically. The DTAM model has an advantage that it can describe non-monotonic protection systems for which the safety problem is decidable. In particular, with further restrictions, we can show that the problem becomes NP-hard. In this paper, we formally define the DTAM model and then discuss various aspects of it thoroughly.

When two parties connect via a possibly unreliable network, ensuring fairness becomes a serious problem. To solve this problem, a lot of Certified E-mail systems are proposed. However, user's privacy including confidentiality and anonymity is not considered in almost all of these systems. In this paper, we propose two private message board systems using an electronic notice board to solve Certified mail problem.

There are two main types of digital watermark systems. In the first, users are given their own detection programs by which to verify the presence of watermark in data they have in their possession. In the second, users must request such verification from a detection center. The disadvantage of the first type is the possibility that a user might be able to analyze the detection program sufficiently to be able to obtain the secret data (secret key) used to embed the watermark. The disadvantage of the second is the possibility that a center might give dishonest results. In this paper, we propose a watermark detection scheme that can be used to overcome the disadvantages of both: it prevents users from obtaining secret key, and it prevents a center from reporting dishonest results. Our scheme is based on a previously proposed scheme which nearly achieved the same goals but, unfortunately, allowed users to receive watermark detection results for data specially created by them so as to reveal, through the results, secret information about how a center created its watermarks. To overcome this drawback, we have developed new scheme by which a center can prove its detection results to a user without revealing any other information. This scheme was developed by extending the work found in. Moreover we provide an option that prevents the center from encroaching on a user's privacy. The resulting watermark detection scheme is the first that, in addition to protecting secret keys of watermarks from user-tampering, is also able to prevent a center from reporting dishonest results. Although the proposed scheme is introduced first using the patch-work watermarking system, it is straightforward to extend it to a scheme that uses the correlation-based watermarking system, which yields a more robust watermark detection scheme.

In 1999, Boneh et al. proposed the Lattice Factoring Method (LFM) for the integer factoring problem for a composite of the form N = p^rq by employing the LLL-algorithm. Time complexity of LFM is measured by the number of calls of the LLL-algorithm. In the worst case, the number is 2^{log p} for a certain constant c. In 2001, Uchiyama and Kanayama introduced a novel criterion and provided an improved algorithm which runs (2^k-p)/|p-N_r+1| times faster (for certain constants k, N_r+1). In this letter, we note another practical improvement applicable to the original and the improved LFM, which enables to provide about 2 times speed-up.

Davidson's scheme utilizes the order of basic blocks to embed a digital signature in a computer program. To preserve the function of the original program, additional jump instructions are inserted. This involves some overhead in both size and performance. In our implementation, the increase in size was between 9% and 24%. The performance of benchmark programs was 86-102% of the original.

Recently, Camenisch et al. and Fischlin proposed provably secure signature schemes in the standard models respectively. In this letter, we propose key substitution attacks on these two signature schemes. We show that an adversary can generate a valid public key corresponding to a legitimate signature.

Distributed signcryption is specifically designed for distributing a signcrypted message to a designated group. As such, it can not be used in anonymous communication. Accordingly, the current study adds an anonymity property to distributed signcryption that results in almost the same computational load as regards the modular arithmetic. Therefore, the new scheme is more efficient than the expansion for anonymity in, and has potential applications in electronic commerce.

In this paper, a novel methodology for designing and analyzing high performance sigma-delta leapfrog modulators for ultra-high resolution analog-to-digital (A/D) converters is presented. The less sensitive topology, the leapfrog topology, in component variations is analyzed by considering the noise transfer function (NTF). By using theoretical analysis, the loop coefficients are constrained to a small, clear and definite range called the stable region (SR). With the output voltage limited within 2 V, an absolutely stable region (ASR) is obtained. A program that analyzes and generates the required coefficients is constructed for easily designing this topology. For a 256 over-sampling ratio (OSR) and the coefficients from ASR, the signal to noise ratio (SNR) and dynamic range (DR) are 105 dB and 100 dB, respectively. In accordance with the behavior simulation results, the system is not only stable and efficient but also suitable for high-resolution applications.

A new robust extended Kalman filter is proposed for the discrete-time nonlinear systems with norm-bounded parameter uncertainties. After linearization of the nonlinear systems, the uncertainties described by the energy bounded constraint can be converted into an indefinite quadratic cost function to be minimized. The solution to the minimization problem is given by the extended Kalman filter derived in a Krein space, which leads to a robust version of the extended Kalman filter. Since the resulting robust filter has the same structure as a standard extended Kalman filter, the proposed filter can be readily designed by simply including the uncertainty terms in its formulas. The results of simulations are presented to demonstrate that the proposed filter achieves the robustness against parameter variation and performs better than the standard extended Kalman filter.

This paper describes a sparse realization of passive reduced-order interconnect models via PRIMA to provide the SPICE compatible models. It is demonstrated that, if the SPICE models are directly realized so that the reduced-order equations obtained via PRIMA are stamped into the MNA matrix, the simulations of networks containing the macromodels become computationally inefficient when size of the reduced-order equations is relatively large. This is due to dense coefficient matrices of the reduced-order equations resulting from congruent transformations in PRIMA. To overcome this disadvantage, we propose a sparse realization of the reduced-order models. Since the expression is equivalent to the reduced-order equations, the passivity of the SPICE models generated is also guaranteed. Computational efficiency on SPICE is demonstrated in performing the transient analysis of circuits containing the proposed macromodels.

In this paper, a fragment-processing solution in 3D graphics rendering algorithms based on fragment lists (i.e. A-buffer) for minimizing loss of image quality is described. While all fragment information should be preserved for exact hidden surface removal, this places additional strain on hardware in terms of silicon gates and clock cycles. Therefore, we propose a fragment processing technique that can effectively merge fragments in order to decrease the depth of fragment lists. It renders scenes quite accurately even in the case when three fragments intersect each other. This algorithm improves hardware acceleration without deteriorating image quality.

The processing of noise-corrupted signals is a common problem in signal processing applications. In most of the cases, it is assumed that the additive noise is white Gaussian and that the constant noise variance is either available or can be easily measured. However, this may not be the case in practical situations. We present a new approach to additive white Gaussian noise variance estimation. The observations are assumed to be from an autoregressive process. The method presented here is iterative, and uses low-order Yule-Walker equations (LOYWEs). The noise variance is obtained by minimizing the difference in the second norms of the noisy Yule-Walker solution and the estimated noise-free Yule-Walker solution. The noise-free solution is constrained to match the observed autocorrelation sequence. In the iterative noise variance estimation method, a variable step-size update scheme for the noise variance parameter is utilized. Simulation results are given to confirm the effectiveness of the proposed method.

Discrete wavelet transform has been successfully used in many image processing applications. In this paper, we present an efficient VLSI architecture for 2-D 3-level lifting-based discrete wavelet transform using the (5, 3) filter. All three-level coefficients are computed interlacingly and periodically to achieve higher hardware utilization and better throughput. In comparison with other VLSI architectures, our architecture requires less size of storage and faster computation speed.

An efficient scheme is proposed which achieves the oblivious transfer with probabilistic receipt, α-OT, approximately for 0 < α < 1. The proposed scheme approximates α-OT with 2^-i-OT for i = 1,2,...,k. It implements γ-OT for some γ such that (α - 2^-k) / (1 - 2^-k) < γ α with - log (1 - α) invocations of 2^-1-OT and at most 2 invocations of 2^-i-OT for each i = 2,...,k. These invocations can be executed in parallel.

This paper presents a novel digital image watermarking algorithm based on the labeled bisecting clustering technique. Each cluster is labeled either '0' or '1' based on the labeling key. Each input image block is then assigned to the nearest codeword or cluster centre whose label is equal to the watermark bit. The watermark extraction can be performed blindly. The proposed method is robust to JPEG compression and some spatial-domain processing operations. Simulation results demonstrate the effectiveness of the proposed algorithm.

The present paper introduces a new construction of a class of binary sequence set having a zero-correlation zone (hereafter binary _zcz sequence set). The cross-correlation function and the side-lobe of the auto-correlation function of the proposed sequence set is zero for the phase shifts within the zero-correlation zone. This paper shows that such a construction generates a binary _zcz sequence set from an arbitrary pair of Hadamard matrices of common size. Since the proposed sequence construction generates a sequence set from an arbitrary pair of Hadamard matrices, many more types of sequence sets can be generated by the proposed sequence construction than is possible by a sequence construction that generates sequence sets from a single arbitrary Hadamard matrix.