Provably Secure Subsitution of Cryptographic Tools

Lea Kissner and David Molnar

Abstract

Many cryptographic protocols secure against malicious players use specially designed cryptographic tools. Essentially, these special tools function much like less-expensive tools, but give extra powers' to a reduction or simulation algorithm. Using these powers, cryptographers can construct a proof of security using standard techniques. However, these powers are not available to either the honest parties or the adversary. In a large class of protocols, by replacing the expensive, specially designed cryptographic tool with a corresponding less-expensive tool, we can improve the protocol's efficiency without changing the functionality available to either the adversary or the honest parties. The key motivating question we address in this paper is whether the new, substituted' protocol is still secure. We introduce a framework for reasoning about this question. Our framework uses translators: special purpose oracles that map outputs of one cryptographic tool to corresponding outputs of a different tool. Translators are similar to, but generally weaker than, the angels'' of Prabhakaran and Sahai. We introduce the notion of substitution-friendly protocols and show that such protocols remain secure after substitution in our framework. We also leverage existing proofs of security; there is no need to re-prove security from scratch. We demonstrate our framework with a non-interactive non-malleable bit commitment protocol.

Note: We've added new examples and revised explanations for better clarity.

Available format(s)
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
provable securityefficiencytranslationfoundations
Contact author(s)
leak @ cs cmu edu
History
2006-10-23: last of 2 revisions
See all versions
Short URL
https://ia.cr/2006/004

CC BY

BibTeX

@misc{cryptoeprint:2006/004,
author = {Lea Kissner and David Molnar},
title = {Provably Secure Subsitution of Cryptographic Tools},
howpublished = {Cryptology ePrint Archive, Paper 2006/004},
year = {2006},
note = {\url{https://eprint.iacr.org/2006/004}},
url = {https://eprint.iacr.org/2006/004}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.