We initiate the study of λ-fold near-factorizations of groups with λ>1. While λ-fold near-factorizations of groups with λ=1 have been studied in numerous papers, this is the first detailed treatment for λ>1. We establish fundamental properties of λ-fold near-factorizations and introduce the notion of equivalence. We prove various necessary conditions of λ-fold near-factorizations, including upper bounds on λ. We present three constructions of infinite families of λ-fold near-factorizations, highlighting the characterization of two subfamilies of λ-fold near-factorizations. We discuss a computational approach to λ-fold near-factorizations and tabulate computational results for abelian groups of small order.

Abstract In situations where every item in a data set must be compared with every other item in the set, it may be desirable to store the data across a number of machines in such a way that any two data items are stored together on at least one machine. One way to evaluate the efficiency of such a distribution is by the largest fraction of the data it requires to be allocated to any one machine. The all-to-all comparison (ATAC) data limit formmachines is a measure of the minimum of this value across all possible such distributions. In this paper we further the study of ATAC data limits. We begin by investigating the data limits achievable using various classes of combinatorial designs. In particular, we examine the cases of transversal designs and projective Hjelmslev planes. We then observe relationships between data limits and the previously studied combinatorial parameters of fractional matching numbers and covering numbers. Finally, we prove a lower bound on the ATAC data limit that improves on one of Hall, Kelly and Tian, and examine the special cases where equality in this bound is possible.

Non-overlapping codes have been studied for almost 60 years. In such a code, no proper, non-empty prefix of any codeword is a suffix of any codeword. In this paper, we study codes in which over-laps of certain specified sizes are forbidden. We prove some general bounds and we give several constructions in the case of binary codes. Our techniques also allow us to provide an alternative, elementary proof of a lower bound on non-overlapping codes due to Levenshtein [9] in 1964.

In this paper, I look back at my career as a mathematician and mathematical cryptographer, mainly concentrating on my student days and the early parts of my career. I also discuss my research philosophy and what I mean by the term “combinatorial cryptography.” Along the way, I recall some influential people, books and papers.

A (t, s, v)-all-or-nothing transform (AONT) is a bijective mapping defined on s-tuples over an alphabet of size v, which satisfies the condition that the values of any t input co-ordinates are completely undetermined, given only the values of any s - t output co-ordinates. The main question we address in this paper is: for which choices of parameters does a (t, s, v)-AONT exist? More specifically, if we fix t and v, we want to determine the maximum integer s such that a (t, s, v)-AONT exists. We mainly concentrate on the case t = 2 for arbitrary values of v, where we obtain various necessary as well as sufficient conditions for existence of these objects. This includes computer searches that establish the existence of (2, q, q)-AONT for all odd primes not exceeding 29. We also show some connections between AONT, orthogonal arrays, and resilient functions.

There have been numerous recent proposals for key predistribution schemes for wireless sensor networks based on various types of combinatorial structures such as designs and codes. Many of these schemes have very similar properties and are analysed in a similar manner. We seek to provide a unified framework to study these kinds of schemes. To do so, we define a new, general class of designs, termed “partially balanced t -designs”, that is sufficiently general that it encompasses almost all of the designs that have been proposed for combinatorial key predistribution schemes. However, this new class of designs still has sufficient structure that we are able to derive general formulas for the metrics of the resulting key predistribution schemes. These metrics can be evaluated for a particular scheme simply by substituting appropriate parameters of the underlying combinatorial structure into our general formulas. We also compare various classes of schemes based on different designs, and point out that some existing proposed schemes are in fact identical, even though their descriptions may seem different. We believe that our general framework should facilitate the analysis of proposals for combinatorial key predistribution schemes and their comparison with existing schemes, and also allow researchers to easily evaluate which scheme or schemes present the best combination of performance metrics for a given application scenario.

We present a formalisation of a category of schemes that we refer to as broadcast-enhanced key predistribution schemes (BEKPSs). These schemes are suitable for networks with access to a trusted base station and an authenticated broadcast channel. We demonstrate that the access to these extra resources allows for the creation of BEKPSs with advantages over key predistribution schemes such as flexibility and more efficient revocation. There are many possible ways to implement BEKPSs, and we propose a framework for describing and analysing them. In their paper “From Key Predistribution to Key Redistribution,” Cichoń et al. [2010] propose a scheme for “redistributing” keys to a wireless sensor network using a broadcast channel after an initial key predistribution. We classify this as a BEKPS and analyse it in that context. We provide simpler proofs of some results from their paper, give a precise analysis of the resilience of their scheme, and discuss possible modifications. We then study two scenarios where BEKPSs may be particularly desirable and propose a suitable family of BEKPSs for each case. We demonstrate that they are practical and efficient to implement, and our analysis shows their effectiveness in achieving suitable trade-offs between the conflicting priorities in resource-constrained networks.

We first review the notion of social secret sharing and its trust function. We then illustrate how this construction can be used in cloud computing to create a self-organizing environment. In fact, we show distributed secure systems using threshold secret sharing can be adjusted automatically based on the resource availability of the cloud providers. Accordingly, we propose a new trust function with social characteristics in order to improve the existing social secret sharing scheme.

In this paper, we propose a security model to capture active attacks against multipath key establishment (MPKE) in sensor networks. Our model strengthens previous models to capture more attacks and achieve essential security goals for multipath key establishment. In this model, we can apply protocols for perfectly secure message transmission to solve the multipath key establishment problem. We propose a simple new protocol for optimal one-round perfectly secure message transmission based on Reed-Solomon codes. Then, we use this protocol to obtain two new multipath key establishment schemes that can be applied provided that fewer than one-third of the paths are controlled by the adversary. Finally, we describe another MPKE scheme that tolerates a higher fraction (less than half) of paths controlled by the adversary. This scheme is based on a new protocol for a weakened version of message transmission, which is very simple and efficient. Our multipath key establishment schemes achieve improved security and lower communication complexity, as compared to previous schemes.

We introduce the notion of a social secret sharing scheme, in which shares are allocated based on a player's reputation and the way he interacts with other participants. During the social tuning phase, weights of players are adjusted such that participants who cooperate will end up with more shares than those who defect.

The authors introduce the notion of a ‘social secret sharing scheme’, in which shares are allocated based on a player's reputation and the way he/she interacts with other participants. During the social tuning phase, weights of players are adjusted such that participants who cooperate will end up with more shares than those who defect. Alternatively, newcomers are able to be enrolled in the scheme while corrupted players are disenrolled immediately. In other words, this scheme proactively renews shares at each cycle without changing the secret, and allows trusted participants to gain more authority. The motivation is that, in real-world applications, components of a secure scheme may have different levels of importance (i.e. the number of shares a player has) as well as reputation (i.e. cooperation with other players for the share renewal or secret recovery). Therefore a good construction should balance these two factors, respectively. In the proposed schemes, both the passive and active mobile adversaries are considered in an unconditionally secure setting.

Recent literature contains proposals for key predistribution schemes for sensor networks in which nodes are deployed in separate groups. In this article we consider the implications of group deployment for the connectivity and resilience of a key predistribution scheme. We propose a flexible scheme, based on the structure of a resolvable transversal design. We demonstrate that this scheme permits effective trade-offs between resilience, connectivity and storage requirements within a group-deployed environment as compared with other schemes in the literature, and show that group deployment can be used to increase network connectivity, without increasing storage requirements or sacrificing resilience.

The ThreeBallot voting system is an end-to-end voter-verifiable voting system. Each voter fills out three ballots according to a few simple rules and takes a copy of one of them home as a receipt for verification purposes. All ballots are posted on a public bulletin board so that any voter may verify the result. In this paper, we provide the first steps toward investigating the effectiveness of attacks using the voter's receipt and the bulletin board, using a theoretical rather than simulation-based approach. Focusing on two-candidate races, we determine thresholds for when a voter's vote can be reconstructed from their receipt, and when a coercer can effectively verify if a voter followed instructions by looking for prespecified patterns on the bulletin board. Combining these two results allows us to determine safe ballot sizes that resist known attacks. We also generalize a previous observation that an individual receipt can leak information about a voter's choices.

Connectivity is a desired property for distributed sensor networks (DSNs)secured by key predistribution schemes (KPSs). Previous research has studied whether a DSN is connected using the random graph model, but there has been no research on how strong the connectivity is. In this paper, we give results on the minimum node degree and κ-connectivity for DSNs secured by random KPSs and deterministic KPSs. As well, we use computer simulations to verify our results and validate the use of the random graph model in computing the connectivity of DSNs.

In this paper, we discuss the use of combinatorial set systems (combinatorial designs) in the design of key predistribution schemes (KPSs) for sensor networks. We show that the performance of a KPS can be improved by carefully choosing a certain class of set systems as “key ring spaces”. Especially, we analyze KPSs based on a type of combinatorial design known as a transversal design . We employ two types of transversal designs, which are represented by the set of all linear polynomials and the set of quadratic polynomials (over some finite field), respectively. These KPSs turn out to have significant efficiency in a shared-key discovery phase without degrading connectivity and resiliency.

We present some improved bounds on necessary conditions for separating hash families of type {w, w} and type {w, w - 1}. In particular, these bounds apply to secure frame- proof codes, which are equivalent to separating hash families of type {w, w}. We also consider existence results for separating hash families of type {w, w2} that can be obtained from the probabilistic method. The asymptotic behavior of these bounds is analyzed.

The problem of non-interactive message authentication using an insecure broadband channel and an authenticated narrow-band channel is considered. This problem has been considered in the context of ad hoc networks, where it is assumed that there is neither a secret key shared among the two parties nor a public-key infrastructure in place. A formal framework for protocols of this type is presented, along with a new protocol which is as efficient as the best previous protocols. The security of the proposed protocol is based on a new property of hash functions called ‘hybrid-collision resistance’.

A multicollision for a function is a set of inputs whose outputs are all identical. A. Joux showed multicollision attacks on the classical iterated hash function. He also showed how these multicollision attacks can be used to get a collision attack on a concatenated hash function. In this paper, we study multicollision attacks in a more general class of hash functions which we term "generalized sequential hash functions." We show that multicollision attacks exist for this class of hash functions provided that every message block is used at most twice in the computation of the message digest

Abstract We construct sets of routings in the complete directed graph $\vec{K}_n$ that tolerate up to f failures of nodes or links. These routings are optimal with respect to several desirable criteria. In addition, our routings have minimum (or close to minimum) possible optical indices, which means that wavelengths can be assigned to the directed paths in the routings in an efficient manner. This property is useful in the context of optical networks. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 48(1), 47–55 2006

Tompa and Woll introduced a problem of cheating in $(k,n)$ threshold secret sharing schemes. In this problem $k-1$ malicious participants aim to cheat an honest one by opening forged shares and causing the honest participant to reconstruct the wrong secret. We first derive a tight lower bound on the size of shares $|\cV_i|$ for secret sharing schemes that protect against this type of attack: $ |\cV_i| \geq (|\cS|-1)/\delta + 1 $, where $\cV_i$ denotes the set of shares of participant $P_i$, $\cS$ denotes the set of secrets, and $\delta$ denotes the cheating probability. We next present an optimum scheme, which meets the equality of our bound, by using "difference sets." A partial converse and some extensions are also shown.

We discuss the use of combinatorial set systems in the design of deterministic key predistribution schemes for distributed sensor networks. We concentrate on analyzing combinatorial properties of the set systems that relate to the connectivity and resilience of the resulting distributed sensor networks.

It is known that every positive integer n can be represented as a finite sum of the form $n={\textstyle\sum} a_i 2^{i}$, where $a_i\in \{0,1,-1\}$ for all i, and no two consecutive a i 's are nonzero. Such sums are called nonadjacent representations. Nonadjacent representations are useful in efficiently implementing elliptic curve arithmetic for cryptographic applications. In this paper, we investigate if other digit sets of the form {0,1,x}, where x is an integer, provide each positive integer with a nonadjacent representation. If a digit set has this property, we call it a nonadjacent digit set (NADS). We present an algorithm to determine if {0,1,x} is an NADS and, if it is, we present an algorithm to efficiently determine the nonadjacent representation of any positive integer. We also present some necessary and sufficient conditions for {0,1,x} to be an NADS. These conditions are used to exhibit infinite families of integers x such that {0,1,x} is an NADS, as well as infinite families of x such that {0,1,x} is not an NADS.

A (k,n)-threshold visual cryptography scheme (VCS) is a method to encode a secret image SI into n shadow images called shares such that any k or more shares enable the "visual" recovery of the secret image. However, by inspecting less than k shares one cannot gain any information on the secret image. The "visual" recovery consists of copying the shares onto transparencies and then stacking them. Any k shares will reveal the secret image without any cryptographic computation. In this paper we analyze the contrast of the reconstructed image for a (k,n)-threshold VCS. We define a canonical form for a (k,n)-threshold VCS and provide a characterization of a (k,,n)-threshold VCS. We completely characterize a contrast optimal (n-1,n)-threshold VCS in canonical form. Moreover, for $n\geq 4$, we provide a contrast optimal (3,n)-threshold VCS in canonical form. We first describe a family of (3,n)-threshold VCS achieving various values of contrast and pixel expansion. Then we prove an upper bound on the contrast of any (3,n)-threshold VCS and show that a scheme in the described family has optimal contrast. Finally, for k=4,5 we present two schemes with contrast asymptotically equal to 1/64 and 1/256, respectively.

In order to decide on advertisement fees for Web servers, Naor and Pinkas (see Proc. Advances in Cryptology-EUROCRYPT'98 (Lecture Notes in Computer Science). New York: Springer-Verlag, vol.1403, p.576-590, 1998) introduced metering schemes. They proposed metering schemes in which any server is able to compute a proof to be sent to an audit agency if and only if it has been visited by at least a certain number, say h, of clients. In such schemes, any server which has been visited by less than h clients has no information about the proof; consequently, it does not receive any money from the audit agency. In order to have a more flexible payment system, Blundo, De Bonis, and Masucci (see Proc. 4th Int. Symp. Distributed Computing-2000 (Lecture Notes in Computer Science). New York: Springer-Verlag, vol.1914, p.194-208,2000) introduced metering schemes with pricing. These schemes allow different rates of payments based on the number of visits that each server has received. In this paper, we are interested in the efficiency of metering schemes with pricing. We propose a new model for metering schemes with pricing and we provide lower bounds on the size of the information distributed to clients and servers, and on the number of random bits needed by the audit agency to set up a metering scheme with pricing. These bounds are tight, as we provide a scheme which achieves them with equality. Compared to the scheme presented by Blundo, De Bonis, and Masucci, our scheme distributes less information to clients and servers. The drawback of our scheme is that it requires servers to interact with the audit agency in order to compute their proofs.

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 (TA) for pirated data. Several researchers have studied different notions of TA and related concepts in previous years. "Strong" versions of TA 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. 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.

In this paper, we investigate combinatorial properties and constructions of two recent topics of cryptographic interest, namely frameproof codes for digital fingerprinting and traceability schemes for broadcast encryption. We first give combinatorial descriptions of these two objects in terms of set systems and also discuss the Hamming distance of frameproof codes when viewed as error-correcting codes. From these descriptions, it is seen that existence of a c-traceability scheme implies the existence of a c-frameproof code. We then give several constructions of frameproof codes and traceability schemes by using combinatorial structures such as t-designs, packing designs, error-correcting codes, and perfect hash families. We also investigate embeddings of frameproof codes and traceability schemes, which allow a given scheme to be expanded at a later date to accommodate more users. Finally, we look briefly at bounds which establish necessary conditions for existence of these structures.

Orthogonal arrays (OAs) are basic combinatorial structures, which appear under various disguises in cryptology and the theory of algorithms. Among their applications are universal hashing, authentication codes, resilient and correlation-immune functions, derandomization of algorithms, and perfect local randomizers. In this paper, we give new explicit bounds on the size of orthogonal arrays using Delsarte’s linear programming method. Specifically, we prove that the minimum number of rows in a binary orthogonal array of length n and strength t is at least $2^n - (n2^{n - 1} /t + 1)$ and also at least $2^n - ( 2^{n - 2} (n + 1)/t\lceil \frac{{t + 1}}{2} \rceil )$. We also prove that these bounds are as powerful as the linear programming bound itself for many parametric situations. An $(n,m,t)$-resilient function is a function $f:\{ 0,1\} ^n \to \{ 0,1\} ^m $ such that every possible output m-tuple is equally likely to occur when the values of t arbitrary inputs are fixed by an opponent and the remaining $n - t$ input bits are chosen independently at random. A basic problem is to maximize t given m and n, i.e., to determine the largest value of t such that an $(n,m,t)$-resilient function exists. In this paper, we obtain upper and lower bounds for the optimal values of t where $1 \leq n \leq 25$ and $1 \leq m < n$. The upper bounds are derived from Delsarte’s linear programming bound, and the lower bounds come from constructions based on error-correcting codes. We also obtain new explicit upper bounds for the optimal values of t. It was proved by Chor et al. in [Proc. 26th IEEE Symp. on Foundations of Computer Science, 1985, pp. 396–407] that an $(n,2,t)$-resilient function exists if and only if $t < \lfloor {\frac{{2n}}{3}} \rfloor $. This result was generalized by Friedman [Proc. 33rd IEEE Symp. on Foundations of Computer Science, 1992, pp. 314–319], who proved a bound for general m. We also prove some new bounds, and complete the determination of the optimal resiliency of resilient functions with $m = 3$ and most of the cases for $m = 4$. Several other infinite classes of (optimal) resilient functions are also constructed using the theory of anticodes.

In this paper, we discuss methods by which a trusted authority can broadcast a message over a network, so that each member of a specified privileged subset of users can decrypt this message to compute a secret key. In contrast with previously constru

The paper describes a very powerful decomposition construction for perfect secret-sharing schemes. The author gives several applications of the construction and improves previous results by showing that for any graph G of maximum degree d, there is a perfect secret-sharing scheme for G with information rate 2/(d+1). As a corollary, the maximum information rate of secret-sharing schemes for paths on more than three vertices and for cycles on more than four vertices is shown to be 2/3.>

Informally, a $( t,w )$-threshold scheme is a way of distributing partial information (shadows) to w participants, so that any t of them can easily calculate a key (or secret), but no subset of fewer than t participants can determine the key. Presented in this paper is an unconditionally secure threshold scheme in which any cheating participant can be detected and identified with high probability by any honest participant, even if the cheater is in coalition with other participants. Also given is a construction that will detect with high probability a dealer who distributes inconsistent shadows (shares) to the honest participants. The scheme is not perfect; a set of $t - 1$ participants can rule out at most $1 + \begin{pmatrix} {w - t + 1} \\ {t - 1} \end{pmatrix}$ possible keys, given the information they have. In this scheme, the key will be an element of GF$( q )$ for some prime power q. Hence q can be chosen large enough so that the amount of information obtained by any $t - 1$ participants is negligible.

The existence of certain types of dual bases in finite fields GF(2/sup m/) is discussed. These special types of dual bases are needed for efficient implementation of (generalized) bit-serial multiplication in GF(2/sup m/). In particular, the question of choosing a polynomial basis of GF(2/sup m/), for example (1, alpha , alpha /sup 2/, alpha /sup 3/, . . ., alpha /sup m-1/), such that the change of basis matrix from the dual basis to a scalar multiple of the original basis has as few '1' entries as possible, is studied. It was previously shown by M. Wang and I. F. Blake (1990) that the optimal situation occurs when the minimal polynomial of alpha is an irreducible trinomial of degree m; then, an appropriate scalar multiple, beta , yields a change of basis matrix that is a permutation matrix. A construction is presented that often yields bases where the change of basis matrix has low weight, in the case where no irreducible trinomial of degree m exists. A simple formula can be used to compute beta and the weight of the change of basis matrix, given the minimal polynomial of alpha .>

A normal basis representation of $\operatorname{GF}(2^{n})$ allows squaring to be accomplished by a cyclic shift. Algorithms for multiplication in $\operatorname{GF}(2^{n})$ using a normal basis have been studied by several researchers. In this paper, algorithms for performing exponentiation in $\operatorname{GF}(2^{n})$ using a normal basis, and how they can be speeded up by using parallelization, are investigated.

We investigate the combinatorial properties of threshold schemes. Informally, a $( t,w )$-threshold scheme is a way of distributing partial information (shadows) to w participants, so that any t of them can easily calculate a key, but no subset of fewer than t participants can determine the key. Our interest is in perfect threshold schemes: no subset of fewer than t participants can determine any partial information regarding the key. We give a combinatorial characterization of a certain type of perfect threshold scheme. We also investigate the maximum number of keys that a perfect $( t,w )$-threshold scheme can incorporate, as a function of $t,w$, and the total number of possible shadows, $v $. This maximum can be attained when there is a Steiner system $S( t,w,v )$ that can be partitioned into Steiner systems $S ( t - 1,w,v )$. Using known constructions for such Steiner systems, we present two new classes of perfect threshold schemes, and discuss their implementation.