This paper presents some new protocols for (M+1)st-price auction, a style of auction in which the highest M bidders win and pay a uniform price, determined by the (M+1)st price. A set of distributed servers collaborates to resolve the (M+1)st price without revealing any information in terms of bids including the winners' bids. A new trick to jointly and securely compute the highest value as a degree of distributed polynomials is introduced. The building block requires just one round for bidders to cast bids and one round for auctioneers to determine the winners.

Suppose that there are players in two hierarchical groups and a computationally unlimited eavesdropper. Using a random deal of cards, a player in the higher group wishes to send a one-bit message information-theoretically securely either to all the players in her group or to all the players in the two groups. This can be done by the so-called 2-level key set protocol. In this paper we give a necessary and sufficient condition for the 2-level key set protocol to succeed.

We describe a scheme of secret communication over the Internet utilizing the potentiality of the TCP/IP protocol suite in a non-standard way. Except for the sender and the receiver of the secret communication it does not need any entities installed with special software. Moreover it does not require them to share any key beforehand. Such features of the scheme stem from the use of IP datagrams with spoofed source addresses and their related error messages for the Internet Control Message Protocol (ICMP) induced by artificial faults. Countermeasures against IP spoofing are deployed in various places since it is often used together with attacks such as distributed denial of service (DDoS) and SPAM mailing. Thus we examine the environment where the scheme works as an intention and also clarify the conditions to obsolete the scheme. Furthermore we estimate the amount of secretly communicated data by the scheme and storage requirements for the receivers and those for the observers who monitor the traffic to detect the very existence of such a secret communication. We also discuss various issues including the sender anonymity achieved by the scheme.

In this paper, we treat visual secret sharing scheme (VSSS) for color images. We first evaluate the brightness of the decrypted color image under certain conditions on the mixture of colors. We obtain a general formula for the construction of VSSS using mixture of colors. We second propose an iterative algorithm for constructing VSSS in a practical situation. If we use the iterative construction, we have only to solve partial differential equations with small n even if n is actually large, where n denotes the number of participants. This iterative construction has never discussed in the both cases under the original images are black-white images and color images. Finally, we propose the way to embed a color image on each share for the case that the original image is color.

In many cryptographic protocols, a common-key encryption is used to provide a secure data-transmission channel. More precisely, the general idea of protocols is to have an encryption provide data authenticity as well as data confidentiality. In fact, there are known to be quite a few ways to provide both forms of security, however none of them are optimized enough to be efficient. We present a new encryption mode that uses a random number generator (RNG). Assuming the security of the RNG, we can prove not only perfect secrecy, but also message authentication. The proven probability of a successful forgery is (n-1)/(2b-1), where b is the number of bits in a block and n is the number of ciphertext blocks. The proposed scheme achieves very high practicality due to the potential advantages in efficiency. When we use a computationally secure RNG, such as instance a pseudorandom number generator PRNG, we have advantages in efficiency; in addition to the PRNG parallel computation, the scheme requires only a single-path process on the data stream so that even a limited hardware resource can operate an encryption of a very long data stream. We demonstrate the practicality of our scheme, by showing a realistic parameter set and the evaluations of its performance.

Surface passivation process of GaN utilizing electron-cyclotron-resonance (ECR) excited plasma has been characterized and optimized for realization of stable operation in GaN-based high-power/high-frequancy electronic devices. From XPS analysis, the NH4OH treatment as well as the ECR-N2 and ECR-H2 plasma treatments were found to be effective in removing natural oxide and contaminants from the GaN surface. The SiNx/GaN structure prepared by the ECR excited plasma chemical vapor deposition (ECR-CVD) process showed better C-V behavior compared to the SiO2/GaN structure. Surface treatment process using the ECR plasma improved interface properties and achieved the Dit value of 21011 cm-2 eV-1 or less. An estimate of the valence band offset by XPS showed that the present SiNx/n-GaN structure has a type-I band lineup, suitable for the surface passivation of GaN-based devices. No pronounced stress remained at the SiNx/GaN interface, which was confirmed by Raman spectroscopy.

Routing security is related to the confidentiality of the route taken by the data transmitted over the network. If the route is detected by the adversary, the probability is higher that the data are lost or the data can be intercepted by the adversary. Therefore, the route must be protected. To accomplish this, we select an intermediate node secretly and transmit the data using this intermediate node, instead of sending the data to the destination node using the shortest path. Furthermore, if we use a number of secret routes from the starting node to the destination node, data security is much stronger since we can transmit partial data rather than the entire data along a secret route. In this paper, the routing algorithm for multiple secret paths on MRNS (Mixed Radix Number System) Network, which requires O(l) for the time complexity where l is the number of links on a node, is presented employing the HCLS (Hamiltonian Circuit Latin Square) and is analyzed in terms of entropy.

We consider methods for threshold RSA decryption among distributed agencies without any dealer or trusted party. The first solution is a combination of two techniques by [9] and [7] . It demonstrates the feasibility of combining the distributed key generation and the RSA secure function application. The second solution is another approach making the distributed key distribution simpler and alleviating a burden of each shareholder in comparison with the first scheme. The latter scheme is newly developed technique based on [9] and further inspired by Simmons' protocol-failure of RSA (we believe that it is very interesting that a "protocol failure attack" be turned into a constructive method). Our comparison between these two schemes indicates a new measure of the performance of a distributed cryptographic protocol that consists of multiple stages.

We propose the problem of how to transmit an information-theoretically secure bit using random deals of cards among players in hierarchical groups and a computationally unlimited eavesdropper. A player in the highest group wants to send players in lower groups a secret bit which is secure from the eavesdropper and some other players. We formalize this problem and design protocols for constructing secret key exchange spanning trees on hierarchical groups. For each protocol we give sufficient conditions to successfully construct a secret key exchange spanning tree for the hand sizes of the players and the eavesdropper.

Kurosawa, Obana, and Ogata proposed a (k,n) threshold scheme such that t cheaters can be identified, where t (k-1)/3. Their scheme is superior to previous schemes with respect to the number of participants for identifying cheaters and the size of a share. In this paper, we improve the detectability of their scheme. By using erasure decoding and the authentication code, we show that cheaters less than k/2 can be identified. Although the size of a share is larger than that of their scheme, it is independent of n.

A secret sharing scheme allows a secret to be shared among a set of participants, P, such that only authorized subsets of P can recover the secret, but any unauthorized subset can not recover the secret. It can be used to protect important secret data, such as cryptographic keys, from being lost or destroyed without accidental or malicious exposure. In this paper, we consider secret sharing schemes based on interpolating polynomials. We show that, by simply increasing the number of shares held by each participant, there is a multiple assignment scheme for any monotone access structure such that cheating can be detected with very high probability by any honest participant even the cheaters form a coalition in order to deceive him.

This paper proposes a new construction of the visual secret sharing scheme for the (n,n)-threshold access structure applicable to color images. The construction uses matrices with n rows that can be identified with homogeneous polynomials of degree n. It is shown that, if we find a set of homogeneous polynomials of degree n satisfying a certain system of simultaneous partial differential equations, we can construct a visual secret sharing scheme for the (n,n)-threshold access structure by using the matrices corresponding to the homogeneous polynomials. The construction is easily extended to the cases of the (t,n)-threshold access structure and more general access structures.

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.

In this paper, we attempt to construct practical secret sharing schemes, which scheme has smaller share size and can detect cheating with high probability. We define two secure ramp schemes, secure ramp scheme and strongly secure ramp scheme. Then, we propose two constructions of secure ramp scheme. These schemes both have small share size and the cheating can be detected with high probability. So, they are practical secret sharing schemes.

Modern cryptology was born in the late seventies and developed in the eighties. A decade since 1991 is the period of continuation of the development and new expansion of cryptology. In this paper we survey the development of cryptologic researches in this decade with emphasis on the results in Japan. We also present some future important works and propose the foundation of a public institution for evaluation of information security techniques.

This paper describes an efficient k-out-of-n threshold digital signature scheme for a smart card based system where a signer uses multiple cards so that the signature can be issued in a dependable manner. The main feature of our method is that it does not require a secret communication path among these cards in the signature issuing protocol, and that it requires low communication and computational complexity. Former is an advantage under the current export control regulation which makes hard to export more than 56-bit cipher techniques, and latter is advantage over so-called robust signature.

As far as the knowledge of authors, the rigorous security of Okamoto-Tanaka identity-based key exchange scheme was shown in [4] for the first time since its invention. However, the analysis deals with only the passive attack. In this paper, we give several models of active attacks against the scheme and show the rigorous security of the scheme in these models. We prove several relationships among attack models, including that (1) breaking the scheme in one attack model is equivalent to breaking the RSA public-key cryptosystem and (2) breaking the scheme in another attack model is equivalent to breaking the Diffie-Hellman key exchange scheme over Zn. The difference of the complexity stems from the difference of the timing of dishonest party's sending out and receiving messages.

Based on the systematic block codes, we propose a (t,n) multi-secret sharing scheme. Compared with the previous works, our scheme has the advantages of smaller communication overhead, easy generator matrix construction and non-disclosure of users secret shares after multiple secret reconstruction operations. These advantages make the practical implementation of our scheme very attractive.

We show some numerical results of computer simulations of secret key reconciliation (SKR) protocol "Cascade" and clarify its properties. By using these properties, we propose to improve the protocol performance on the number of publicly exchanged bits which should be as few as possible.

A repeating watermarking technique based on visual secret sharing (VSS) scheme provides the watermark repeated throughout the image for avoiding the image cropping. In this paper, the watermark is divided into public watermark and secret watermark by using the VSS scheme to improve the security of the proposed watermarking technique. Unlike the traditional methods, the original watermark does not have to be embedded into the host image directly and, thus, it is hard to be detected or removed by the pirates or hackers. The retrieved watermark extracted from the watermarked image does not require the complete original image, but requires a secret watermark. Furthermore, the watermarking technique suits the watermark with an adaptive size of binary image for designing the watermarking system. The experimental results show that the proposed method can withstand the common image processing operations, such as filtering, lossy compression and the cropping attacking etc. The embedded watermark is imperceptible, and that the extracted watermark identifies clearly the owner's copyright.