Paper 2019/1173

Immunization against Complete Subversion without Random Oracles

Giuseppe Ateniese, Danilo Francati, Bernardo Magri, and Daniele Venturi

Abstract

We seek constructions of general-purpose immunizers that take arbitrary cryptographic primitives, and transform them into ones that withstand a powerful “malicious but proud” adversary, who attempts to break security by possibly subverting the implementation of all algorithms (including the immunizer itself!), while trying not to be detected. This question is motivated by the recent evidence of cryptographic schemes being intentionally weakened, or designed together with hidden backdoors, e.g., with the scope of mass surveillance. Our main result is a subversion-secure immunizer in the plain model, that works for a fairly large class of deterministic primitives, i.e. cryptoschemes where a secret (but tamperable) random source is used to generate the keys and the public parameters, whereas all other algorithms are deterministic. The immunizer relies on an additional independent source of public randomness, which is used to sample a public seed. Assuming the public source is untamperable, and that the subversion of the algorithms is chosen independently of the seed, we can instantiate our immunizer from any one-way function. In case the subversion is allowed to depend on the seed, and the public source is still untamperable, we obtain an instantiation from collision-resistant hash functions. In the more challenging scenario where the public source is also tamperable, we additionally need to assume that the initial cryptographic primitive has sub-exponential security. Previous work in the area only obtained subversion-secure immunization for very restricted classes of primitives, often in weaker models of subversion and using random oracles.

Note: An abridged version of this work appeared in the proceedings of the 17th International Conference on Applied Cryptography and Network Security (ACNS 2019).

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Theoretical Computer Science (2021)
DOI
10.1016/j.tcs.2021.01.002
Keywords
Complete subversionCliptographyStandard model
Contact author(s)
dfrancat @ stevens edu
History
2021-01-11: last of 2 revisions
2019-10-10: received
See all versions
Short URL
https://ia.cr/2019/1173
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1173,
      author = {Giuseppe Ateniese and Danilo Francati and Bernardo Magri and Daniele Venturi},
      title = {Immunization against Complete Subversion without Random Oracles},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/1173},
      year = {2019},
      doi = {10.1016/j.tcs.2021.01.002},
      url = {https://eprint.iacr.org/2019/1173}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.