Abstract
We present a simple method for constructing identification schemes resilient against impersonation and man-in-the-middle attacks. Though zero-knowledge or witness hiding protocols are known to withstand attacks of the first kind, all such protocols previously proposed suffer from a weakness observed by Bengio et al.: a malicious verifier may simply act as a moderator between the prover and yet another verifier, thus enabling the malicious verifier to pass as the prover.
We exhibit a general class of identification schemes that can be efficiently and securely transformed into identification schemes withstanding an adaptive man-in-the-middle attacker. The complexity of the resulting (witness hiding) schemes is roughly twice that of the originals. Basically, any three-move, public coin identification scheme that is zero knowledge against the honest verifier and that is secure against passive impersonation attacks, is eligible for our transformation. This indicates that we need only seemlingly weak cryptographic intractability assumptions to construct a practical identification scheme resisting adative man-in-the-middle impersonation attacks. Moreover, the required primitive protocols can efficiently be constructed under the factoring or discrete logarithm assumptions.
Research done while employed at CWI, Amsterdam, The Netherlands
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
M. Abadi, E. Allender, A. Broder, J. Feigenbaum and L. Hemachandra: On Generating Solved Instances of Computational Problems, Proceedings of Crypto’ 88, Springer Verlag LNCS, vol. 403, pp. 297–310.
L. Babai and S. Moran: Arthur-Merlin Games: A Randomized Proof System and a Hierarchy of Complexity Classes, JCSS, vol. 36, pp. 254–276, 1988.
M. Bellare and O. Goldreich: On Defining Proofs of Knowledge, Proceedings of Crypto’ 92, Springer Verlag LNCS, vol. 740, pp. 390–420.
S. Bengio, G. Brassard, Y. Desmedt, C. Goutier and J.J. Quisquater: Secure Implementation of Identification Systems, Journal of Cryptology, 1991 (4): 175–183.
D. Chaum: Provers Can Limit the Number of Verifiers, unpublished.
R. Cramer and I. Damgård: Secure Signature Schemes based on Interactive Protocols, Proceedings of Crypto’ 95, Springer Verlag LNCS, vol. 963, pp. 297–310.
R. Cramer, I. Damgård and B. Schoenmakers: Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols, Proceedings of Crypto’ 94, Springer verlag LNCS, vol. 839, pp. 174–187.
D. Dolev, C. Dwork and M. Naor: Non-malleable cryptography, Proceedings of STOC’ 91, pp. 542–552.
A. Fiat and A. Shamir: How to Prove Yourself: Practical Solutions to Identification and Signature Problems, Proceedings of Crypto’ 86, Springer Verlag LNCS, vol. 263, pp. 186–194
U. Feige, A. Shamir: Witness Indistinguishable and Witness Hiding Protocols, Proceedings of STOC’ 90, pp. 416–426.
U. Feige, A. Fiat and A. Shamir: Zero-Knowledge Proofs of Identity, Journal of Cryptology 1 (1988) 77–94.
U. Feige and A. Shamir: Zero-Knowledge Proofs of Knowledge in Two Rounds, Proceedings of Crypto’ 89, Springer Verlag LNCS, vol. 435, pp. 526–544.
S. Goldwasser, S. Micali and C. Rackoff: The Knowledge Complexity of Interactive Proof Systems, SIAM J. Computing, Vol. 18, pp. 186–208, 1989.
Efficient Identification Schemes Secure against Impersonation and Man-in-the-Middle Attacks, preprint, October 1995.
L. Guillou, J.J. Quisquater: A Practical Zero-Knowledge Protocol fitted to Security Microprocessor Minimizing both Transmission and Memory, Proceedings of Eurocrypt’ 88, Springer Verlag LNCS, vol. 330, pp. 123–128.
M. Jacobson, R. Impagliazzo and K. Sako: Designated Verifier Proofs and their Applications, Proc. of Eurocrypt’ 96, Springer Verlag LNCS, vol. 1070, pp. 143–154.
T. Okamoto: Provably Secure and Practical Identification Schemes and Corresponding Signature Schemes, Proceedings of Crypto’ 92, Springer Verlag LNCS, vol. 740, pp. 31–53.
C. P. Schnorr: Efficient Signature Generation by Smart Cards, Journal of Cryptology, 4(3): 161–174, 1991.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cramer, R., Damgård, I. (1997). Fast and Secure Immunization Against Adaptive Man-in-the-Middle Impersonation. In: Fumy, W. (eds) Advances in Cryptology — EUROCRYPT ’97. EUROCRYPT 1997. Lecture Notes in Computer Science, vol 1233. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-69053-0_7
Download citation
DOI: https://doi.org/10.1007/3-540-69053-0_7
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-62975-7
Online ISBN: 978-3-540-69053-5
eBook Packages: Springer Book Archive