栗原 淳

<p>This paper investigates an adversarial model in the scenario of private information retrieval (PIR) from n coded storage servers, called Byzantine adversary. The Byzantine adversary is defined as the one altering b server responses and erasing u server responses to a user's query. In this paper, two types of Byzantine adversaries are considered; 1) the classic omniscient type that has the full knowledge on n servers as considered in existing literature, and 2) the reasonable limited-knowledge type that has information on only b+u servers, i.e., servers under the adversary's control. For these two types, this paper reveals that the resistance of a PIR scheme, i.e., the condition of b and u to correctly obtain the desired message, can be expressed in terms of a code parameter called the coset distance of linear codes employed in the scheme. For the omniscient type, the derived condition expressed by the coset distance is tighter and more precise than the estimation of the resistance by the minimum Hamming weight of the codes considered in existing researches. Furthermore, this paper also clarifies that if the adversary is limited-knowledge, the resistance of a PIR scheme could exceed that for the case of the omniscient type. Namely, PIR schemes can increase their resistance to Byzantine adversaries by allowing the limitation on adversary's knowledge.</p>

<p>In private information retrieval (PIR) from coded storage servers, consider the case where some of servers are Byzantine adversaries and unresponsive. There have been proposed several specialized schemes guaranteeing that the user can correctly obtain the desired message even in the adversarial situation. However, to the best of our knowledge, such resistance to the adversaries in PIR schemes based on arbitrary codes have been not precisely characterized. In this paper, we reveal that the exact resistance to Byzantine and unresponsive servers is expressed in terms of the coset distance of linear codes in linear PIR schemes based on arbitrary storage code.</p>

<p>Content-centric networking (CCN) is an emerging networking architecture that is being actively investigated in both the research and industrial communities. In the latest version of CCN, a large number of interests have to be issued when large content is retrieved. Since CCN routers have to search several tables for each incoming interest, this could cause a serious problem of router workload. In order to solve this problem, this paper introduces a novel strategy of "grouping" multiple interests with common information and "packing" them to a special interest called the list interest. Our list interest is designed to co-operate with the manifest of CCN as its dual. This paper demonstrates that by skipping and terminating several search steps using the common information in the list interest, the router can search its tables for the list interest-based request with dramatically smaller complexity than the case of the standard interest-based request. Furthermore, we also consider the deployment of list interests and design a novel TCP-like congestion control method for list interests to employ them just like standard interests.</p>

This paper proposes a coding scheme to securely store a secret file in a distributed storage system that uses an arbitrary regenerating code. Our scheme encodes the secret file to the input of a certain regenerating code by using the coset coding scheme with a maximum rank distance (MRD) code. We show that our scheme can protect the secret file from being leaked to an eavesdropper in the distributed storage system. Existing security schemes for distributed storage systems are based on specific regenerating codes, and they cannot be used with other regenerating codes. In contrast, our scheme can guarantee the security against the eavesdropper independently of the construction of the underlying regenerating code.

This paper precisely characterizes secret sharing schemes based on arbitrary linear codes by using the relative dimension/length profile (RDLP) and the relative generalized Hamming weight (RGHW). We first describe the equivocation &Delta;_m of the secret vector $\vec{s}$=[s₁,...,s_l] given m shares in terms of the RDLP of linear codes. We also characterize two thresholds t₁ and t₂ in the secret sharing schemes by the RGHW of linear codes. One shows that any set of at most t₁ shares leaks no information about $\vec{s}$, and the other shows that any set of at least t₂ shares uniquely determines $\vec{s}$. It is clarified that both characterizations for t₁ and t₂ are better than Chen et al.'s ones derived by the regular minimum Hamming weight. Moreover, this paper characterizes the strong security in secret sharing schemes based on linear codes, by generalizing the definition of strongly-secure threshold ramp schemes. We define a secret sharing scheme achieving the &alpha;-strong security as the one such that the mutual information between any r elements of (s₁,...,s_l) and any &alpha;-r+1 shares is always zero. Then, it is clarified that secret sharing schemes based on linear codes can always achieve the &alpha;-strong security where the value &alpha; is precisely characterized by the RGHW.

This paper presents a novel technique to realize Karnin et al.'s (k,n)-threshold schemes over binary field extensions as a software. Our realization uses the matrix representation of finite fields and matrix-vector multiplications, and enables rapid operations in software implementation. The theoretical evaluation and computer simulation reveal that our realization of Karnin et al.'s scheme achieves much faster processing time than the ordinary symbol oriented realization of the scheme. Further, we show that our realization has comparable performance to the existing exclusive-OR-based fast schemes of Fujii et al. and Kurihara et al.

In this paper, we present an authentication mechanism for ISDB-T broadcast streams, especially a One-Seg broadcast stream, which is suitable for low-power devices. Our method makes it possible to authenticate data streams at a low computational cost. The method requires a small memory for buffering to process the broadcast stream and is resistant to packet-loss. We evaluated the computational cost of our method by computer simulation and theoretical estimation, and we show here that our method achieved good properties for authenticating data streams broadcast through lossy channels, e.g. wireless channels. Furthermore, we developed a mobile phone that can authenticate One-Seg broadcast streams with our method, and we report the effectiveness of our scheme here.

Shamir's (k, n)-threshold secret sharing scheme (threshold scheme) has two problems: a heavy computational cost is required to make shares and recover the secret, and a large storage capacity is needed to retain all the shares. As a solution to the heavy computational cost problem, several fast threshold schemes have been proposed. On the other hand, threshold ramp secret sharing schemes (ramp scheme) have been proposed in order to reduce each bit-size of shares in Shamir's scheme. However, there is no fast ramp scheme which has both low computational cost and low storage requirements. This paper proposes a new (k, L, n)-threshold ramp secret sharing scheme which uses just EXCLUSIVE-OR(XOR) operations to make shares and recover the secret at a low computational cost. Moreover, by proving that the fast (k, n)-threshold scheme in conjunction with a method to reduce the number of random numbers is an ideal secret sharing scheme, we show that our fast ramp scheme is able to reduce each bit-size of shares by allowing some degradation of security similar to the existing ramp schemes based on Shamir's threshold scheme.

In Shamir's (k,n)-threshold secret sharing scheme (threshold scheme) [1], a heavy computational cost is required to make n shares and recover the secret from k shares. As a solution to this problem, several fast threshold schemes have been proposed. However, there is no fast ideal (k,n)-threshold scheme, where k and n are arbitrary. This paper proposes a new fast (k,n)-threshold scheme which uses just EXCLUSIVE-OR (XOR) operations to make n shares and recover the secret from k shares. We prove that every combination of k or more participants can recover the secret, but every group of less than k participants cannot obtain any information about the secret in the proposed scheme. Moreover, the proposed scheme is an ideal secret sharing scheme similar to Shamir's scheme, in which every bitsize of shares equals that of the secret. We also evaluate the efficiency of the scheme, and show that our scheme realizes operations that are much faster than Shamir's.

In Shamir's (k, n)-threshold secret sharing scheme [1], a heavy computational cost is required to make n shares and recover the secret from k shares. As a solution to this problem, several fast threshold schemes have been proposed. However, there is no fast ideal (k, n)-threshold scheme, where k&ge;3 and n is arbitrary. This paper proposes a new fast (3, n)-threshold scheme by using just EXCLUSIVE-OR (XOR) operations to make shares and recover the secret, which is an ideal secret sharing scheme similar to Shamir's scheme. Furthermore, we evaluate the efficiency of the scheme, and show that it is more efficient than Shamir's in terms of computational cost. Moreover, we suggest a fast (k, n)-threshold scheme can be constructed in a similar way by increasing the sets of random numbers constructing pieces of shares.