Suppose there is a public key cryptosystem based on the discrete logarithm problem and let this cryptosystem be IND-CCA secure under standard model. Does this statement mean that the given cryptosystem is IND-CCA secure if Diffie-hellman assumption holds (that is the problem on which the given cryptosystem is based) or there may be any other assumptions (problems)?


1 Answer 1


A cryptosystem is not "based on an assumption" ; it is based on some mathematical structure (e.g. prime order elliptic curves, or prime order fields). Informally, a cryptosystem is said IND-CCA secure (which means: it satisfies the indistinguishability security notion, against adversaries which are given access to a decryption oracle) under some assumption A if given access to an adversary that breaks the IND-CCA security of the scheme, one can construct an algorithm breaking A.

But you cannot say that "A is the problem on which the cryptosystem is based": for a given cryptosystem, different security notions can be based on different assumptions. For example, take the case of ElGamal: it is IND-CPA secure under the DDH assumption, and (a slight variant of) it was also proven IND-CCA1 secure (CCA1 indicates that the adversary can make decryption queries only before receiving the challenge ciphertext - this is also known as security against lunchtime attacks), but only under a very different and less standard assumption (see this paper for example, or some of the related papers it mentions in the intro).

So when a cryptosystem is said to be IND-CCA secure, it does not tell anything about the assumption on which it is based.

The term "in the standard model" relates to a completely different things (it does not say anything either on the particular computational assumption to which a security notion for the scheme can be reduced): it is common in crypto, when dealing with a hard problem, to consider simplified "worlds" in which the players could have access to some ideal primitive, and then to instantiate this primitive "in practice" with something which seems a good candidate for this ideal primitive, based on our current understanding of it.

The most common example is that of the random oracle model: we assume that the players are in a world in which they have access to an oracle which acts as a truly random function, and then we prove that some cryptosystem is secure (e.g. IND-CCA secure) under some computational assumption in this simplified world. This does however not prove that in the real world, the cryptosystem would be secure; using SHA-256, for example, as a random oracle seems to work in practice, but SHA-256 is not a random oracle.

Saying that something is secure in the standard model is just a way to say that no such idealized world is considered: the proof is "in the real world" and does not assume any idealized primitive.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.