Hot answers tagged

10

For symmetric algorithms (like AES or DES or RC4 -- but not for RSA or ECDSA), a key is a sequence of bits, such that any sequence of bits of the same size is a potential key. So longer keys means more possible keys. Exhaustive search is about trying all possible keys until a match is found. It is an absolute limit to the strength of an algorithm: ...


9

A distinguisher is an arbitrary algorithm. In fact, we do NOT want to formalize anything about the distinguisher (except that its output is a single bit, although we don't even really need to do this). In definitions, we require that no distinguisher should succeed with non-negligible probability. So, this should hold for any algorithm. Of course, we do ...


7

If the DDH is hard in a group $G$ with generator $g$, then it is hard to decide given $(g,g^a,g^b,g^c)$ whether $ab\equiv c\pmod{ord(G)}$. If you take as $G$ the group $Z_p^*$ of order $p-1$ with $p$ being prime, then you will have $(p-1)/2$ elements being quadratic residues ($QR$) and the other half being non-quadratic residues ($QNR$). Now, we know that ...


6

To answer your first question on key length: DES uses a 56 bit key. A brute-force attack will need a maximum complexity of $2^{56}$ to find the correct key. Now by today's standards this is not much. A complexity of $2^{90}$ or more is considered secure enough. By that standard AES with any key size – 128, 192 or 256 – is strong enough to use. As far as ...


5

Quoting from "On beating the hybrid argument" (by Bill Fefferman, Ronen Shaltiel, Christopher Umans and Emanuele Viola; 2012): The hybrid argument allows one to relate the distinguishability of a distribution (from uniform) to the predictability of individual bits given a prefix. The argument incurs a loss of a factor k equal to the bit-length of the ...


4

There are a number of distinguishers that it it would be easy to prove are not present in a hash function. For example, I can easily prove that Skein does not have the distinguisher "the 2nd bit in the output is equal to the first bit of the output with probability 1". The proof would be a simple example of a message whose digest does not have this property ...


4

Why the CFS signature is affected Let us review the structure of the CFS signature, which is strongly related to the Niederreiter PKE scheme. In the Niederreiter PKE scheme, a public key is $H \in \mathbb{F}^{n \times k}$, which is a scrambled parity-check matrix of the Goppa codes. A plaintext is a decodable error; for example, we set $S = \{\vec{e} \in ...


3

Since the keys are fixed from beginning (the sub-protocols input are ciphertexts), isn't it possible to give the secret key to the (non-uniform) distinguisher as an extra advice (the only restrictions for the advice is that its bitlength is polynomial in the security parameter), and thus allowing the distinguisher to decrypt? This is up to your security ...


3

For any $n \in \mathbf{N}$, let $X_n$ be a random variable which always equals $n$, and $Y_n$ be a random variable which equals $n$ or $n+1$ each with probability $1/2$. Then the probability ensembles $X = \{X_n\}_{n\in \mathbf{N}}$ and $Y = \{Y_n\}_{n\in \mathbf{N}}$ are not computationally indisinguishable. A possible distinguisher is an algorithm $D$ ...


3

He's doing a pretty poor job of expressing a very simple idea here, which is that if there exists a distinguisher $D$ for which $Pr\lbrack D(H^{i-1})=1\rbrack$ > $Pr\lbrack D(H^{i})=1\rbrack$ (which means the advantage is negative before taking the absolute value), there also exists a distinguisher $\overline{D}$ for which $Pr\lbrack D(H^{i})=1\rbrack$ > ...


3

If $(X \approx X')$ and $(Y \approx Y')$, then it holds that $(X \times Y) \approx (X' \times Y')$. Indeed, let us consider an adversary which is able to distinguish $(X \times Y)$ from $(X' \times Y')$ with probability $1/2+\varepsilon$; the adversary returns $0$ if he estimates that the sample comes from $(X' \times Y')$, and $1$ else. Indeed, let us ...


3

Your idea for constructing a distinguisher from a predictor is fine, assuming you know that the predictor predicts the last bit. The more general statement is: if you can predict any bit of the output, say the $i$th bit, given the first $i-1$ bits, then you can also build a distinguisher. A similar idea to what you showed also works to prove this ...


2

A longer key length means a greater search space for someone trying to brute force the key. There are $2^{128}$ times more 256-bit keys than 128-bit keys. So, all other things being equal, a brute force search for a 256-bit key could be impractical by a factor of billions in a case where a brute force search for a 128-bit key might be practical. However, ...


1

Short answer The distinguisher is only given the output of the generator on a uniformly chosen seed of appropriate length, along with a truly random string of the same length as the output of the generator. So, no, the distinguisher is not given $a$, $b$ and $m$. However, as you note we can still consider an algorithm in which those values are hardcoded, ...


1

Perhaps a proof by contradiction? Either they are both indistinguishable from uniform or not. If so, they are indistinguishable from each other. Since that contradicts the premise, at least one must be distinguishable from uniform.


1

No, $X = \{X_n\}_{n \in \mathbf{N}}$ means $X = X_1, X_2, \ldots$ where each $X_i$ is a distribution. So one could let each $X_i$ be the uniform distribution on strings of length $i$. That means there is a polynomial $q$ such that for all $n$ and $x$, if $X_n$ assigns non-zero probability to $x$ then the length of $x$ is at most $q(i\hspace{.02 in})$. ...


1

Obviously not; one can easily define probability distributions $P$ and $P'$ such that $P(X,Y)=P'(X,Y)$ and $P(Y,Z)=P'(Y,Z)$, but $P(X,Y,Z) \ne P'(X,Y,Z)$ For one such example, take $P$ be the probability distinguish where $X$, $Y$ and $Z$ are uniformly and independently distributed boolean variables; and $P'$ be the probability distribution that $X$ and $Y$ ...


1

Modern block encryption algorithms are so secure that trying to keep the choice of algorithm secret usually results in more harm than good! An encrypted message is garbage if it cannot be successfully decrypted by the recipient. And if you're going to the trouble of encrypting it, that implies it's a very important message. So it's best to make sure there ...



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