We propose a new type of revocation scheme for efficient public-key black-box traitor tracing. Our revocation scheme is flexible and efficient in the sense that (i) any number of subscribers can be revoked in each distribution under an assumption that the number of revoked subscribers who collude in one coalition is limited to a threshold and (ii) both each subscriber's storage and the transmission overhead are independent of n, while (i) the maximum number of revoked ones cannot be changed or (ii) they depend on n in previous schemes, where n is the total number of subscribers. The flexibility in revocation is significant since flexible revocation can be integrated with efficient black-box tracing and this integration can be achieved without a substantial increase in the transmission overhead over the previous schemes. In this paper, we present a concrete construction of an efficient public-key black-box traceable and revocable scheme by combining flexible revocation with a known black-box tracing algorithm which works under the same attack model as assumed in the previous schemes. Our scheme achieves that (i) the transmission overhead remains efficient, especially linear only in k in case of bulk revocation and (ii) the tracing algorithm runs in O(log n) time, while the previous ones cannot satisfy both of these properties, where k is the maximum number of traitors in a coalition.

Asymptotic bounds are considered for unidirectional byte error-correcting codes. Upper bounds are developed from the concepts of the Singleton, Plotkin, and Hamming bounds. Lower bounds are also derived from a combination of the generalized concatenated code construction and the Varshamov-Gilbert bound. As the result, we find that there exist codes of low rate better than those on the basis of Hamming distance with respect to unidirectional byte error-correction.

We propose a direct-sequence spread-spectrum multi-access (DS/SSMA) receiver that incorporates multipath diversity combining and multistage co-channel interference (CCI) cancellation. This receiver structure which is more resistant to the near/far problem essentially removes more and more of the CCI with each successive cancellation stage. With the assumption that perfect channel estimates have been obtained, we analyze the bit error rate (BER) performance of this system when received powers are unequal. Results show that the BER can approach that of a single-user case as the number of CCI cancellation stages increases.

This paper describes truncated and impossible differentials of Feistel block ciphers with round functions of 2-layer SPN (Substitution and Permutation Network) transformation modules such as the 128-bit block cipher Camellia, which was proposed by NTT and Mitsubishi Electric Corporation. Our work improves on the best known truncated and impossible differentials, and has found a nontrivial 9-round truncated differential that may lead to a possible attack against a reduced-round version of Camellia without input/output whitening, FL or FL-1 (Camellia-NFL), in the chosen plain text scenario. Previously, only 6-round differentials were known that may suggest a possible attack of Camellia-NFL reduced to 8-rounds. We also show a nontrivial 7-round impossible differential, whereas only a 5-round impossible differential was previously known. We also consider the truncated differential of a reduced-round version of Camellia (Camellia-DS) whose round functions are composed of D-S (Diffusion and Substitution) transformation modules and without input/output whitening, FL or FL-1 (Camellia-DS-NFL), and show a nontrivial 9-round truncated differential, which may lead to a possible attack in the chosen plain text scenario. This truncated differential is effective for general Feistel structures with round functions composed of S-D (Substitution and Diffusion) or D-S transformation.

Recent spread of applications of errorcorrecting codes is really remarkable. This is mainly due to the devolopment of LSI encoders and decoders (codecs) for errorcorrecting codes. This paper picks up some LSI codecs developed recently for Reed-Solomon codes, double-error-correcting Bose-Chaudhuri-Hocqeunghem codes, difference-set cyclic codes and convolutional codes for Viterbi decoding and discuss the related topics in applications of error-correcting codes. We also discuss remaining problems of coding theory which are important from the aspect of practical applications.

This paper demonstrates and confirms that a large-network-oriented key sharing method called the key predistribution system (KPS) is really practical and useful for supporting end-to-end cryptographic communication, by presenting a prototype implementation of KPS using special IC cards and its application to facsimile systems. This prototype can build a secure channel over any ordinary facsimile network using the following types of equipments: (1) an IC card implementing a linear scheme for KPS and the DES algorithm, (2) an adaptor-type interface device between the IC card and a facsimile terminal with no cryptographic function, and (3) a device for each managing center of KPS.

In a seminal paper of identity based encryption (IBE), Boneh and Franklin [6] mentioned an interesting transform from an IBE scheme to a signature scheme, which was observed by Moni Naor. In this paper, we give formal security treatments for this transform and discover several implications and separations among security notions of IBE and transformed signature. For example, we show for such a successful transform, one-wayness of IBE is an essential condition. Additionally, we give a sufficient and necessary condition for converting a semantically secure IBE scheme into an existentially unforgeable signature scheme. Our results help establish strategies on design and automatic security proof of signature schemes from (possibly weak) IBE schemes. We also show some separation results which strongly support that one-wayness, rather than semantic security, of IBE captures an essential condition to achieve secure signature.

This paper shows the analysis of a multihop Fast Frequency Hopping/Spread Spectrum Multiple Access (FFH/SSMA) System in a selective fading channel, in which we consider the frequency correlation characteristics between the signals on the adjacent hopping frequencies of the desired and intersymbol interference and we also take into account of the effects of interference having close hopping frequencies. A multihop-FFH scheme in which several hopping frequencies are used in order to transmit one data symbol, can be classified into a serialhop-FFH and a parallelhop-FFH scheme. More precise bit error probabilities of the multihop-FFH/SSMA systems are theoretically derived with reducing approximation than the bit error probability corresponding to a conventional analysis using the hit probability. As a result, it is classified that the parallelhop-FFH/SSMA system can achieve the better performance of bit error probability than the singlehop and the serialhop-FFH/SSMA systems in a selective fading channel, while the serialhop-FFH/SSMA system can considerably improve the bit error probability over the singlehop and the parallelhop-FFH/SSMA system in an AWGN channel. The performances depend on the number of simultaneously accessing users. Moreover, the computer simulations confirm the theoretical results.

The access control method adopted by UNIX is simple, understandable, and useful. However, it is quite possible that unexpected information flows occur when we are cooperating with some group members on UNIX. Introducing notions such as "flow right," "maximal permission" and "minimal umask value", this note proposes a simple method, can be seen as a natural extension of UNIX, to control indirect information flows without losing availability and understandability of UNIX.

This paper proves several theorems on probabilistic cryptosystems. From these theorems it follows directly that a probabilistic cryptosystem proposed by the authors, whose security is based upon the (supposed) infeasibility of γth-Residuosity Problem, is polynomially secure. Techniques developed in the paper are of independent interest.

It is shown that the effective secret-key size of TOYOCRYPT-HS1 stream cipher is only 96 bits, although the secret key consists of 128 bits. This characteristic opens a door for developing an algorithm for cryptanalysis based on the time-memory-data trade-off with the overall complexity significantly smaller than the exhaustive search over the effective key space.

In this paper, we discuss secure protocols for shared computation of algorithms associated with digital signature schemes based on discrete logarithms. Generic solutions to the problem of cooperatively computing arbitraty functions, though formally provable according to strict security notions, are inefficient in terms of communication--bits and rounds of interaction--; practical protocols for shared computation of particular functions, on the other hand, are often shown secure according to weaker notions of security. We propose efficient secure protocols to share the generation of keys and signatures in the digital signature schemes introduced by Schnorr (1989) and ElGamal (1985). The protocols are built on a protocol for non-interactive verifiable secret sharing (Feldman, 1987) and a novel construction for non-interactively multiplying secretly shared values. Together with the non-interactive protocols for shared generation of RSA signatures introduced by Desmedt and Frankel (1991), the results presented here show that practical signature schemes can be efficiently shared.

Reliability-based decoding algorithm in multistage decoding of multilevel codes is discussed. Through theoretical analyses, effects of soft reliability information are examined for different types of partitionings.

An anonymous password-authenticated key exchange (anonymous PAKE) protocol is designed to provide both password-only authentication and user anonymity against a semi-honest server, who follows the protocol honestly. Very recently, Yang and Zhang have proposed a new anonymous PAKE (NAPAKE) protocol that is claimed efficient compared to the previous constructions. In this paper, we propose a very-efficient anonymous PAKE (called, VEAP) protocol that provides the most efficiency among their kinds in terms of computation and communication costs. The VEAP protocol guarantees semantic security of session keys in the random oracle model under the chosen target CDH problem, and unconditional user anonymity against a semi-honest server. If the pre-computation is allowed, both the user and the server are required to compute only one modular exponentiation, respectively. Surprisingly, this is the same computation cost of the well-known Diffie-Hellman protocol that does not provide authentication at all. In addition, we extend the VEAP protocol in two ways: the first is designed to reduce the communication costs of the VEAP protocol and the second shows that stripping off anonymity parts from the VEAP protocol results in a new PAKE protocol.

We present a new variant of Attribute based encryption (ABE) called Dual-Policy ABE. Basically, it is a conjunctively combined scheme between Key-Policy and Ciphertext-Policy ABE, the only two previous types of ABE. Dual-Policy ABE allows simultaneously two access control mechanisms over encrypted data: one involves policies over objective attributes ascribed to data and the other involves policies over subjective attributes ascribed to user credentials. The previous two types of ABE can only allow either functionality above one at a time.

In this paper, we investigate multilevel coding and multistage decoding for satellite broadcasting with moderate decoding complexity. An unconventional signal set partitioning is used to achieve unequal error protection capabilities. Two possibilities are shown and analyzed for practical systems: (i) linear block component codes with near optimum decoding, (ii) punctured convolutional component codes with a common trellis structure.

Credit-based electronic payment systems are considered to play important roles in future automated payment systems. Like most other types of payment systems, however, credit-based systems proposed so far generally involve computationally expensive cryptographic operations. Such a relatively heavy computational load is preventing credit-based systems from being used in applications which require very fast processing. A typical example is admission-fee payment at the toll gate of an expressway without stopping a vehicle that travels at a high speed. In this article, we propose a very fast credit-based electronic payment protocol for admission-fee payment. More specifically, we propose a payment system between a high-speed vehicle and a toll gate which uses only very simple and fast computations. The proposed system makes use of an optimized Key Pre-distribution System (or KPS) to obtain high resistance against collusion attacks.

A digital signature does not allow any alteration of the document to which it is attached. Appropriate alteration of some signed documents, however, should be allowed because there are security requirements other than that for the integrity of the document. In the disclosure of official information, for example, sensitive information such as personal information or national secrets is masked when an official document is sanitized so that its nonsensitive information can be disclosed when it is demanded by a citizen. If this disclosure is done digitally by using the current digital signature schemes, the citizen cannot verify the disclosed information correctly because the information has been altered to prevent the leakage of sensitive information. That is, with current digital signature schemes, the confidentiality of official information is incompatible with the integrity of that information. This is called the digital document sanitizing problem, and some solutions such as digital document sanitizing schemes and content extraction signatures have been proposed. In this paper, we point out that the conventional digital signature schemes are vulnerable to additional sanitizing attack and show how this vulnerability can be eliminated by using a new digitally signed document sanitizing scheme with disclosure condition control.

Almost all of the current public-key cryptosystems (PKCs) are based on number theory, such as the integer factoring problem and the discrete logarithm problem (which will be solved in polynomial-time after the emergence of quantum computers). While the McEliece PKC is based on another theory, i.e. coding theory, it is vulnerable against several practical attacks. In this paper, we summarize currently known attacks to the McEliece PKC, and then point out that, without any decryption oracles or any partial knowledge on the plaintext of the challenge ciphertext, no polynomial-time algorithm is known for inverting the McEliece PKC whose parameters are carefully chosen. Under the assumption that this inverting problem is hard, we propose a slightly modified version of McEliece PKC that can be proven, in the random oracle model, to be semantically secure against adaptive chosen-ciphertext attacks. Our conversion can achieve the reduction of the redundant data down to 1/3-1/4 compared with the generic conversions for practical parameters.

Channel coding for bandwidth limited channels based on multilevel bit-interleaved channels is discussed in this paper. This coding and decoding structure has the advantage of simplified design, and naturally incorporates flexible and powerful design of unequal error protection (UEP) capabilities, especially over time-varying channels to be often found in mobile radio communications. Multilevel coded modulation with multistage decoding, and bit-interleaved coded modulation are special cases of the proposed general framework. Simulation results verify the usefulness of the system considered.