Provably secure

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. 

However, in the same article it was proved that any secrecy scheme that is provably secure in this sense is equivalent to one-time pads (see Section 1.5) or even less efficient. Thus, for a while, there was no further research in this field. Besides, for most applications, one-time pads were regarded as too inefficient, because the length of the secret key, which has to be exchanged beforehand, must be at least equal to the overall length of the messages that might be sent later. Hence one continued to use other schemes in practice. 

One reason why not much effort was spent on constructing provably secure digital signature schemes originally is that security in this sense was widely believed to be paradoxical, according to a remark in [WillSO], misled by Rivest see [G0MR88]. (The remark talks about all constructive proofs however, it implicitly makes additional assumptions about the structure of such a proof.)... 

The search for convincing security notions and provably secure signature schemes was parallel with that for other types of cryptologic schemes. 

Damg90 Ivan Bjerre Damgard Payment Systems and Credential Mechanisms with Provable Security Against Abuse by Individuals Crypto 88, LNCS 403, Springer-Verlag, Berlin 1990, 328-335. 

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. 

PfWa92a Birgit Pfitzmann, Michael Waidner How to Break and Repair a Provably Secure Untraceable Payment System Crypto 91, LNCS 576, Springer-Verlag, Berlin 1992, 338-350. 

The first prototype of quantum cryptographic apparatus came into existence around 1990 [147]. In the meantime, quantum cryptography has become a well-known technique of communication in a provably secure way, and together with an intensive research in the held of quantum computers it has given rise to a whole new branch of science quantum information theory [148]. Viewed from this perspective, quantum cryptography today is only a subset of a broad held of quantum communications that also include quantum teleportation, quantum dense coding, quantum error-correcting codes, and quantum data compression. 

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. 

Wagner, D. Cryptanalysis of a provably secure CRT-RSA algorithm. In ACM Conference on Computer and Commrmications Security, pp. 92-97. ACM, Washington, DC (2004)... 

Multiple speciHcations, i.e., different specifications intended for different degrees of security, which would be redundant otherwise. For instance, with fail-stop signature schemes one first requires that no forgeries occur, but secondly, if a forgery occurs nevertheless, it should be provable. This makes sense because the second requirement is to hold on weaker assumptions than the first... 

Proof. The implicit and explicit requirements fi-om Definitions 7.1 and 7.31 are obviously fulfilled, and effectiveness of authentication and the security for the risk bearer are shown as in Lemma 9.12. Furthermore, it is clear that every successful forgery /that is not the correct signature in the same position y in the sequence is provable. It remains to be shown that the reuse of halves of the one-time secret keys does not increase the likelihood with which such a forgery is the correct signature. Thus, with all the quantifiers as in Criterion 3 of Theorem 7.34 in the version of Definition 9.1, it has to be shown that for/= (m , s ) with s = (j, x , y ) ... 

For the first summand. Lemma 11.7 was used. The second summand means that the best guess of an attacker is not provable to be a forgery. As it was shown to be a successful forgery in Part a), the security for the signer can be applied. Definition 7.17f yields for all pairs (pk, histi ) of possible values of PK and Histi i, and with simplifications due to the fact that B is the correct B,... 

---