A {\em secret sharing} (SS) scheme is a method to encrypt a secret $S$ into $n$ pieces called {\em shares}, each of which has no information of the secret, but $S$ can be decrypted from some specified collection of shares. For example, in $(k,n)${\em -threshold} SS schemes, any $k$ out of $n$ shares can decrypt $S$ while $k-1$ or less shares do not leak out any information of $S$. The $(k,n)$ threshold access structure can be extended to a {\em general access structure}, which is specified by the families of qualified sets and forbidden sets, such that a qualified set can decrypt the secret, and a forbidden set does not leak out any information of the secret. SS schemes are one of the most important techniques for secure data storage, and hence, many researches have been devoted to this subject.
The decoding of ordinary SS schemes is implemented by a computer. But, the decoding of {\em visual secret sharing} (VSS) schemes is realized based on human eyesight by peering at several shares stacked up. In this thesis, we propose some new efficient construction methods of SS and VSS schemes, which are treated in Part I and Part II, respectively.
We aim in Part I to construct efficient ordinary SS schemes. First, we derive the lower bounds of coding rates for {\em ramp} SS schemes. Ramp SS schemes are extensions of ordinary SS schemes, which we call {\em perfect} SS schemes in order to distinguish them from ramp SS schemes. Hence, our results include some known results of coding rates for prefect SS schemes as special cases.
In order to derive the lower bounds of coding rates in ramp SS schemes, we classify shares into three categories called {\em super-additive}, {\em additive}, and {\it sub-additive}. Then, we clarify that the coding rates for sub-additive shares are less efficient than the other two types of shares. We also derive the lower bounds of coding rates for super-additive and additive shares.
In previous works for the lower bounds of coding rates for perfect SS schemes, they are often classified into two categories called {\em ideal} or {\em non-ideal} SS schemes, and the properties of access structures are investigated in each category. In this thesis, we extend the notion of ideal perfect SS schemes to define {\em well-realized} ramp SS schemes. By evaluating the lower bounds of coding rates for ramp SS schemes, we analyze what kind of access structures cannot be well-realized as ramp SS schemes. These results are extensions of known ones for non-ideal perfect SS schemes and ramp SS schemes with general access structures.
Next, we propose a new method to construct SS schemes with general access structures in Part I. It is well known how to construct efficient $(k,n)$-threshold SS schemes although no efficient construction method is known for arbitrarily given general access structures. The {\em cumulative map}, which is a special case of {\em multiple assignment map}, is a known simple construction method of SS schemes with general access structures. But, it is generally inefficient, especially in the case that access structures are close to $(k,n)$-threshold access structures. In this thesis, we design the {\em optimal} multiple assignment maps using integer programming. The coding rate obtained by our method is optimal in the multiple assignment maps, and hence, it is more efficient than the cumulative map. Furthermore, since the proposed construction is very simple, it can easily be applied to SS schemes with general ramp and/or incomplete access structures.
In Part II, we propose some construction methods of VSS schemes, which are superior in the viewpoint of the quality of decrypted images and the generalities of access structures.
In VSS schemes, each pixel of a decrypted image consists of a set of {\em subpixels} which is represented by a {\em basis matrix}. In previous works, it was difficult to derive basis matrices since they are combinatorially defined. Hence, many known studies on VSS schemes treated only black-white (BW) binary secret images, and there are few studies of VSS schemes for color secret images because they must deal with more combinations of colors in basis matrices compared with the case of BW binary secret images. Based on such backgrounds, a simple construction method was proposed to derive VSS schemes with color images called {\em algebraic} construction, which does not use the combinatorial methods. It is known that the algebraic construction can realize an efficient VSS scheme, but it could not be applied to VSS schemes for BW binary secret images. In order to improve such defects, a modified algebraic construction was proposed. However, the performance of the modified method has not been studied. In this thesis, we clarify that the modified algebraic construction can attain the {\em optimal} $(n,n)$-threshold VSS schemes for gray-scale images, and we also derive the basis matrices for the optimal $(n,n)$-threshold VSS schemes for gray-scale images.
We also consider VSS schemes for plural secret images in this thesis. We note that the known VSS schemes for plural secret images can treat only BW binary secret images. Furthermore, some definitions of such VSS schemes are not accurate in the sense of security. In other words, decrypted images may leak out some information of the other decrypted images in such VSS schemes. Hence, we carefully define the security condition of VSS schemes for plural secret images. We also propose the construction methods of the secure VSS schemes that satisfy such security conditions. Furthermore, we note that the proposed VSS scheme can treat color secret images with shades, and hence, our VSS scheme includes most of previous VSS schemes as special cases.