# Questions tagged [hardness-assumptions]

Mathematical problems that are thought to be difficult to solve for all cases in polynomial time

87 questions
Filter by
Sorted by
Tagged with
249 views

### Difficulty of generating a string “The (md5|sha1) hash of this string is (x)” that hashes to (x) vs. regular hash collision between files?

I know that collisions in md5 and sha1 have been demonstrated in particular pairs of files (by incrementing some none viewable portion of a PDF, etc). Would generating the above string be ...
91 views

### Naor Pinkas OT - senders security; reduction to DDH

This question concerns the security of the sender in the Naor Pinkas OT. The protocol can be found here. We can reduce the security to the DDH assumption. How exactly is this done? Can someone ...
208 views

### How hard is Self-DLOG?

This question while asking for something different brings up an intriguing problem: If you can find $x$ such that $x\equiv R^x\pmod p$ then you can break DSA. Now I thought that one might be able to ...
174 views

### Universal forgery based on mathematical problem

It is known that DSA admits universal forgery under assumption that the Attacker can solve the equation $x\equiv R^x\pmod p.$ Are there any other protocols admitting universal forgery based on non-...
140 views

626 views

### q-Strong Bilinear Diffie-Hellman

I'm having trouble finding the first paper that introduced the $q$-Strong Bilinear Diffie-Hellman ($q$-SBDH) assumption which, roughly speaking, is: Let $\mathbb{G},\mathbb{G}_T$ be two groups of ...
926 views

### Is factorization modulo a product of primes an NP-hard problem?

For example, let, $p$ and $q$ be two large prime numbers. We set $n = p \cdot q$. Now, let $a \cdot b = c \pmod n$. Given $c$ and $n$, is finding the factors $a$ and $b$ computationally difficult? I ...
128 views

### Extracting $x$ given $g^x, g^{x + y}, y$

Given a cyclic group $G$ of prime order $q$ with generator $g$ in which computing the discrete logarithm is hard. Is it (still) hard to find the discrete logarithm $dlog_g(g^x) = x$ if the ...
207 views

1k views