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.

Server-aided secret computation (SASC) protocols were proposed as methods to allow a not-so-powerful computer (a client) to compute a function efficiently with the aid of a powerful computer (a server) without revealing the client's secret to the server. A smart card system is considered to be the most promising application for SASC protocols. Matsumoto et al. proposed a class of protocols, called S2, which is suitable for RSA secret computation. It includes many variations, such as binary S2, non-binary S2, and KS schemes. Although it is expected that the non-binary S2 will be the most efficient scheme, performances for these protocols have not been fully analyzed, except for the KS scheme. This paper discusses how to determine appropriate parameters for non-binary S2. Performance was generally analyzed by using normalized variables. It is shown that a client can compute a signature 50 times faster, with a 105 times more powerful server's aid, than in the case without a server, provided that communication cost can be ignored. The SASC protocol performance is also discussed under the practical condition that a server is an 8-bit CPU and that the communication rate is 9.6 kbps. The client can sign a message in about 10 seconds, with the aid of a 32-bit CPU. This analysis coincides well with the experimental result. It is estimated that a client with a 16-bit CPU will accomplish a less that 2 second processing time with a 4.6 kbps server.

This paper proposes a new algorithm to achieve about two-times speedup of modular exponentiation which is implemented by Montgomery multiplication based on Residue Number Systems (RNS). In RNS Montgomery multiplication, its performance is determined by two base transformations dominantly. For the purpose of realizing parallel processing of these base transformations, i. e. "duplicate processing," we present two procedures of RNS Montgomery multiplication, in which RNS bases a and b are interchanged, and perform them alternately in modular exponentiation iteration. In an investigation of implementation, 1.87-times speedup has been obtained for 1024-bit modular multiplication. The proposed RNS Montgomery multiplication algorithm has an advantage in achieving the performance corresponding to that the upper limit of the number of parallel processing units is doubled.

This paper describes a novel shared file system, whose main features are enhanced security and its concurrency control mechanism. The system is especially suitable for access from mobile hosts. Users can edit their shared files concurrently. Shared files are encrypted and decrypted only by clients, and the file server cannot know the contents. The server asynchronously receives the edited parts, which are already encrypted, and merges them into the current version, deciphering neither the stored file nor the encrypted editing data. We call the mechanism 'privacy enhanced merging'. The mechanism and the underlying encryption algorithm, shared file data structure and procedures followed by clients and the server are shown.

We first model the formal security model of multisignature scheme following that of group signature scheme. Second, we prove that the following three probabilistic multisignature schemes based on a trapdoor permutation have tight security; PFDH (probabilistic full domain hash) based multisignature scheme (PFDH-MSS), PSS (probabilistic signature scheme) based multisignature scheme (PSS-MSS), and short signature PSS based multisignature scheme (S-PSS-MSS). Third, we give an optimal proof (general result) for multisignature schemes, which derives the lower bound for the length of random salt. We also estimate the upper bound for the length in each scheme and derive the optimal length of a random salt. Two of the schemes are promising in terms of security tightness and optimal signature length. In appendix, we describe a multisignature scheme using the claw-free permutation and discuss its security.

At CHES 2000, Schindler introduced a timing attack that enables the factorization of an RSA-modulus if RSA implementations use the Chinese Remainder Theorem and Montgomery multiplication. In this paper we introduce another approach for deriving the secret prime factor by focusing on the conditional branch Schindler used in his attack. One of the countermeasures against Schindler's attack is the blinding method. If input data are blinded with a fixed value or short-period random numbers, Schindler's attack does not work but our method can still factorize the RSA-modulus.

Most number-theoretic cryptosystems are constructed based on a modular exponentiation, which requires a large number of processing steps. Therefore, one of the most significant problems in cryptographic research is how to reduce the time needed to carry out a modular exponentiation operation. This paper proposes an improved modular exponentiation algorithm using a new table-look-up method. On executing a modular exponentiation computation, first, it must be decomposed efficiently into a series of modular multiplications. For this decomposition, the Binary method is used in this paper. When the Binary method is so implemented as to process the exponent in the-most-significant-bit-first manner, multiplier M, as well as modulus N, can also be considered as a common constant in 1/3 of the decomposed modular multiplications. Thus, with some additional procedure, one can compute beforehand the residues concerning M and N. This makes it possible to process the multiplication and reduction simultaneously. This algorithm is faster than conventional ones which take into account only that the modulus N can be considered a constant. The effectiveness of the proposed method is investigated with an evaluation model proposed in this paper and evaluated by software implemented on a engineering workstation and on a digital signal processor. The evaluation model indicates that the proposed method reduces the execution time by 17% compared with a conventional table-look-up method, if bit length k of modulus N is sufficiently large. The corresponding figure in the computer simulation is 14% for k=512.