Hot answers tagged

10

The answer to this question is not straightforward and has a lot to do with the "conference culture" of computer science. Unlike other fields, the main publication venues for CS are conferences and not journals. This isn't to say that journals don't have an important role; rather, you don't follow journals to see what research is being done - you follow ...


9

This is based on an averaging argument (which is also used in the proof of the Goldreich-Levin hardcore bit). First, I assume that when writing $Pr[A(x,y)=1] \geq \epsilon$, then the probability is taken over a random choice of both $x$ and $y$. Now, the claim is that there exists a subset of $x$ values of a ``large enough size'' so that for every $x$ in ...


7

I purposefully did not look at the details of the change you are proposing because whatever the change is, the answer is a resounding YES. If you make any change to a cryptographic construction, then you must prove the security of the modified scheme. If you are lucky, you may be able to reduce the security of the modified scheme to the original scheme, or ...


5

If $H(X)$ and $H(Y)$ were not evaluated as a part of selecting $X$ and $Y$, then yes; the assumption of a random Oracle is that $H(Z)$ is an independent and uniformly distributed variable for every new (not previously submitted to the Oracle) value $Z$. If this isn't the case, then this need not hold. One obvious counterexample is: $X := 1; Y := 2 \textit{...


4

(I assume you are asking about this paper based on your previous questions.) They do not prove BDDH in their security proofs. Assume that an attacker $A$ breaks IND-sMID-CPA of the above scheme with probability greater than $\epsilon$ within time $t$ [...]. We show that using $A$, one can construct an attacker $B$ for solving the BDDH problem. In ...


2

The permutation used for Even-Mansour needs to approximate a random permutation. This is the model in which all of the $r$-round Even-Mansour proofs are done. If you have a permutation that is distinguishable from random in a small number of queries, those proofs become null and void—though in some cases the cipher may still be secure. Now, it is perfectly ...


1

No, it's no easier than the standard DBDH problem. Here's the reduction that shows that: suppose that we have an Oracle that solves your problem (given $g^s, g^y, g^r, g^t, g^{st-rs}, g^{(yr+d)/t}, e(g,g)^x$ is $e(g,g)^x = e(g,g)^{syr}$?) Now, suppose we're given $g^s, g^y, g^r, e(g,g)^x$, and are asked whether $e(g,g)^x = e(g,g)^{syr}$. What we do is ...


1

Second question: $\Delta$ is defined on distributions so the distributions of $f(X)$ and $f(Y)$ are the same, since $X,Y$ are both uniform. The supremum definition makes this clearer. First question: Unless the map is one to one, hence a bijective, when equality holds, the probability that $f(X)=f(Y)$ can only increase compared to the probability that $...


1

Why do most of papers in the well-known conferences provide only the proof sketch? Space constraints, mostly (the paper has to fit in a certain number of pages). Often, the full proofs are given in the preprint version, available from the author's home page or the ePrint archive.


1

Let $K$ be the set of all possible keys (for AES-256, this set has $2^{256}$ elements.) Let $M$ be the set of all possible messages (for AES, it has $2^{128}$ elements). Let $C$ be the set of all possible cipher texts (for AES, again $2^{128}$ elements). I was reading a proof to the statement: Perfect privacy implies that $|K|=|M|$ ...



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