Proof of secure erasure

In computer security, proof of secure erasure (PoSE) or proof of erasure is a remote attestation, by which an embedded device proves to a verifying party, that it has just erased (overwritten) all its writable memory. The purpose is to make sure that no malware remains in the device. After that typically a new software is installed into the device.

The verifying party may be called the verifier, the device being erased the prover. The verifier must know the device's writable memory size from a trusted source and the device must not be allowed to communicate with other parties during execution of the protocol, which proceeds as follows. The verifier constructs a computational problem, which cannot be solved (in reasonable time or at all) using less than the specified amount of memory, and sends it to the device. The device responds with the solution and the verifier checks its correctness.

In the simplest implementation the verifier sends a random message as large as the device's memory to the device, which is expected to store it. After the device has received the complete message, it is required to send it back. Security of this approach is obvious, but it includes transfer of a huge amount of data (twice the size of the device's memory).

This can be halved if the device responds with just a hash of the message. To prevent the device from computing it on the fly without actually storing the message, the hash function is parametrized by a random value sent to the device after the message.

Avoiding the huge data transfer requires a suitable (as stated in Overview) computational problem, whose description is short. Dziembowski et al. achieve this by constructing what they call an (m − δ, ε)-uncomputable hash function, which can be computed in quadratic time using memory of size m, but with memory of size m − δ it can be computed with at most a negligible probability ε.

Karvelas and Kiayias claim to have designed the first PoSE with quasilinear time and sublinear communication complexity.

...
Wikipedia