Talk:Computational hardness assumption

Untitled

I am stunned to see that the article states that the RSA problem is more difficult than integer factorisation. This is not yet proven, and as such is merely speculations. 212.242.167.26 (talk) 17:21, 25 February 2008 (UTC)

Good point. But I think the intention was to say that it is stronger assumption that RSA problem is hard than that integer factorization is hard, because it is not yet proven that the RSA problem is as hard as the integer factorization problem. I think that the article should be clarified somehow. I'm not quite sure how, yet. DRLB (talk) 14:53, 26 February 2008 (UTC)

Same goes for the DLP and Diffie-Hellman. AFAIK there is no proof that DHP is easier than DLP, actually there's a link from the Computational Diffie-Hellman assumption page to a paper that suggests they may be equivalent. —Preceding unsigned comment added by 84.110.170.10 (talk) 17:18, 22 June 2008 (UTC)

according to http://en.wikipedia.org/wiki/RSA_problem "the RSA problem is at least as easy as factoring, but it might well be easier" with sufficient explanations. so someone please change "RSA problem (stronger than factorization)" to "RSA problem (weaker than factorization)" - am i right? Hm nerd (talk) 17:56, 20 August 2015 (UTC)

Sorry, you're actually wrong :-( "stronger assumption" is equivalent to "easier problem" (*at least as easy) Aviad.rubinstein (talk) 22:08, 19 February 2018 (UTC)

Strong vs Weak assumptions

Two things. For one, I think the article is wrong when saying: "solving the problem underlying assumption B is polytime reducible to solving the problem underlying assumption A – which means that if B is solvable in poly time, A definitely is, but the reverse doesn't follow" (it should be the other way around: if B is polytime reducible to A, then a polynomial solution for A implies one for B, but the reverse doesn't follow).

I agree, but I'd even be more careful with nomenclature about assumptions and underlying problems. I would rather see that text changed to "solving the problem underlying assumption B is polytime reducible to solving the problem underlying assumption A. A corollary is that if A's problem is solvable in polytime, then B's problem will also be solvable in polytime. The reverse is not necessarily true."

I'm using "corollary" to be careful with the polytime reducible notion. Problem A may only be solvable in super-polynomial time, but Problem B could still be polytime reducible to Problem A.

Would a simple example of polytime reducibility be appropriate? For example, Problem1 is "sort an array" and Problem2 is "get the largest member from an array". Problem2 is polytime reducible to Problem1, because an algorithm solving Problem1 can be used as a subroutine for an algorithm solving Problem2. The array gets sorted, and in polynomial (constant, in fact) time, the algorithm for Problem2 can pick off the first/last member in the array.

99.43.0.31 (talk) 04:08, 3 August 2016 (UTC)

Second, it's not very intuitive how strength of an assumption is related to cryptographic system strength (from the article, "When devising cryptographic protocols, one hopes to be able to prove security using the weakest possible assumptions."). Example, factorization is listed as [a] stronger [assumption] than the RSA problem. So I'd read this as "integer factorization being hard is a stronger assumption than RSA being hard", and together with the previous statement about devising protocols, I'd be supposed to accept it's better to rely on the RSA problem for security, than it is to rely on factorization. But since integer factorization actually seems a harder problem to solve than the RSA problem, this seems absurd. I suspect the intended meaning is that the harder a problem seems to be, the weaker a computational hardness assumption based on it is, but can someone more knowledgeable than me on the terminology clarify this? (And if my previous assumption is correct, then pretty much the entire list of hardness assumptions needs to be corrected; factorization listed as a weaker assumption than RSA etc) 134.102.206.230 (talk) 13:53, 14 April 2016 (UTC)

The article isn't all that clear about how assumption strength is related to crytpo-system security. Note that the RSA problem is easily shown to be polytime reducible to the factorization problem. Consider two assumptions: "the RSA problem is intractable", and "the factorization problem is intractable". The former is a stronger (more presumptuous) assumption than the latter. The RSA protocol, relying on the former assumption for security, is less ideal than a protocol that only needs to assumes the latter.

In the listing of protocols/assumptions, entries like "RSA problem (weaker than factorization)" might be better written as "RSA problem (easier than factorization)", or "RSA problem intractability (stronger assumption than factorization intractability)".

What do people think?

99.43.0.31 (talk) 04:08, 3 August 2016 (UTC)

Intro buries the lead

The introduction "buries the lead". It may not be easy, but the gist of the subject should be given in the first sentence. BMJ-pdx (talk) 22:25, 23 February 2018 (UTC)

I agree. The very first sentence needs to say what a computational hardness assumption is, not beat around the bush the way it does now. —David Eppstein (talk) 02:35, 24 February 2018 (UTC)

Pretty good

This one since this one.

PS: Thanks for the lesson @Jamie Loki

Nishimoto, Gilberto Kiyoshi (talk) 00:32, 23 September 2023 (UTC)