StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POAre there public key cryptography algorithms that are provably NP-hard to defeat?
primarykey
Id
311064
data
AcceptedAnswerId
3654889
AnswerCount
11
ClosedDate
2012-12-19T19:12:21.813
CommentCount
0
CommunityOwnedDate
CreationDate
2008-11-22T08:06:20.480
FavoriteCount
8
LastActivityDate
2011-11-19T22:27:49.493
LastEditDate
2008-11-22T09:35:48.160
LastEditorUserId
3892
OwnerUserId
3892
ParentId
0
PostTypeId
1
Score
21
ViewCount
6862
LastEditorDisplayName
Steve Steiner
text
Body
Should practical quantum computing become a reality, I am wondering if there are any public key cryptographic algorithms that are based on NP-complete problems, rather than integer factorization or discrete logarithms. Edit: Please check out the "Quantum computing in computational complexity theory" section of <a href="http://en.wikipedia.org/wiki/Quantum_computer" rel="noreferrer">the wiki article on quantum computers.</a> It points out that the class of problems quantum computers can answer (BQP) is believed to be strictly easier than NP-complete. Edit 2: 'Based on NP-complete' is a bad way of expressing what I'm interested in. What I intended to ask is for a Public Key encryption algorithm with the property that any method for breaking the encryption can also be used to break the underlying NP-complete problem. This means breaking the encryption proves P=NP.
Tags
<cryptography><complexity-theory><quantum-computing>
Title
Are there public key cryptography algorithms that are provably NP-hard to defeat?
singulars
PostAcceptedAnswerId
1. PO
 singulars
 PostTypePostTypeId
 PTAnswer
PostParentId
1. This table or related slice is empty.
PostTypePostTypeId
1. PTQuestion
UserLastEditorUserId
1. USSteve Steiner
UserOwnerUserId
1. USSteve Steiner
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. PL
 singulars
 LinkTypeLinkTypeId
 LTLinked
PostsAcceptedAnswerId
1. This table or related slice is empty.
PostsParentIdCreationDate
1. PO
 singulars
 PostTypePostTypeId
 PTAnswer
2. PO
 singulars
 PostTypePostTypeId
 PTAnswer
3. PO
 singulars
 PostTypePostTypeId
 PTAnswer
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 POAre there public key cryptography algorithms that are provably NP-hard to defeat?
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
2. VO
 singulars
 PostPostId
 POAre there public key cryptography algorithms that are provably NP-hard to defeat?
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
3. VO
 singulars
 PostPostId
 POAre there public key cryptography algorithms that are provably NP-hard to defeat?
 UserUserId
 USMaxim Ananyev
 VoteTypeVoteTypeId
 VTFavorite
CommentsPostId
1. This table or related slice is empty.

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.