Abstract
Discrete log based identification and signature schemes are well-suited to identity proof and signature generation, but not suitable for verification, by smart cards, due to their highly asymmetric compu- tational load between the prover/signer and the verifier. In this paper, we present very efficient and practical protocols for fast verification in these schemes, where the verifier with limited computing power per- forms its computation fast with the aid of the powerful prover/signer. The proposed protocols require very small amounts of computation and communication. The prover/signer only needs to perform a few modular exponentiations in real-time and the two interacting parties only need to communicate a few long numbers. Using the proposed prover-aided verification (PAV) protocol, the verifier can perform the Schnorr-like identification scheme almost as fast as the Guillou-Quisquater scheme. We generalize the PAV protocol into the signer-aided verification (SAV) protocol, which can be used for verification of any public function.
Chapter PDF
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
A. Fiat and A. Shamir: ‘How to prove yourself: Practical solution to identification and signature problems’, Advances in Cryptology-Crypto '86, Springer-Verlag, pp.186–194 (1988).
L.C. Guillou and J.J. Quisquater: ‘A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory’, Advances in Cryptology-Eurocrypt'88, Springer-Verlag, pp.123–128 (1988).
K. Ohta and T. Okamoto: ‘A modification of the Fiat-Shamir scheme’, Advances in Cryptology-Crypto'88, Springer-Verlag, pp.232–243 (1990).
C.P. Schnorr: ‘Efficient signature generation by smart cards’, Journal of Cryptology, 4(3), pp.161–174 (1991).
E.F. Brickell and K.S. McCurley: ‘An interactive identification scheme based on discrete logarithm and factoring’, Journal of Cryptology, 5(1), pp.29–39 (1992).
T. Okamoto: ‘Provably secure and practical identification schemes and corresponding signature schemes’, Advances in Cryptology-Crypto'92, Springer-Verlag, pp.31–53 (1993).
E.F. Brickell, D.M. Gordon, K.S. McCurley and D.B. Wilson: ‘Fast exponentiation with precomputation’, Advances in Cryptology-Eurocrypt'92, Springer-Verlag, pp.200–207 (1993).
C.H. Lim and P.J. Lee: ‘More flexible exponentation with precomputation’, Advances in Cryptology-Crypto'94, Springer-Verlag, pp.95–107 (1994).
P. de Rooij: ‘Efficient exponentiation using precomputation and vector addition chains’, In Pre-proceedings of Eurocrypt'94, pp.403–416 (1994).
T. Matsumoto, K. Kato and H. Imai: ‘Speeding up secret computations with insecure auxiliary devices’, Advances in Cryptology-Crypto'88, Springer-Verlag, pp.497–506 (1990).
J.J. Quisquater and M. De Soete: ‘Speeding up smart card RSA computation with insecure coprocessors’, In Proc. Smart Card 2000, North-Holland, 191–197 (1991).
B. Pfitzmann and M. Waidner: ‘Attacks on protocols for server-aided RSA computation’, Advances in Cryptology-Eurocrypt'92, Springer-Verlag, pp.153–162 (1993).
T. Matsumoto, H. Imai, C.S. Laih and S.M. Yen: ‘On verifiable implicit asking protocols for RSA computation’, Advances in Cryptology-Auscrpyt'92, Springer-Verlag, pp.296–308 (1993).
S. Kawamura and A. Shimbo: ‘Fast server-aided secret computation protocols for modular exponentiation’, IEEE J. Selected Areas in Commun., 11(5), 778–784 (1993).
J. Burns and C.J. Mitchell: ‘Parameter selection for server-aided RSA computation schemes’, IEEE Trans. Computers, 43(2), 163–174 (1994).
S.M. Yen and C.S. Laih: ‘Server-aided honest computation for cryptographic applications’, Computers Math. Applic., 26(12), pp.61–64 (1993).
U. Feige, A. Fiat and A. Shamir: ‘Zero-knowledge proofs of identity’, J. Cryptology, 1(2), pp.77–94 (1988).
M. Girault: ‘An identity-based identification scheme based on discrete logarithms modulo a composite number’, Advances in Cryptology-Eurocrypt'90, Springer-Verlag, pp.481–486 (1991).
M. Girault: ‘Self-certificated public keys’, Advances in Eurocrypt'91, Springer-Verlag, pp.490–497 (1991).
K. Nyberg and R. Rueppel: ‘Message recovery for signature schemes based on the discrete logarithm problem’, submitted to Designs, Codes and Cryptography (also appears in Pre-proceedings of Eurocrypt'94).
P. Horster, H. Petersen and M. Michels: ‘Meta-ElGamal signature schemes’, In Proceedings of 2nd ACM Conference on Computer and Communication Security (1994).
P. Horster, H. Petersen and M. Michels: ‘Meta message recovery and meta blinded signature schemes based on the discrete logarithm problem and their applications’, In Pre-Proceedings of Asiacrypt'94, pp.185–196 (1994).
L. Harn and Y. Xu: ‘Design of generalized ElGamal type digital signature schemes based on discrete logarithm’, Electronics Letters, 30(24), pp.2025–2026 (1994).
NIST: ‘Digital signature standard’, FIPS PUB 186 (1994).
S. Goldwasser, S. Micali and C. Rackoff: ‘The knowledge complexity of interactive proof systems’, SIAM J. Comput., 18(1), pp.186–208 (1989).
D. Naccache, D. M'raihi, D. Raphaeli and S. Vaudenay: ‘Can D.S.A. be improved ?-Complexity trade-offs with the digital signature standard’, In Pre-proceedings of Eurocrypt'94 (1994).
C.H. Lim and P.J. Lee: ‘Security of interactive DSA batch verification’, Electronics Letters, 30(19), pp.1592–1593 (1994).
C.H. Lim and P.J. Lee: ‘Fast authenticated key exchange with the aid of the communicating partner’, in preparation (available from the authors by e-mail).
C.H. Lim and P.J. Lee: ‘Signer-aided probabilistic verification of digital signatures using random decomposition’, in preparation (available from the authors by e-mail).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lim, C.H., Lee, P.J. (1995). Server(Prover/Signer)-Aided Verification of Identity Proofs and Signatures. In: Guillou, L.C., Quisquater, JJ. (eds) Advances in Cryptology — EUROCRYPT ’95. EUROCRYPT 1995. Lecture Notes in Computer Science, vol 921. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-49264-X_6
Download citation
DOI: https://doi.org/10.1007/3-540-49264-X_6
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-59409-3
Online ISBN: 978-3-540-49264-1
eBook Packages: Springer Book Archive