Adversaries and Information Leaks (Tutorial)

详细信息    查看全文

• 作者：Geoffrey Smith
• 刊名：Lecture Notes in Computer Science
• 出版年：2008
• 出版时间：2008
• 年：2008
• 卷：4912
• 期：1
• 页码：383-400
• 全文大小：245.2 KB
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

Secure information flow analysis aims to prevent programs from leaking their H (high) inputs to their L (low) outputs. A major challenge in this area is to relax the standard noninterference properties to allow “small” leaks, while still preserving security. In this tutorial paper, we consider three instances of this theme. First, we consider a type system that enforces the usual Denning restrictions, except that it specifies that encrypting a H plaintext yields a L ciphertext. We argue that this type system ensures security, assuming strong encryption, by giving a reduction that maps a noninterference adversary (which tries to guess which of two H inputs was used, given the L outputs) to an IND-CPA adversary (which tries to guess which of two plaintexts are encrypted, given the ciphertext). Second, we explore termination leaks in probabilistic programs when typed under the Denning restrictions. Using a notion of probabilistic simulation, we show that such programs satisfy an approximate noninterference property, provided that their probability of nontermination is small. Third, we consider quantitative information flow, which aims to measure the amount of information leaked. We argue that the common information-theoretic measures in the literature are unsuitable, because these measures fail to distinguish between programs that are wildly different from the point of view of an adversary trying to guess the H input.