New answers tagged

6

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


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


0

I'll assume that the attacker has the value $g$ as well. If so, we can rewrite $M \cdot e(g, g)^{ab} = M \cdot e(g^a, g)^b = M \cdot h^b$ (where the attacker knows the value $h = e(g^a, g)$. Assuming that $a$ is relatively prime to the size of the subgroup generated by $e(g, g)$, and that $M$ is a member of that subgroup,then, yes, it is indistinguishable; ...


-2

Without the value of both A and B, I guess a conclusive decision might not be possible. But, I think I've got a probablistic method that determines (B>=A)==true when the gap B-A is large enough, and determines (B>=A)==false when B<A or A and B are so close that the algorithm cannot give correct answer with enough confidence. The method has 4 ...


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


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


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


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


0

As far as I know the statement is not correct. perfect secrecy implies $|K|\geq |M|$ (as you can see in Theorem 2.10 in Introduction to Modern Cryptography) and does not implies $|M|=|K|$ necessarily. Your mentioned proof works well for $|K|>|M|$ (and yes I believe $p$ refers to probability) . also here is Katz and Lindell proof for this theorem (this ...


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


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.


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



Top 50 recent answers are included