# Tag Info

9

SHA-1 was SHattered by Stevens et al. They demonstrated that collisions in SHA-1 are practical. They give the first instance of a collision for SHA-1. It is an identical-prefix collision attack that enabled the attacker to forge two distinct PDF documents that have the same SHA-1 hash value. I.e. They extended a given prefix $p$ with two distinct near-...

9

See my paper with Eric Bach, "Factoring with cyclotomic polynomials", where we show that if the cyclotomic polynomial $\Phi_k(p)$ is $B$-smooth for any $p$ dividing $N$, then we can factor $N$ in time polynomial in $\log N$ and $k$ and $B$. In particular this gives a $(p+1)$-method (see the earlier work of Williams) and $(p^2+1)$ method. http://www.ams.org/...

6

Yes, you can use Levin universal search to construct a "universal one-way function" (e.g., these lecture notes). From this one-way function you can then construct symmetric-key encryption primitives (pseudorandom generators, block ciphers, CPA/CCA-secure encryption) using standard theoretical constructions. One-way function $\to$ pseudorandom generator: ...

6

Yes, if the encryption algorithm achieves IND-CPA security (semantic security), this implies that an adversary cannot predict any linear combination of encrypted bits better than random guessing. The easiest way to see this is to note that IND-CPA (left-or-right indistinguishability) implies real-or-random indistinguishability under chosen-plaintext attack:...

5

Update: The description below is for a different problem (in which you have all pairwise distances in a set rather than pairwise distances between two distinct sets). I'll leave it up anyway since it is closely related. This problem is called the beltway problem, and is a special case of the general $d$-torus embedding problem. It is also closely related to ...

4

Here is a suggestion, for $K = 6$ and $N = 251$. We are given a list $a_i - b_j \pmod{N}$. Start by taking one of them, without loss of generality $a_1-b_1$. Without loss of generality $b_1=0$, and we obtain the value of $a_1$. Now take another one, and hope that it is of the form $a_2-b_1$ (this happens with probability $5/35 = 1/7$), and deduce $a_2$. At ...

3

Here's a different approach, based upon iteratively finding numbers that cannot appear among $\{a_1,\dots,a_6\}$. Call a set $A$ an over-approximation of the $a$'s if we know that $\{a_1,\dots,a_6\} \subseteq A$. Similarly, $B$ is an overapproximation of the $b$'s if we know that $\{b_1,\dots,b_6\} \subseteq B$. Obviously, the smaller $A$ is, the more ...

3

Here's an observation that I think gives you a foothold, possibly enough of one to solve the problem. Suppose we have four differences $a_1-b_1$, $a_1-b_2$, $a_2-b_1$, $a_2-b_2$ that arise as the pairwise differences between two $a$'s and two $b$'s. Call this a quartet of differences. Notice that we have a non-trivial relationship: (a_1-b_1)-(a_1-b_2) =...

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