Abstract
We describe a probabilistic polynomial-time process calculus for analyzing cryptographic protocols and use it to derive compositionality properties of protocols in the presence of computationally bounded adversaries. We illustrate these concepts on oblivious transfer, an example from cryptography. We also compare our approach with a framework based on interactive Turing machines.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abadi, M., Gordon, A.: A calculus for cryptographic protocols: the spi-calculus. Information and Computation 143, 1–70 (1999)
Abadi, M., Rogaway, P.: Reconciling two views of cryptography (The computational soundness of formal encryption). Journal of Cryptology 15(2), 103–127 (2002)
Backes, M., Jacobi, C., Pfitzmann, B.: Deriving cryptographically sound implementations using composition and formally verified bisimulation. In: Formal Methods Europe. LNCS, vol. 2931, pp. 310–329. Springer, Heidelberg (2002)
Backes, M., Pfitzmann, B., Waidner, M.: Universally composable cryptographic library. Manuscript available on eprint.iacr.org as 2003/015 (2003)
Beaver, D.: Foundations of secure interactive computing. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 377–391. Springer, Heidelberg (1992)
Beaver, D.: Secure multiparty protocols and zero-knowledge proof systems tolerating a faulty minority. Journal of Cryptology 4, 75–122 (1991)
Canetti, R.: Universally composable security: A new paradigm for cryptographic protocols. In: 42-nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 136–145. IEEE Press, Los Alamitos (2001), Full paper available at eprint.iacr.org as 2000/067
Canetti, R., Krawczyk, H.: Analysis of key-exchange protocols and their use for building secure channels. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 453–474. Springer, Heidelberg (2001)
Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally composable twoparty and multi-party secure computation. In: 34-th ACM Symposium on Theory of Computing, pp. 484–503 (2002), Full paper available at eprint.iacr.org as 2002/140
Dolev, D., Yao, A.: On the security of public-key protocols. In: Proc. 22-nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 350–357 (1981)
ElGamal, T.: A public-key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory IT-31, 469–472 (1985)
Even, S., Goldreich, O., Lempel, A.: A randomized protocol for signing contracts. Communications of the ACM 28(6), 637–647 (1985)
Goldreich, O.: Foundations of Cryptography: Basic Tools. Cambridge Univ. Press, Cambridge (2001)
Goldreich, O.: Foundations of Cryptography – Vol. 2. Working Draft of Ch. 7 (2003), Available at www.wisdom.weizmann.ac.il/~oded
Goldwasser, S., Levin, L.: Fair computation of general functions in presence of immoral majority. In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 77–93. Springer, Heidelberg (1991)
Lincoln, P., Mitchell, J., Mitchell, M., Scedrov, A.: Probabilistic polynomialtime framework for protocol analysis. In: Reiter, M. (ed.) 5-th ACM Conferece on Computer and Communication Security, pp. 112–121. ACM Press, New York (1998)
Lincoln, P., Mitchell, J., Mitchell, M., Scedrov, A.: Probabilistic polynomialtime equivalence and security analysis. In: Wing, J.M., Woodcock, J.C.P., Davies, J. (eds.) FM 1999. LNCS, vol. 1708, pp. 776–793. Springer, Heidelberg (1999)
Lynch, N.: Distributed Algorithms. Morgan Kaufman, San Francisco (1996)
Mateus, P., Pacheco, A., Pinto, J., Sernadas, A., Sernadas, C.: Probabilistic situation calculus. Annals of Mathematics and Artificial Intelligence 32(1), 393–431 (2001)
Micali, S., Rogaway, P.: Secure computation. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 392–404. Springer, Heidelberg (1992)
Milner, R.: Communication and Concurrency. Prentice-Hall, Englewood Cliffs (1989)
Mitchell, J., Mitchell, M., Scedrov, A.: A linguistic characterization of bounded oracle computation and probabilistic polynomial time. In: 39-th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 725–733. IEEE Computer Society Press, Los Alamitos (1998)
Mitchell, J., Ramanathan, A., Scedrov, A., Teague, V.: A probabilistic polynomial-time calculus for analysis of cryptographic protocols. Electronic Notes in Theoretical Computer Science 45 (2001)
Needham, R., Schroeder, M.: Using encryption for authentication in large networks of computers. Communications of the ACM 21(12), 993–999 (1978)
Pfitzmann, B., Schunter, M., Waidner, M.: Cryptographic security of reactive systems. Electronic Notes in Theoretical Computer Science 32 (2000)
Pfitzmann, B., Waidner, M.: Composition and integrity preservation of secure reactive systems. In: 7-th ACM Conference on Computer and Communications Security, pp. 245–254. ACM Press, New York (2000)
Rabin, M.: How to exchange secrets by oblivious transfer. Tech. memo TR-81, Aiken Computation Laboratory, Harvard U (1981)
Roscoe, A.W.: Modelling and verifying key-exchange protocols using CSP and FDR. In: 8-th IEEE Computer Security Foundations Workshop (CSFW). IEEE Computer Society Press, Los Alamitos (1995)
Schneider, S.: Security properties and CSP. In: IEEE Symposium Security and Privacy (1996)
Yao, A.: Theory and applications of trapdoor functions. In: 23-rd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 80–91. IEEE Press, Los Alamitos (1982)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mateus, P., Mitchell, J., Scedrov, A. (2003). Composition of Cryptographic Protocols in a Probabilistic Polynomial-Time Process Calculus. In: Amadio, R., Lugiez, D. (eds) CONCUR 2003 - Concurrency Theory. CONCUR 2003. Lecture Notes in Computer Science, vol 2761. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45187-7_22
Download citation
DOI: https://doi.org/10.1007/978-3-540-45187-7_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40753-9
Online ISBN: 978-3-540-45187-7
eBook Packages: Springer Book Archive