Designing a protocol to exchange a secret key is one of the most fundamental subjects in cryptography. Using a random deal of cards, pairs of card players (agents) can share secret keys that are information-theoretically secure against an eavesdropper. A key set protocol, which uses a random deal of cards, can perform an Eulerian secret key exchange, in which the pairs of players sharing secret keys form an Eulerian circuit passing through all players. Along the Eulerian circuit any designated player can send a message to the rest of players and the message can be finally sent back to the sender. Checking the returned message with the original one, the sender can know whether the message circulation has not been influenced by a possible single transmission error or false alteration. It has been known that any Eulerian circuit formed by the protocol has length at most 3/2k, where k is the number of players. Note that the length corresponds to the time required to send the message to all players and acknowledge the secure receipt. In this paper, we show that the average length of Eulerian circuits is approximately k+ln k.

This paper presents a non-interactive and optimally resilient distributed multiplication scheme. By non-interactive we mean that the players need to use outgoing communication channels only once without the need to synchronize with the other players as long as no disruption occurs. Our protocol withstands corrupt players up to less than the half of the players, so it provides optimal resiliency. Furthermore, the shared secrets are secure even against infinitely powerful adversaries. The security is proven under the intractability assumption of the discrete logarithm problem. Those properties are achieved by using an information theoretically secure non-interactive verifiable secret sharing as a kind of non-interactive proof system between a single prover and distributed verifiers. Compared to a former interactive solution in the same setting, the cost is an increase in local computation and communication complexity that is determined by the factor of the threshold used in the verifiable secret sharing.

In this paper, we propose a new secure server-aided RSA secret computation protocol which guards against not only the attacks in [1],[2],[15],[18] but also the new powerful active attacks in [3],[4]. The new protocol is also efficient to support high security level.

The use of Internet for various business applications and resource sharing has grown tremendously over the last few years. Internet security has become an important issue for both academic and industrial sectors. Much related network security research has been conducted such as user authentication, data confidentiality, and data integrity. In some applications, a critical document can be divided into pieces and allocated in different locations over the Internet for security access concern. To access such an important document, one must reconstruct the divided pieces from different locations under the given Internet environment. In this paper, a probability model for reconstructing secret sharing and algorithms to perform share assignment are presented. Also, an evaluation algorithm to measure the probability of secret sharing reconstruction is proposed. Illustrative examples and simulation results are provided to demonstrate the applicability of our method.

In the visual secret sharing scheme proposed by Naor and Shamir, a secret image is encoded into shares, of which size is larger than that of the secret image and the shares are decoded by stacking them without performing any cryptographic computation. In this paper we propose a (k,n) visual secret sharing scheme to encode a black-and-white image into the same size shares as the secret image, where the reconstructed image of the proposed scheme is visible as well as that of the conventional scheme.

Although threshold key-recovery systems for the discrete log based cryptosystems such as the ElGamal scheme have been proposed by Feldman and Pedersen , no (practical) threshold key-recovery system for the factoring based cryptosystems such as the RSA scheme has been proposed. This paper proposes the first (practical) threshold key-recovery systems for the factoring based cryptosystems including the RSA and Rabin schemes. Almost all of the proposed systems are unconditionally secure, since the systems utilize unconditionally secure bit-commitment protocols and unconditionally secure VSS.

CEFLAR is one way of realizing ATM-ABR with no cell loss. This paper shows that the transition characteristics of CEFLAR(transition time to achieve fair share), important when addressing network fairness, strongly depend on the acceleration-ratio coefficient, not the rate decrease factor or the distance between source and congestion estimation nodes. This paper also shows that the average throughput of a transmission line in transition degrades as the rate decrease factor decreases and as the distance between the source and congestion estimation nodes increases.

In this paper, we propose a new conference key distribution scheme and the supervision of a conference when users are in a level-based hierarchy. In a conference key distribution system, one message is transmitted to the participants from a chairman, a legitimate member can decrypt it and reveal the common session key. The proposed scheme can be implemented without using any tamper-proof hardware. For users in a level-based hierarchy, by applying the key distribution scheme, the higher priority users can derive the conference key and supervise the lower level users' communications. Further, the users in the same level who are not members of the conference or in lower levels can not expose the conference key. To break the common session key, a malicious user has to suffer from the difficulty of factorization and discrete logarithm problems.

Secret sharing schemes are good for protecting the important secrets. They are, however, inefficient if the secret shadow held by the shadowholder cannot be reused after recovering the shared secret. Traditionally, the (t, n) secret sharing scheme can be used only once, where t is the threshold value and n is the number of participants. To improve the efficiency, we propose an efficient dynamic secret sharing scheme. In the new scheme, each shadowholder holds a secret key and the corresponding public key. The secret shadow is constructed from the secret key in our scheme, while in previously proposed secret sharing schemes the secret key is the shadow. In addition, the shadow is not constructed by the shadowholder unless it is necessary, and no secure delivery channel is needed. Morever, this paper will further discuss how to change the shared secret, the threshold policy and cheater detection. Therefore, this scheme provides an efficient way to maintain important secrets.

The visual secret sharing scheme (VSSS) proposed by Naor and Shamir provides a way to encrypt a secret black-white image into shares and decrypt the shares without using any cryptographic computation. This paper proposes an extension of VSSS to sharing of color or gray-scale images. In this paper (k,n) VSSS for images with J different colors is defined as a collection of J disjoint subsets in n-th product of a finite lattice. The subsets can be sequentially constructed as a solution of a certain simultaneous linear equation. In particular, the subsets are simply expressed in (n,n), (n-1,n) and (2,n) cases. Any collections of k-1 shares reveal no information on a secret image while stacking of k arbitrary shares reproduces the secret image.

Let T1, , Tn be n spanning trees rooted at node r of graph G. If for any node v, n paths from r to v, each path in each spanning tree of T1, , Tn, are internally disjoint, then T1, , Tn are said to be independent spanning trees rooted at r. A graph G is called an n-channel graph if G has n independent spanning trees rooted at each node of G. We generalize the definition of n-channel graphs. If for any node v of G, among the n paths from r to v, each path in each spanning tree of T1, , Tn, there are k internally disjoint paths, then T1, , Tn are said to be (k,n)-independent spanning trees rooted at r of G. A graph G is called a (k,n)-channel graph if G has (k,n)-independent spanning trees rooted at each node of G. We study two fault-tolerant communication tasks in (k,n)-channel graphs. The first task is reliable broadcasting. We analyze the relation between the reliability and the efficiency of broadcasting in (k,n)-channel graphs. The second task is secure message distribution such that one node called the distributor attempts to send different messages safely to different nodes. We should keep each message secret from the nodes called adversaries. We give two message distribution schemes in (k,n)-channel graphs. The first scheme uses secret sharing, and it can tolerate up to t+k-n listening adversaries for any t < n if G is a (k,n)-channel graph. The second scheme uses unverifiable secret sharing, and it can tolerate up to t+k-n disrupting adversaries for any t < n/3 if G is a (k,n)-channel graph.

This paper describes two attacks against blind decryption (decode) based on the commutative random-self reducibility and RSA systems utilizing the transformability of digital signatures proposed in [2]. The transformable digital signature was introduced in [2],[8] for defeating an oracle attack, where the decrypter could be abused as an oracle to release useful information for an attacker acting as a requester of blind decryption. It was believed in [2],[8] that the correctness of a query to an oracle was ensured by the transformable signature derived from an original signature issued by the decrypter in advance, and a malicious query to an oracle could be detected before the blind decryption by the decrypter or would lead to release no useful information to an attacker. The first attack can decrypt all encrypted data with one access to an oracle. The second one generates a valid signature for an arbitrary message selected by an attacker abusing the validation check procedure.

The effect of sampling-pulse pedestals, generated by pulse compression, on the temporal resolution in electro-optic (EO) sampling is studied both theoretically and experimentally. Analysis is made on how the pedestals degrade a measurement bandwidth and a temporal waveform. Based on the analysis, a practical guideline on the suppression of pedestals is also given. Gain-switched laser diode (LD) pulses adiabatically soliton-compressed using a dispersion decreasing fiber are used to confirm the theoretical results, and are successfully applied to high-temporal-resolution (>100 GHz) EO sampling measurements.

Recently, two new efficient server-aided RSA secret computation protocols were proposed. They are efficient and can guard against some active attacks. In this letter, we propose two multi-round active attacks which can effectively reduce their security level even break them.

In this paper, we propose a practical and secure electronic voting scheme which meets the requirements of large scale general elections. This scheme involves voters, the administrator or so called the government and some scrutineers. In our scheme, a voter only has to communicate with the administrator three times and it ensures independence among voters without the need of any global computation. This scheme uses the threshold cryptosystem to guarantee the fairness among the candidate's campaign and to provide mechanism for achieving the function that any voter can make an open objection to the tally if his vote has not been published. This scheme preserves the privacy of a voter against the administrator, scrutineers, and other voters. Completeness, robustness, and verifiability of the voting process are ensured and hence no one can produce a false tally, corrupt or disrupt the election.

In this paper a new type of public-key cryptosystem, proxy cryptosystem, is studied. The proxy cryptosystem allows an original decryptor to transform its ciphertext to a ciphertext for a designated decryptor, proxy decryptor. Once the ciphertext transformation is executed, the proxy decryptor can compute a plaintext in place of the original decryptor. Such a cryptosystem is very useful when an entity has to deal with large amount of decrypting operation. The entity can actually speed-up the decrypting operation by authorizing multiple proxy decyptors. Concrete proxy cryptosystems are constructed for the ElGamal cryptosystem and the RSA cryptosystem. A straightforward construction of the proxy cryptosystem is given as follows. The original decryptor decrypts its ciphertext and re-encrypts an obtained plaintext under a designated proxy decryptor's public key. Then the designated proxy decryptor can read the plaintext. Our constructions are more efficient than such consecutive execution of decryption and re-encryption. Especially, the computational work done by the original decryptor is reduced in the proxy cryptosystems.

Lower bounds on the size of shares |Vi| which are more tight than |Vi>| |S| is the size of the secret, are known only for some graphical access structures. This paper shows lower bounds on |Vi| greater than |S| for some non-graphical access structures Γ. We first prove that if {P1, Pi} Γ-for any Pi P^ = {P2, , Pn} and Γ ^= 2P^ Γ is the access structure of a (k, n-1) -threshold scheme on P^, thenmaxilog|Vi>| n+k-3/n-1 log|S|for Pi {P1, P2, , Pn}. Next, we show that maxilog |Vi| 1.5log |S| holds for a wider class of access structures.

Weakness of a block cipher, which has provable immunity against linear cryptanalysis, is investigated. To this end, the round transformation used in MISTY, which is a data encryption algorithm recently proposed by M. Matsui from Mitsubishi Electric Corporation, is compared to the round transformation of DES from the point of view of pseudrandom generation. An important property of the MISTY cipher is that, in terms of theoretically provable resistance against linear and differential cryptanalysis, which are the most powerful cryptanalytic attacks known to date, it is more robust than the Data Encryption Standard or DES. This property can be attributed to the application of a new round transform in the MISTY cipher, which is obtained by changing the location of the basic round-function in a transform used in DES. Cryptograohic roles of the transform used in the MISTY cipher are the main focus of this paper. Our research reveals that when used for constructiong pseudorandom permutations, the transform employed by the MISTY cipher is inferior to the transform in DES, though the former is superior to the latter in terms of strength against linear and differential attacks. More specifically, we show that a 3-round (4-round, respectively) concatenation of transforms used in the MISTY cipher is not a pseudorandom (super pseudorandom, respectively) permutation.

This paper describes some dynamical properties of higher order neural networks with decreasing energy functions. First, we will show that for any symmetric higher order neural network which permits only one element to transit at each step, there are only periodic sequences with the length 1. Further, it will be shown that for any higher order neural network, with decreasing energy functions, which permits all elements to transit at each step, there does not exist any periodic sequence with the length being over k + 1, where k is the order of the network. Lastly, we will give a characterization for higher order neural networks, with the order 2 and a decreasing energy function each, which permit plural elements to transit at each step and have periodic sequences only with the lengh 1.

For the dependent protocols to perform the server-aided RSA secret computation, the damage caused by the active attacks is greater than that by the passive attacks. Though there are two dependent proposed protocols against active attacks, the cost of the two protocols is still high. In this paper, we propose two efficient dependent protocols. Even considering the low cost of these two protocols, they can also guard against the proposed active attacks.