Talk:Semantic security

Cryptography: Computer science High‑importance

	This article is within the scope of WikiProject Cryptography, a collaborative effort to improve the coverage of Cryptography on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.CryptographyWikipedia:WikiProject CryptographyTemplate:WikiProject CryptographyCryptography articles
High	This article has been rated as High-importance on the importance scale.
	This article is supported by WikiProject Computer science (assessed as High-importance).

Plaintext attack paragraph[edit]

In the chosen plaintext attack paragraph, shouldn't the game be Game theory ? Gene.arboit 02:01, 10 August 2005 (UTC)[reply]

I don't think so. Game theory does not help to understand or analyze the games used to define security notions. 24.228.93.22 15:06, 7 September 2005 (UTC)[reply]

Is semantic security really the widely accepted definition for PKC?[edit]

I think the widely accepted definition of a secure public key cryptosystem is IND-CCA2 (that is security against adaptive chosen ciphertext attacks) mentioned later in this article. Also I find the following comment misleading: Semantically secure encryption algorithms include Goldwasser-Micali, ElGamal and Paillier. These schemes are considered provably secure... Yes, these schemes have been shown to be semantically secure under some assumptions, but before using each of these schemes in practice one should add a padding scheme, so that they are IND-CCA2 secure and not just semantically secure. It's just my opinon of course. What do others think? 24.228.93.22 15:06, 7 September 2005 (UTC)[reply]

- Ok, fair enough. Perhaps we should weaken that statement, and say that "semantic security is a definition" (but there are stronger ones, such as IND-CCA2).
- Re: Elgamal/Paillier/G-M, those schemes are semantically secure, so there's nothing wrong with saying that, as long as we're clear that they're not IND-CCA2 secure.
- It's probably not a good idea to say something like "add a padding scheme before using them", because in truth it might be better to use a variant like Cramer-Shoup or one of the more complex hybrid encryption systems-- both of which would be encryption schemes on their own. And some padding schemes are only secure when used with certain encryption functions, etc.Dachshund 03:54, 12 September 2005 (UTC)[reply]

We need to present an actual definition of Semantic Security here. Right now we have a definition of indistinguishability (IND-CPA), which is equivalent, but we should present the original, messy definition as well.Dachshund 03:54, 12 September 2005 (UTC)[reply]

Semantic Security for Private-Key Encryption[edit]

'Semantic security' (resp. ciphertext indistinguishability) is used in the analysis of private-key encryption as well, not only for PKC. 85.124.63.18 (talk) 22:44, 21 January 2009 (UTC)[reply]

I am going to try and rectify this by adding some information about private-key semantic security, but I don't know much about public-key cryptography so may leave that section as-is. -Zynwyx (talk) 16:26, 1 September 2012 (UTC)[reply]

Definition is Wrong[edit]

Clearly whoever wrote it did not read Goldwasser & Micali 1984. What they've defined is perfect secrecy (sort of), which is totally different. It's pretty shocking how bad cryptography articles are on Wikipedia. Will fix... RobertHannah89 (talk) 04:46, 28 October 2012 (UTC)[reply]

74.98.210.142 (talk) 18:54, 31 July 2016 (UTC) Even worse, some cypher with perfect secrecy do not fit the definition given for semantic security, imagine a one-time pad like encryption scheme with plaintext, cyphertext, and key space being the integers from 0 to (2^n)-1 (all n-bit strings), encryption function cyphertext=(plaintext+key) mod 2^n and decryption function plaintext=(cyphertext-key) mod 2^n. This has perfect secrecy for the same reason as the one time pad, for any given ciphertext, any plaintext can be obtained with an equally plausible key. Yet, this is not semantically secure as (incorrectly) defined in the article. An adversary who receives {pt1,pt2,ct1,ct2} and is asked which plaintext corresponds to which cyphertext simply computes ((ct1-pt1)-(ct2-pt2)) mod 2^n and ((ct1-pt2)-(ct2-pt1)) mod 2^n. The expression that has the plaintexts and cyphertexts matched correctly would yield zero while the wrong one would yield twice the difference of the plaintexts, which is very unlikely to be zero mod 2^n. In this way, the adversary determines which ciphertext belongs to which plaintext with high probability.[reply]

The correct definition of semantic security is that the attacker produces two messages of the same length and sends them to the encryption "oracle", the "oracle" chooses a random key and chooses one of the two messages at random, the "oracle" then encrypts the chosen message with the chosen key and sends the result to the attacker. If there exists an "efficient" attacker that can determine which message was encrypted "significantly" better than random chance, then the cipher is not semantically secure.

I will edit the page after someone reviews the above analysis.

The error in the above analysis is that the same key is used for both encryption. This would directly break perfect secrecy. — Preceding unsigned comment added by 92.73.94.97 (talk) 17:06, 18 April 2018 (UTC)[reply]