The disclosed embodiments provide a system with a memory with an interface that includes tamper-evident features to enhance software security. The system includes a set of memory elements, wherein each memory element comprises storage for a set of bits that encode a data word and an associated validity indicator, which indicates whether the memory element contains a valid data word. It also includes a memory interface for the set of memory elements. This memory interface supports a conditional-write operation, which overwrites a data word in a memory element if an associated validity indicator indicates that the data word does not contain valid data, and which does not overwrite the data word and raises an error if the associated validity indicator indicates that the data word already contains valid data.