Proof Of Secure Erasure

In computer security, proof of secure erasure (PoSE) or proof of erasure is a remote attestation protocol, 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.

Overview

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.

Protocol constructions

Naive approach

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.

Communication-efficient constructions

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 ε.

Communication- and time-efficient constructions

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

Relation to proof of space

Proof of space is a protocol similar to proof of secure erasure in that both require the prover to dedicate a specific amount of memory to convince the verifier. Nevertheless, there are important differences in their design considerations.

Because the purpose of proof of space is similar to proof of work, the verifier's time complexity must be very small. While such property may be useful for proof of secure erasure as well, it is not fundamental to its usefulness.

Proof of secure erasure on the other hand requires the prover to be unable to convince the verifier using less than the specified amount of memory. Even this may be useful for the other protocol, however proof of space is not harmed if the prover may succeed even with significantly less space.

References

{{reflist

Data erasure
Computer security procedures
Cryptographic protocols
Communications protocols