Methods and apparati for auditing uses of cryptographic keys. In a method embodiment of the present invention, a set of audited uses for a cryptographic key is defined; the key is generated inside a protected execution environment of a digital computer; all software and firmware that is usable in the execution environment to access the key is demonstrated to an auditor; and, for each audited use of the key, a non-tamperable audit record describing said use is released.