Volpano, D, Smith, G. (2000). Verifying secrets and relative secrecy
. Conference Record of the Annual ACM Symposium on Principles of Programming Languages, 268-276. 10.1145/325694.325729
Volpano, D, Smith, G. (2000). Verifying secrets and relative secrecy
. Conference Record of the Annual ACM Symposium on Principles of Programming Languages, 268-276. 10.1145/325694.325729
Systems that authenticate a user based on a shared secret (such as a password or PIN) normally allow anyone to query whether the secret is a given value. For example, an ATM machine allows one to ask whether a string is the secret PIN of a (lost or stolen) ATM card. Yet such queries are prohibited in any model whose programs satisfy an information-flow property like Noninterference. But there is complexity-based justification for allowing these queries. A type system is given that provides the access control needed to prove that no well-typed program can leak secrets in polynomial time, or even leak them with nonnegligible probability if secrets are of sufficient length and randomly chosen. However, there are well-typed deterministic programs in a synchronous concurrent model capable of leaking secrets in linear time.
