Sealstack modeling

Syntax and notiation for sealing/unsealing

NB: We always assume that sealing and unsealing have access to a random oracle \(H_\text{salt}\) where \(\text{salt} = (sid||dig_D)\) where \(sid\) is some session id and \(dig_D\) is a digest of the data \(D\) (for example the root of the Merkle Tree computed on the data \(D\)). We keep these parameters implicit when obvious from the context.

• \(\mathsf{Seal}(D) \to R\): sealing data \(D\) computes a replica \(R\)
• \(\mathsf{Unseal}(R) \to D\): unsealing a replica \(R\) allows to recompute the data

We define \(T_\text{seal}\) as the (parallel) time required to run seal.
We consider the setting of asymmetric constructions where the time to seal and unseal may be different. We describe the ratio between sealing and unsealing time through a constant \(k \in \mathbb{N}\) so that the time to unseal is \(\frac{T_\text{seal}}{k}\).

We also consider the time \(T_\text{chal}\) "allowed for responding to a challenge". This time is always such that \(T_\text{seal} > T_\text{chal}\). Later in this note we will consider the ratio \(T_\text{seal}/T_\text{chal}\).

A sealstacking adversary

Here we model an adversary running a single stack (we could model a bundle of stacks as a generalization later).

The adversary:

• Claims to store some easy dummy data \(D_1\)
• Sets \(R_1 \gets \mathsf{Seal}(D_1)\)
• Claims to store \(D_2 := R_1\)
• Sets \(R_2 \gets \mathsf{Seal}(D_2)\)
• …
• Claims to store \(D_n := R_n\)
• Sets \(R_n \gets \mathsf{Seal}(D_n)\)
• Deletes all data except for \(R_n\)

When challenged on data instance \(j \in [n]\):

• runs \(\mathsf{Unseal}(\mathsf{Unseal}(...(\mathsf{Unseal}(R_n))...))\)
• (this is unsealing run \(n-j\) times)

Space complexity of this adversary

It stores only \(1|R|\) as opposed to \(n|R|\), the storage of the honest adversary.

Time complexity of this adversary

It is \(T' = (n-1)T_\text{unseal} = \frac{(n-1)}{k}T_\text{seal}\). (in the worst case)

Notice that the the adversary is successful if it is able to answer in time \(T' < T_\text{chal}\), that is if \(\frac{n-1}{k}T_\text{seal} < T_\text{chal}\).
This occurs when
\[ \frac{T_\text{seal}}{T_\text{chal}}< \frac{k}{n-1} \]

As an intuition, if sealing time is 3x the challenge time,. then the adversary can successfully respond to challenges for a stack of size up to \(n \approx k/3\).