Provable Security
(finished)What we want
The aim of this project is to develop new provably secure cryptographic schemes and to improve existing ones. Although many provable secure constructions are known today, there are still some cryptographic applications where no (or rather inefficient) provable secure solutions have been observed yet. Another important task in this area is to analyze the security proofs of established schemes in order to improve the reduction cost, because the latter directly affects the recommended size of the security parameters and therefore the practical performance.
Rationale
As the history of cryptography shows, the very fact that a cryptosystem withstands cryptanalysis for a while should not be taken as an evidence of its security. For example, it took more than ten years of research to completely break the knapsack-based Chor-Rivest cryptosystem. For these reasons, already in the early 1980s some researchers (for example, Goldreich, Goldwasser, Micali, and Rivest) tried to adopt the framework from computational complexity theory for the purpose of rigorously defining the security of cryptographic schemes. In this model, a cryptosystem is called provable secure if there is a polynomial reduction proof from a well-established hard problem (such as the integer factorization problem) to an attack against the security of the cryptosystem. Informally, this means that if there is a polynomially bounded adversary breaking the scheme, then the problem assumed to be hard can also be solved in polynomial time. As this is a contradiction, there exists no such adversary (provided the hardness assumption related to the problem is true).
It remains to clarify the phrase breaking the scheme. To keep this overview simple, we focus on encryption schemes. A long time it was believed that just one-wayness (i.e. the infeasibility of determining a plaintext from its ciphertext) would be an adequate security notion for encryption schemes. However, it turned out that for many applications much stronger requirements have to be met: Namely, it should be infeasible to obtain any relevant information about the plaintext from its ciphertext. This is captured in the notion of semantic security, which nowadays is assumed to be a standard demand on encryption schemes.
Whereas the paradigm of provable security in the beginning has been only of theoretical interest (mainly due to the highly inefficient early solutions), today it is widely believed that for most applications only systems providing provable security should be used. The reasons for this change of mind are the increasing importance of data security in everybody's daily life as well as the development of more and more practical provable secure schemes.
The following person worked on the Provable Security project
Katja Schmidt-Samoa
- Katja Schmidt-Samoa
"A New Rabin-type Trapdoor Permutation Equivalent to Factoring" (abstract)
STM 2005, in conjunction with ESORICS 2005
Electronic Notes in Theoretical Computer Science, to appear
- Katja Schmidt-Samoa, Tsuyoshi Takagi
"Paillier's Cryptosystem Modulo p2q and Its Applications to Trapdoor Commitment Schemes" (abstract)
Mycrypt 2005, LNCS 3715, to appear
- Katja Schmidt-Samoa, "Factorization-based Fail-Stop Signatures
Revisited", ICICS 2004, LNCS 3269, pp. 118-131, 2004, Springer-Verlag
Kaoru Kurosawa, Katja Schmidt-Samoa, Tsuyoshi Takagi, "A Complete and
Explicit Security Reduction Algorithm for RSA-based Cryptosystems",
ASIACRYPT 2003, LNCS 2894, pp. 474-491, 2003, Springer-Verlag
