We present the first O(1)-size designated confirmer signatures (DCS) with security in the state-of-the-art model of Camenisch and Michels, Eurocrypt 2000, without random oracles. In particular, we achieve the security notion called the "invisibility of signature" therein. We do so by a simple upgrade of Gentry, et al. [7]. Then we also present O(1)-size identity-based DCS without random oracle by without invisibility, and O(1)-size undeniable signature without random oracle and with invisibility.

Since the formalization of ring signature by Rivest, Shamir and Tauman in 2001, there are lots of variations appeared in the literature. Almost all of the variations rely on the random oracle model for security proof. In this paper, we propose a ring signature scheme based on bilinear pairings, which is proven to be secure against adaptive chosen message attack without using the random oracle model. It is one of the first in the literature to achieve this security level.

Write-unidirectional memories (WUMs) were introduced by Willems, Vinck, and Borden as an information-theoretic model for storing and updating information on a rewritable medium with the writing constraints: During the odd (resp., even) cycles of updating information, the encoder can only write 1's (resp., 0's) in selected bit positions of WUMs, and not change the contents of other positions. In this correspondence, motivated by the research works of Wolf, Wyner, Ziv, and Ko/spl uml/rner on write-once memories (WOMs), we study the problem of how to reuse a WUM for fixed T successive cycles with nonperiodic codes (i.e., all coding strategies are permitted for every cycle). For the situation where the encoder knows and the decoder does not know the previous content of the memory, we determine the zero-error capacity region, the average capacity, and the maximum total number of information bits stored in the WUM for fixed T successive cycles. Motivated by the research works of Heegard on WOMs with symmetric input noise, we introduce two models of WUMs with symmetric or asymmetric input noise. By using /spl epsiv/-error as performance criterion, we extend the above results for WUMs to the two models of WUMs with symmetric or asymmetric input noise.

In this paper, the undetected error probability for binary codes is studied. First complementary codes are studied. Next, a new proof of Abdel-Ghaffar's (1997) lower bound on the undetected error probability is presented and some generalizations are given. Further, upper and lower bounds on the undetected error probability for binary constant weight codes are given, and asymptotic versions are studied.

A permutation array (PA) of length n and minimum distance d is a set of permutations of n elements such that any two permutations coincide in at most n - d positions. Some constructions of PAs are given.

Svanstrom (see IEEE ibid., vol.43, p.1630-2, Sept. 1997) gave a lower bound on the size of ternary constant-weight codes (CWCs). This bound is generalized and improved in some cases.

The depth distribution of a linear code was recently introduced by T. Etzion (see ibid., vol.43, pp.1361-3, July 1997). In this correspondence, a number of basic and interesting properties for the depth of finite words and the depth distribution of linear codes are obtained. In addition, we study the enumeration problem of counting the number of linear subcodes with the prescribed depth constraints, and derive some explicit and interesting enumeration formulas. Furthermore, we determine the depth distribution of Reed-Muller code RM (m,r). Finally, we show that there are exactly nine depth-equivalence classes for the ternary [11,6,5] Golay codes.

The problem of redundancy of source coding with respect to a fidelity criterion is considered. For any fixed rate R>0 and any memoryless source with finite source and reproduction alphabets and a common distribution p, the nth-order distortion redundancy D/sub n/(R) of fixed-rate coding is defined as the minimum of the difference between the expected distortion per symbol of any block code with length n and rate R and the distortion rate function d(p,R) of the source p. It is demonstrated that for sufficiently large n, D/sub n/(R) is equal to -(/spl part///spl part/R)d(p,R) ln n/2n+o(ln n/n), where (/spl part///spl part/R)d(p,R) is the partial derivative of d(p,R) evaluated at R and assumed to exist. For any fixed distortion level d>0 and any memoryless source p, the nth-order rate redundancy R/sub n/(d) of coding at fixed distortion level d (or by using d-semifaithful codes) is defined as the minimum of the difference between the expected rate per symbol of any d-semifaithful code of length n and the rate-distortion function R(p,d) of p evaluated at d. It is proved that for sufficiently large n, R/sub n/(d) is upper-bounded by ln n/n+o(ln n/n) and lower-bounded by In n/2n+o(In n/n). As a by-product, the lower bound of R/sub n/(d) derived in this paper gives a positive answer to a conjecture proposed by Yu and Speed (1993).

A new on-line universal lossy data compression algorithm is presented. For finite memoryless sources with unknown statistics, its performance asymptotically approaches the fundamental rate distortion limit. The codebook is generated on the fly, and continuously adapted by simple rules. There is no separate codebook training or codebook transmission. Candidate codewords are randomly generated according to an arbitrary and possibly suboptimal distribution. Through a carefully designed "gold washing" or "information-theoretic sieve" mechanism, good codewords and only good codewords are promoted to permanent status with high probability. We also determine the rate at which our algorithm approaches the fundamental limit.

Presents efficient algorithms for collecting information distributed among indistinguishable (anonymous) processors while performing certain operations on the information being collected. The efficiency objective is to minimize the communication-delay product and to obtain trade-offs between the two. The main contribution of the paper is a new efficient algorithm for performing sumlike operations (such as Abelian group operations and elementary symmetric functions) and the use of metrically regular graphs (which include the widely used hypercube interconnections) for information dissemination in distributed computations. The best algorithm has a communication-delay product of O(Nlog/sup 3/ N) (for W nodes), and obtaining an optimal /spl Omega/(Nlog/sup 2/N) algorithm remains an open problem.>

An efficient decoding algorithm for algebraic-geometric codes is presented. For codes from a large class of irreducible plane curves, including Hermitian curves, it can correct up to [(d*-1)/2] errors, where d* is the designed minimum distance. With it we also obtain a proof of d/sub min//spl ges/d* without directly using the Riemann-Roch theorem. The algorithm consists of Gaussian elimination on a specially arranged syndrome matrix, followed by a novel majority voting scheme. A fast implementation incorporating block Hankel matrix techniques is obtained whose worst-case running time is O(mn/sup 2/), where m is the degree of the curve. Applications of our techniques to decoding other algebraic-geometric codes, to decoding BCH codes to actual minimum distance, and to two-dimensional shift register synthesis are also presented.>

Elias (1991) derived upper and lower bounds on the sizes of error-correcting codes for list decoding. The asymptotic values of his lower bounds for linear codes and for nonlinear codes are separated. The present authors derive improved lower bounds for linear and for nonlinear codes. They conjecture their two bounds are identical. However, they were able to verify this only for small lists.>

The identification coding theorems of R. Ahlswede and G. Dueck (1981) have shown that for any nonzero probabilities of missed and false identification, it is possible to transmit exp(exp(nR)) messages with n uses of a noisy channel, where R is as close as desired to the Shannon capacity of the channel. That capability is achieved by the identification codes explicitly constructed with a three-layer concatenated constant-weight code used in conjunction with a channel transmission code of rate R.>

The rth generalized Hamming weight of a linear code is the minimum support size of any r-dimensional subcode. It has been found useful in the studies of cryptography and trellis coding. The authors derive several results on expressing the generalized Hamming weights of a product code in terms of those of its component codes. They also formulate a general conjecture.>

The generalized Hamming weights of a linear code are fundamental code parameters related to the minimal overlap structures of the subcodes. They were introduced by V.K. Wei (1991) and shown to characterize the performance of the linear code in certain cryptographical applications. Results are presented on the generalized Hamming weights of several classes of binary cyclic codes, including primitive double-error-correcting and triple-error-correcting BCH codes, certain reversible cyclic codes, and some extended binary Goppa codes. In particular, the second generalized Hamming weight of primitive double-error-correcting BCH codes is determined and upper and lower bounds are obtained for the generalized Hamming weights for the codes studied. These bounds are compared to results from other methods.>

Two results are presented concerning the partial periods (p-p's) of an m-sequence of period 2/sup n/-1. The first proves the existence of an m-sequence whose p-p's of length approximately (n+d log/sub 2/ n) have minimum distance between d and 2d for small d. The second result is of an asymptotic nature and proves that the normalized minimum distance of p-p's whose length is any fraction of the period of the m-sequence, approaches 1/2 as the period of m-sequence tends to infinity.>

Motivated by cryptographical applications, the algebraic structure, of linear codes from a new perspective is studied. By viewing the minimum Hamming weight as a certain minimum property of one-dimensional subcodes, a generalized notion of higher-dimensional Hamming weights is obtained. These weights characterize the code performance on the wire-tap channel of type II. Basic properties of generalized weights are derived, the values of these weights for well-known classes of codes are determined, and lower bounds on code parameters are obtained. Several open problems are also listed.>

An optical orthogonal code (OOC) is a family of

Simulated annealing is a computational heuristic for obtaining approximate solutions to combinatorial optimization problems. It is used to construct good source codes, error-correcting codes, and spherical codes. For certain sets of parameters codes that are better than any other known in the literature are found.

A trellis code is {\em homogeneous} if the number of branches emanating from each node (or state) in the trellis diagram is constant. For example, convolutional codes are linear homogeneous trellis codes. A trellis code is {\em nonhomogeneous} if the number of branches emanating from each node in the trellis diagram is not the same. The two-user binary adder channel is a multiple-access channel with two binary inputs,x_{1}andx_{2}, and one ternary output,y = x_{1} + x_{2}, where the addition is done in the real number field. The adder channel is synchronous if both encoders and the decoder maintain block (frame) synchronism. It is quasi-synchronous if the encoders do not start their blocks at the same time, but the decoder knows the position of each block. The difference between the starting times of the blocks is called the slippage. The channel is asynchronous if no block synchronism exists among the encoders and the decoder. Some uniquely decodable code pairs(C_{1}, C_{2})are presented that can be used to transmit information reliably over the quasi-synchronous binary adder channel with two users. One of the codes is a nonhomogeneous trellis code, the other is a common block code. Our code rates are better than Deaett-Wolf codes and are close to or equal to the asymptotic rates of Kasami {\em et al}. A method for calculating the rates of nonhomogeneous trellis codes is described. An algorithm for finding more uniquely decodable code pairs for the quasi-synchronous binary adder channel is formulated.

A trellis code is a "sliding window" method of encoding a binary data stream as a sequence of signal points in Rn. When a trellis code is used to encode data at the rate ofkbits/channel symbol, each channel input depends not only on the most recent block ofkbits to enter the encoder, but will also depend on a set of ν bits preceding this block. The ν bits determine the state of the encoder and the most recent block ofkbits generates the channel symbol conditional on the encoder state. The performance of a trellis code depends on a suitably defined minimum distance property of that code. This paper obtains upper bounds on this minimum distance that are better than any previously known.

Block coding for the binary symmetric broadcast channel with two receivers is investigated. A graph-theoretic approach to the construction of a class of block codes with unequal error protection for two different sets of messages is presented. A code in this class is a direct sum of two component codes; each set of messages is encoded based on one component code. The codes in this class are easy to implement. Decoding of these codes is presented, and lower bounds on the achievable rates of these codes are derived. The bounds are tighter than the Katsman's bounds.

The error-trapping decoder is the simplest way of decoding cyclic codes satisfyingR < 1 / t, wheretis the maximum number of errors to be corrected andRis the code rate. These codes have low rates and/or correct only a few errors. Kasami has used the concept of covering polynomials to demonstrate modified error-trapping decoders for several binary cyclic codes not satisfyingR<1/t. In this paper Kasami's decoder is modified further for correcting multiple symbol errors on nonbinary cyclic codes satisfyingR < 2 / t. The Berlekamp decoder for these codes requires Galois field multiplication and division of two variables which are difficult to implement. Our decoder does not require these multiplications and divisions. Further, for all double-error-correcting codes, and triple-error-correcting codes with rateR < 2/3, an algorithm is presented for finding a minimum set of covering monomials.

We relate coding for the two-user multiple-access binary adder channel to a problem in graph theory, known as the independent set problem. Graph-theoretic approaches to coding for both synchronized and nonsynchronized two-user adder channels are presented. Using the Tuŕan theorem on the independence number of a simple graph, we are able to improve the lower bounds on the achievable rates of uniquely and\delta-decodable codes for the synchronized adder channel derived by Kasami and Lin. We are also able to derive lower bounds on the achievable rates of uniquely decodable codes for the nonsynchronized adder channel. We show that the rates of Deaett-Wolf codes for the nonsynchronized adder channel fall below the bounds. Synchronizing sequences for the nonsynchronized adder channel are constructed.