Talk:Security of cryptographic hash functions: Difference between revisions

Revision as of 03:05, 9 July 2016

Latest revision as of 05:47, 9 February 2024

(4 intermediate revisions by 4 users not shown)

Line 1:

{{WikiProject Cryptographybanner shell|class=start}}Start|

{{WikiProject Computer Security|class=startCryptography}}

{{WikiProject Computer Security}}

}}

==Restructuring proposal==

Line 13 ⟶ 15:

[[:Provably secure cryptographic hash function]] → {{no redirect|Security of cryptographic hash functions}} – Possibly move this article to [[Security of cryptographic hash functions]] and then incorporate the content of [[Cryptographic hash function#Properties]] and [[Provably secure cryptographic hash function#Types of Security of Hash Functions]] along with a section about Provably secure cryptographic hash functions. <small>'''Relisted'''. [[User:BrownHairedGirl|<span style="color:#663200;">Brown</span>HairedGirl]] <small>[[User talk:BrownHairedGirl|(talk)]] • ([[Special:Contributions/BrownHairedGirl|contribs]])</small> 18:07, 5 February 2014 (UTC)</small> [[User:RavelTwig|RavelTwig]] ([[User talk:RavelTwig|talk]]) 02:11, 28 January 2014 (UTC)

:''The above discussion is preserved as an archive of the proposal. <span style="color:red">'''Please do not modify it.'''</span> Subsequent comments should be made in a new section on this talk page. No further edits should be made to this section.''</div><!-- Template:pollbottom -->

==Merge Proposal==

Line 38 ⟶ 40:

[[User:IQAndreas|IQAndreas]] ([[User talk:IQAndreas|talk]]) 03:05, 9 July 2016 (UTC)

== PSPACE-complete?! ==

The text says that finding a collision in a particular hash function "is supposed to be hard, at least PSPACE-complete." But, this can't be true unless NP = PSPACE, since finding a collision is trivially in NP. Right?! <!-- Template:Unsigned --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:NoahSD|NoahSD]] ([[User talk:NoahSD#top|talk]] • [[Special:Contributions/NoahSD|contribs]]) 18:17, 9 January 2019 (UTC)</small> <!--Autosigned by SineBot-->

== Parts of the article need to be rewritten ==

As a computer scientist with knowledge of complexity theory but not of cryptographic hashing I am a bit puzzled about what is being said in the article.

As far as I can understand, the article seems to say that commonly used cryptographic hash functions are "hard" only in the sense that nobody seems to have figured out to "break" them (whatever notion of "breaking" is being used.) This seems like a very weak form of "hardness".

Then, there are other cryptographic hash functions, that are "hard" in the complexity theory sense, e.g. NP-hard, so that breaking seems unlikely given that no NP-hard problem has a polynomial time solution algorithm.

However, also this latter hardness is not very strong: very large instances of NP-hard problems are solved, as not all instances of NP-hard problems are at all difficult to solve. There are large classes of instances from any NP-hard problem that can be solved in linear time: they are trivial.

To have a convincing ''proof'' of hardness also in the complexity theory sense, one would need to somehow tie the hardness to some empirically hard class of instances of an NP-hard problem.