# Tag Info

## Hot answers tagged semantic-security

6

The LWE assumption I think we should start from the LWE assumption. Let $n$ and $q$ be integers and let $\chi$ be a distribution over $\mathbb{Z}_q$. We often take $\chi$ as a Gaussian with small variance. (We take an error $e$ from this distribution $\chi$ and assume that $|e| \ll q$.) The LWE assumption states that any efficient adversary cannot ...

4

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 ...

2

Why is proof-by-reduction needed? In general, reduction proofs are a very common thing in computer science. Specifically in cryptography, the reasoning goes something like this: The general cryptographic community believes that problem $X$ is very difficult to solve. I have designed a new cipher $Y$ and want to convince the community that it would ...

2

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 ...

2

What if it could? What does this definition mean in practice? Consider $M_0=$ attack and $M_1=$ don't attack. If the adversary can distinguish which message you are sending to your troops, they can optimize their strategy to defeat you. Another example. Say you are casting a yes ($1$) no ($0$) vote for a proposed piece of legislation. If the adversary ...

2

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 ...

1

Here is the proof I came up with. Please let me know if you see any problems with it... Statement to prove: If an encryption scheme is secure in the IND\$-CPA sense, then it is secure in the IND-CPA sense as well. i.e. IND\$-CPA $\Rightarrow$ IND-CPA The contrapositive is easier to prove: $\neg$IND-CPA $\Rightarrow$ $\neg$IND\\$-CPA. This statement is a ...

1

That basically means 'an adversary running in a reasonable amount of time can (or cannot) distinguish one message from another once encrypted'. If we didn't care about that, there would be no point in using cryptography altogether. mikeazo gives a few good examples why this is important. Furthermore here's the definition for the security of an encryption ...

1

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 ...

Only top voted, non community-wiki answers of a minimum length are eligible