  A Proof of Secure Erasure (PoSE) is a communication protocol where a verifier
seeks evidence that a prover has erased its memory within the time frame of the
protocol execution. Designers of PoSE protocols have long been aware that, if a
prover can outsource the computation of the memory erasure proof to another
device, then their protocols are trivially defeated. As a result, most
software-based PoSE protocols in the literature assume that provers are
isolated during the protocol execution, that is, provers cannot receive help
from a network adversary. Our main contribution is to show that this assumption
is not necessary. We introduce formal models for PoSE protocols playing against
provers aided by external conspirators and develop three PoSE protocols that we
prove secure in this context. We reduce the requirement of isolation to the
more realistic requirement that the communication with the external conspirator
is relatively slow. Software-based protocols with such relaxed isolation
assumptions are especially pertinent for low-end devices, where it is too
costly to deploy sophisticated protection methods.
