Tag Info

Yes. Such proofs are possible for El Gamal. It involves a zero knowledge proof of equality of a discrete log, together with the homomorphic property of El Gamal encryption. Recall that given $E(a)$ and $E(b)$, anyone can form $E(a/b)$ using the homomorphic property of El Gamal. Suppose $E(a/b)=(r,s)=(g^k,h^k a/b)$ (where $g$ is the generator and $h$ is ...

In your formula, $n$ appears to relate to the key space, not the message space. The message space does not intervene in the definition of IND-CPA, and that's a good thing because practical message spaces consist in messages which "make sense" in a given context. There are situations where the attacker already guesses quite a lot of the attacked message, and ...

Well, whether it is a secure tweakable block cipher depends on how resistant (E,D) are to related key attacks; that's not a standard assumption for block ciphers. For example, this would not be a secure tweakable block cipher with 3DES; because every 8th bit is ignored, the attacker can effectively test the value of the 7 adjacent bits (except for the 7 ...

Repeatedly encrypting the same message to the same ciphertext is full of practical attacks. Encryption is supposed to leak no information about the content of the message other than its length, and there are very real ways to exploit the information leakage you mention. Some of them have to do with the fact that plaintext domains are not always very large. ...

Encryption using a block cypher such as AES by passing plaintext blocks directly to the encryption function is known as Electronic Code Book mode (ECB) and is not CPA secure as (as you say in your question) it is entirely deterministic and two identical plaintext blocks will result in two identical ciphertext blocks. To prevent this an initialisation ...

Cryptography is not just about confidentiality of the message, but also confidentiality of information about the message. Given the ciphertext, an attacker should not be able to determine any information about a message without knowing the key. If you can tell that message A is equal to message B, that's a leak of information. This could be useful when ...

The Caesar cipher (aka Shift cipher) has, as you said, a key space of size 26. To achieve perfect secrecy, it thus can have at most 26 plaintexts and ciphertexts. With a message space of one character (and every key only used once), it would fit the definition of perfect secrecy. For the usual use with messages longer than one character, or multiple ...

Not a complete answer, but since you mentioned "unmodified RSA" I feel it's relevant. Something stronger than vanilla RSA is necessary, even if it isn't semantic security. Example: What if you have a public key exponent of 3 and the symmetric key being encrypted is 16 bytes long? Using raw RSA, $m^e$ would be about $128 * 3 = 384$ bits long and thus ...

To be secure against a chosen-plaintext attack, an encryption scheme must be non-deterministic — that is, its output must include a random element, so that e.g. encrypting the same plaintext twice will result in two different ciphertexts. Indeed, if that was not the case, an attacker could easily win the IND-CPA game just by using the encryption ...

You are in a twist here: semantic security (equal to IND-CPA) can only be fulfilled by probabilistic encryption schemes. You need a deterministic encryption scheme for your drop-out tolerance. As it was pointed out previously, any homomorphic encryption allows you to proof in zero knowledge the equality of two ciphertexts: known: $c_0 = ...

Well, the obvious way to do this is: Before the protocol occurs, Alice runs the $Gen$ procedure to create a public and a private key For her round, Alice sends her public key to Bob For his round, Bob selects a random symmetric key $\in \{0,1\}^n$, encrypts it with Alice's public key, and sends that encryption to Alice. Alice decrypts the message that Bob ...

To expand / generalize @poncho's reply, given a block cipher $(E,D)$ with keylength $n$, you can make a new one $(E',D')$ with key length $n+1$, which ignores the last bit of the key and just runs $(E,D)$. If $(E,D)$ is a secure PRP, then so is $(E',D')$. But plugging $(E',D')$ into the OP's construction does not yield a secure tweakable block cipher. To see ...