Abstract
A new public key cryptosystem based on propositional calculus is presented. The system is proved optimal in the sense that any cryptanalytic method against it can be used to break other cryptosystems as well. Such a cryptanalytic method could also be used to solve in polynomial time the membership problem of any language in NPnCoNP. Only worst case complexities are considered.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
W. Diffie and M. Hellman, New directions in cryptography, IEEE Transactions on Information Theory IT-22 (1976), 644–654.
S. Goldwasser and S. Micali, Probabilistic encryption & how to play mental poker keeping secret all partial information, in: Proceedings of the 14th ACM Symposium on the Theory of Computing (1982), 365–377.
A. Salomaa, Computation and Automata (Cambridge University Press, 1985).
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1989 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kari, J. (1989). A cryptosystem based on propositional logic. In: Dassow, J., Kelemen, J. (eds) Machines, Languages, and Complexity. IMYCS 1988. Lecture Notes in Computer Science, vol 381. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0015940
Download citation
DOI: https://doi.org/10.1007/BFb0015940
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-51516-6
Online ISBN: 978-3-540-48203-1
eBook Packages: Springer Book Archive