Verifying Secrets and Relative Secrecy

Abstract

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-type deterministic programs in a synchronous concurrent model capable of leaking secrets in linear time.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 2000
Accession Number
ADA493035

Entities

People

  • Dennis Volpano
  • Geoffrey B. Smith

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • Cyber

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Cryptography
  • Cybersecurity
  • Information Security
  • Language
  • Learning
  • Multithreading
  • Polynomials
  • Probability
  • Probability Distributions
  • Programming Languages
  • Security
  • Simulations

Fields of Study

  • Computer science

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Computational Linguistics
  • Cybersecurity.