The first ten years of public-key cryptography
Proceedings of the IEEEPublished 1 May 1988
Whitfield Diffie
Citations211
SJR quartileQ1
SJR score6.25
SNIP11.38
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The discussion covers exponential key exchange, the trap-door knapsack public-key cryptosystem, the Rivest-Shamir-Adleman (RSA) system, and the breaking of theknapsack cryptos system.
Abstract
The development of public-key cryptography is described, and its principles are elucidated. The discussion covers exponential key exchange, the trap-door knapsack public-key cryptosystem, the Rivest-Shamir-Adleman (RSA) system, and the breaking of the knapsack cryptosystem. Early responses to public-key systems and the problem of key management are examined. Applications and implementations are described. Significant development in multiplying, factoring, and finding prime numbers which have resulted from public-key research are sketched. Directions in public-key research are discussed.>
Keywords
Computer Science
IEEE Transactions on Information TheoryNew directions in cryptography
14,441 Citations1976Whitfield Diffie, Martin E. Hellman
Communications of the ACMHow to share a secret
13,453 Citations1979Adi Shamir
This technique enables the construction of robust key management schemes for cryptographic systems that can function securely and reliably even when misfortunes destroy half the pieces and security breaches expose all but one of the remaining pieces.
Communications of the ACMA method for obtaining digital signatures and public-key cryptosystems
13,142 Citations1983Ronald L. Rivest, Adi Shamir +1 more
Communications of the ACMA method for obtaining digital signatures and public-key cryptosystems
13,083 Citations1978Ronald L. Rivest, Adi Shamir +1 more
An encryption method is presented with the novel property that publicly revealing an encryption key does not thereby reveal the corresponding decryption key, soriers or other secure means are not needed to transmit keys.
The Design and Analysis of Computer Algorithms
9,456 Citations1974Alfred V. Aho, John E. Hopcroft
This text introduces the basic data structures and programming techniques often used in efficient algorithms, and covers use of lists, push-down stacks, queues, trees, and graphs.
Communications of the ACMUntraceable electronic mail, return addresses, and digital pseudonyms
4,260 Citations1981David Chaum
A technique based on public key cryptography is presented that allows an electronic mail system to hide who a participant communicates with as well as the content of the communication - in spite of an unsecured underlying telecommunication system.
Lecture notes in computer scienceHow To Prove Yourself: Practical Solutions to Identification and Signature Problems
3,870 Citations2007Amos Fiat, Adi Shamir
Simple identification and signature schemes which enable any user to prove his identity and the authenticity of his messages to any other user without shared or public keys are described.
1979 International Workshop on Managing Requirements Knowledge (MARK)Safeguarding cryptographic keys
3,379 Citations1979G. R. Blakley
Certain cryptographic keys, such as a number which makes it possible to compute the secret decoding exponent in an RSA public key cryptosystem, 1 , 5 or the system master key and certain other keys in a DES cryptos system, 3 are so important that they present a dilemma.
SIAM Journal on ComputingThe Knowledge Complexity of Interactive Proof Systems
3,186 Citations1989Shafi Goldwasser, Silvio Micali +1 more
A computational complexity theory of the “knowledge” contained in a proof is developed and examples of zero-knowledge proof systems are given for the languages of quadratic residuosity and 'quadratic nonresiduosity.
Communications of the ACMUsing encryption for authentication in large networks of computers
2,360 Citations1978Roger M. Needham, Michael Schroeder
Use of encryption to achieve authenticated communication in computer networks is discussed and example protocols are presented for the establishment of authenticated connections, for the management of authenticated mail, and for signature verification and document integrity guarantee.
Communications of the ACMSecurity without identification: transaction systems to make big brother obsolete
1,650 Citations1985David Chaum
The large-scale automated transaction systems of the near future can be designed to protect the privacy and maintain the security of both individuals and organizations.
Journal of CryptologyThe dining cryptographers problem: Unconditional sender and recipient untraceability
1,403 Citations1988David Chaum
The solution presented here is unconditionally or cryptographically secure, depending on whether it is based on one-time-use keys or on public keys, respectively, and can be adapted to address efficiently a wide variety of practical considerations.
IEEE Transactions on Information TheoryAn improved algorithm for computing logarithms overGF(p)and its cryptographic significance (Corresp.)
1,186 Citations1978S.C. Pohlig, Martin E. Hellman
An improved algorithm is derived which requires O =(\log^{2} p) complexity if p - 1 has only small prime factors and such values of p must be avoided in the cryptosystem.
A practical scheme for non-interactive verifiable secret sharing
1,078 Citations1987Paul Feldman
This paper presents an extremely efficient, non-interactive protocol for verifiable secret sharing, which provides asynchronous networks with a constant-round simulation of simultaneous broadcast networks whenever even a bare majority of processors are good.
DSpace@MIT (Massachusetts Institute of Technology)DIGITALIZED SIGNATURES AND PUBLIC-KEY FUNCTIONS AS INTRACTABLE AS FACTORIZATION
1,024 Citations1979M. O. Rabin
It is proved that for any given n, if the authors can invert the function y = E (x1) for even a small percentage of the values y then they can factor n, which seems to be the first proved result of this kind.
Graduate texts in mathematicsA Course in Number Theory and Cryptography
846 Citations1987Neal Koblitz
IEEE Transactions on Information TheoryHiding information and signatures in trapdoor knapsacks
815 Citations1978Ralph C. Merkle, Martin E. Hellman
Specific instances of the knapsack problem that appear very difficult to solve unless one possesses "trapdoor information" used in the design of the problem are demonstrated.
Communications of the ACMSecure communications over insecure channels
744 Citations1978Ralph C. Merkle
This paper shows that it is possible to select a key over open communications channels in such a fashion that communications security can be maintained, and describes a method which forces any enemy to expend an amount of work which increases as the square of the work required of the two communicants to select the key.
Electronics and Communications in Japan (Part III Fundamental Electronic Science)Secret sharing scheme realizing general access structure
678 Citations1989Mitsuru Ito, Akira Saito +1 more
This paper shows that by providing the trustees with several information data concerning the distributed information of the (k, n) threshold method, any access structure can be realized.
IEEE Transactions on Information TheoryA modular approach to key safeguarding
660 Citations1983C.A. Asmuth, Jordana C. Bloom
A method is proposed for a key safeguarding scheme in which the shadows are congruence classes of a number associated with the original key that provides efficient error detection and exposes deliberate tampering.
ComputerSpecial Feature Exhaustive Cryptanalysis of the NBS Data Encryption Standard
557 Citations1977Whitfield Diffie, Martin E. Hellman
Proofs that yield nothing but their validity and a methodology of cryptographic protocol design
544 Citations1986Oded Goldreich, Silvio Micali +1 more
This paper demonstrates the generality and wide applicability of zero-knowledge proofs, a notion introduced by Goldwasser, Micali and Rackoff that efficiently demonstrate membership in the language without conveying any additional knowledge.
Lecture notes in computer scienceAdvances in Cryptology — CRYPTO’ 86
517 Citations1987Andrew Odlyzko, CRYPTO 1986
Lecture notes in computer scienceCryptography with Cellular Automata
376 Citations2007Stephen Wolfram
This abstract discusses a stream cipher based on a simple one-dimensional cellular automaton that can be obtained from binary plaintext P as usual according to Ci = Pi XOR a(i); the plaintext can be recovered by repeating the same operation, but only if the sequence a( i) is known.
Lecture notes in computer scienceDiscrete logarithms in finite fields and their cryptographic significance
366 Citations2007Andrew Odlyzko
This paper surveys and analyzes known algorithms in this area, with special attention devoted to algorithms for the fields GF(2n), finding that in order to be safe from attacks using these algorithms, the value of n for which GF( 2n) is used in a cryptosystem has to be very large and carefully chosen.
IEEE Transactions on Information TheoryFast evaluation of logarithms in fields of characteristic two
299 Citations1984Don Coppersmith
The ideas give a dramatic improvement even for moderate-sized fields such as GF (2^{127}) , and make (barely) possible computations in fields of size around 2^{400} .
AlgorithmicaDiscrete logarithms inGF(p)
273 Citations1986Don Coppersmith, Andrew M. Odlzyko +1 more
Several related algorithms are presented for computing logarithms in fieldsGF(p),p a prime, with novel ingredients are new ways of obtaining linear equations and new methods of solving these linear equations by adaptations of sparse matrix methods from numerical analysis to the case of finite rings.
IEEE Transactions on Information TheoryA polynomial-time algorithm for breaking the basic Merkle - Hellman cryptosystem
270 Citations1984Adi Shamir
It is shown that the basic variant of this Merkle-Hellman cryptosystem, in which the elements of the public key are modular multiples of a superincreasing sequence, is breakable in polynomial time.
IEEE Transactions on Information TheoryA modification of the RSA public-key encryption procedure (Corresp.)
268 Citations1980Hywel C Williams
For this modified version of the RSA scheme, it is shown that, if the encryption procedure can be broken in a certain number of operations, then R can be factored in only a few more operations.
Multiuser cryptographic techniques
267 Citations1976Whitfield Diffie, Martin E. Hellman
It is shown how such a public key cryptosystem would allow the development of an authentication system which generates an unforgeable, message dependent digital signature.
IEEE Transactions on Information TheoryA knapsack-type public key cryptosystem based on arithmetic in finite fields
239 Citations1988Benny Chor, Ronald L. Rivest
A knapsack-type public key cryptosystem is introduced that is the system is based on a novel application of arithmetic in finite fields, and the density can be made high enough to foil so-called low-density attacks against the system.
Almost all primes can be quickly certified
200 Citations1986S. Goldwasser, Joe Kilian
A new probabilistie primality test is presented, different from the tests of Miller, Solovay-Strassen, and Rabin in that its assertions of primality are certain, rather than being correct with high probability or dependent on an unproven assumption.
Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)On Digital Signatures and Public-Key Cryptosystems.
177 Citations1977Ronald L. Rivest, Adi Shamir +1 more
It is shown that the single operation of raising a number to a fixed power modulo a composite modulus is sufficient to implement digital signatures: a way of creating for a (digitized) document a recognizable, unforgeable, document-dependent digitized signature whose authenticity the signer can not later deny.
Journal of CryptologyA key distribution system equivalent to factoring
177 Citations1988Kevin S. McCurley
Using these keys in the ElGamal public-key cryptosystem provides a scheme for which the decryption of a message requires the ability to factor the modulus and break the original Diffie and Hellman scheme.
Mathematics of ComputationA method of factoring and the factorization of 𝐹₇
170 Citations1975Michael A. Morrison, John Brillhart
Lecture notes in computer scienceA Secure and Privacy-Protecting Protocol for Transmitting Personal Information Between Organizations
158 Citations2007David Chaum, Jan‐Hendrik Evertse
It is proved that the privacy of individuals is protected in a way that is optimal against cooperation of all organizations, even if the organizations have infinite computational resources.
Lecture notes in computer scienceAdvances in Cryptology — CRYPTO ’85 Proceedings
157 Citations1986Hugh C. Williams
DSpace@MIT (Massachusetts Institute of Technology)Towards a practical public-key cryptosystem.
143 Citations1978Loren M Kohnfelder
This paper focuses on the construction of a communication system using the RSA method, and the motivation for this method and the challenges faced in implementing this method.
A Fast Modular Multiplication Algorithm with Application to Two Key Cryptography
109 Citations1983Ernest F. Brickell
This paper presents an algorithm which will perform multiplication modulo C in [log2C] + 7 clock pulses and it is shown that this algorithm can be programmed to solve the inequality of the LaSalle inequality.
Non-transitive transfer of confidence: A perfect zero-knowledge interactive protocol for SAT and beyond
106 Citations1986Gilles Brassard, Claude Crépeau
A perfect zero-knowledge interactive proof is a protocol by which Alice can convince Bob of the truth of some theorem in a way that yields no information as to how the proof might proceed (in the sense of Shannon's information theory).
Lecture notes in computer scienceBreaking Iterated Knapsacks
85 Citations2007Ernest F. Brickell
An outline of an attack that is used successfully to break iterated knapsacks is presented, although it is not provided that the attack almost always works.
Lecture notes in computer scienceStrong Primes are Easy to Find
75 Citations2007J. W. Gordon
It is shown that the problem of finding strong, random,Large primes is only 19% harder than finding random, large primes.
The Mathematical IntelligencerRecent developments in primality testing
75 Citations1981Carl Pomerance
All methods that have been proposed thus far are either restricted to very special cases or are so laborious and prolix that even for numbers that do not exceed the limits of tables constructed by estimable men, they try the patience of even the practiced calculator.
SIAM Journal on Algebraic and Discrete MethodsComputing Logarithms in Finite Fields of Characteristic Two
70 Citations1984Ian F. Blake, Ryoh Fuji‐Hara +2 more
The aim of the work is to show that the algorithm is feasible for the field with $2^{127} $ elements on which several proposed public key distribution systems have been based, and it is felt that the discrete logarithm is still a viable technique for sufficiently large fields.
CryptologiaPRELIMINARY COMMENTS ON THE M.I.T. PUBLIC-KEY CRYPTOSYSTEM
61 Citations1977Gustavus J. Simmons, Michael J. Norris
SIAM Journal on ComputingA Pipeline Architecture for Factoring Large Integers with the Quadratic Sieve Algorithm
61 Citations1988Carl Pomerance, Jeffrey W. Smith +1 more
The quadratic sieve factoring algorithm and a pipeline architecture on which it could be efficiently implemented are described and it is predicted much larger numbers could be practically factored.
Lecture notes in computer scienceDemonstrating that a Public Predicate can be Satisfied Without Revealing Any Information About How
60 Citations2007David Chaum
The problem solved here may be defined in the following way: Both parties y and z agree on a Boolean expression called a predicate; y claims to know a secret value satisfymg the predicate; z wants very high certainty that y does have such a value; while y is willing to demonstrate possession of the secret satisfying value, y is unwilling to reveal the secret value to z.
Lecture notes in computer scienceAnalysis of a Public Key Approach Based on Polynomial Substitution
51 Citations2007Harriet Fell, Whitfield Diffie
It is shown that it is impossible to produce a public key cryptosystem if the total degree of the encryption polynomial determines the size of the public key when the devices used to limit the number of coefficeints are nilpotence and J-rings.
RSA/Rabin Bits are 1/2 + 1 / Poly (Log N) Secure
45 Citations1984Werner Alexi, Benny Chor +2 more
It is proved that RSA least significant bit is 1/2 + (1/[logc N]) secure, for any constant c (where N is the RSA modulus).
The cryptographic security of truncated linearly related variables
42 Citations1985Johan Håstad, Adi Shamir
A polynomial time algorithm for computing the values of variables x, 1, k when some of their bits and some linear relationships between them are known, which is essentially optimal in its use of information.
Lecture notes in computer scienceStatus Report on Factoring (At the Sandia National Laboratories)
15 Citations2007James Davis, D. B. Holdridge +1 more
The difficulty of factoring large integers has become a vital parameter in estimating the security achievable in many secure data schemes -- and conversely factoring techniques are potentially a tool for the cryptanalyst if the cryptographer misjudges the difficulty offactoring a composite number on which he bases a system.
1979 International Workshop on Managing Requirements Knowledge (MARK)Public key vs. conventional key encryption
13 Citations1979Charles S. Kline, Gerald J. Popek
An innovative approach to encryption, called public key algorithms, has recently been proposed as a way to address many of the key distribution and other problems which are present in conventional algorithm-based approaches.
Recent Advances in the design and implementation of Large Integer Factorization Algorithms
4 Citations1983M. C. Wunderlich
The latest and possibly fastest of the general factoring methods for large composite numbers is the quadratic sieve of Carl Pomerance, and an implementation is suggested which combines the forces of a fast pipeline computer such as the Cray I, and a high speed highly parallel array processorsuch as the Goodyear MPP.
OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information)Two-chip implementation of the RSA public-key encryption algorithm
4 Citations1982R.F. Rieden, J.B. Snyder +2 more
A system has been developed which employs two identical integrated circuits to perform the encryption algorithm developed by Rivest, Shamir, and Adleman (RSA) on a 336-bit message.