Shamir's Secret Sharing Scheme is well established and widely used. It allows a so-called Dealer to split and share a secret k among n Participants such that at least t shares are needed to reconstruct k, where 0 <; t ≤ n. Nothing about the secret can be learned from less than t shares. To split secret k, the Dealer generates a polynomial f, whose independent term is k and the coefficients are randomly selected using a uniform distribution. A share is a pair (x, f(x)) where x is also chosen randomly using a uniform distribution. This scheme is useful, for example, to distribute cryptographic keys among different cloud providers and to create multi-factor authentication. The security of Shamir's Secret Sharing Scheme is usually analyzed using a threat model where the Dealer is trusted to split and share secrets as described above. In this paper, we demonstrate that there exists a different threat model where a malicious Dealer can compute shares such that a subset of less than t shares is allowed to reconstruct the secret. We refer to such subsets as hidden sets. We formally define hidden sets and prove lower bounds on the number of possible hidden sets for polynomials of degree t - 1. Yet, we show how to detect hidden sets given a set of n shares and describe how to create hidden sets while sharing a secret using a modification of Shamir's scheme.

We present a new construction of ordered orthogonal arrays (OOAs) of strength t with (q + 1)t columns over a finite field Fqusing linear feedback shift register sequences (LFSRs). OOAs are naturally related to (t, m, s)-nets, linear codes, and MDS codes. Our construction selects suitable columns from the array formed by all subintervals of length (qt-1)/(q-1) of an LFSR sequence generated by a primitive polynomial of degree t over Fq. We prove properties about the relative positions of runs in an LFSR, which guarantee that the constructed OOA has strength t. The set of parameters of our OOAs are the same as the ones given by Rosenbloom and Tsfasman (1997) and Skriganov (2002), but the constructed arrays are different. We experimentally verify that our OOAs are stronger than the Rosenbloom-Tsfasman-Skriganov OOAs in the sense that ours are “closer” to being a “full” orthogonal array. We also discuss how our OOA construction relates to previous techniques to build OOAs from a set of linearly independent vectors over Fq, as well as to hypergraph homomorphisms.

In this paper, we define and study error locating arrays (ELAs), which can be used in software testing for locating faulty interactions among parameters or components in a system. We give constructions of ELAs for arbitrary strength t, based on covering arrays. We show that the number of tests given by ELAs grows as $O(\log k)$, where k is the number of parameters/components in the system, assuming other quantities (the number g of values per parameter, the strength t of faulty interactions, and the number d of faulty interactions) are bounded by a constant. We then give a series of results for the case of pairwise interactions ($t=2$). We study the computational complexity of deciding whether a graph describing the faulty pairwise interactions is “locatable.” We characterize the locatable graphs for the binary case ($g=2$). We design and analyze efficient algorithms that locate errors under certain assumptions on the structure of the faulty pairwise interactions. Under the assumption of known “safe values,” our algorithm performs a number of tests that is polynomial in $\log k$ and d, where k is the number of parameters in the system and d is an upper bound on the number of faulty pairwise interactions. For the binary alphabet case, we provide an algorithm that does not require safe values and runs in expected polynomial time in $\log k$ whenever $d\in O(\log\log k)$.

In this paper, we extend previously known results on the complexities of normal elements. Using algorithms that exhaustively test field elements, we are able to provide the distribution of the complexity of normal elements for binary fields with degree extensions up to 39. We also provide current results on the smallest known complexity for the remaining degree extensions up to 512 by using a combination of constructive theorems and known exact values. We give an algorithm to exhaustively search field elements by using Gray codes, which allows us to reuse previous computations. We compare this with a standard method. We analyze this algorithm and show both experimentally and asymptotically that the Gray code optimization gives substantial savings. The total computation of the distribution of the complexity of normal elements for degrees up to 39 in our experiments allows us to draw several conjectures. In particular, our data provides remarkable evidence for the conjecture that the complexity of normal elements follows a normal distribution. Finally, we conjecture that there is no linear bound on the minimum complexity with respect to the degree of the extension.

The orthogonal matching pursuit (OMP) algorithm is an adaptive nonlinear algorithm for signal decomposition using an overcomplete dictionary. A tree-search based orthogonal matching pursuit (TB-OMP) has been proposed (Cotter et al. (2001)). Although the TB-OMP algorithm improves the approximation performance, its computation time requirement increases exponentially making the algorithm impractical for certain applications. In this paper, we propose the flexible tree-search based orthogonal matching pursuit (FTB-OMP). The algorithm provides design parameters that give flexibility to establish a tradeoff between approximation performance and experimental time complexity. Sparse signal representations are frequently required in problems related to signal processing and communication areas. The proposed FTB-OMP algorithm is a promising solution for such problems.