Public-key cryptosystem

Size of Public Key File The problem is that the public key file might be large, proportional to w, the number of subsets. In the Complete Subtree method w = 2N — 1 and in the Subtree Difference method it is N log N. An interesting open problem is to come up with a public-key cryptosystem where it is possible to compress the public-keys to a more manageable size. For instance, an identity-based cryptosystem would be helpful for the information-theoretic case where keys are assigned independently. A recent proposal that fits this requirement is [8]. 

Prefix-Truncated Headers We would like to use the Prefix-Truncation, described in Section 4.1, with public-key cryptosystem to reduce the header size without sacrificing security of long-term keys. It can not be employed with an arbitrary public key cryptosystem (e.g. RSA). However, a Diffie-Hellman public key system which can be used for the Prefix-Truncation technique can be devised in the following manner. 

R. Cramer and V. Shoup, A Practical Public Key Cryptosystem Provably Secure Against Adaptive Chosen Ciphertext Attack. Advances in Cryptology - CRYPTO 1999, Lecture Notes in Computer Science 1462, Springer, pp. 13-25. 

The name public-key cryptosystems is also used. With some authors, it designates all asymmetric schemes, with others, asymmetric secrecy schemes only. 

DaPrSO Donald W. Davies, Wyn L. Price The Application of Digital Signatures Based on Public Key Cryptosystems 5th International Conference on Computer Communication (ICCC) 1980, Computer Communications Increasing Benefits for Society Atlanta, Oct. 27-30, 1980, 525-530. 

Davi82 George Davida Chosen Signature Cryptanalysis of the RSA (MIT) Public Key Cryptosystem TR-CS-82-2, University of Wisconsin, Milwaukee, Oct. 1982. (Quoted in [Merr83].)... 

DeMe82 Richard A. DeMillo, Michael Merritt Chosen Signature Cryptanalysis of Public Key Cryptosystems Technical Memorandum, School of Information and Computer Science, Georgia Institute of Technology, Atlanta, Georgia, Oct. 25, 1982. 

Denn84 Dorothy E. Denning Digital Signatures with RSA and Other Public-Key Cryptosystems Communications of the ACM 27/4 (1984) 388-392. 

ElGa85 Taher ElGamal A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms IEEE Transactions on Information Theory 31/4 (1985) 469-472. 

GaHY89 Zvi Galil, Stuart Haber, Moti Yung Symmetric Public-Key Cryptosystems Bellcore TM ARH-013160, 13th July 1989. 

GrSe88 Joachim Grollmann, Alan L. Selman Complexity measures for public-key cryptosystems SIAM Journal on Computing 17/2 (1988) 309-335. 

MerkSO Ralph C. Merkle Protocols for Public Key Cryptosystems 1980 IEEE Symposium on Security and Privacy, IEEE Computer Society lYess, 122-134. 

NaYu90 Moni Naor, Moti Yung Public-key Cryptosystems Provably Secure against Chosen Ciphertext Attacks 22nd Symposium on Theory of Computing (STOC) 1990, ACM, New York 1990, 427-437. 

Okam88 Tatsuaki Okamoto A Digital Multisignature Scheme Using Bijective Public-Key Cryptosystems ACM Transactions on Computer Systems 6/4 (1988) 432-441. 

QuCo82 Jean-Jacques Quisquater, C. Couvreur Fast Decipherment Algorithm for RSA Public-Key Cryptosystem Electronics Letters 18/21 (1982) 905-907. 

RiSA78 Ronald L. Rivest, Adi Shamir, Leonard Adleman A Method for Obtaining Digital Signatures and Public-Key Cryptosystems Communications of the ACM 21/2 (1978) 120-126, reprinted 26/1 (1983) 96-99. 

Several number theoretic concepts (prime numbers, modulo arithmetic, relatively prime, etc.) were introduced in the first three sections of this chapter. Many of them are central to the creation and implementation of check digit schemes. They also can be applied in the area of cryptography to create some fairly sophisticated codes that are extremely difficult to break. The RSA Public-Key Cryptosystem, discussed in this section, is one such code. 

The RSA Public-Key Cryptosystem. All of the ciphers presented so far can easily be broken. A person who has intercepted a message encrypted with one of these ciphers could just try every possible letter or number (00 to 26) permutation to decipher it. This is a very simple task, since a ccmnputer can test all of the possibilities in a matter of minutes. Such easy cracking defeats the purpose of creating the cipher in the first place. One that is not easily broken is needed. 

Both of these problems are addressed in the RSA public-key cryptosystem developed by R. L. Rivest, A. Shamir, and L. Adleman [19], (20). Although it is a fairly simple cipher, it is very hard to break. Moreover. Alice and Bob do not need to meet and agree on a cipher. The code is based on modulo arithmetic, and Alice, the sender of the message, only needs to know how to encipher a message, while Bob, the receiver, is the only person who needs to know how to decipher it. The cipher works as follows. 

Luciano, D., and Prichett, G., Ciyplology From Caesar Ciphers to Public-Key Cryptosystems, College Mathematics Journal, 18(1), 1987, 2-17. 

Pseudorandom number generators, 2472—2473 Psychological disorders, 1170 Psychophysics, 1071-1072 Psychosocial stress, 1170 P3P (Platform for Privacy Preferences), 269 PTS, see Predetermined time standards Public health approach to occupational safety and health, 1157-1159 Public information, 232 Public-key cryptosystems, 733-734 Public network-based applications, 243-244 Public utility industries, work injuries in, 1070 Puerto Rico, 957-958, 959 Pull systems (production) ... 

Public key cryptosystem A two-key cryptosystem in which the encryption key is made public, and the decryption key is kept secret. 

The fundamental mathematical idea behind public key cryptosystems are trapdoor one-way functions. A function is one-way if it is hard to invert it that is, given a value y it is computationally infeasible to find x such that /(x) = y. A one-way function is said to have the trapdoor property if given the trapdoor information, it becomes easy to invert the function. To use a trapdoor one-way function as a public key cryptosystem, the one-way function is used as the encryption algorithm, parametrized by its public key. The trapdoor information is the secret key. Trapdoor one-way functions are conjectured, but not proven, to exist. As such, all known public key cryptosystems are in... 

The earliest proposed public key systems were based on NP-complete problems such as the knapsack problem, but these were quickly found to be insecure. Some variants are still considered secure, but are not efficient enough to be practical. The most widely used public key cryptosystems, the RSA and El Gamal systems, are based on number theoretic and algebraic properties. Some newer systems are based on elliptic curves and lattices. Recently, Ronald Cramer and Victor Shoup developed a public key cryptosystem that is both practical and provably secure against adaptive chosen ciphertext attacks, the strongest kind of attack. The RSA system is described in detail below. 

It is crucial to the security of a public key cryptosystem that messages are somehow randomized before encryption. To see this, suppose that encryption were deterministic and that an attacker knows that an encrypted message sent to Alice is either Yes or No, but wants to team which. Since Alice s public key Ke is public, the attacker can simply compute EncCYes , Ke) and nc( No , Ke) to see which one actually corresponds to the ciphertext. 

Rivest, R. L., Shamir A., and Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Comm. ACM, Febmary 1978, 120-126. 

The security of the public key distribution protocol relies on the theoretically unproven assumption that factoring large numbers is intractable on classical computers. As described in [7], quantum computers can break some of the best public key cryptosystems. 

---