# Tag Info

8

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

First, on the difference between perfect security and semantic security. Both definitions concern confidentiality, so let us first define what confidentiality means. Note first that an adversary as some a priori knowledge of the message. We can capture that by e.g. having the adversary choose two messages and then flipping a fair coin to decide which one to ...

2

The initial notion of semantic security from Goldwasser and Micali has been shown to be euqivalent to what we call today indistinguishability under chosen plaintext attacks (IND-CPA). Yes that's only security against a passive adversary and actually the weakest reasonable security notion that we use today. The authors of the second paper you link seem to ...

1

For perfect secrecy: $$number\_ of\_keys >= number\_of\_cipher >= number\_of\_plaintext$$ According to Shannon's perfect secrecy theorem: let, $$number\_ of\_keys = number\_of\_cipher = number\_of\_plaintext$$ then we have perfect secrecy if and only if: each key is used with same probability, and for each (plain,cipher) pair there is unique ...

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

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