More Web Proxy on the site http://driver.im/

Article

Let a Non-barking Watchdog Bite: Cliptographic Signatures with an Offline Watchdog

Authors:

Sherman S. M. Chow,

Alexander Russell,

Hong-Sheng ZhouAuthors Info & Claims

Public-Key Cryptography – PKC 2019: 22nd IACR International Conference on Practice and Theory of Public-Key Cryptography, Beijing, China, April 14-17, 2019, Proceedings, Part I

Pages 221 - 251

https://doi.org/10.1007/978-3-030-17253-4_8

Published: 14 April 2019 Publication History

Abstract

We study how to construct secure digital signature schemes in the presence of kleptographic attacks. Our work utilizes an offline watchdog to clip the power of subversions via only one-time black-box testing of the implementation. Previous results essentially rely on an online watchdog which requires the collection of all communicating transcripts (or active re-randomization of messages).

We first give a simple but generic construction, without random oracles, in the partial-subversion model in which key generation and signing algorithms can be subverted. Then, we give the first digital signature scheme in the complete-subversion model in which all cryptographic algorithms can be subverted. This construction is based on the full-domain hash. Along the way, we enhance the recent result of Russell et al. (CRYPTO 2018) about correcting a subverted random oracle.

References

[1]

Abe M, Chase M, David B, Kohlweiss M, Nishimaki R, and Ohkubo M Constant-size structure-preserving signatures: generic constructions and simple assumptions J. Cryptology 2016 29 4 833-878

Digital Library

[2]

Ateniese G, Magri B, and Venturi D Ray I, Li N, and Kruegel C Subversion-resilient signature schemes ACM CCS 2015 2015 New York ACM Press 364-375

[3]

Bellare M and Hoang VT Oswald E and Fischlin M Resisting randomness subversion: fast deterministic and hedged public-key encryption in the standard model Advances in Cryptology - EUROCRYPT 2015 2015 Heidelberg Springer 627-656

[4]

Bellare M, Jaeger J, and Kane D Ray I, Li N, and Kruegel C Mass-surveillance without the state: strongly undetectable algorithm-substitution attacks ACM CCS 2015 2015 New York ACM Press 1431-1440

[5]

Bellare M, Paterson KG, and Rogaway P Garay JA and Gennaro R Security of symmetric encryption against mass surveillance Advances in Cryptology – CRYPTO 2014 2014 Heidelberg Springer 1-19

[6]

Bellare M and Rogaway P Ashby V Random oracles are practical: a paradigm for designing efficient protocols ACM CCS 1993 1993 New York ACM Press 62-73

[7]

Bellare M and Rogaway P Maurer U The exact security of digital signatures-how to sign with RSA and Rabin Advances in Cryptology — EUROCRYPT 1996 1996 Heidelberg Springer 399-416

[8]

Boneh D and Boyen X Short signatures without random oracles and the SDH assumption in bilinear groups J. Cryptology 2008 21 2 149-177

Digital Library

[9]

Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: 42nd FOCS, pp. 136–145. IEEE Computer Society Press, October 2001

[10]

Chen R, Mu Y, Yang G, Susilo W, Guo F, and Zhang M Cheon JH and Takagi T Cryptographic reverse firewall via malleable smooth projective hash functions Advances in Cryptology – ASIACRYPT 2016 2016 Heidelberg Springer 844-876

[11]

Coron J-S Bellare M On the exact security of full domain hash Advances in Cryptology — CRYPTO 2000 2000 Heidelberg Springer 229-235

[12]

Coron J-S, Dodis Y, Malinaud C, and Puniya P Shoup V Merkle-Damgård revisited: how to construct a hash function Advances in Cryptology – CRYPTO 2005 2005 Heidelberg Springer 430-448

Digital Library

[13]

Degabriele JP, Farshim P, and Poettering B Leander G A more cautious approach to security against mass surveillance Fast Software Encryption 2015 Heidelberg Springer 579-598

[14]

Desmedt Y Goldwasser S Abuses in cryptography and how to fight them Advances in Cryptology — CRYPTO 1988 1990 New York Springer 375-389

[15]

Dodis Y, Ganesh C, Golovnev A, Juels A, and Ristenpart T Oswald E and Fischlin M A formal treatment of backdoored pseudorandom generators Advances in Cryptology – EUROCRYPT 2015 2015 Heidelberg Springer 101-126

[16]

Dodis Y, Mironov I, and Stephens-Davidowitz N Robshaw M and Katz J Message transmission with reverse firewalls—secure communication on corrupted machines Advances in Cryptology – CRYPTO 2016 2016 Heidelberg Springer 341-372

Digital Library

[17]

Fischlin, M., Mazaheri, S.: Self-guarding cryptographic protocols against algorithm substitution attacks. In: 31st IEEE Computer Security Foundations Symposium, CSF 2018, Oxford, United Kingdom, 9–12 July 2018, pp. 76–90 (2018)

[18]

Giacon F, Heuer F, and Poettering B Abdalla M and Dahab R KEM combiners Public-Key Cryptography – PKC 2018 2018 Cham Springer 190-218

[19]

Liu C, Chen R, Wang Y, and Wang Y Susilo W and Yang G Asymmetric subversion attacks on signature schemes Information Security and Privacy 2018 Cham Springer 376-395

Digital Library

[20]

Maurer U, Renner R, and Holenstein C Naor M Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology Theory of Cryptography 2004 Heidelberg Springer 21-39

[21]

Mironov I and Stephens-Davidowitz N Oswald E and Fischlin M Cryptographic reverse firewalls Advances in Cryptology - EUROCRYPT 2015 2015 Heidelberg Springer 657-686

[22]

Perlroth, N., Larson, J., Shane, S.: NSA able to foil basic safeguards of privacy on web. The New York Times, September 2013

[23]

Russell A, Tang Q, Yung M, and Zhou H-S Cheon JH and Takagi T Cliptography: clipping the power of kleptographic attacks Advances in Cryptology – ASIACRYPT 2016 2016 Heidelberg Springer 34-64

Digital Library

[24]

Russell, A., Tang, Q., Yung, M., Zhou, H.-S.: Destroying steganography via amalgamation: kleptographically CPA secure public key encryption. Cryptology ePrint Archive, Report 2016/530 (2016). http://eprint.iacr.org/2016/530

[25]

Russell A, Tang Q, Yung M, and Zhou H-S Thuraisingham BM, Evans D, Malkin T, and Xu D Generic semantic security against a kleptographic adversary ACM CCS 2017 2017 New York ACM Press 907-922

[26]

Russell A, Tang Q, Yung M, and Zhou H-S Shacham H and Boldyreva A Correcting subverted random oracles Advances in Cryptology – CRYPTO 2018 2018 Cham Springer 241-271

Digital Library

[27]

Young A and Yung M Koblitz N The dark side of “black-box” cryptography or: should we trust capstone? Advances in Cryptology — CRYPTO 1996 1996 Heidelberg Springer 89-103

[28]

Young A and Yung M Fumy W Kleptography: using cryptography against cryptography Advances in Cryptology — EUROCRYPT 1997 1997 Heidelberg Springer 62-74

[29]

Zhang C, Cash D, Wang X, Yu X, and Chow SSM Dinh TN and Thai MT Combiners for chosen-ciphertext security Computing and Combinatorics 2016 Cham Springer 257-268

Cited By

Cheng JWang YChen RHuang X(2024)Subverting Cryptographic Protocols from a Fine-Grained Perspective- A Case Study on 2-Party ECDSAInformation Security and Privacy10.1007/978-981-97-5028-3_19(370-390)Online publication date: 15-Jul-2024
https://dl.acm.org/doi/10.1007/978-981-97-5028-3_19
Davis HGreen MHeninger NRyan KSuhl A(2024)On the Possibility of a Backdoor in the Micali-Schnorr GeneratorPublic-Key Cryptography – PKC 202410.1007/978-3-031-57718-5_12(352-386)Online publication date: 15-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-57718-5_12
Wong HMa JYin HChow S(2023)How (Not) to Build Threshold EdDSAProceedings of the 26th International Symposium on Research in Attacks, Intrusions and Defenses10.1145/3607199.3607230(123-134)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3607199.3607230
Show More Cited By

Recommendations

On-line non-transferable signatures revisited
PKC'11: Proceedings of the 14th international conference on Practice and theory in public key cryptography conference on Public key cryptography

Undeniable signatures, introduced by Chaum and van Antwerpen, and designated confirmer signatures, introduced by Chaum, allow a signer to control the verifiability of his signatures by requiring a verifier to interact with the signer to verify a ...
Optimal Security Proofs for Signatures from Identification Schemes
Proceedings, Part II, of the 36th Annual International Cryptology Conference on Advances in Cryptology --- CRYPTO 2016 - Volume 9815

We perform a concrete security treatment of digital signature schemes obtained from canonical identification schemes via the Fiat-Shamir transform. If the identification scheme is random self-reducible and satisfies the weakest possible security notion ...
Security of BLS and BGLS signatures in a multi-user setting

Traditional single-user security models do not necessarily capture the power of real-world attackers. A scheme that is secure in the single-user setting may not be as secure in the multi-user setting. Inspired by the recent analysis of Schnorr ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Public-Key Cryptography – PKC 2019: 22nd IACR International Conference on Practice and Theory of Public-Key Cryptography, Beijing, China, April 14-17, 2019, Proceedings, Part I

Apr 2019

620 pages

ISBN:978-3-030-17252-7

DOI:10.1007/978-3-030-17253-4

Editors:
Dongdai Lin
SKLOIS, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China
,
Kazue Sako
Security Research Laboratories, NEC Corporation, Kawasaki, Japan

© International Association for Cryptologic Research 2019.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 14 April 2019

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cheng JWang YChen RHuang X(2024)Subverting Cryptographic Protocols from a Fine-Grained Perspective- A Case Study on 2-Party ECDSAInformation Security and Privacy10.1007/978-981-97-5028-3_19(370-390)Online publication date: 15-Jul-2024
https://dl.acm.org/doi/10.1007/978-981-97-5028-3_19
Davis HGreen MHeninger NRyan KSuhl A(2024)On the Possibility of a Backdoor in the Micali-Schnorr GeneratorPublic-Key Cryptography – PKC 202410.1007/978-3-031-57718-5_12(352-386)Online publication date: 15-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-57718-5_12
Wong HMa JYin HChow S(2023)How (Not) to Build Threshold EdDSAProceedings of the 26th International Symposium on Research in Attacks, Intrusions and Defenses10.1145/3607199.3607230(123-134)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3607199.3607230
Faonio AFiore DNizzardo LSoriente C(2022)Subversion-Resilient Enhanced Privacy IDTopics in Cryptology – CT-RSA 202210.1007/978-3-030-95312-6_23(562-588)Online publication date: 7-Feb-2022
https://dl.acm.org/doi/10.1007/978-3-030-95312-6_23
Bemmann PChen RJager T(2021)Subversion-Resilient Public Key Encryption with Practical WatchdogsPublic-Key Cryptography – PKC 202110.1007/978-3-030-75245-3_23(627-658)Online publication date: 10-May-2021
https://dl.acm.org/doi/10.1007/978-3-030-75245-3_23

View Options

View options

Media

Figures

Other

Tables

View Table of Contents