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

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


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

My experience of such proofs is that often you're proving a much stronger statement: in any execution of Game i+1, either everything is distributed identically to Game i or else F must have happened. In other words, the conditional distribution of game i+1 conditioned on F not happening is identical to the distribution of Game i. For example, one of ...


5

As fgrieu notes in the comments, the protocol might not even work reliably in the absence of adversaries: if the tag fails to receive the reader's reply of "True", the keys will get out of sync. (If that happens, the tag will just retry the next exchange with the old key, so this could be fixed by having the reader remember one more "subkey". But the ...


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


4

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


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

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

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

The reason NIST chose one algorithm out of the five AES finalists, even though all of them were pretty well-respected (and some were, at the time, considered likely to be more secure then Rijndael) is because NIST is a standards body, and the whole point of the AES project was to find a standard algorithm. The issue with approving lots of algorithms is that ...


3

However I think that the requirement on $\Pr[F]$ is way too strong: one can prove security with much more frequent faults. Maybe this short paper by Alexander W. Dent could be of interest: A Note On Game-Hopping Proofs? In this paper he introduces a fourth kind of game hop, namely transitions based on large failure events, which seems to be exactly what ...


3

Ok, here's a version that definitely works. Three points: If we know $S_2$ is close to $1/2$, then the statement that $S_1$ and $S_2$ are close is equivalent to saying that $S_1$ is close to $1/2$. So I'll prove the latter version. The way to deal with the edge cases, I think, is to demand Pr$[S_2|F] = 1/2$. This is the case whenever the game (not the ...


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

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

Not always, it depends on the particular encryption scheme. Strictly speaking, the proofs only say that breaking indistinguishability is equivalent to breaking the hardness assumption they are based on. There are some cryptosystems, like Rabin's, where the security of the key is equivalent to the security of the ciphertexts, i.e. factoring <=> key ...


2

I am not aware of any work that proposes a Gap problem related to LWE. The reason is probably that LWE is an average-case problem specifically designed for the use in crypto. However, there are the related worst-case problems, e.g. the shortest vector problem (SVP), that come with a Gap version. So, you might want to have a look at GapSVP and GapCVP.


2

It is called circular security. It is problematic because it is not captured by the usual security definitions. I.e., even if an encryption scheme is proven secure by some regular definition, it is usually not a given to be circular secure. To see why consider, for example, the usual definition of semantic security for a public-key encryption scheme $\Pi = ...


2

For CPA security it is actually enough that the first scheme, i.e., $\pi = (gen, enc, dec)$ is CPA secure. Lets define the CPA game of a general scheme $\pi = (Gen, Enc, Dec)$ against an adversary $A$ as follows: We sample $(pk, sk) \leftarrow Gen(1^\lambda)$, and send $pk$ to $A$. $A$ outputs messages $m_0$ and $m_1$. We sample $b \leftarrow \{0,1\}$ (a ...


2

In the standard definition of security for public key encryption schemes there exists only one public key. Therefore the decryption oracle will always decrypt with the secret key that corresponds to the public key given to the attacker. It does not matter how the $c_1$ in your question is computed, it can be computed using the real public key, a different ...


2

What you present is a generalized version of the so called fixed-argument pairing inversion (FAPI) problem. The FAPI problem is given an element $z\in G_T$ and an element $h\in G$ to compute $f\in G$ such that $e(h,f)=z$. Note, that FAPI is implied by the computational Diffie Hellman problem: Given $(g,g^a,g^b)\in G^3$, call the FAPI oracle with $z\gets ...


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


1

TL;DR, you don't. At this point, we have algorithms we believe are unbroken by current adversaries. For hashing, this includes the SHA-2 family of hashes, SHA-3, BLAKE2b and others. For authentication, we have the HMAC family of functions, the UMAC family of functions, Poly1305, and others. For symmetric encryption, we have AES, ChaCha20, and others. For ...


1

If the MAC is well designed and there is no better attack than guessing, the attacker can choose at least two attacks: a. Find the key for MAC and be able to sign any message. b. Guess (maybe randomly) a MAC of an arbitrary message. (If unsuccessful, maybe retry the attack.) The feasibility of attack a depends on the size of the key, but not on the size ...


1

I am having a hard time understanding your argument why you think this could be simulated. However, here is an explanation of why it could not. Assume Bob is honest and has input $y$, now we have to simulate the view of Alice. As the simulator, as you state, we only get the input and output of Alice. I.e, we only know $x$ and $f(x,y)$. We only need to ...



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