Strongly Secure Linear Network Coding

In a network with capacity h for multicast, information $X^h = (X_1,X_2, ..., X_h)$ can be transmitted from a source node to sink nodes without error by a linear network code. Furthermore, secret information $S^r = (S_1, S_2, ..., S_r)$ 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 $S_i$ 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 $(S_{i_1} , S_{i_2} , … , S_{i_{r-j}}$ even if the 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, it is derived some sufficient conditions of alphabet size to realize the strongly $k$-secure network coding for the case of $k Index Terms : network coding, secure network coding, linear network coding, secret sharing schemes, strong ramp secret sharing schemes.

東京大学 大学院新領域創成科学研究科 複雑理工学専攻