For $1 \le p \le n-1$, define $\Cov{n}{p}$ as the family of graphs on the vertex set $\{1,\ldots, n\}$ with a covering number of at most p (equivalently, with an independence number of at least $n-p$). Since the underlying vertex set is fixed, we may identify each graph in $\Cov{n}{p}$ with its edge set. In particular, we may view $\Cov{n}{p}$ as a simplicial complex. For $i\ge -1$, we show that the rank of the ith homology group of $\Cov{n}{p}$ is a linear combination, with coefficients being polynomials in n, of the ranks of the ith homology groups of $\Cov{p+2}{p}, \ldots, \Cov{2p+1}{p}$. Our proof takes place in a more general setting where we consider complexes of hypergraphs. In addition, we show that the $(2p-1)$-skeleton of $\Cov{n}{p}$ is shellable, which implies that $\Cov{n}{p}$ is $(2p-2)$-connected. For $p \le 3$, we give a complete description of the homology groups of $\Cov{n}{p}$.

We investigate a simple method of fraud management for secure devices that may serve as an alternative or complement to conventional hardware-based tamper resistance. Under normal operating conditions in our scheme, a secure device includes an authentication code in its communications, e.g., in the digital signatures it issues. This code may be verified by a fraud management center under a pre-determined key σ. When the device detects an attempted break-in, it modifies σ. This results in a change to the authentication codes issued by the device such that the fraud management center can detect the apparent break-in. Hence, in contrast to the case with typical tamper-resistance schemes, the deployer of our proposed scheme seeks to trace break-ins, rather than prevent them. In reference to the wartime practice of physically capturing and subverting underground radio transmitters – a practice analogous to the capture and use of secret information on secure devices – we denote this idea by the German term funkspiel, meaning “radio game.” One challenge in constructing a funkspiel scheme is to ensure that an attacker privy to the authentication codes of the secure device both before and after the break-in, as well as the secrets of the device following the break-in, cannot detect the alteration to σ. Additional challenges ∗Some of this work was done while visiting RSA Laboratories.