A Survey of Researches of Relationship between Symbolic and Computational Semantics in Security Analysis(<Special Topics> Formal Approach to Information Security)

Bibliographic Information

Other Title
  • 記号論及び計算論によるセキュリティ解析の相互関係(<特集>数理的技法による情報セキュリティ)
  • 記号論及び計算論によるセキュリティ解析の相互関係
  • キゴウロン オヨビ ケイサンロン ニ ヨル セキュリティ カイセキ ノ ソウゴ カンケイ

Search this article

Abstract

Two kinds of models are used for analyzing cryptography protocols. One is the computational model where encrypted information are deciphered by computation of probabilistic polynomial-time Turing machines. The other is the symbolic model (or, Dolev-Yao Model) where a set of algebraic lows are applied. Analysis with the symbolic model is simple and easy to understand since it is regarded as abstract-level analysis by discarding a phenomenon of which probability is negligible. Due to subtlety of difference between these two kinds of analysis, several attempts have been made to bridge the gap between these two models. Among them, a work by Abadi and Rogaway and a work by Micciancio and Warinschi provide basic idea for bridging the gap. In this article, we mainly provide a survey of these works. Abadi and Rogaway showed that messages are not computationally indistinguishable if they are equivalent symbolically. This property is the soundness of symbolic analysis for computational one. Micciancio and Warinschi showed its converse, i. e. completeness property. We also summarize extensions of these works, which are analysises in more practical setting.

Journal

References(10)*help

See more

Details 詳細情報について

Report a problem

Back to top