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.     

Linear Key Predistribution Schemes

In a key predistribution scheme, some secret information is distributed among a set of users. For a given family of privileged groups, this secret information must enable every user in a privileged group to compute a common key associated with that group. Besides, this common key must remain unknown to some specified coalitions of users outside the privileged group. We present in this paper a new model, based on linear algebraic techniques, for the design of key predistribution schemes that unifies all previous proposals. This new model provides a common mathematical formulation and a better understanding of key predistribution schemes. Two new families of key predistribution schemes that are obtained by using this model are presented. Those families provide, for some specification structures, schemes that have better information rates than the ones given in previous proposals or fit in situations that have not been considered before.     

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.     

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.     

Key predistribution schemes for distributed sensor networks via block designs

Key predistribution schemes for distributed sensor networks have received significant attention in the recent literature. In this paper we propose a new construction method for these schemes based on combinations of duals of standard block designs. Our method is a broad spectrum one which works for any intersection threshold. By varying the initial designs, we can generate various schemes and this makes the method quite flexible. We also obtain explicit algebraic expressions for the metrics for local connectivity and resiliency. These schemes are quite efficient with regard to connectivity and resiliency and at the same time they allow a straightforward shared-key discovery.     

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.     

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 the complexity of some arborescences finding problems on a multihop radio network

An arborescence of a multihop radio network is a directed spanning tree (with rootx) such that the edges are directed away from the root. Based upon an arborescence,x canbroadcast a message to other nodes according to the directed edges of the spanning tree. The minimum transmission power arborescence problem is to find an arborescence such that the message can be broadcasted to other nodes by using a minimal amount of transmission power. The minimum delay arborescence problem is to find an arborescence such that a message can be broadcasted to other nodes by using a minimal number of broadcast transmission. In this paper we show that both these problems areNP-complete. The reductions are from the maximum leaf spanning tree problem.Areverse arborescence is similar to an arborescence except that the edges are directed toward the root. Based upon a reverse arborescence, the root node cancollect information from other nodes. In this paper we also show that the reverse minimum transmission power arborescence problem can be solved with the same computational complexity as that of finding a minimum cost spanning tree, and the reverse minimum delay arborescence problem can be solved with the same computational complexity as that of finding a spanning tree.     

Message Recovery for Signature Schemes Based on the Discrete Logarithm Problem

The new signature scheme presented by the authors in [13] is the first signature scheme based on the discrete logarithm problem that gives message recovery. The purpose of this paper is to show that the message recovery feature is independent of the choice of the signature equation and that all ElGamal-type schemes have variants giving message recovery. For each of the six basic ElGamal-type signature equations five variants are presented with different properties regarding message recovery, length of commitment and strong equivalence. Moreover, the six basic signature schemes have different properties regarding security and implementation. It turns out that the scheme proposed in [13] is the only inversionless scheme whereas the message recovery variant of the DSA requires computing of inverses in both generation and verification of signatures. In general, message recovery variants can be given for ElGamal-type signature schemes over any group with large cyclic subgroup as the multiplicative group of GF(2n) or elliptic curve over a finite field.The present paper also shows how to integrate the DLP-based message recovery schemes with secret session key establishment and ElGamal encryption. In particular, it is shown that with DLP-based schemes the same functionality as with RSA can be obtained. However, the schemes are not as elegant as RSA in the sense that the signature (verification) function cannot at the same time be used as the decipherment (encipherment) function.     

Minimum broadcast tree decompositions

Recursive constructions for decomposing the complete directed graph D_n into minimum broadcast trees of order n are given, thereby showing the existence of such decompositions for all n. Such decompositions can be used for a routing system in a network where every participant has the ability to broadcast a message to the group; as each arc is used in only one tree, a participant’s further actions upon receipt of a message depend only on its sender, and so all routing information can be stored locally rather than in the message itself.     

树网络上f模式最优广播问题的线性算法

网络G的一个结点v上的一次广播是指从它将一个消息传递给若干相邻结点.所谓f模式广播,是指结点v在一次广播中至多向f(v)个相邻结点传递信息(f为给定的整值函数).假定每一次广播的执行时间为一单位.网络G的广播过程是广播的时间安排,使所有结点均获得消息.最优广播问题是求总时间最少的广播过程.在G是树网络情形,文献中已给出时间界为O(n2)的算法.本文给出线性时间的简捷算法.     

A minimum broadcast graph on 26 vertices

Broadcasting is the process of information dissemination in a communication network in which a message, originated by one member, is transmitted to all members of the network. A broadcast graph is a graph which permits broadcasting from any originator in minimum time. The broadcast function B(n) is the minimum number of edges in any broadcast graph on n vertices. In this paper, we construct a broadcast graph on 26 vertices with 42 edges to prove B(26) = 42.     

A switch-modulated method for chaos digital secure communication based on user-defined protocol

In this paper, a scheme for digital secure communication is proposed. In this scheme, we use a control function which is defined by two communicants based on chaos synchronization. At first, different signals are sent according to the promissory transmission situation of control signal, then transmission field which is consist of protocol and transmission content is produced. After these processing, the correlation of the transmitted signals are decreased. In addition, the using of the compound non-linear function transformation can further intercalate the secret key, so a determined intruder is very difficult to retrieve the message using forecasting method.     

Lattice-based completely non-malleable public-key encryption in the standard model

An encryption scheme is non-malleable if giving an encryption of a message to an adversary does not increase its chances of producing an encryption of a related message (under a given public key). Fischlin introduced a stronger notion, known as complete non-malleability, which requires attackers to have negligible advantage, even if they are allowed to transform the public key under which the related message is encrypted. Ventre and Visconti later proposed a comparison-based definition of this security notion, which is more in line with the well-studied definitions proposed by Bellare et al. The authors also provide additional feasibility results by proposing two constructions of completely non-malleable schemes, one in the common reference string model using non-interactive zero-knowledge proofs, and another using interactive encryption schemes. Therefore, the only previously known completely non-malleable (and non-interactive) scheme in the standard model, is quite inefficient as it relies on generic NIZK approach. They left the existence of efficient schemes in the common reference string model as an open problem. Recently, two efficient public-key encryption schemes have been proposed by Libert and Yung, and Barbosa and Farshim, both of them are based on pairing identity-based encryption. At ACISP 2011, Sepahi et al. proposed a method to achieve completely non-malleable encryption in the public-key setting using lattices but there is no security proof for the proposed scheme. In this paper we review the mentioned scheme and provide its security proof in the standard model. Our study shows that Sepahi’s scheme will remain secure even for post-quantum world since there are currently no known quantum algorithms for solving lattice problems that perform significantly better than the best known classical (i.e., non-quantum) algorithms.     

Generalised Cumulative Arrays in Secret Sharing

Cumulative arrays have played an important role in the early development of the secret sharing theory. They have not been subject to extensive study so far, as the secret sharing schemes built on them generally result in much larger sizes of shares, when compared with other conventional approaches. Recent works in threshold cryptography show that cumulative arrays may be the appropriate building blocks in non-homomorphic threshold cryptosystems where the conventional secret sharing methods are generally of no use. In this paper we study several extensions of cumulative arrays and show that some of these extensions significantly improve the performance of conventional cumulative arrays. In particular, we derive bounds on generalised cumulative arrays and show that the constructions based on perfect hash families are asymptotically optimal. We also introduce the concept of ramp perfect hash families as a generalisation of perfect hash families for the study of ramp secret sharing schemes and ramp cumulative arrays.     

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.      

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.      

Approximation algorithms for minimum broadcast schedule problem in wireless sensor networks

A wireless sensor network usually consists of a large number of sensor nodes deployed in a field. One of the major communication operations is to broadcast a message from one node to the rest of the others. In this paper, we adopt the conflict-free communication model and study how to compute a transmission schedule that determines when and where a node should forward the message so that all nodes could receive the message in minimum time. We give two approximation algorithms for this NP-hard problem that have better theoretically guaranteed performances than the existing algorithms. The proposed approach could be applied to some other similar problems.     

Novel generic construction of leakage-resilient PKE scheme with CCA security

Leakage of private state information (e.g. the secret keys) through various leakage attacks (e.g. side channel attacks, cold-boot attacks, etc) has become a serious threat to the security of computer systems in practice. Nowadays, it has become a common requirement that cryptographic schemes should withstand the leakage attacks. Although some research progresses have been made towards designing leakage-resilient cryptographic schemes, there are still some unsolved issues. For example, the computational costs of the existing generic construction of leakage-resilient public-key encryption (PKE) schemes is generally very high. One of the main reasons is that the underlying building blocks, e.g. non-interactive zero-knowledge argument, one-time lossy filter or one-time signature, are computationally expensive. Moreover, the above constructions of PKE with leakage resilience normally require the upper bound of leakage to be fixed. However, in many real-world applications, this requirement cannot provide sufficient protection against various leakage attacks. In order to mitigate the above problems, this paper presents a generic method of designing leakage amplified PKE schemes with leakage resilience and chosen-ciphertext attacks (CCA) security. Firstly, we define a new cryptography primitive, called identity-based hash proof system with two encapsulated key (T-IB-HPS). Then, two generic constructions of leakage-resilient PKE schemes are proposed using T-IB-HPS and message authentication code (MAC). The CCA security of our proposed constructions can be reduced to the security of the underlying T-IB-HPS and MAC. In the proposed generic method, the leakage parameter has an arbitrary length that can be flexibly adjusted according to the specific leakage requirements. In order to demonstrate the practicability of our generic method, two instantiations of T-IB-HPS are introduced. The first instantiation is proved based on the truncated augmented bilinear Diffie–Hellman exponent assumption, and the second instantiation is proved based on the related security assumptions over the composite order bilinear group.