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.     

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.     

Anonymous Membership Broadcast Schemes

A membership broadcast scheme is a method by which a dealer broadcasts a secret identity among a set of users, in such a way that only a single user is sure that he is the intended recipient. Anonymous membership broadcast schemes have several applications, such as anonymous delegation, cheating prevention, etc. In a w-anonymous membership broadcast scheme any coalition of at most w users, which does not include the user chosen by the dealer, has no information about the identity of the chosen user. Wang and Pieprzyk proposed a combinatorial approach to 1-anonymous membership broadcast schemes. In particular, they proposed a 1-anonymous membership broadcast scheme offering a logarithmic complexity for both communication and storage. However, their result is non-constructive. In this paper, we consider w-anonymous membership broadcast schemes. First, we propose a formal model to describe such schemes and show lower bounds on the communication and randomness complexities of the schemes. Afterwards, we show that w-anonymous membership broadcast schemes can be constructed starting from (w + 1)-wise independent families of permutations. The communication and storage complexities of our schemes are logarithmic in the number of users.     

On Some Methods for Unconditionally Secure Key Distribution and Broadcast Encryption

This paper provides an exposition of methods by which a trusted authority can distribute keys and/or broadcast a message over a network, so that each member of a privileged subset of users can compute a specified key or decrypt the broadcast message. Moreover, this is done in such a way that no coalition is able to recover any information on a key or broadcast message they are not supposed to know. The problems are studied using the tools of information theory, so the security provided is unconditional (i.e., not based on any computational assumption).We begin by surveying some useful schemes for key distribution that have been presented in the literature, giving background and examples (but not too many proofs). In particular, we look more closely at the attractive concept of key distribution patterns, and present a new method for making these schemes more efficient through the use of resilient functions. Then we present a general approach to the construction of broadcast schemes that combines key predistribution schemes with secret sharing schemes. We discuss the Fiat-Naor Broadcast Scheme, as well as other, new schemes that can be constructed using this approach.     

Some New Results on Key Distribution Patterns and Broadcast Encryption

This paper concerns methods by which a trusted authority can distribute keys and/or broadcast a message over a network, so that each member of a privileged subset of users can compute a specified key or decrypt the broadcast message. Moreover, this is done in such a way that no coalition is able to recover any information on a key or broadcast message they are not supposed to know. The problems are studied using the tools of information theory, so the security provided is unconditional (i.e., not based on any computational assumption).In a recent paper st95a, Stinson described a method of constructing key predistribution schemes by combining Mitchell-Piper key distribution patterns with resilient functions; and also presented a construction method for broadcast encryption schemes that combines Fiat-Naor key predistribution schemes with ideal secret sharing schemes. In this paper, we further pursue these two themes, providing several nice applications of these techniques by using combinatorial structures such as orthogonal arrays, perpendicular arrays, Steiner systems and universal hash families.     

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.     

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.     

A Public-Key Traitor Tracing Scheme with Revocation Using Dynamic Shares

We proposed a new public-key traitor tracing scheme with revocation capability using dynamic shares and entity revocation techniques. Our schemes traitor tracing and revocation programs cohere tightly. The size of the enabling block of our scheme is independent of the number of receivers. Each receiver holds one decryption key only. The distinct feature of our scheme is that when traitors are found, we can revoke their private keys (up to some threshold z) without updating the private keys of other receivers. In particular, no revocation messages are broadcast and all receivers do nothing. Previously proposed revocation schemes need update existing keys and entail large amount of broadcast messages. Our traitor tracing algorithm works in a black-box way. It is conceptually simple and fully k-resilient, that is, it can find all traitors if the number of them is k or less. The encryption algorithm of our scheme is semantically secure assuming that the decisional Diffie-Hellman problem is hard.AMS Classification: 11T71, 68P30     

On the Use of RSA as a Secret Key Cryptosystem

One fundamental difference between the use of symmetric and publickey cryptosystems is that the former requires trust between sender and receiver. Typically they will share a secret key and neitherhas any protection from the other. However, many users are nowfinding that they want keys to be used for 'one purpose only'and are relying on hardware functionality to introduce the conceptof unidirectional keys for symmetric algorithms. (So, for instance,the hardware functionality might ensure that a key used for encryptingmessages from user A to user B cannot be used for encrypting messages in the opposite direction.) For public key systems this concept of unidirectional keys is automatically satisfied. However,when the encrypting key is made public, the exposure of this key means that the deciphering key is only safe from compromise when the keys are very large. If, on the other hand, both keys were kept secret then it might be possible to use much smallerkeys. In this paper we investigate ways of using the primitives of an RSA public key cryptosystem in a symmetric key 'setting'i.e. where neither key is made public.     

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.      

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.     

On optimal arrangements of keys with double hashing

Given a set of n keys, the keys are arranged in a hash table of size n such that the worst-case retrieval time is minimized. It is shown that, when double hashing is used, one can, with probability 1 ? o(1), arrange the keys to achieve a worst-case retrieval time O(log n). This gives a solution to an open problem in Rivest (J. Assoc. Comput. Mach.25 (1978), 200–209).     

A key-lock-pair oriented access control scheme for the growth of users and files

A new access control scheme for the growth of users and files in file protection systems is proposed. Our scheme associates each user with a user key and each file with a file key. For each key, there are some corresponding locks, that can be extracted from a nonsingular matrix. Through simple operations on keys and locks, privacy decisions of the protection system can easily be revealed. Furthermore, by employing our method, whenever a new user or file is joined, the corresponding key values and lock values will be determined immediately without changing any previously defined keys and locks.     

An optimal algorithm to assign cryptographic keys in a tree structure for access control

In a computer communication system, there exists a possibility of two or more users collaborating to derive a key to which they are not entitled. Therefore, a method for ensuring the system is necessary. In this paper, we propose an efficient heuristic algorithm for assigning cryptographic keys among a group of users organized in a tree structure. Comparing with the existing assignment schemes, our scheme always produces economic cryptographic keys, which are smaller than the keys generated by the previous work in a tree structure.This work was supported in part by the National Science Council of the Republic of China under the grant NSC 81-0416-E-002-20.     

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.      

Models of Network Access Using Feedback Fluid Queues

At the access to networks, in contrast to the core, distances and feedback delays, as well as link capacities are small, which has network engineering implications that are investigated in this paper. We consider a single point in the access network which multiplexes several bursty users. The users adapt their sending rates based on feedback from the access multiplexer. Important parameters are the user's peak transmission rate p, which is the access line speed, the user's guaranteed minimum rate r, and the bound on the fraction of lost data. Two feedback schemes are proposed. In both schemes the users are allowed to send at rate p if the system is relatively lightly loaded, at rate r during periods of congestion, and at a rate between r and p, in an intermediate region. For both feedback schemes we present an exact analysis, under the assumption that the users' file sizes and think times have exponential distributions. We use our techniques to design the schemes jointly with admission control, i.e., the selection of the number of admissible users, to maximize throughput for given p, r and . Next we consider the case in which the number of users is large. Under a specific scaling, we derive explicit large deviations asymptotics for both models. We discuss the extension to general distributions of user data and think times.     

New Combinatorial Bounds for Authentication Codes and Key Predistribution Schemes

This paper provides new combinatorial bounds and characterizations of authentication codes (A-codes) and key predistribution schemes (KPS). We first prove a new lower bound on the number of keys in an A-code without secrecy, which can be thought of as a generalization of the classical Rao bound for orthogonal arrays. We also prove a new lower bound on the number of keys in a general A-code, which is based on the Petrenjuk, Ray-Chaudhuri and Wilson bound for t-designs. We also present new lower bounds on the size of keys and the amount of users' secret information in KPS, the latter of which is accomplished by showing that a certain A-code is hiding inside any KPS.     

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.     

Multiround Unconditionally Secure Authentication

Authentication codes are used to protect communication against a malicious adversary. In this paper we investigate unconditionally secure multiround authentication schemes. In a multiround scheme a message is authenticated by passing back and forth several codewords between the sender and receiver. We define a multiround authentication model and show how to calculate the probability of a successful attack for this model. We prove the security for a 3-round scheme and give a construction for the 3-round scheme based on Reed-Solomom codes. This construction has a very small key size for even extremely large messages. Furthermore, a secure scheme for an arbitrary number of rounds is given. We give a new upper bound for the keys size of an n-round scheme.     

On the mean number of encryptions for tree-based broadcast encryption schemes

The challenge of stateless-receiver broadcast encryption lies in minimizing storage and the number of encryptions while maintaining system security. Tree-based key distribution schemes offer the best known trade-off between the two parameters. Examples include the complete subtree scheme [D. Wallner, et al., Internet draft, http://www.ietf.org/ID.html [10]; C.K. Wong, et al., in: Proc. SIGCOMM, 1998, pp. 68–79 [11]], the subset difference scheme [D. Naor, et al., in: CRYPTO 2001, Lecture Notes in Comput. Sci., vol. 2139, 2001, pp. 41–62 [7]], and the layered subset difference scheme [D. Halevy, A. Shamir, in: CRYPTO 2002, Lecture Notes in Comput. Sci., vol. 2442, 2002, pp. 47–60 [5]]. We introduce generating functions for this family of schemes, which lead to analysis of the mean number of encryptions over all privileged sets of users. We also derive the mean number of encryptions when the number of privileged users is fixed. We expect that the techniques introduced as well as the results in this work will find applications in related areas.