Affiliation: University of Waterloo
KIST: A new encryption algorithm based on splay
In this paper, we proposed a new encryption algorithm called KIST. This algorithm uses an asynchronous key sequence and a splay tree. It is very efficient in the usage of both space and time. Some elementary security tests have been done.
Combinatorial batch codes
In this paper, we study batch codes, which were introduced by Ishai, Kushilevitz, Ostrovsky and Sahai. A batch code specifies a method to distribute a database of n items among m devices (servers) in such a way that any k items can be retrieved by reading at most t items from each of the servers. It is of interest to devise batch codes that minimize the total storage, denoted by N, over all m servers. In this paper, we study the special case t=1, under the assumption that every server stores a subset of the items. This is purely a combinatorial problem, so we call this kind of batch code a "combinatorial batch code''. For various parameter situations, we are able to present batch codes that are optimal with respect to the storage requirement, N. We also study uniform codes, where every item is stored in precisely c of the m servers (such a code is said to have rate 1/c). Interesting new results are presented in the cases c = 2, k-2 and k-1. In addition, we obtain improved existence results for arbitrary fixed c using the probabilistic method.
Comments on ``Distributed Symmetric Key Management for Mobile Ad hoc Networks" from INFOCOM 2004
In IEEE INFOCOM 2004, Chan proposed a distributed key management scheme for mobile ad hoc networks, and deduced the condition under which the key sets distributed to the network nodes can form a cover-free family (CFF), which is the precondition that the scheme can work. In this paper, we indicate that the condition is falsely deduced. Furthermore, we discuss whether CFF is capable for key distributions in ad hoc networks.
An Access Control Scheme for Partially Ordered Set Hierarchy with Provable Security
In a hierarchical structure, an entity has access to another if and only if the former is a superior of the later. The access control scheme for a hierarchy represented by a partially ordered set (poset) has been researched intensively in the past years. In this paper, we propose a new scheme that achieves the best performance of previous schemes and is provably secure under a comprehensive security model.
Combinatorial Properties of Frameproof and Traceability Codes
In order to protect copyrighted material, codes may be embedded in the content or codes may be associated with the keys used to recover the content. Codes can offer protection by providing some form of traceability for pirated data. Several researchers have studied different notions of traceability and related concepts in recent years. "Strong" versions of traceability allow at least one member of a coalition that constructs a "pirate decoder" to be traced. Weaker versions of this concept ensure that no coalition can "frame" a disjoint user or group of users. All these concepts can be formulated as codes having certain combinatorial properties. In this paper, we study the relationships between the various notions, and we discuss equivalent formulations using structures such as perfect hash families. We use methods from combinatorics and coding theory to provide bounds (necessary conditions) and constructions (sufficient conditions) for the objects of interest.
Constructions and Bounds for Unconditionally Secure Commitment Schemes
Commitment schemes have been extensively studied since they were introduced by Blum in 1982. Rivest recently showed how to construct unconditionally secure commitment schemes, assuming the existence of a trusted initializer. In this paper, we present a formal mathematical model for such schemes, and analyze their binding and concealing properties. In particular, we show that such schemes cannot be perfectly concealing: there is necessarily a small probability that Alice can cheat Bob by committing to one value but later revealing a different value. We prove several bounds on Alice's cheating probability, and present constructions of schemes that achieve optimal cheating probabilities. We also show a close link between commitment schemes and the classical ``affine resolvable designs''.