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.

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.

In this paper, a new method is proposed to construct a visual secret sharing scheme with a general access structure for plural secret images. Although the proposed scheme can be considered as an extension of Droste's method that can encode only black-white images, it can encode plural gray-scale and/or color secret images.

Linear complexity can be used to detect predictable nonrandom sequences, and hence it is included in the NIST randomness test suite. But, as shown in this paper, the NIST test suite cannot detect nonrandom sequences that are generated, for instance, by concatenating two different M-sequences with low linear complexity. This defect comes from the fact that the NIST linear complexity test uses deviation from the ideal value only in the last part of the whole linear complexity profile. In this paper, a new faithful linear complexity test is proposed, which uses deviations in all parts of the linear complexity profile and hence can detect even the above nonrandom sequences. An efficient formula is derived to compute the exact area distribution needed for the proposed test. Furthermore, a simple procedure is given to compute the proposed test statistic from linear complexity profile, which requires only O(M) time complexity for a sequence of length M.

We propose a randomness test based on the T-complexity of a sequence, which can be calculated using a parsing algorithm called T-decomposition. Recently, the Lempel-Ziv (LZ) randomness test based on LZ-complexity using the LZ78 incremental parsing was officially excluded from the NIST test suite in NIST SP 800-22. This is caused from the problem that the distribution of P-values for random sequences of length 106 is strictly discrete for the LZ-complexity. Our proposed test can overcome this problem because T-complexity has almost ideal continuous distribution of P-values for random sequences of length 106. We also devise a new sequential T-decomposition algorithm using forward parsing, while the original T-decomposition is an off-line algorithm using backward parsing. Our proposed test can become a supplement to NIST SP 800-22 because it can detect several undesirable pseudo-random numbers that the NIST test suite almost fails to detect.

In this paper, we propose two schemes, which enable any VF code to realize direct- or fast-access decoding for any long source sequence. Direct-access decoding means that any source symbol of any position can be directly decoded within constant time, not depending on the length of source sequence N, without decoding the whole codeword sequence. We also evaluate the memory size necessary to realize direct-access decoding or fast-access decoding with decoding delay O(log log N), O(log N), and so on, in the proposed schemes.

The redundancy of universal lossy data compression for discrete memoryless sources is considered in terms of type and d-ball covering. It is shown that there exists a universal d-semifaithful code whose rate redundancy is upper bounded by (A-1/2)n-1ln n+o(n-1ln n), where A is the cardinality of source alphabet and n is the block length of the code. This new bound is tighter than known ones, and moreover, it turns out to be the attainable minimum of the universal coding proposed by Davisson.

The subset sum problem, which is often called as the knapsack problem, is known as an NP-hard problem, and there are several cryptosystems based on the problem. Assuming an oracle for shortest vector problem of lattice, the low-density attack algorithm by Lagarias and Odlyzko and its variants solve the subset sum problem efficiently, when the “density” of the given problem is smaller than some threshold. When we define the density in the context of knapsack-type cryptosystems, weights are usually assumed to be chosen uniformly at random from the same interval. In this paper, we focus on general subset sum problems, where this assumption may not hold. We assume that weights are chosen from different intervals, and make analysis of the effect on the success probability of above algorithms both theoretically and experimentally. Possible application of our result in the context of knapsack cryptosystems is the security analysis when we reduce the data size of public keys.

In this paper, a method is proposed to construct an n-out-of-n visual secret sharing scheme for gray-scale images, for short an (n,n)-VSS-GS scheme, which is optimal in the sense of contrast and pixel expansion, i.e., resolution. It is shown that any (n,n)-VSS-GS scheme can be constructed based on the so-called polynomial representation of basis matrices treated in [15],[16]. Furthermore, it is proved that such construction can attain the optimal (n,n)-VSS-GS scheme.

In this paper we analize the performance of Trellis Coded Modulation (TCM) schemes with coherent detection operating in a frequency flat, mobile Rayleigh fading environment, and with different knowledge levels on both the amplitude and phase fading processes (the latter is not assumed as usual to be ideally tracked), or Channel State Information (CSI). For example, whereas ideal CSI means that both the amplitude and phase fading characteristics are perfectly known by the receiver, other situations that are treated consider perfect knowledge of the amplitude (or phase) with complete disregard of the phase (or amplitude), as well as non concern on any of them. Since these are extreme cases, intermediate situations can be also defined to get extended bounds based on Chernoff which allow the phase errors, in either form of constant phase shifts or randomly distributed phase jitter, to be included in the upper bounds attainable by transfer function methods, and are applicable to multiphase/level signaling schemes. We found that when both fading characteristics are considered, the availability of CSI enhances significatively the performance. Furthermore, for non constant envelope schemes with non ideal CSI and for constant envelope schemes with phase errors, an asymmetry property of the pairwise error probability is identified. Theoretical and simulation results are shown in support of the analysis.

A Bitplane Tree Weighting (BTW) method with arithmetic coding is proposed for lossless coding of gray scale images, which are represented with multiple bitplanes. A bitplane tree, in the same way as the context tree in the CTW method, is used to derive a weighted coding probability distribution for arithmetic coding with the first order Markov model. It is shown that the proposed method can attain better compression ratio than known schemes with MDL criterion. Furthermore, the BTW method can be extended to a high order Markov model by combining the BTW with the CTW or with prediction. The performance of these modified methods is also evaluated. It is shown that they attain better compression ratio than the original BTW method without increasing memory size and coding time, and they can beat the lossless JPEG coding.

A new Hybrid-ARQ scheme with a convolutional code and the Viterbi decoding is proposed, which uses the packet combining technique and a retransmission criterion based on an estimated decoding error rate. The throughput and bit error rate are evaluated by theoretical bounds and computer simulations. It is shown that a given error rate tolerance can be attained with good throughput for any signal to noise ratio, i.e. for the slow time-varying channels. Furthermore, the throughput performance can be improved by retransmitting not all but a part of packet.

In this paper, the posterior matching scheme proposed by Shayevits and Feder is extended to the Gaussian broadcast channel with feedback, and the error probabilities and achievable rate region are derived for this coding strategy by using the iterated random function theory. A variant of the Ozarow-Leung code for the general two-user broadcast channel with feedback can be realized as a special case of our coding scheme. Furthermore, for the symmetric Gaussian broadcast channel with feedback, our coding scheme achieves the linear-feedback sum-capacity like the LQG code and outperforms the Kramer code.

In a network with capacity h for multicast, information Xh=(X1, X2, , Xh) can be transmitted from a source node to sink nodes without error by a linear network code. Furthermore, secret information Sr=(S1, S2, , Sr) can be transmitted securely against wiretappers by k-secure network coding for k h-r. In this case, no information of the secret leaks out even if an adversary wiretaps k edges, i.e. channels. However, if an adversary wiretaps k+1 edges, some Si may leak out explicitly. In this paper, we propose strongly k-secure network coding based on strongly secure ramp secret sharing schemes. In this coding, no information leaks out for every (Si1, Si2, ,Sir-j) even if an adversary wiretaps k+j channels. We also give an algorithm to construct a strongly k-secure network code directly and a transform to convert a nonsecure network code to a strongly k-secure network code. Furthermore, some sufficient conditions of alphabet size to realize the strongly k-secure network coding are derived for the case of k < h-r.

In this paper, we treat (k, L, n) ramp secret sharing schemes (SSSs) that can detect impersonation attacks and/or substitution attacks. First, we derive lower bounds on the sizes of the shares and random number used in encoding for given correlation levels, which are measured by the mutual information of shares. We also derive lower bounds on the success probabilities of attacks for given correlation levels and given sizes of shares. Next we propose a strong (k, L, n) ramp SSS against substitution attacks. As far as we know, the proposed scheme is the first strong (k, L, n) ramp SSSs that can detect substitution attacks of at most k-1 shares. Our scheme can be applied to a secret SL uniformly distributed over GF(pm)L, where p is a prime number with p≥L+2. We show that for a certain type of correlation levels, the proposed scheme can achieve the lower bounds on the sizes of the shares and random number, and can reduce the success probability of substitution attacks within nearly L times the lower bound when the number of forged shares is less than k. We also evaluate the success probability of impersonation attack for our schemes. In addition, we give some examples of insecure ramp SSSs to clarify why each component of our scheme is essential to realize the required security.

The performance of the hybrid-ARQ scheme with a convolutional code, in which the retransmission criterion is based on an estimated decoding error rate, is evaluated for moderately time-varying channels. It is shown by computer simulations that the simple average diversity combining scheme can almost attain the same performance as the optimally weighted diversity combining scheme. For the whole and partial retransmission schemes with the average diversity combining, the theoretical bounds of throughput and bit error rate are derived, and it is shown that their bounds are tight and the treated schemes can attain a given error rate with good throughput for moderately time-varying channels. Furthermore, the throughput is shown to be improved by the partial retransmission scheme compared with the whole retransmission scheme.

A new class of the universal representation for the positive integers is proposed. The positive integers are divided into infinite groups, and each positive integer n is represented by a pair of integers (p,q), which means that n is the q-th number in the p-th group. It is shown that the new class includes the message length strategy as a special case, and the asymptotically optimal representation can easily be realized. Furthermore, a new asymptotically and practically efficient representation scheme is proposed, which preserves the numerical, lexicographical, and length orders.

Power exponentiation is an important operation in modern cryptography. This operation can be efficiently calculated using the concept of the addition chain. In this paper, two new systematic methods, a Run-length method and a Hybrid method, are proposed to generate a short addition chain. The performance of these two methods are theoretically analyzed and it is shown that the Hybrid method is more efficient and practical than known methods. The proposed methods can reduce the addition chain length by 8%, in the best case, compared to the Window method.

It is known that for any general access structure, a secret sharing scheme (SSS) can be constructed from an (m,m)-threshold scheme by using the so-called cumulative map or from a (t,m)-threshold SSS by a modified cumulative map. However, such constructed SSSs are not efficient generally. In this paper, a new method is proposed to construct a SSS from a (t,m)-threshold scheme for any given general access structure. In the proposed method, integer programming is used to derive the optimal (t,m)-threshold scheme and the optimal distribution of the shares to minimize the average or maximum size of the distributed shares to participants. From the optimality, it can always attain lower coding rate than the cumulative maps because the cumulative maps cannot attain the optimal distribution in many cases. The same method is also applied to construct SSSs for incomplete access structures and/or ramp access structures.

The performance evaluation by analysis of systems employing Reduced State Viterbi decoding is addressed. This type of decoding is characterized by an inherent error propagation effect, which yields a difficulty in the error probability analysis, and has been usually neglected in the literature. By modifying the Full State trellis diagram, we derive for Reduced State schemes, new transfer function bounds with the effects of error propagation. Both the Chernoff and the tight upper bound are applied to the transfer function in order to obtain the bit error probability upper bound. Furthermore, and in order to get a tighter bound for Reduced State decoding schemes with parallel transitions, the pairwise probability of the two sequences involved in an error event is upper bounded, and then the branch metric of a sequence taken from that bound is associated with a truncated instead of complete Gaussian noise probability density function. To support the analysis, particular assessment is done for a Trellis Coded Modulation scheme.