We present a new improvement in the linear programming technique to derive lower bounds on the information ratio of secret sharing schemes. We obtain non-Shannon-type bounds without using information inequalities explicitly. Our new technique makes it possible to determine the optimal information ratio of linear secret sharing schemes for all access structures on 5 participants and all graph-based access structures on 6 participants. In addition, new lower bounds are presented also for some small matroid ports and, in particular, the optimal information ratios of the linear secret sharing schemes for the ports of the Vamos matroid are determined.

Beimel and Orlov proved that all information inequalities on four or five variables, together with all information inequalities on more than five variables that are known to date, provide lower bounds on the size of the shares in secret sharing schemes that are at most linear on the number of participants. We present here another two negative results about the power of information inequalities in the search for lower bounds in secret sharing. First, we prove that all information inequalities on a bounded number of variables can only provide lower bounds that are polynomial on the number of participants. Second, we prove that the rank inequalities that are derived from the existence of two common informations can provide only lower bounds that are at most cubic in the number of participants.

An encryption scheme should satisfy semantic security or indistinguishability of encryptions against chosen plaintext attack (IND-CPA). We propose an elliptic curve scheme over the ring /spl Zopf/(n/sup 2/), which is efficient and semantically secure in the standard model. It is based on factoring, and it has expansion factor 2 (previous schemes with these features present expansion factors greater than or equal to 4). Demytko's primitive has been used to obtain efficiency and probabilistic encryption. Semantic security of this scheme is based on a new decisional assumption, namely, the decisional small root assumption. Confidence in this assumption is also discussed.