×

Mathematical problems in cryptology. (English) Zbl 0851.94017

The paper contains a wide ranging survey of the problems of interest in modern cryptography. Beginning with some historical background and terminology, it gives a brief description of data encryption standard (DES) and public key cryptography, including systems based on knapsacks, the linear code system of McEliece and systems based on formal language theory and on partially linear transformations. The RSA system is also described. The wide variety of cryptographic protocols available, including threshold schemes, resiliency, contract signing, identification and many others, are noted. The role of complexity theory in cryptography is discussed with particular attention to the characteristics of one-way functions. The existence of secure pseudorandom generators is considered. Sections on the notions of probabilistic encryption, cryptographic security and NP-completeness and zero-knowledge proofs conclude the paper. One hundred and sixty references are included. 169 Refs.

MSC:

94A60 Cryptography
94-02 Research exposition (monographs, survey articles) pertaining to information and communication theory
68P25 Data encryption (aspects in computer science)

Software:

McEliece
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] W. Alexi, B. Chor, O. Goldreich, and C. P. Schnorr, ?RSA/Rabin bits are 1/2 + l/poly(logn) secure,? In:Proc. 25th Annu. IEEE Symp. on Found. Comput. Sci., 1984, pp. 449?457.
[2] W. Alexi, B. Chor, O. Goldreich, and C. Schnorr, ?RSA/Rabin bits are 1/2 + 1/poly secure,?SIAM J. Comput.,17, No. 2, 194?209 (1988). · Zbl 0644.94011 · doi:10.1137/0217013
[3] E. W. Allender, ?Some consequences of the existence of pseudorandom generators,? In:Proc. 19th Annu. ACM Symp. on Theory of Comput., 1987, pp. 151?159.
[4] L. Babai, ?Trading group theory for randomness,? In:Proc. 17th Annu. ACM Symp. on Theory of Comput., 1985, pp. 421?429.
[5] E. Bach and J. Shallit, ?Factoring with cyclothomic polynomials,?Math. Comput.,52, No. 185, 201?219 (1989). · Zbl 0661.10008 · doi:10.1090/S0025-5718-1989-0947467-1
[6] W. W. R. Ball and H. S. M. Coxeter,Mathematical Recreation and Essays, Toronto Univ. Press, (1974).
[7] E. Bazeries,Les Chiffres Secrets Devoiles, Paris (1901).
[8] D. Beaver, ?Perfect privacy for two party protocols,? Technical Report TR-11-89, Harvard University (1989). · Zbl 0722.68007
[9] M. Bellare, S. Micali, and R. Ostrovsky, ?Perfect zero-knowlege in constant rounds,? In:Proc. 22nd Annu. ACM Symp. on Theory of Comput., 1990, pp. 482?493.
[10] J. D. Benaloh (Cohen) and M. Yung, ?Distributing the power of a government to enhance the privacy of voters,? In:Proc. of the 5th ACM Symp. on Principles of Distributed Comput., 1986.
[11] M. Ben-Or et al., ?Everything provable is provable in zero-knowlege,?CRYPTO-88 (proceedings). Goldwasser, S. (ed.), Springer-Verlag, Led. Notes Computer Sci.,403, 37?56 (1990).
[12] M. Ben-Or, S. Goldwasser, and A. Wigderson, ?Completeness theorems for noncryptographic faulttolerant distributed computation,? In:Proc. 20th Annu. ACM Symp. on Theory of Comput., 1988, pp. 1?10.
[13] M. Ben-Or and N. Linial, ?Collective coin-flipping, robust voting schemes and minima of Banzhaf values,? In:Proc. 26th Annu. IEEE Symp. on Found, of Computer Sci., 1985, pp. 408?416.
[14] B. V. Berezin and P. V. Doroshkevich, ?Digital signature scheme based on traditional cryptography,?Zashchita Informatsii,2, 148?167 (1992).
[15] R. Berger, S. Kannan, and R. Peralta, ?A framework for the study of cryptographic protocols,?Proc. CRYPTO-85, Springer. Led. Notes Comput. Sci., No. 215, 87?103 (1985). · Zbl 0598.94009
[16] E. R. Berlekamp,Algebraic Coding Theory, McGraw-Hill, New York (1968). · Zbl 0988.94521
[17] E. R. Berlekamp, ?Factoring polynomials over large finite fields,?Math. Comput.,24, 713?735 (1978). · Zbl 0247.12014 · doi:10.1090/S0025-5718-1970-0276200-X
[18] G. R. Blakley, ?Safeguarding cryptographic keys,? In:Proc. of AFIPS National Computer Conference, Vol. 48, 1979, pp. 313?317.
[19] M. Blum, ?Three applications of the oblivious transfer. Part I: Coin flipping by telephone. Part II: How to exchange secrets. Part III: How to send certified electronic mail,? Dept. EECS, University of California, Berkeley, California (1981).
[20] M. Blum, ?Coin flipping by telephone: A protocol for solving impossible problems,? In:Proc. 24th IEEE Compcon 133?137 (1982),SIGACT News, Vol. 15, 1983, pp. 23?27.
[21] M. Blum, ?All-or-nothing certified mail.?Workshop on Mathematical Aspects of Cryptography, Endicott House, MIT (1985).
[22] M. Blum and S. Micali, ?How to generate cryptographically strong sequences of pseudo-random bits,?SIAM J. Comput. 13, No. 4, 850?864 (1984). · Zbl 0547.68046 · doi:10.1137/0213053
[23] J. Boyar, G. Brassard, and R. Peralta, ?Subquadratic zero-knowledge,? In:Proc. 32nd Annu. IEEE Symp. on Found, of Comput. Sci., 1991, pp. 69?78. · Zbl 0890.68054
[24] G. Brassard, C. Crépeau, and J.-M. Robert, ?Information theoretic reductions among disclosure problems,? In:Proc. 27th Annu. IEEE Symp. on Found, of Computer Sci., 1986, pp. 168?173.
[25] E. F. Brickell and A. M. Odlyzko, ?Cryptoanalysis: A survey of recent results.?Proc. IEEE,76, No. 5. 578 593 (1988). · Zbl 0818.94014 · doi:10.1109/5.4443
[26] J. L. Carter and M. N. Wegman, ?Universal classes of hash functions,?J. Comput. Syst. Sci.,18, No. 2, 143 154 (1979). · Zbl 0412.68090 · doi:10.1016/0022-0000(79)90044-8
[27] D. Chaum, C. Crépeau, and I. Damgård, ?Multiparty unconditionally secure protocols,? In:Proc. 20th Annu. ACM Symp. on Theory of Comput., 1988, pp. 11?19.
[28] B. Chor, M. Geréb-Graus. and E. Kushilevitz, ?Private computations over the integers,? In:Proc. 31st Annu. IEEE Symp. on Found, of Computer Sci., 1990, pp. 335?344.
[29] B. Chor and E. Kushilevitz, ?A zero-one law for Boolean privacy,? In:Proc. 21th Annu. ACM Symp. on Theory of Comput., 1989, pp. 62?72. · Zbl 0717.94009
[30] B. Cleor and R. Rivest, ?A knapsack type public key cryptosystem based on arithmetic in finite fields,? In:Proc. CRYPTO-84, New York, NY:Springer-Verlag, 1985, pp. 54?65.
[31] I. Cohen and M. Fisher, ?A robuts and verifiable cryptographically secure election scheme,? In:Proc. 26th Annu. IEEE Symp. on Found of Computer Sci., 1985, pp. 372?382,
[32] D. Coppersmith, ?Fast evaluation of logarithms in fields of characteristic two,?IEEE Trans. Inf. Theory,30, No. 4, 587?594 (1984). · Zbl 0554.12013 · doi:10.1109/TIT.1984.1056941
[33] D. Coppersmith. A. M. Odlyzko, and R. Schroeppel, ?Discrete logarithms in GF(p),?Algorithmica,1, 1?15 (1986). · Zbl 0631.12010 · doi:10.1007/BF01840433
[34] Data Encryption Standard 1977,Federal Information Processing Standard (FIPS), Publication 46, National Bureau of Standards. U. S. Department of Commerce: Washington, DC. (January, 1977).
[35] R. M. Davis, ?The Data Encryption Standard in perspective,?IEEE Communications Society Magazine,16, 5?9 (1978). · doi:10.1109/MCOM.1978.1089771
[36] A. de Grandpre,La Cryptographie Pratique, Paris (1905).
[37] H. M. Deitel,An Introduction to Operating Systems, Addison-Wesley, Reading, Massachusetts (1984).
[38] R. A. Demillo, N. A. Lynch, and M. J. Merritt, ?Cryptographic protocols,? In:Proc. 14th Annu. ACM Symp. on Theory of Com-put., 1982, pp. 383?400.
[39] ?DES-Algorithmus entschlusselt??Datenschutz-Berater,12, No. 5, 3?5 (1989).
[40] W. Diffie, ?The first ten years of public-key cryptography,?Proc. IEEE,76, No. 5, 560?577 (1988). · doi:10.1109/5.4442
[41] W. Diffie and M. Hellman, ?New directions in cryptography,?IEEE Trans. Inform. Theory,IT-22, 644?654 (1976). · Zbl 0435.94018 · doi:10.1109/TIT.1976.1055638
[42] W. Diffie and M. E. Hellman, ?A critique of the proposed Data Encryption Standard,?Comm. ACM,19, 164?165 (1976).
[43] W. Diffie and M. E. Hellman, ?Exhaustive cryptoanalysis of the NBS data encryption standard,?Computer,10, 74?84 (June 1977). · Zbl 05332334 · doi:10.1109/C-M.1977.217750
[44] W. Dime and M. E. Hellman, ?Privacy and authentication: an introduction to cryptography,?Proc. IEEE,67, No. 3, 397?427 (1979). · doi:10.1109/PROC.1979.11256
[45] D. Dolev. C. Dwork, O. Waarts, and M. Yung, ?Perfectly secure message transmission,? In:Proc. 31st Annu. IEEE Symp. on Found, of Computer Sci., 1990, pp. 36?45. · Zbl 0774.68017
[46] C. Dwork, D. Shmoys, and L. Stockmeyer, ?Flipping persuasively in constant time,?SIAM J. Computing,19, No. 3, 472?499 (1990). · Zbl 0698.68043 · doi:10.1137/0219032
[47] T. El Gamal, ?A public key cryptosystem and a, signature scheme based on discrete logarithms,?IEEE Trans. Inform. Theory,IT-31, 469?472 (1985).
[48] S. Even, O. Goldreich, and A. Lempel, ?A randomized protocol for signing contracts,?Commun. ACM,28, 637?647 (1985). · Zbl 0538.94011 · doi:10.1145/3812.3818
[49] S. Even, A. Selman, and Y. Yacobi, ?The complexity of promise problems with applications to publickey cryptography,?Inf. Control,61, No. 2, 159?173 (1984). · Zbl 0592.94012 · doi:10.1016/S0019-9958(84)80056-X
[50] S. Even and Y. Yacobi, ?Cryptocomplexity and NP-completeness,? In:Proc. 8th Colloq. on Automata, Languages and Programming, Lecture Notes in Computer Science, Springer-Verlag, Berlin, 1980, pp. 195?207. · Zbl 0444.94013
[51] A. Fiat and A. Shamir, ?How to prove yourself: practical solutions to identification and signature problems.? (Technical Report), The Weizmann Institute of Science, Rehevot, Israel (1986).
[52] A. Figl,Sisteme des Chiffrierens, Graz (1923).
[53] L. Fort now, ?The complexity of perfect zero-knowledge,? In:Proc. 19th Annu. ACM Symp. on Theory of Comput., 1987, pp. 204?209.
[54] E. M. Gabidulin, A. V. Paramonov, and O. V. Tretjakov, ?Ideals over a non-commutative ring and their applications in cryptology.? In:Proc. EUROCRYPT’91, Lecture Notes in Computer Science, No. 547. Springer-Verlag, New York, 1991. · Zbl 0766.94009
[55] M. R. Garey and D. S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, New York (1979). · Zbl 0411.68039
[56] C. M. Givierge,Course de Cryptographie, Paris (1925).
[57] O. Goldreich, ?A simple protocol for signing contracts.? In:Proc. CRYPTO 83, Plenum Press, 1984, pp. 133?136.
[58] O. Goldreich, ?A uniform complexity treatment of encryption and zero-knowledge,?Technion CS-TR 570 (June 1989). · Zbl 0795.68069
[59] O. Goldreich et al., ?Security preserving amplification of hardness,? In:31st Annu. IEEE Symp. on Found, of Comput. Sci., 1990, pp. 318?326.
[60] O. Goldreich, S. Goldwasser, and S. Micali, ?How to construct random functions,? In:Proc. 25th Annu. IEEE Symp. on Found, of Computer Sci., 1984, pp. 464?479. · Zbl 0596.65002
[61] O. Goldreich and H. Krawczyk, ?On the composition of zero-knowledge proof systems,? In:Proc. 17th Internat. Coll. on Automata, Languages and Programming, Springer, Berlin (1990). · Zbl 0766.68033
[62] O. Goldreich, H. Krawczyk, and M. Luby, ?On the existence of pseudo-random generators,? In:Proc. 29th Annu. IEEE Symp. on Found, of Comput. Sci., 1988, pp. 12?24.
[63] O. Goldreich and L. A. Levin, ?A hard-core predicate for all one-way functions,? In:Proc. 21st Annu. ACM Symp. on Theory of Comput., 1989, pp. 25?32.
[64] O. Goldreich, S. Micali, and A. Wigderson, ?Proofs that yield nothing but their validity and a methodology of cryptographic protocol design,? In:Proc. 27th IEEE Symp. on Found, of Computer Sci., 1986, pp. 174?187.
[65] O. Goldreich. S. Micali, and A. Wigderson, ?How to play any mental game,? In:Proc. 19th Annu. ACM Symp. on Theory of Com-put., 1987, pp. 218?229. · Zbl 0636.94010
[66] S. Goldwasser and S. Micali, ?Probabilistic encryption,?J. Comput. Syst. Sci.,28, 270?299 (1984). · Zbl 0563.94013 · doi:10.1016/0022-0000(84)90070-9
[67] S. Goldwasser, S. Micali, and C. Rackoff, ?The knowledge complexity of interactive proof systems,? In:Proc. 17th Annu. ACM Symp. on Theory of Comput., 1985, pp. 291?304. · Zbl 0900.94025
[68] S. Goldwasser and M. Sipser, ?Private coins versus public coins in interactive proof systems,? In:Proc. 18th Annu. ACM Symp. on Theory of Comput., 1986, pp. 59?68.
[69] R. M. Goodman and A. J. McAuley, ?A new trapdoor knapsack public key cryptosystem,? In:Advances in Cryptology, EUROCRYPT’84, New York, NY, Springer-Verlag, 1985, pp. 150?158. · Zbl 1392.94915
[70] Guan Puhua, ?Cellular automaton public-key cryptosystem,?Complex Systems,1, 51?57 (1987).
[71] Guan Puhua, ?Public-key cryptosystem based on higher order cellular automata,?IEEE Trans. Inf. Theory (1987). · Zbl 0652.94014
[72] Guan Puhua and H. Zassenhaus, ?Solving systems of equations over finite fields,?J. Number Theory (1987).
[73] J. Hastad, ?Solving simultaneous modular equations of low degree.?SIAM J. Comput.,17, No. 2, 336 341 (1988). · Zbl 0642.94029 · doi:10.1137/0217019
[74] J. Hastad, ?Pseudo-random generators under uniform assumptions.? In:Proc. 22nd Annu. ACM Symp. on Theory of Comput., 1990, pp. 395?404.
[75] M. E. Hellman, ?A cryptoanalytic time-memory tradeoff,?IEEE Trans. Inf. Theory,IT 26, 401?406 (1980). · Zbl 0436.94016 · doi:10.1109/TIT.1980.1056220
[76] L. S. Hill, ?Cryptography in an algebraic alphabet,?Amer. Math. Monthly,36, No. 6, 306?312 (1929). · JFM 55.0062.08 · doi:10.2307/2298294
[77] L. S. Hill, ?Concerning certain linear transformation apparatus of cryptography,?Amer. Math. Monthly,38, No. 3, 135?154(1931). · JFM 57.0120.01 · doi:10.2307/2300969
[78] A. Hodges,Alan Turing; The Enigma of Intelligence, Unwin Paperbacks (1985). · Zbl 0541.68001
[79] S. Homer and J. Wang, ?Absolute results concerning one-way functions and their applications,?Math. Syst. Theory. 22, No. 1, 21?35 (1989). · Zbl 0677.94008 · doi:10.1007/BF02088290
[80] M.-D. A. Huang and S.-H. Teng, ?Secure and verifiable schemes on election and general distributed computing problems,? In:7th Annual ACM Symposium on Principles of Distributed Computing, 1988, pp. 182?196.
[81] M.-D. Huang and S.-H. Teng, ?A universal problem in secure and verifiable distributed computation,? In:Advances in Cryptology CRYPTO’88, Lecture Notes in Comput. Sci., Springer-Verlag, New York, Berlin, 1988, pp. 336?351.
[82] M.-D. Huang and S.-H Teng, ?Security, verifiability and universality in distributed computing,?J. Algorithms,11, 492?521 (1990). · Zbl 0709.68019 · doi:10.1016/0196-6774(90)90023-8
[83] R. Impagliazzo L. Levin, and M. Luby, ?Pseudo-random generation from one-way functions,? In:Proc. 21st Symp. on Theory of Comput., 1989, pp. 12?24.
[84] D. Joseph and P. Young, ?Some remarks on witness functions for nonpolynomial and noncomplete sets in NP.?Theor. Comput. Sci.,39, 225?237 (1985). · Zbl 0597.68042 · doi:10.1016/0304-3975(85)90140-9
[85] D. Kahn,The Codebreakers: The Story of Secret Writing, Mac Millan, New York (1967).
[86] J. Kari, ?A cryptoanalytic observation concerning systems based on language theory,?Discr. Appl. Math.,21, No. 23, 265?268 (1988). · Zbl 0664.94013 · doi:10.1016/0166-218X(88)90073-X
[87] J. Kari, ?Observations concerning a public-key cryptosystem based on iterated morphisms,?Theoretical Computer Sci.,66, No. 1, 45?53 (1989). · Zbl 0674.94009 · doi:10.1016/0304-3975(89)90144-8
[88] J. Kari, ?Security of ciphering in view of complexity theory,?MTA Szamitas techn., es autom. kut. intez. tanulm., No. 208, 163?169 (1988).
[89] Ko Ker-I, T. J. Long, and Du Ding-Zhu, ?On one-way functions and polynomial-time isomorphisms,?Theor. Comput. Sci.,47, No. 3, 263?276 (1986). · Zbl 0635.68038 · doi:10.1016/0304-3975(86)90152-0
[90] N. Koblitz, ?Use of algebraic curves in public-key cryptography,?Cryptography Tagungsber. Math. Forschungsinst., Oberwolfach, No. 41, 18 (1989).
[91] K. Kurosawa and K. Matsu, ?M mod 3 security of RSA,?Electronics Letters,25, No. 7, 445?446 (1989). · Zbl 0684.94011 · doi:10.1049/el:19890305
[92] E. Kushilevitz, ?Privacy and communication complexity,? In:Proc. 30th IEEE Symp. on Found, of Computer Sci., 1989, pp. 416?421.
[93] L. Lamport, ?Constructing digital signatures from one-way functions,?SRI Intl. CSL-98, (1979).
[94] A. Lange,De la Cryptographie, Paris (1918).
[95] A. Lange and E. A. Soudart,Traité de Cryptographie, Paris (1925).
[96] M. Leclerc, ?A linear algorithm for breaking periodic Vernam ciphers,?Ars Combinatoria,27, 177?179 (1989). · Zbl 0672.94006
[97] A. K. Lenstra, ?Fast and rigorous factorization under the generalized Riemann hypothesis,?Proc. A. Kon. Ned. Akad. Wetensch.,91, No. 4, 443?454 (1983). · Zbl 0669.10012
[98] A. K. Lenstra. H. W. Lenstra, M. S. Manasse, and J. M. Pollard, ?The number field sieve? (Preprint). · Zbl 0806.11065
[99] L. A. Levin, ?One-way functions and pseudorandom generators.? In:Proc. 17th Annu. ACM Symp. on Theory of Comput., 1985, pp. 363?365. · Zbl 0641.68061
[100] Li Gong, ?Verifiable-text attacks in cryptographic protocols,? In:IEEE INFOCOM’90: Conf. Comput. Commun.: 9th Annu. Jt. Conf. IEEE Comput. and Commun. Soc. ?Multiple Facets, Integer,? San-Francis co, Calif., June 3?7, 1990, Vol. 2, Los Alamitos, California, 1990, pp. 686?693.
[101] D. L. Long and A. Wigderson, ?The discrete logarithm hides O(logn) bits,?SIAM J. Comput. 17, No. 2, 363?372 (1988). · Zbl 0644.94017 · doi:10.1137/0217021
[102] S. C. Lu and L. N. Lee, ?A simple and effective public-key cryptosystem,?COMSAT Tech. Rev., 15?24, (1979).
[103] M. Luby and C. Rackoff, ?How to construct pseudorandom permutations from pseudorandom functions,?SIAM J. Comput.,17, No. 2, 373?386 (1988). · Zbl 0644.94018 · doi:10.1137/0217022
[104] J. L. Massey, ?An introduction to contemporary cryptology,?Proc. IEEE,76, No. 5, 533?549 (1988). · doi:10.1109/5.4440
[105] ?Mathematical concepts of dependable systems.?Tagungsber., Math. Forschungsinst., Oberwolfach.,17, 1?20 (1990).
[106] K. S. McCurley, ?A key distribution system equivalent to factoring,?J. Cryptol.,1, No. 2, 95?105 (1988). · Zbl 0659.94003 · doi:10.1007/BF02351718
[107] R. J. McEliece, ?A public-key cryptosystem based on algebraic coding theory.? In:Deep Space Network Progress Report 42-44, Jet Propulsion Laboratory, Pasadena, 1978, pp. 114?116.
[108] R. McEliece and D. Sarwate, ?On sharing secrets and Reed-Solomon codes,?Commun. ACM,24, No. 9. 583?584 (1981). · doi:10.1145/358746.358762
[109] F. J. McWilliams and N. J. A. Sloane,The Theory of Error-Correcting Codes, North-Holland, Amsterdam (1977).
[110] R. Merkle,Letters to the Editor, Time Magazine,120, No. 20, 8 (Nov. 1982).
[111] R. C. Merkle and M. E. Hellman, ?Hiding information and signatures in trapdoor knapsa.cks,?IEEE Trans. Inform. Theory,IT-24, No. 5, 525?530 (Sept. 1978). · doi:10.1109/TIT.1978.1055927
[112] S. Micali, C. Rackoff, and R. Sloan, ?Notions of security of public-key cryptosystems,?SIAM J. Comput.,17, No. 2, 412?426 (1988). · Zbl 0644.94013 · doi:10.1137/0217025
[113] J. H. Moore, ?Protocol failures in cryptosystems,?Proc. IEEE,76, No. 5, 594?602 (1988). · doi:10.1109/5.4444
[114] R. Morris, ?The Data Encryption Standard-retrospective and prospects.?IEEE Comm. Soc. Mag.,16, 11?14 (1978). · doi:10.1109/MCOM.1978.1089783
[115] M. Naor and M. Yung, ?Universal one-way hash functions and their crytographic application,? In:Proc. 21st Annu. ACM Symp. on Theory of Comput., 1989, pp. 33?43.
[116] M. Naor and M. Yung, ?Public-key crytosystems provably secure against chosen ciphertext attacks,? In:Proc. 22nd Annu. ACM Symp. on Theory of Comput., 1990, pp. 427?437.
[117] H. Niederreiter, ?Knapsack-type cryptosystems and algebraic coding theory,?Problems Control Inform. Theory,15, 159?166 (1986). · Zbl 0611.94007
[118] A. M. Odlyzko, ?Discrete logarithms in finite fields and their cryptographic significance,? In:Led. Notes Comput. Sci., 1985, pp. 224?314. · Zbl 0594.94016
[119] E. Okamoto and K. Tanaka, ?Identity-based information security management system for personal computer networks,?IEEE J. Selec. Areas Commun.,7, No. 2, 290?294 (1989). · doi:10.1109/49.17700
[120] Y. Oren, ?On the cunning power of cheating verifiers: some observations about zero-knowledge proofs,?Proc. 28th Annu, Symp. on Found, of Comput. Sci., 462?471 (1987).
[121] C. H. Papadimitriou and K. Steiglitz,Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, Englewood Cliffs, New Jersey (1982). · Zbl 0503.90060
[122] J. P. Pieprzyk, ?On public-key cryptosystems built using polynomial rings,? In:Advances in Cryptology-Eurocrypt. 85, New York, NY: Springer-Verlag, 1986.
[123] C. Pomerance, ?The quadratic sieve factoring algorithm,?Led. Notes Comput. Sci., No. 209, 169?182 (1985). · Zbl 0596.10006 · doi:10.1007/3-540-39757-4_17
[124] M. O. Rabin, ?Digital signatures and public key functions as intractable as factorization,? In:Technical Memo TM-212, Lab. Comput. Sci., MIT (1979).
[125] T. Rabin and M. Ben-Or, ?Verifiable secret sharing and multiparty protocols with honest majority,” In:Proc. 21st Annu. ACM Symp. on Theory of Comput., 1989, pp. 73?85.
[126] C. Rackoff, ?Relativized questions involving probabilistic algorithms,?J. ACM. 29, No. 1, 261?268 (1982). · Zbl 0477.68037 · doi:10.1145/322290.322306
[127] H. Riesel, ?Modern factorization methods,?BIT,25, No. 1, 205?222 (1985). · Zbl 0607.10005 · doi:10.1007/BF01934998
[128] R. Rivest, A. Shamir, and L. Adleman, ?A method for obtaining digital signatures and public-key cryptosystems,?Comm. ACM,21, No. 2, 120?126 (1978). · Zbl 0368.94005 · doi:10.1145/359340.359342
[129] J. Rompel, ?One-way functions are necessary and sufficient for secure signatures,? In:Proc. 22nd Annu. ACM Symp. on Theory of Comput., 1990, pp. 387?394.
[130] G. Rosenberg, ?Some recent developments in formal language theory.? In:Proc. Int. Congress Math. Helsinki, 15?23 Aug., 1978, Vol. 2, Helsinki, 1980, pp. 973?978.
[131] A. Salomaa, ?The formal languages column.?Bull. eut. Assoc. Theor. Comput. Sci., No. 33, 42?53 (1987). · Zbl 0661.68072
[132] A. Saloma.a, and S. Yu, ?On a, public-key cryptosystem based on iterated morphisms and substitutions,?Theor. Comput. Sci.,48, 283?296 (1986). · Zbl 0636.94007 · doi:10.1016/0304-3975(86)90099-X
[133] C. P. Schnorr, ?Efficient indentification and signatures for smart cards,?Kryptographie Tagungsber. Math. Forschungsmst., Oberwolfach, No. 41, 18?19 (1989).
[134] A. W. Schrift and A. Shamir, ?The discrete log is very discreet,? In:Proc. 22nd Annu. ACM Symp. on Theory of Computing, 1990, pp. 405?415.
[135] A. L. Selman, ?Complexity issues in cryptograph,? In:Comput. Complexity Theory, Providence, Rhode Island, 1989, pp. 92?107.
[136] M. A. Seysen, ?Probabilistic factorization algorithm with quadratic forms of negative discriminant,?Math. Comput.,48, No. 178, 757?780 (1987). · Zbl 0619.10004 · doi:10.1090/S0025-5718-1987-0878705-X
[137] A. Shamir, ?How to share a secret,?Commun. ACM,29, 612?613 (1979). · Zbl 0414.94021 · doi:10.1145/359168.359176
[138] A. Shamir, ?Identity-based cryptosystems and signature schemes,? In:Proc. Crypto-84, Santa Barbara, California, 1984, pp. 47?53. · Zbl 1359.94626
[139] A. Shamir, ?A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem,?IEEE Trans. Inform. Theory, IT-30, No. 5, 699?704 (1984). · Zbl 0552.94007 · doi:10.1109/TIT.1984.1056964
[140] A. Shamir, ?The search for provably secure identification schemes,? In:Proc. of the Internat. Congress of Math., Berkeley, California, 1986, pp. 1488?1495.
[141] A. Shamir, ?A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosvstem,? In:Proc. 23rd Annu. IEEE Symp. on Found, of Computer Sci., 1982, pp. 145?152.
[142] A. Shamir, ?IP=PSPACE,? In:Proc. 31st Annu. IEEE Symp. on Found, of Computer Sci., 1990, pp. 11?15.
[143] A. Shamir and R. E. Zippel, ?On the security of the Merkle-Hellman cryptographic scheme,?IEEE Trans. Informat. Theory, IT-26, 339?340 (1980). · Zbl 0431.94031 · doi:10.1109/TIT.1980.1056197
[144] C. E. Shannon, ?A mathematical theory of communication,?Bell Syst. Techn. J.,27, No. 3, 379?423, (1948);27, No. 4, 623?656, (1948). · Zbl 1154.94303 · doi:10.1002/j.1538-7305.1948.tb01338.x
[145] C. E. Shannon, ?Communication theory of secrecy systems,?Bell Syst. Tech. J.,28, No. 4, 656?715, (1949). · Zbl 1200.94005 · doi:10.1002/j.1538-7305.1949.tb00928.x
[146] V. M. Sidelnikov and S. O. Shestakov, ?On insecurity of cryptosystems based on generalized Reed-Solomon codes.?Discrete Math. Appl.,2, No. 4, 439?444, (1992). · Zbl 0796.94006
[147] G. J. Simmons, ?Authentication theory/coding theory,? In:Advances in Cryptology, Proc. CRYPTO 84, Lecture Notes in Computer Science, No. 196, G. R. Blakley and D. Chaum, eds., New York: Springer, 1986, pp. 411?431.
[148] G. J. Simmons, ?A survey of information authentication,?Proc. IEEE,76, No. 5, 603?620 (1988). · doi:10.1109/5.4445
[149] J. Stern, ?Using error correcting codes in cryptography,?Cryptography Tagungsber. Math. Forschungsinst., Oberwolfach., No. 41, 11?12 (1989).
[150] I. Stewart, ?Factorizing large numbers,?Math. Spectrum,20, No. 3, 74?77 (1987?1988).
[151] K. G. Subramanian, R. Siromoney, and P. J. Abisha, ?A D0L-T0L public key cryptosystem,?Inf. Process. Lett.,26, No. 2, 95?97 (1987). · Zbl 0637.94014 · doi:10.1016/0020-0190(87)90044-5
[152] R. Sugarman et al., ?On foiling computer crime,?IEEE Sped., No. 16, 31?41 (July 1979). · doi:10.1109/MSPEC.1979.6368156
[153] P. L. E. Valerio,De la Cryptographie, Part 1, Paris (1893); Part 2. Paris (1896).
[154] B. Vallee, ?Factorization entière par generation quasi-uniforme de petits residus quadratiques.?C. R. Acad. Sci. Ser. 1,308, No. 3, 59?62 (1989).
[155] B. L. Van Der Waerden,Algebra I, Springer-Verlag, Berlin (1971).
[156] H. O. Vardlay.The American Black Chamber, Indianapolis (1931).
[157] O. N. Vasilenko, ?Current methods for testing for primality of numbers. A survey,?Kybernet. Sb., No. 25: 162?188 (1988). · Zbl 0669.10013
[158] U. V. Vazirani and V. V. Vazirani, ?RSA bits are 0. 732+? secure.? In:Sec. Adv. Cryptol. Proc. Crypto S3, Proc. Workshop Theory and Appl. Cryptogr. Techn. Santa Barbara, California, Aug. 21?24, 1983, New York-London, 1984, pp. 369?375.
[159] G. S. Vernam, ?Cipher printing telegraph system for secret wire and radio telegraphic communications,?AIEE,45, 109?115 (1926). · doi:10.1109/JAIEE.1926.6534724
[160] S. S. Wagstaff and J. W. Smith, ?Methods of factoring large integers,?Led. Notes Math., 1240, 281?303 (1987). · Zbl 0613.10004 · doi:10.1007/BFb0072986
[161] M.-I. Wiener, ?Cryptoanalysis of short RSA secret exponents,?IEEE Trans. Inform. Theory,36. No. 3, 553?558 (1990). · Zbl 0703.94004 · doi:10.1109/18.54902
[162] H. C. Williams, ?A modification of the RSA public-key encryption procedure,?IEEE Trans. Inform. Theory,26, No. 6, 726?729 (1980). · Zbl 0466.94018 · doi:10.1109/TIT.1980.1056264
[163] S. V. Yablonskii.Introduction to Discrete Mathematics [translated from Russian], Mir, Moscow (1989).
[164] A. C. Yao, ?Some complexity questions related to distributive computing,? In:Proc. 11th Annu. ACM Symp. on Theory of Computing, 1979, pp. 209?213.
[165] A. Yao, ?Protocols for secure computations,? In:Proc. 23rd Annu. IEEE Symp. on Found, of Com-put. Sci., 1982, pp. 160?164.
[166] A. Yao, ?Theory and applications of trapdoor functions.? In:Proc. 23rd Annu. IEEE Symp. on Found,of Comput. Sci., 1982, pp. 80?91.
[167] A. Yao, ?How to generate and exchange secrets,? In:Proc. 27th Annu. IEEE Symp. on Found, of Comput. Sci., 1986, pp. 162?167.
[168] P. Young, ?Some structural properties of polynomial reducibilities and sets in NP.? In:Proc. 15th Annu. ACM Symp. on Theory of Comput., 1983, pp. 392?401.
[169] G. Yuval ?How to swindle Rabin,?Cryptologia,3, 187?189 (1979). · doi:10.1080/0161-117991854025
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.