A visual cryptography scheme (VCS) is one of the secret sharing schemes for digital images. In the VCS,$n$images called shares are generated from a secret image and are distributed to$n$respective participants. In this paper, we first give a new construction of basis matrices of the VCS realizing the$(2, n)$-threshold access structure. We use a combinatorial design known as an affine resolvable BIBD. In the construction, the relative difference is almost equal to the optimal value, while the pixel expansion is almost half compared with an existing construction attaining the optimal value if we use a$(4l, 2l, 2l-1)$affine resolvable BIBD. We also give a construction of basis matrices using a$(4l, 2l, 2l-1)$affine resolvable BIBD for a certain access structure. In this access structure, participants are partitioned into disjoint groups of size two and the two participants belonging to any group can reproduce a secret image. In addition, any three participants from different groups can obtain no information on a secret image.

In the coded caching scheme proposed by Maddah-Ali and Niesen, we usually consider the setup where$K$users have respective cache memories of equal size and request arbitrary one of$N$files to a server. The server broadcasts a signal to the$K$users so that each user can reproduce the requested file from the transmitted signal together with the contents in their cache memory. Finding the memory-rate tradeoff is one of the fundamental problems in the coded caching problem. In this paper, we extend the coded caching problem to the case where$K$users have cache memories of unequal sizes. We succeed in giving a new upper bound of the memory-rate tradeoff under a certain assumption. We establish the upper bound by developing a new scheme in which$N$files are divided into sub files of unequal sizes according to the sizes of cache memories. The validity of this scheme is established by using combinatoric arguments. We also show that adding new users with no cache memory to the$K$users can reduce the rate of the transmitted signal.

Visual cryptography schemes are used for secret sharing of digital images. In this paper we develop a new simple construction of a visual cryptography scheme with the maximum relative difference for an arbitrarily given strong access structure. Our construction is based on finding the optimal rational-valued solution to a certain linear programming problem which is closely related to the maximization of the relative difference. Validity of the construction is theoretically proved. Several examples are also given for demonstrating usefulness of our construction.

Digital fingerprinting codes are used to protect copyrighted contents from unauthorized redistribution. In this paper we focus on a digital fingerprinting code that can identify both of two malicious users and investigate coding theorems. We give a new definition of an identifier of the malicious users which enables us to give an explicit formula of the joint capacity, the supremum achievable rate of the number of users. Two coding theorems are given under the two kinds of setups depending on the knowledge of an attack model of the malicious users.

We propose a new capacitive proximity sensor that detects deformations of a suction cup as a tactile sense. We confirmed that one sensor module provides three applications for reliable picking and a simplified setup. The first application is the picking height decision. The second one is the placing height decision for detecting whether the grasped object is placed on the placement surface. These two applications are achieved by detecting the push-in stroke of the suction cup. The final application is detection of whether the suction cup is in partial contact or full contact with the object. This function can correct the picking posture as well as detect whether picking is possible before the pull-up motion. We also demonstrate that the partial contact position can be estimated in real time.

A secret sharing scheme is one of cryptographic primitives to share a secret among participants so that only qualified subsets of participants can access the secret. In this paper, we give a new access structure with 13 participants based on a finite projective plane of order 3 and construct an ideal secret sharing scheme realizing the access structure. The minimal qualified set of the access structure consists of all the lines of the finite projective plane as well as all the collection of 7-point sets satisfying a certain property. The soundness of the scheme is established theoretically together with exhaustive search by computer.

Digital fingerprinting codes are embedded in licensed digital contents for preventing illegal distribution. Digital fingerprinting codes are usually designed so that with high probability we can identify a part (or all) of the guilty users who collude to generate a pirated copy. In this paper we first consider the situation where the number of guilty users is equal to two and their attack model is known. We give a lower bound on the joint capacity of the digital fingerprinting codes. The lower bound is expressed as the expectation of the mutual information and is obtained by using certain score functions based on the log-likelihood ratio [12]. This result can be extended to a more general case where the number of guilty users is equal to t ≥ 2.

A (θ, n)-threshold visual cryptography scheme ((θ, n)-VCS) is one of secret sharing schemes for black-white images. In the (θ, n)-VCS, a dealer generates n black-white images called shares from a secret image by using two Boolean matrices called basis matrices. In this paper we propose a new construction of the basis matrices of the (4, n)-VCS using a combinatorial structure known as the 3-design. We establish validity of the obtained basis matrices and give formulas of the pixel expansion m and the relative difference αnof superimposed n shares. This construction can yield basis matrices with a much smaller pixel expansion than existing ones.

We consider a certain class of the (t, n)-threshold visual cryptography scheme called the (t, n)-PVCS in which quality of the reproduced image that appears by superimposition of more than or equal to t shares improves as the number of the superimposed shares increases. We first formulate a linear programming problem followed by an integer programming problem in order to maximize the relative difference caused by superimposition of all the n shares. Next, we propose a construction of the (3, n)-PVCS using the incident matrix of a BIBD. We also discuss the conditions for the BIBD under which the obtained pair of basis matrices becomes optimal.

Digital fingerprinting codes are embedded to licenced digital contents for preventing illegal distribution by colluders. Digital fingerprinting codes are usually required to have the ability to specify a part (or all) of the colluders with high probability who generate a pirated copy. In this paper we evaluate the joint capacity C(PINT) of the digital fingerprinting code against the interleaving attack by c colluders. Quite recently, Laarhoven shows that C(PINT) = 1.1604/(2c2 ln 2) for sufficiently large c. However, this formula includes numerical optimization and is not a good approximation of the capacity C(PINT) for small values of c. In this paper we obtain two series that yield various upper and lower bounds of C(PINT), respectively, which give fairly well approximation of C(PINT) for a wide range of c. The upper and the lower bounds are obtained by using the Taylor expansion indicated by Furon and Pérez-Freire [8] together with the analysis of the l-th moments of a binomial distribution around its mean for l≥2. In particular, the lower bounds give approximation of c2C(PINT) for various ranges of c.

In the problem of encoding tasks introduced by Bunte and Lapidoth, a finite alphabet χ is partitioned to M disjoint subsets {ℒm}mM=1 called lists. In this paper we consider the partition of χ into M lists satisfying L(x) ≤ λ(x) for all x ∈ χ for an arbitrarily given mapping λ: χ → [1, ∞), where L(x) denotes the cardinality of the list ℒmsatisfying x ∈ ℒm. We investigate the minimum number M*(λ) of the lists meeting this constraint and give a lower and an upper bounds on M*(λ) described in terms of λ. We also show that the partition algorithm given by Bunte and Lapidoth attains M*(λ) with a slight modification. Relationships between M*(λ) and the Rényi entropy are also discussed.

In this paper we investigate a secret sharing scheme based on a shortened systematic Reed-Solomon code. In the scheme L secrets S1, S2, ..., SLand n shares X1, X2, ..., Xnsatisfy certain n - k + L linear equations. Security of such a ramp secret sharing scheme is analyzed in detail. We prove that this scheme realizes a (k; n)-threshold scheme for the case of L = 1 and a ramp (k, L, n)-threshold scheme for the case of 2 ≤ L ≤ k - 1 under a certain assumption on S1, S2, ..., SL.

Embedding anti-collusion fingerprinting codes to digital contents enables us to protect the digital contents from piracy. Recently, Trappe et al. proposed an anti-collusion code (AND-ACC) such that all the illegal users are exactly detected from a binary sequence obtained from AND of all the codewords of the illegal users, where the number of the illegal users is assumed to be less than or equal to a constant k ≥ 2. In this paper we focus on the AND-ACC and analyze the number of codewords M with increasing the codeword length n for an arbitrarily fixed k ≥ 2. First, we define the zero-error capacity C*kof the AND-ACC and give a lower and an upper bounds of C*k. The lower bound of C*kis obtained by using a lemma used in a coding theorem on the identification codes. In addition, we extend the AND-ACC to the case where negligible detection error is permitted. We define the capacity Ckand give a lower and an upper bounds of Ck. These bounds are established by using techniques used for coding of a multiple-access channel.

This paper unveils a new connection between majorization theory and the smooth Rényi entropy of order α. We completely characterize the subprobability distribution that attains the infimum included in the definition of the smooth Rényi entropy Hαε(p) of order α by using the notions of majorization and the Schur convexity/concavity, where p denotes a probability distribution on a discrete alphabet and ε ϵ [0,1) is an arbitrarily given constant. We can apply the obtained result to characterization of asymptotic behavior of 1/n Hαε(p) as n → ∞ for general sources satisfying the strong converse property.

Coding theorems on a$(2,2)$-threshold scheme with an opponent are discussed in an asymptotic setup, where the opponent tries to impersonate one of the two participants. A situation is considered where$n$secrets$S^{n}$from a memoryless source is blockwisely encoded to two shares and the two shares are decoded to$S^{n}$with permitting negligible decoding error. We introduce correlation level of the two shares and characterize the minimum attainable rates of the shares and a uniform random number for realizing a$(2, 2)$-threshold scheme that is secure against the impersonation attack by the opponent. It is shown that if the correlation level between the two shares equals to$\ell \geq 0$, the minimum attainable rates coincide with$H(S)+\ell $, where$H(S)$denotes the entropy of the source, and the maximum attainable exponent of the success probability of the impersonation attack equals to$\ell $. It is also shown that a simple scheme using an ordinary$(2,2)$-threshold scheme attains all the bounds as well.

We consider a situation where n-tuples generated from a general source are encoded by a fixed-length code and discuss coding theorems on the worst-case redundancy, where the worst-case redundancy is defined as the maximum of the difference between the rate and the ideal codeword length per symbol with respect to all the correctly decodable n-tuples. We treat the four cases where the decoding error probability εnis required to satisfy (a) limn→∞εn= 0, (b) lim infn→∞εn= 0, (c) lim supn→∞εn≤ ε, and (d) lim infn→∞εn≤ ε, respectively, where ε ∈ [0; 1) is an arbitrary constant. We give general formulas of the optimum worst-case redundancy that are closely related to the width of the entropy-spectrum of a source.

Secret sharing schemes which are secure under the presence of malicious participants who forge their shares have been investigated by many researchers so far. In this paper we consider a secret sharing scheme with a key at an encoder and a decoder and analyze its security against the substitution attack by malicious participants. We first give conditions that the secret sharing scheme with a key must satisfy. Next, we construct a simple secret sharing scheme with a key that generates n shares and detects forged shares with high probability. We can prove that, if at most n - 1 malicious participants collude and try to deceive the other participants by forged shares optimally, the success probability of such an attack is upper-bounded by |S|-1/|X|-1, where |S| and |X| denote the sizes of the secret and the n shares, respectively. In addition, we investigate basic properties of the scheme especially for the case of n = 2.

This paper presents two new coding theorems on a (2, 2)-threshold scheme with an opponent who impersonates one of the shareholders. In the (2, 2)-threshold scheme an encoder blockwisely generates two shares Xnand Ynfrom n secrets Snand a uniform random number En, where Snis generated from a general source. There are three kinds of inputs to a decoder, (Nn., Yn), (X̅n, Xn) and (Xn, Y̅n), where X̅nand Y̅nare fraudulent shares generated by the opponent. The decoder judges whether the input is legitimate or not under negligible decoding error probability that vanishes as n → ∞. The two coding theorems given in this paper characterize the minimum attainable rates of Xn, Ynand Enand the maximum attainable exponent of the probability of the successful impersonation attack. It turns out that the (2, 2)-threshold scheme with a cheater is related to not only hypothesis testing but also optimistic coding of general sources and channels.

It is known that a secret sharing scheme (SSS) with perfect cheating detection cannot be realized because such a SSS requires infinite share rates. However, this impossibility comes from the fact that block coding is not used and any decoding error is not allowed in the SSS. Hence, in this paper, we consider a SSS constructed by block coding with an arbitrarily small decoding error probability. It is shown that the perfect cheating detection with finite rates is possible for the 2-out-of-2 SSS in a certain asymptotic sense. Furthermore, the supremum of the achievable exponent in the maximum success probability of impersonation attack turns out to be the mutual information between the two shares.

In this paper, coding theorems on the (t, m) -threshold scheme for a general source are discussed, where m means the number of the shares and t means a threshold. The (t,m) -threshold scheme treated in this paper encrypts n source outputs Xnto m shares at once and is required to satisfy the two conditions that 1) Xnis reproduced from arbitrary t shares, and 2) almost no information of Xnis revealed from any t - 1 shares. It is shown that the (t,m) -threshold scheme must satisfy certain inequalities including the limit inferiors in probability. One of the inequalities is closely related to the minimum length of the fair random bits needed to a dealer for realizing the (t, m) -threshold scheme. In addition, it is shown that a certain variation of Shamir's threshold scheme meets the two conditions. The same approach can be taken to the problems of Shannon's cipher system with the perfect secrecy and fixed-length source coding with vanishing decoding error probability. It is shown that the same kind of inequalities, which indicate the converse coding theorems, hold in both two cases.

In this paper we discuss coding theorems for extensions of the information-theoretic stegosystem proposed by Cachin. We consider a stegosystem in which a covertext is generated from a general source. The variational distance between the probability distributions of a covertext and a stegotext is required to be negligible for ensuring validity as a stegosystem. We determine the maximum rate at which a sender can transmit a message to a receiver securely in the presence of an opponent under the assumption on an oracle at the decoder. In addition, we show that the assumption on the oracle is not needed when side information of a covertext is available at a decoder.

This correspondence is concerned with new connections between source coding and two kinds of families of hash functions known as the families of universal hash functions and N-strongly universal hash functions, where N ges 2 is an integer. First, it is pointed out that such families contain classes of well-known source codes such as bin codes and linear codes. Next, performance of a source coding scheme using either of the two kinds of families is evaluated. An upper bound on the expectation of the decoding error probability is obtained for each family. The expectation of the decoding error probability is analyzed in detail for the cases of discrete memoryless sources and sources without the memoryless assumption under a certain class of decoders.

This paper is concerned with a variation of the (t, n)-threshold visual secret sharing scheme ((t, n)-VSSS for short). In the (t, n)-VSSS a secret image is encrypted to n images called shares. While we can reproduce the secret image by stacking arbitrary t shares, no information is revealed from less than t shares. We consider a new (t, n)-VSSS in which stacking more than t shares enables us to recognize a secret image more clearly than stacking just t shares. In particular, for the cases of t = 2, 3,4, 5 we can prove the existence of basis matrices of the (t, n)-VSSS that almost perfectly reproduces a secret image when all the n shares are stacked if n is sufficiently large

This paper is concerned with coding theorems for a generalized wiretap channel. In the problem of the wiretap channel it is important to characterize the secrecy capacity, i.e., the maximum achievable rate of information securely transmitted from a sender to a legitimate receiver in the presence of a wiretapper. In our model, channels are not restricted to memoryless channels. We first define the secrecy capacity Csand evaluate Csfrom information-spectrum approach. We give a new upper bound of Csnot including auxiliary random variables and explore conditions under which the obtained upper bound becomes tight for the cascaded wiretap channel

This correspondence is concerned with asymptotic properties on the codeword length of a fixed-to-variable length code (FV code) for a general source {X/sup n/}/sub n=1//sup /spl infin// with a finite or countably infinite alphabet. Suppose that for each n /spl ges/ 1 X/sup n/ is encoded to a binary codeword /spl phi//sub n/(X/sup n/) of length l(/spl phi//sub n/(X/sup n/)). Letting /spl epsiv//sub n/ denote the decoding error probability, we consider the following two criteria on FV codes: i) /spl epsiv//sub n/ = 0 for all n /spl ges/ 1 and ii) lim sup/sub n/spl rarr//spl infin///spl epsiv//sub n/ /spl les/ /spl epsiv/ for an arbitrarily given /spl epsiv/ /spl isin/ [0,1). Under criterion i), we show that, if X/sup n/ is encoded by an arbitrary prefix-free FV code asymptotically achieving the entropy, 1/nl(/spl phi//sub n/(X/sup n/)) - 1/nlog/sub 2/ 1/PX/sup n/(X/sup n/) /spl rarr/ 0 in probability as n /spl rarr/ /spl infin/ under a certain condition, where P/sub X//sup n/ denotes the probability distribution of X/sup n/. Under criterion ii), we first determine the minimum rate achieved by FV codes. Next, we show that 1/nl(/spl phi//sub n/(X/sup n/)) of an arbitrary FV code achieving the minimum rate in a certain sense has a property similar to the lossless case.

We consider a source coding scheme in which we use a mapping f /spl isin/ /spl Fscr/ as an encoder, where /spl Fscr/ is a class of universal hash functions. It is shown that, if /spl Fscr/ satisfies a certain condition, for any discrete source there exist an encoder using an f /spl isin/ /spl Fscr/ and a decoder such that the decoding error probability becomes negligible for sufficiently large blocklength. We also give the error exponent of the minimum-entropy decoder for i.i.d. sources that is not less than the error exponent of linear encoders.

Robot dynamics under static and Coulomb frictions are shown to be equivalent to a nonlinear position-dependent circuit including a set of on-off switches and analyzed as a variable structure system. It is shown that, under the existence of static and Coulomb frictions at each joint, an ordinary PD feedback with gravity compensation, for set-point position control leads to a trapping of motion at some immovable state within a finite time without reaching the given target position. On the contrary, by introducing regressors for uncertain parameters of gravity forces and static and Coulomb frictions it is possible to show that a proper update law of such regressors together with an adequate PD feedback renders the target state of the robot system globally, asymptotically stable without incurring any offset and without measuring any force/torque signals. It is shown that regressors can be treated as an operator with positivity and thereby regarded as a time-varying capacitor. These observations suggest a proposal of robots that are subject to only the law of inertia, that is, a proposal of inertia-only robots or gravity/friction-free robots.