New answers tagged hardness-assumptions
0
Here's a simpler game. There is an unknown modulus $m$, for which you know an upper bound $M \ge m$. You must devise a strategy for sampling an integer $x$ such that $y = x \bmod m$ is close to uniform in $\mathbb{Z}_m$.
Does it work to choose $x$ uniformly in $\mathbb{Z}_M$? No, consider the case of $M= 1.5m+1$.
$$\begin{array}{c|cccccccc}
x & 0 & 1 ...
1
There is a big question (that Meir Maor hints at) underlying your problem, namely:
Must the algorithm work for a fixed group, or any group?
Note that there exist groups for which DLOG (and things that reduce to DLOG) are easy, the most basic example is the group $(\mathbb{Z}/n\mathbb{Z}, +)$.
Even among groups that have been used within cryptography, there ...
0
There are very few consequences. In fact it is fairly likely Discrete logarithm is in P, or at least it is not likely to be NP hard. Discrete logarithm is random self reducible which is one of the reasons we like it. A random instance is as hard as the worst case.
Sadly the existence of an NP-Hard random self reducible problem implies the collapse of the ...
2
First, it should be clear that one can always increase the noise in an LWE instance without hurting security, so (for fixed modulus) larger modulus-to-noise ratio implies "not worse" security.
Of course, this does not explain why the security should vary with respect to $\sigma/q$, instead of some more complicated expression.
There are two reasons ...
0
I think that making this link is not common at all.
A good reason is that for example bilinear group with symmetric pairing (Type 1) can be considered as secure for the discrete-log assumption but it will be never the case for the DDH assumption.
If you receive $(g,x,y,z)$, you can easily check if $e(g,z)=e(x,y)$, and this equality is enough to decide if it ...
Top 50 recent answers are included
