Tag Info

Hot answers tagged

7

A fast 64-bit hash cannot be completely secure, since a $2^{32}$ brute force collision search is completely doable, and even a $2^{64}$ preimage attack could be feasible. As a MAC used for hash table keying, that doesn't really matter (unless you leak the key). Finding just a few collisions isn't a problem and gathering statistics for an attack would ...


6

It is equivalent to the computational Diffie-Hellman problem; if you can one of the two problems, you can solve the other (with a polynomial number of queries to the oracle which solves the other). If you can solve the Diffie-Hellman problem, you can solve your problem: this can be seen by first noting that, with a Diffie-Hellman solver, given $g^b$, you ...


5

This scheme is insecure, as anyone with the public key can generate a forgery of an arbitrary message. To do this, the forger would take the message $M$, the public key $y$, pick an arbitrary $z$, and compute $r = y^{-H(M)} g^{z} \bmod p$ and output $(r,z)$


5

Intuition The intuition behind the proof is that a valid ciphertext is correctly generated and, thus, an adversary should query to the random oracles to generate random strings in the ciphertext. In addition, notice that the hash value on an unqueried string is undetermined (to the adversary) in the random oracle model. Therefore, the chance to construct a ...


5

Update: My previous answer, although technically true, didn't answer your question. The issue is that the strong-DDH is not hard when using pairing groups, so my answer was merely stating that your problem is at least as hard as an easy problem (duh!) After some thought, I realized your problem is at least as hard as the 2-weak Bilinear Diffie-Hellman ...


4

Yes, it is a secure PRF, as long as the attacker can make at most $2^n-1$ queries. The key lemma is purely information-theoretic in nature. From this lemma, you can prove your result using standard methods. Lemma. Let $x=(x_1,\dots,x_q),y=(y_1,\dots,y_q)$ are any sequence of $q$ $n$-bit values, where $q<2^n$ and the $x_i$'s are all distinct. Then ...


4

Theorem. (Barring any errors, which are certainly possible): Let $A$ be any adversary attacking $F$. As long as $A$ makes fewer than $2^n$ queries, there is an adversary $B[A]$ attacking $f$, making at most twice the queries of $A$ and running in (roughly) the same time such that $ \mathsf{Adv}^{\mathsf{prf}}_F(A) = \mathsf{Adv}^{\mathsf{prf}}_{f}(B[A]). $ ...


4

Not if the attacker is given enough time to ask for the values $F(k,x)$ for all $2^n$ values of $x$. We have $\Sigma_x F(k,x) = 0$ which is distinguishable from random.


4

As correctly pointed out by Ricky Demer it is not necessarily true. However, this implication does not hold for very specific cases. In the case of random oracle gates the existence of the RO changes the functionality of the "scheme", since with RO there are RO-Gates and without there aren't. In most cases the existence of the RO does not affect the ...


4

The equation $t'=t+n\cdot t_c$ is an estimation to put an upper limit on $t'$. It might be possible that an attacker $A'$ can use a different, more efficient algorithm. But since the attack will work with using $A$, there exists an attacker $A'$ with at most $t'$. This means it's actually not an equation, but an inequality $t' \leq t + n \cdot t_c$. And then ...


4

From the key creators point of view, notice that:$g_1\bmod p=1$ and $g_2\bmod q=1$. Which means that $(g_1-1)\cdot(g_2-1)\bmod N=0$. Which implies that $g_1-1$ and $g_2-1$ share a common divisor with $p$ and $q$. To obtain $p$ we simply take $\gcd(g_1-1,N)$. To obtain $q$ we simply take $\gcd(g_2-1,N)$, or $N/p$. Because we have been able to factor the ...


3

This may just be a matter of terminology. A claim that an algorithm is "secure" is meaningless without qualifying/quantifying what it is secure against. Conventionally, the security/strength of cryptographic primitives is described and analysed in terms of computational and memory cost (i.e. secure against an attacker capable of performing a certain number ...


3

Such reductions I know are the reductions in hardcore predicates/functions from computational assumptions, say, from the OWP/OWF/RSA/DCR/CDH/DBDH assumptions, the reductions in (provably-secure) PRGs/PRFs from computational assumptions, say, from the OWP/OWF/RSA/DCR/CDH/DBDH assumptions, and the reductions in LPN/LWE. Re: Can you be more specific? ...


3

One method of doing this would be to construct a Feistel network using the n-bit blockcipher as a round function. A drawback of this approach is that because you're using a blockcipher (a pseudo-random permutation) in place of a pseudo-random function, you are almost immediately limited to being secure to only $q \ll 2^{n/2}$ queries as a result of the ...


3

If they don't trust the server they sure shouldn't send any money. The "trusted" third party is used to solve the problem of participants who don't trust each other. So by definition, your problem can only be somewhat mitigated, not solved completely. I'm not sure what you mean by "provably fair". If the server can't prove he cannot cheat, it's not provably ...


3

A viable answer to the question, as posed in the title, is: No If a stream cipher involves a limited number of messages (say 10) of limited length (say 1000 characters each) enciphered with differently keyed streams, then surely there is not sufficient information available for breaking the cipher? As you would expect, this depends completely on the ...


3

In general this is not the case. Consider a PRF F which ignores the first bit of the key. Then you can distinguish F'(k,.)=F(.,k) from a random function (and thus break its security as a PRF) by querying it on inputs x and x', where with x' we denote x with the first bit flipped. Note that the outputs of F'(k,.) will collide on inputs x and x' as ...


3

HMAC-SHA-256 is sufficient for up to 256 bit security. Confer e.g. NIST SP 800-107. This recommendation is based on the premise that collision attacks are infeasible against common uses of HMAC, and that you consequently only have to worry about primary pre-image attacks that attempt to recover the secret key (and use this for forging subsequent messages). ...


3

As @xagawa mentioned in his comment, it depends on what you mean by "controled". In the case of using a programmable random oracle, yes, the reduction (in particular the simulation of the challenger of the real game) decides about what to return as answer to an oracle query. Thereby, the reduction has to guarantee that the "programmed" answers are ...


3

NTRU, as it was originally introduced, is based on what people now call the "NTRU assumption", which really just assumes that it is difficult to break NTRU. Annoyingly circular, but that's how it is. Similar to how breaking RSA is not provably as hard as factoring (technically it is based on the "RSA assumption"), but people still think it is hard, NTRU ...


3

You have to worry not just about a pair of blinding values being equal, but more complex relationships between them. Thus, finding a proof of security for this approach looks non-trivial to me. Let me elaborate. Suppose $R_j$ is the $j$th blinding variable you use. If $R_i = R_j$, that's a problem, but as you say, that can be made very unlikely. ...


2

Firstly, I should clarify: I am just referring to the standard definition of a random oracle. There are other scenario's (better discussed in DrL's answer), but these tend to be explicitly referred to. That is, if you have a standard 'random oracle', this answer should hold. On the other hand, if you have a different type of oracle, this won't hold. A ...


2

AFAIK, no one has proven that AES on a single 128-bit block with a true-random 128-bit key does not provide information theoretic security (such a proof would probably be the end of AES as it would demonstrate a weakness). OTOH, no one has proven that it does. I suppose it is possible that it does, but such a proof is likely to be extremely difficult. Just ...


2

You have just to look at the signing/verification relation. Just write it as $$m\cdot s \equiv r\cdot \alpha + k \bmod (p-1)$$ And the verification relation should be $$g^{s\cdot m}\stackrel{?}{\equiv} y^r\cdot r \bmod p$$ where $y=g^\alpha$ is the public key and you eavesdrop a signature $(r,s)$ for $m$. Obseve that you can take any multiplicative ...


2

Not necessarily. For example, if there is a public-coin collision-resistant hash family then there is a (statistical) zero-knowledge argument system (with negligible soundness error) for NP that uses a constant number of rounds and has a public-coin verifier. However, in the random oracle model, constant-round public-coin computational zero-knowledge ...


2

The problem that arises in the security proof is that the adversary who may win the real game with some probability may however cause the simulation to nearly always abort (by issuing a private key query that requires the simulation to abort) and the probability of an abort may be different for different sets of private key queries. So, the problem is that ...


2

Let $q$ be given by $\:$ for all $n$, $\: q(n) = 1 \;\;$. $\;\;\;\;\;$ For every $P^*\hspace{-0.05 in}$, every $\: x\in L_R \:$, $\frac{p-\kappa(|x|)}{q(|x|)} = \frac{p-\kappa(|x|)}1 = \:p\hspace{-0.04 in}-\hspace{-0.04 in}\kappa(|x|) \: \leq \: p\hspace{-0.04 in}-\hspace{-0.04 in}0 \: = \: p \: \leq \: 1 \;\;$. For every $P^*\hspace{-0.05 in}$, every $\: ...


2

A classic example of this sort of thing would be the Goldreich-Levin hard-core bit for an arbitrary one-way function. The proof of security for the Goldreich-Levin construction involves showing that if Mallory can predict this single-bit value (even with probability slightly better than $1/2$), then it is possible to invert the one-way function. Thus, this ...


2

No. There's no known proof that CONF is equivalent to the discrete log, in general. When $q$ is prime, CONF is equivalent to the Diffie-Hellman problem. And it's a long-standing problem whether the Diffie-Hellman problem is equivalent than the discrete log; see, e.g., Are there groups where the computational Diffie Hellman problem is easy but the discrete ...


2

Mostly. The two problems are actually more closely equivalent in a gap model than in a non-gap model. Square-DH clearly reduces to CDH either way, but CDH reduces to two calls to Square-DH (you have 3, but you can use $(u-v)^2$ to make it 2). This is fine if the Square-DH adversary is always right, but maybe the adversary only solves the Square-DH problem ...



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