Cryptography

We describe a simple scheme based on families of coverfree subsets. It is a too inefficient for practical purposes.

There are $n$ users and a single source. The source has several MAC keys $K_1,...,K_m$, where $m$ will be determined later.

The $i$th receiver has a set of keys $S_i\subseteq \{K_1,...,K_m\}$.

To send a message $M$, the source transmits $M,{\mathrm{MAC}}_{K_1}(M),...,{\mathrm{MAC}}_{K_m}(M)$.

Recipient $i$ accepts a packet $P$ if all the MAC's corresponding to their set $S_i$ verify.

At the bare minimum, we want 1-security, that is, any user $j$ should not be able to forge a packet for any other user $i$, so we must have $S_i⊈S_j$. The best way to do this is to use all subsets of size $m/2$ from the set of keys, so we need $n=\left(\begin{array}{c}m\\ m/2\end{array}\right)$, so $m=O(\log n)$.

More generally, for $t$-security (i.e. so that no group of $t$ users can forge a packet), we require a family of $t$-coverfree subsets, which can be done with $m=O(t^2\log n)$. Thus the packet size is quadratic in $t$. It can be shown that a smaller packet size implies nonrepudiation, that is, a MAC that short would in fact be a signature.

This solution uses time for security. Assume the total clock skew is $\Delta$, and that the total routing time is less than or equal to some time $T$.

We use hash chains, i.e:

$$K_0\to K_1=H(K_0)\to \cdots \to K_m=H(K_{m-1})$$

For setup, give $K_m$ to all recipients, for some sufficiently large $m$. The source has $K_0$. Then:

Time $1$: send $M_1,{\mathrm{MAC}}_{K_{m-1}}(M_1)$

Time $2$: send $M_2,{\mathrm{MAC}}_{K_{m-2}}(M_2)$

Time $T$: send $M_T,{\mathrm{MAC}}_{K_{m-T}}(M_T)$. By this stage, all users should have received $M_1,\mathrm{MAC}(M_1)$.

Time $T+\Delta$: send $M_{T+\Delta },{\mathrm{MAC}}_{K_{m-T-\Delta }}(M_{T+\Delta })$, and also send $K_{m-1}$

Time $2T+\Delta$: all users can validate $M_1$

To validate the first packet:

1. Check that $K_m$ is in the hash chain

2. Verify ${\mathrm{MAC}}_{K_{m-1}}(M_1)$

3. Reject $M_1$ if received after time $T+\Delta =T_{\mathrm{local}}$

Note that this scheme requires the users to buffer packets for $T$ time steps.

It has been shown [Jacobson-Coppersmith] that one can construct a hash chain where computing any element of it takes time $O(\log n)$ in $O(\log n)$ space.

Signing every packet is too expensive, but signing many packets is vulnerable to packet loss. The solution is to sign many packets at once but verify them individually.

For example, suppose we have four packets $p_1,...,p_4$. We construct a hash tree (diagram will be here when Mozilla supports SVG :-) (e.g. if we label the tree nodes $n_1,...,n_7$, we have

$$n_1=H(p_1),n_2=H(p_2),n_3=H(p_3),n_4=H(p_4),n_5=H(n_1\mid \mid n_2),n_6=H(n_3\mid \mid n_4),n_7=H(n_5\mid \mid n_6)$$

and transmit the packet plus enough nodes of the tree to derive the root node:

1. send $p_1,n_2,n_6,\mathrm{sign}(n_7)$

2. send $p_2,n_1,n_6,\mathrm{sign}(n_7)$

3. send $p_3,n_4,n_5,\mathrm{sign}(n_7)$

4. send $p_4,n_3,n_5,\mathrm{sign}(n_7)$

The overhead is $O(\log n)$ hashes plus a signature per packet.

However, this method requires buffering at the source. We can use one-time signatures to alleviate this.

One-Time Signatures are signatures that can be constructed and verified very quickly, but can only be used once (or a few times).

For example [Lamport], consider the following scheme:

• Private key: $x_1^0,...,x_{160}^0,x_1^1,...,x_{160}^1$.

• Public key: $H(x_1^0),...,H(x_{160}^0),H(x_1^1),...,H(x_{160}{)}^1)$

• Sign($M$): compute $\mathrm{SHA}1(M)=h\in \{\mathrm{0,1}{\}}^{160}$. The signature is $x_1^{h_1},...,x_{160}^{h_{160}}$ where $h_i$ is the $i$ bit of $h$.

Another example. BiBa OTS (Bins and balls):

• Let $n$ be the security parameter. Let $H$ be a hash function $H:\{\mathrm{0,1}{\}}^{*}\to \{\mathrm{0,1}{\}}^m$ where $m\ll n$.

• Private key: $x_1,...,x_n\in \{\mathrm{0,1}{\}}^k$

• Public key: $\mathrm{SHA}1(x_1),...,\mathrm{SHA}1(x_n)$

• Sign($M$): find $1\le i<j\le n$ such that $H(M\mid \mid x_i)=H(M\mid \mid x_j)$. The signature is $(x_i,x_j)$ ("Find two balls that hit the same bin.")

We can now remove the buffering problem as follows. Build a hash tree from the public keys ${\mathrm{PK}}_1,...,{\mathrm{PK}}_n$ of some one-time signature scheme. Sign the tree and transmit the public keys with signatures (so we commit to public keys instead of packets), and simply sign each packet.

Build a directed acyclic graph (DAG) using the packets as nodes. Then proceed as in the previous scheme, except this time we use a hash DAG, instead of a hash tree.

To resist up to $t$ packets being lost, we need a graph that remains connected even if $t$ nodes are removed.

An $\epsilon$-expander graph $(V,E)$ is a graph such that for all $S\subseteq V$, we have $\mid \mathrm{neighbour}(S)\mid \ge (1+\epsilon )\mid S\mid$ if (?) $\mid S\mid \le \mid V\mid /(1+\epsilon )$.

There exist methods of constructing constant degree $d$ expanders on $n$ nodes such that removing $n^{\epsilon }$ nodes for some constant $\epsilon$ does not disconnect the graph.