Lower bounds on the information rate of secret sharing schemes with homogeneous access structure

We present some new lower bounds on the optimal information rate and on the optimal average information rate of secret sharing schemes with homogeneous access structure. These bounds are found by using some covering constructions and a new parameter, the k-degree of a participant, that is introduced in this paper. Our bounds improve the previous ones in almost all cases.     

A note on secret sharing schemes with three homogeneous access structure

A secret sharing scheme is a method which allows a secret to be shared among a set of participants in such a way that only qualified subsets of participants can recover the secret. The characterization of ideal access structures and the search for bounds on the optimal information rate are two important problems in secret sharing. This paper deals with these problems for 3-homogeneous access structures, that is, whenever the minimal qualified subsets have exactly three participants.     

Strongly secure ramp secret sharing schemes for general access structures

Ramp secret sharing (SS) schemes can be classified into strong ramp SS schemes and weak ramp SS schemes. The strong ramp SS schemes do not leak out any part of a secret explicitly even in the case that some information about the secret leaks out from some set of shares, and hence, they are more desirable than the weak ramp SS schemes. In this paper, it is shown that for any feasible general access structure, a strong ramp SS scheme can be constructed from a partially decryptable ramp SS scheme, which can be considered as a kind of SS scheme with plural secrets. As a byproduct, it is pointed out that threshold ramp SS schemes based on Shamir's polynomial interpolation method are not always strong.     

Attack on a concast signature scheme

Al-Ibrahim, Ghodosi and Pieprzyk proposed several methods of batch signature verification suitable for concast communication. These schemes are all based on El-Gamal-type signature schemes. We prove that their preferred scheme, which does not require interaction among the various signers, is insecure.     

Protocols useful on the Internet from distributed signature schemes

Distributed cryptography deals with scenarios where a cryptographic operation is performed by a collective of persons. In a distributed signature scheme, a group of players share some secret information in such a way that only authorized subsets of players can compute valid signatures. We propose methods to construct some computationally secure protocols from distributed signature schemes, namely, we construct metering schemes from distributed noninteractive signature schemes. We also show that distributed deterministic signature schemes can be used to design distributed key distribution schemes. In particular, we construct the first metering and distributed key distribution schemes based on the RSA primitive.     

A note on optimal metering schemes

A metering scheme is a method by which an audit agency is able to measure the interaction between servers (e.g., web servers) and clients (e.g., browsers) during a certain number of time frames. Metering schemes involve distributing information to clients and servers. Obviously, such information distribution affects the overall communication complexity. A metering scheme is said to be optimal if the information distributed to clients and servers is the minimum possible.Optimal metering schemes have been proposed by Naor and Pinkas [Lecture Notes in Comput. Sci., Vol. 1403, pp. 576-590] and Masucci and Stinson [Lecture Notes in Comput. Sci., Vol. 1895, pp. 72-87). In this paper we show a construction for optimal metering schemes, called the vector space construction, that generalizes previous constructions for optimal metering schemes.     

Breaking the Shin-Shin-Rhee remotely keyed encryption schemes

Remotely keyed encryption (RKE) schemes provide fast symmetric encryption and decryption using a small-bandwidth security module and a powerful host. Such schemes keep the key inside the security module to prevent key compromise.Shin, Shin, and Rhee proposed a length-preserving as well as a length-increasing RKE scheme that both use only a single round of interaction between host and security module. With the length-preserving scheme they claim to answer an open problem of Blaze, Feigenbaum, and Naor.However, in the present paper we show that both their schemes are completely insecure. Further, we present heuristic arguments on why a one-round length-preserving RKE scheme might be impossible.     

Universal routing schemes

Summary.  In this paper, we deal with the compact routing problem, that is implementing routing schemes that use a minimum memory size on each router. A universal routing scheme is a scheme that applies to all n-node networks. In [31], Peleg and Upfal showed that one cannot implement a universal routing scheme with less than a total of Ω(n ^1+1/(2s+4)) memory bits for any given stretch factor s≧1. We improve this bound for stretch factors s, 1≦s<2, by proving that any near-shortest path universal routing scheme uses a total of Ω(n ²) memory bits in the worst-case. This result is obtained by counting the minimum number of routing functions necessary to route on all n-node networks. Moreover, and more fundamentally, we give a tight bound of Θ(n log n) bits for the local minimum memory requirement of universal routing scheme of stretch factors s, 1≦s<2. More precisely, for any fixed constant ɛ, 0<ɛ<1, there exists a n-node network G on which at least Ω(n ^ɛ) routers require Θ(n log n) bits each to code any routing function on G of stretch factor <2. This means that, whatever you choose the routing scheme, there exists a network on which one cannot compress locally the routing information better than routing tables do. Received: August 1995 / Accepted: August 1996     

Proxy signature schemes based on factoring

The proxy signature schemes allow proxy signers to sign messages on behalf of an original signer, a company or an organization. However, most of existing proxy signature schemes are based on the discrete logarithm problem. In this paper, the author would like to propose two efficient proxy signature schemes based on the factoring problem, which combine the RSA signature scheme and the Guillou-Quisquater signature scheme. One is a proxy-unprotected signature scheme that is more efficient. No matter how many proxy signers cooperatively sign a message, the computation load for verifiers would remain almost constant. The other is a proxy-protected signature scheme that is more secure. Finally, to protect the privacy of proxy signers, the author proposes a proxy-protected signature scheme with anonymous proxy signers.     

Reactively secure signature schemes

Protocols for problems like Byzantine agreement, clock synchronization, or contract signing often use digital signatures as the only cryptographic operation. Proofs of such protocols are frequently based on an idealizing “black-box” model of signatures. We show that the standard cryptographic security definition for digital signatures is not sufficient to ensure that such proofs are still valid if the idealized signatures are implemented with real, provably secure signatures. We propose a definition of signature security suitable for general reactive, asynchronous environments, called reactively secure signature schemes, and prove that, for signature schemes where signing just depends on a counter as state, the standard security definition implies our definition. We further propose an idealization of digital signatures that can be used in a reactive and composable fashion, and we show that reactively secure signature schemes constitute a secure implementation of our idealization.