Skip to Main content Skip to Navigation
Conference papers

A Composable Computational Soundness Notion

Véronique Cortier 1 Bogdan Warinschi 2
1 CASSIS - Combination of approaches to the security of infinite states systems
FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174), INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Computational soundness results show that under certain conditions it is possible to conclude computational security whenever symbolic security holds. Unfortunately, each soundness result is usually established for some set of cryptographic primitives and extending the result to encompass new primitives typically requires redoing most of the work. In this paper we suggest a way of getting around this problem. We propose a notion of computational soundness that we term deduction soundness. As for other soundness notions, our definition captures the idea that a computational adversary does not have any more power than a symbolic adversary. However, a key aspect of deduction soundness is that it considers, intrinsically, the use of the primitives in the presence of functions specified by the adversary. As a consequence, the resulting notion is amenable to modular extensions. We prove that a deduction sound implementation of some arbitrary primitives can be extended to include asymmetric encryption and public data-structures (e.g. pairings or list), without repeating the original proof effort. Furthermore, our notion of soundness concerns cryptographic primitives in a way that is independent of any protocol specification language. Nonetheless, we show that deduction soundness leads to computational soundness for languages (or protocols) that satisfy a so called commutation property.
Document type :
Conference papers
Complete list of metadatas
Contributor : Véronique Cortier <>
Submitted on : Saturday, November 5, 2011 - 9:26:27 PM
Last modification on : Thursday, March 5, 2020 - 4:49:50 PM



Véronique Cortier, Bogdan Warinschi. A Composable Computational Soundness Notion. 18th ACM Conference on Computer and Communications Security - CSS 2011, Oct 2011, Chicago, United States. pp.63-74, ⟨10.1145/2046707.2046717⟩. ⟨inria-00638552⟩



Record views