Secret sharing schemes with partial broadcast channels

In a conventional secret sharing scheme a dealer uses secure point-to-point channels to distribute the shares of a secret to a number of participants. At a later stage an authorised group of participants send their shares through secure point-to-point channels to a combiner who will reconstruct the secret. In this paper, we assume no point-to-point channel exists and communication is only through partial broadcast channels. A partial broadcast channel is a point-to-multipoint channel that enables a sender to send the same message simultaneously and privately to a fixed subset of receivers. We study secret sharing schemes with partial broadcast channels, called partial broadcast secret sharing schemes. We show that a necessary and sufficient condition for the partial broadcast channel allocation of a (t, n)-threshold partial secret sharing scheme is equivalent to a combinatorial object called a cover-free family. We use this property to construct a (t, n)-threshold partial broadcast secret sharing scheme with O(log n) partial broadcast channels. This is a significant reduction compared to n point-to-point channels required in a conventional secret sharing scheme. Next, we consider communication rate of a partial broadcast secret sharing scheme defined as the ratio of the secret size to the total size of messages sent by the dealer. We show that the communication rate of a partial broadcast secret sharing scheme can approach 1/O(log n) which is a significant increase over the corresponding value, 1/n, in the conventional secret sharing schemes. We derive a lower bound on the communication rate and show that for a (t,n)-threshold partial broadcast secret sharing scheme the rate is at least 1/t and then we propose constructions with high communication rates. We also present the case of partial broadcast secret sharing schemes for general access structures, discuss possible extensions of this work and propose a number of open problems.      

Design of Self-Healing Key Distribution Schemes

A self-healing key distribution scheme enables dynamic groups of users of an unreliable network to establish group keys for secure communication. In such a scheme, a group manager, at the beginning of each session, in order to provide a key to each member of the group, sends packets over a broadcast channel. Every user, belonging to the group, computes the group key by using the packets and some private information. The group manager can start multiple sessions during a certain time-interval, by adding/removing users to/from the initial group. The main property of the scheme is that, if during a certain session some broadcasted packet gets lost, then users are still capable of recovering the group key for that session simply by using the packets they have received during a previous session and the packets they will receive at the beginning of a subsequent one, without requesting additional transmission from the group manager. Indeed, the only requirement that must be satisfied, in order for the user to recover the lost keys, is membership in the group both before and after the sessions in which the broadcast messages containing the keys are sent. This novel and appealing approach to key distribution is quite suitable in certain military applications and in several Internet-related settings, where high security requirements need to be satisfied. In this paper we continue the study of self-healing key distribution schemes, introduced by Staddon et al. [37]. We analyze some existing constructions: we show an attack that can be applied to one of these constructions, in order to recover session keys, and two problems in another construction. Then, we present a new mechanism for implementing the self-healing approach, and we present an efficient construction which is optimal in terms of user memory storage. Finally, we extend the self-healing approach to key distribution, and we present a scheme which enables a user to recover from a single broadcast message all keys associated with sessions in which he is member of the communication group.     

Linear spaces and transversal designs: k-anonymous combinatorial configurations for anonymous database search notes

Anonymous database search protocols allow users to query a database anonymously. This can be achieved by letting the users form a peer-to-peer community and post queries on behalf of each other. In this article we discuss an application of combinatorial configurations (also known as regular and uniform partial linear spaces) to a protocol for anonymous database search, as defining the key-distribution within the user community that implements the protocol. The degree of anonymity that can be provided by the protocol is determined by properties of the neighborhoods and the closed neighborhoods of the points in the combinatorial configuration that is used. Combinatorial configurations with unique neighborhoods or unique closed neighborhoods are described and we show how to attack the protocol if such configurations are used. We apply k-anonymity arguments and present the combinatorial configurations with k-anonymous neighborhoods and with k-anonymous closed neighborhoods. The transversal designs and the linear spaces are presented as optimal configurations among the configurations with k-anonymous neighborhoods and k-anonymous closed neighborhoods, respectively.     

Establishing the broadcast efficiency of the Subset Difference Revocation Scheme

When an organisation chooses a system to make regular broadcasts to a changing user base, there is an inevitable trade off between the number of keys a user must store and the number of keys used in the broadcast. The Complete Subtree and Subset Difference Revocation Schemes were proposed as efficient solutions to this problem. However, all measurements of the broadcast size have been in terms of upper bounds on the worst-case. Also, the bound on the latter scheme is only relevant for small numbers of revoked users, despite the fact that both schemes allow any number of such users. Since the broadcast size can be critical for limited memory devices, we aid comparative analysis of these important techniques by establishing the worst-case broadcast size for both revocation schemes.      

Generalized Fibonacci broadcasting: An efficient VOD scheme with user bandwidth limit

Broadcasting is attractive in delivering popular videos in video-on-demand service, because the server broadcast bandwidth is independent of the number of users. However, the required server bandwidth does depend on how much bandwidth each user can use, as well as on the user's initial waiting time. This paper addresses the issue of limiting the user bandwidth, and proposes a new broadcasting scheme, named Generalized Fibonacci Broadcasting (GFB). In terms of many performance graphs, we show that, for any given combination of the server bandwidth and user bandwidth, GFB can achieve the least waiting time among all the currently known fixed-delay broadcasting schemes. Furthermore, it is very easy to implement GFB. We also demonstrate that there is a trade-off between the user waiting time and the buffer requirement at the user.     

Revocable hierarchical identity-based encryption with shorter private keys and update keys

Revocable hierarchical identity-based encryption (RHIBE) is an extension of HIBE that supports the revocation of user’s private keys to manage the dynamic credentials of users in a system. Many different RHIBE schemes were proposed previously, but they are not efficient in terms of the private key size and the update key size since the depth of a hierarchical identity is included as a multiplicative factor. In this paper, we propose efficient RHIBE schemes with shorter private keys and update keys and small public parameters by removing this multiplicative factor. To achieve our goals, we first present a new HIBE scheme with the different generation of private keys such that a private key can be simply derived from a short intermediate private key. Next, we show that two efficient RHIBE schemes can be built by combining our HIBE scheme, an IBE scheme, and a tree based broadcast encryption scheme in a modular way.     

Properties and constraints of cheating-immune secret sharing schemes

A secret sharing scheme is a cryptographic protocol by means of which a dealer shares a secret among a set of participants in such a way that it can be subsequently reconstructed by certain qualified subsets. The setting we consider is the following: in a first phase, the dealer gives in a secure way a piece of information, called a share, to each participant. Then, participants belonging to a qualified subset send in a secure way their shares to a trusted party, referred to as a combiner, who computes the secret and sends it back to the participants.Cheating-immune secret sharing schemes are secret sharing schemes in the above setting where dishonest participants, during the reconstruction phase, have no advantage in sending incorrect shares to the combiner (i.e., cheating) as compared to honest participants. More precisely, a coalition of dishonest participants, by using their correct shares and the incorrect secret supplied by the combiner, have no better chance in determining the true secret (that would have been reconstructed if they submitted correct shares) than an honest participant.In this paper we study properties and constraints of cheating-immune secret sharing schemes. We show that a perfect secret sharing scheme cannot be cheating-immune. Then, we prove an upper bound on the number of cheaters tolerated in such schemes. We also repair a previously proposed construction to realize cheating-immune secret sharing schemes. Finally, we discuss some open problems.     

Signcryption schemes with threshold unsigncryption,and applications

The goal of a signcryption scheme is to achieve the same functionalities as encryption and signature together, but in a more efficient way than encrypting and signing separately. To increase security and reliability in some applications, the unsigncryption phase can be distributed among a group of users, through a (t, n)-threshold process. In this work we consider this task of threshold unsigncryption, which has received very few attention from the cryptographic literature up to now (maybe surprisingly, due to its potential applications). First we describe in detail the security requirements that a scheme for such a task should satisfy: existential unforgeability and indistinguishability, under insider chosen message/ciphertext attacks, in a multi-user setting. Then we show that generic constructions of signcryption schemes (by combining encryption and signature schemes) do not offer this level of security in the scenario of threshold unsigncryption. For this reason, we propose two new protocols for threshold unsigncryption, which we prove to be secure, one in the random oracle model and one in the standard model. The two proposed schemes enjoy an additional property that can be very useful. Namely, the unsigncryption protocol can be divided in two phases: a first one where the authenticity of the ciphertext is verified, maybe by a single party; and a second one where the ciphertext is decrypted by a subset of t receivers, without using the identity of the sender. As a consequence, the schemes can be used in applications requiring some level of anonymity, such as electronic auctions.     

Gruppen secret sharing or how to share several secrets if you must?

Each member of an n-person team has a secret, say a password. The k out of n gruppen secret sharing requires that any group of k members should be able to recover the secrets of the other n ? k members, while any group of k ? 1 or less members should have no information on the secret of other team member even if other secrets leak out. We prove that when all secrets are chosen independently and have size s, then each team member must have a share of size at least (n ? k)s, and we present a scheme which achieves this bound when s is large enough. This result shows a significant saving over n independent applications of Shamir’s k out of n ? 1 threshold schemes which assigns shares of size (n ? 1)s to each team member independently of k. We also show how to set up such a scheme without any trusted dealer, and how the secrets can be recovered, possibly multiple times, without leaking information. We also discuss how our scheme fits to the much-investigated multiple secret sharing methods.     

Bottleneck routing with elastic demands

Bottleneck routing games are a well-studied model to investigate the impact of selfish behavior in communication networks. In this model, each user selects a path in a network for routing her fixed demand. The disutility of a user only depends on the most congested link visited. We extend this model by allowing users to continuously vary the demand rate at which data is sent along the chosen path. As our main result we establish tight conditions for the existence of pure strategy Nash equilibria.     

Centralized and decentralized management of groundwater with multiple users

In this work, we investigate two groundwater inventory management schemes with multiple users in a dynamic game-theoretic structure: (i) under the centralized management scheme, users are allowed to pump water from a common aquifer with the supervision of a social planner, and (ii) under the decentralized management scheme, each user is allowed to pump water from a common aquifer making usage decisions individually in a non-cooperative fashion. This work is motivated by the work of Saak and Peterson [14], which considers a model with two identical users sharing a common aquifer over a two-period planning horizon. In our work, the model and results of Saak and Peterson [14] are generalized in several directions. We first build on and extend their work to the case of n non-identical users distributed over a common aquifer region. Furthermore, we consider two different geometric configurations overlying the aquifer, namely, the strip and the ring configurations. In each configuration, general analytical results of the optimal groundwater usage are obtained and numerical examples are discussed for both centralized and decentralized problems.     

Unconditionally secure key assignment schemes

In this paper we propose an information-theoretic approach to the access control problem in a scenario where a group of users is divided into a number of disjoint classes. The set of rules that specify the information flow between different user classes in the system defines an access control policy. An access control policy can be implemented by using a key assignment scheme, where a trusted central authority (CA) assigns an encryption key and some private information to each class.We consider key assignment schemes where the key assigned to each class is unconditionally secure with respect to an adversary controlling a coalition of classes of a limited size. Our schemes are characterized by a security parameter r, the size of the adversary coalition. We show lower bounds on the size of the private information that each class has to store and on the amount of randomness needed by the CA to set up any key assignment scheme. Finally, we propose some optimal constructions for unconditionally secure key assignment schemes.     

Polynomial-time algorithm for fixed points of nontrivial morphisms

A word w is a fixed point of a nontrivial morphism h if w=h(w) and h is not the identity on the alphabet of w. The paper presents the first polynomial algorithm deciding whether a given finite word is such a fixed point. The algorithm also constructs the corresponding morphism, which has the smallest possible number of non-erased letters.     

Classification of subsets with minimal width and dual width in Grassmann, bilinear forms and dual polar graphs

Brouwer, Godsil, Koolen and Martin [Width and dual width of subsets in polynomial association schemes, J. Combin. Theory Ser. A 102 (2003) 255-271] introduced the width w and the dual width w^* of a subset in a distance-regular graph and in a cometric association scheme, respectively, and then derived lower bounds on these new parameters. For instance, subsets with the property w+w^*=d in a cometric distance-regular graph with diameter d attain these bounds. In this paper, we classify subsets with this property in Grassmann graphs, bilinear forms graphs and dual polar graphs. We use this information to establish the Erd?s-Ko-Rado theorem in full generality for the first two families of graphs.     

An incentive charging scheme for video-on-demand

Video-on-demand (VOD) systems can provide either an individual service or batch service. For individual service, a user can receive video immediately after making a request and he/she can perform interactive operations (such as pause, jump, fast forward and rewind), and the system uses one video stream to serve one user. For batch service, a user has to wait after making a request and cannot perform interactive operations, but the system can use one video stream to serve a batch of users. Therefore, individual service has a better quality while batch service requires less resources to serve each user. In this paper, we consider a VOD system providing both services and propose an incentive charging scheme to optimize the coexistence of both services. This scheme imposes a lower service charge on batch service in order to attract users to choose this service. Consequently, the service provider can get more revenue by serving more concurrent users via batch service and users can choose their preferred services. We analyze the incentive charging scheme and maximize the mean revenue subject to a given availability specification. The numerical results show that the incentive charging scheme is particularly effective in peak hours when the demand for the VOD service is large.     

Sequential and dynamic frameproof codes

There are many schemes in the literature for protecting digital data from piracy by the use of digital fingerprinting, such as frameproof codes and traitor-tracing schemes. The concept of traitor-tracing has been applied to a digital broadcast setting in the form of dynamic traitor-tracing schemes and sequential traitor-tracing schemes, which could be used to combat piracy of pay-TV broadcasts, for example. In this paper, we extend the properties of frameproof codes to this dynamic model, defining and constructing both l-sequential c-frameproof codes and l-dynamic c-frameproof codes. We also give bounds on the number of users supported by such schemes.      

Hypergraph decomposition and secret sharing

A secret sharing scheme is a protocol by which a dealer distributes a secret among a set of participants in such a way that only qualified sets of them can reconstruct the value of the secret whereas any non-qualified subset of participants obtain no information at all about the value of the secret. Secret sharing schemes have always played a very important role for cryptographic applications and in the construction of higher level cryptographic primitives and protocols.In this paper we investigate the construction of efficient secret sharing schemes by using a technique called hypergraph decomposition, extending in a non-trivial way the previously studied graph decomposition techniques. A major advantage of hypergraph decomposition is that it applies to any access structure, rather than only structures representable as graphs. As a consequence, the application of this technique allows us to obtain secret sharing schemes for several classes of access structures (such as hyperpaths, hypercycles, hyperstars and acyclic hypergraphs) with improved efficiency over previous results. Specifically, for these access structures, we present secret sharing schemes that achieve optimal information rate. Moreover, with respect to the average information rate, our schemes improve on previously known ones.In the course of the formulation of the hypergraph decomposition technique, we also obtain an elementary characterization of the ideal access structures among the hyperstars, which is of independent interest.     

Efficient revocable identity-based encryption via subset difference methods

Providing an efficient revocation mechanism for identity-based encryption (IBE) is very important since a user’s credential (or private key) can be expired or revealed. revocable IBE (RIBE) is an extension of IBE that provides an efficient revocation mechanism. Previous RIBE schemes essentially use the complete subtree (CS) scheme of Naor, Naor and Lotspiech (CRYPTO 2001) for key revocation. In this paper, we present a new technique for RIBE that uses the efficient subset difference (SD) scheme of Naor et al. instead of using the CS scheme to improve the size of update keys. Following our new technique, we first propose an efficient RIBE scheme in prime-order bilinear groups by combining the IBE scheme of Boneh and Boyen and the SD scheme and prove its selective security under the standard assumption. Our RIBE scheme is the first RIBE scheme in bilinear groups that has O(r) number of group elements in an update key where r is the number of revoked users. Next, we also propose another RIBE scheme in composite-order bilinear groups and prove its full security under static assumptions. Our RIBE schemes also can be integrated with the layered subset difference scheme of Halevy and Shamir (CRYPTO 2002) to reduce the size of a private key.     

Complete tree subset difference broadcast encryption scheme and its analysis

The subset difference (SD) method proposed by Naor, Naor and Lotspiech is the most popular broadcast encryption (BE) scheme. It is suitable for real-time applications like Pay-TV and has been suggested for use by the AACS standard for digital rights management in Blu-Ray and HD-DVD discs. The SD method assumes the number of users to be a power of two. We propose the complete tree subset difference (CTSD) method that allows the system to support an arbitrary number of users. In particular, it subsumes the SD method and all results proved for the CTSD method also hold for the SD method. Recurrences are obtained for the CTSD scheme to count the number, N(n, r, h), of possible ways r users in the system of n users can be revoked to result in a transmission overhead or header length of h. The recurrences lead to a polynomial time dynamic programming algorithm for computing N(n, r, h). Further, they provide bounds on the maximum possible header length. A probabilistic analysis is performed to obtain an O(r log n) time algorithm to compute the expected header length in the CTSD scheme. Further, for the SD scheme we obtain an explicit limiting upper bound on the expected header length.     

On threshold schemes from large sets

An anonymous (t, w)-threshold scheme is one of the schemes for secret sharing. Combinatorial designs and especially large sets of Steiner systems and of Steiner systems “with holes” have an important role in the design of perfect (t, w)-threshold schemes. In this article we investigate perfect (4, 4)-threshold schemes. We use large sets to form such systems with a large number of keys. In particular we construct the first known infinite families of large sets of H-designs with block size 4. © 1996 John Wiley & Sons, Inc.