Skip to main content
Computer Science

Return to Question

Bumped by Community user
added 80 characters in body
Source Link
Sidharth Ghoshal
Sidharth Ghoshal
  • 375
  • 1
  • 2
  • 10

There has been a lot of work on building cryptosystems whose general security guarantees are attached to famous complexity classes.

This post Gives a list of some famous cryptosystems whose underlying problem is NP-Hard problem.

While I don't expect this to have much practical merit it really does beg what I think is an interesting theoretical question. Can we construct cryptosystems whose underlying problem is undecidable, such as the halting problem or automated theorem proving or the group word problem?

The way such a scheme might behave is that you declare some arbitrary conjecture/instance of other general undecidable problem as a public key, and people can use this conjecture to encrypt their messages, and only the person having the proof of the conjecture could decrypt, vice versa.

Someone Else thought of this too: http://www.cs.utsa.edu/~wagner/PKC/pkc.pdf

Some rebuttals on the practicality of such systems: https://crypto.stackexchange.com/questions/81114/updated-utilizing-a-non-computable-function-to-create-a-one-way-function/81115#81115

There has been a lot of work on building cryptosystems whose general security guarantees are attached to famous complexity classes.

This post Gives a list of some famous cryptosystems whose underlying problem is NP-Hard problem.

While I don't expect this to have much practical merit it really does beg what I think is an interesting theoretical question. Can we construct cryptosystems whose underlying problem is undecidable, such as the halting problem or automated theorem proving or the group word problem?

The way such a scheme might behave is that you declare some arbitrary conjecture/instance of other general undecidable problem as a public key, and people can use this conjecture to encrypt their messages, and only the person having the proof of the conjecture could decrypt, vice versa.

There has been a lot of work on building cryptosystems whose general security guarantees are attached to famous complexity classes.

This post Gives a list of some famous cryptosystems whose underlying problem is NP-Hard problem.

While I don't expect this to have much practical merit it really does beg what I think is an interesting theoretical question. Can we construct cryptosystems whose underlying problem is undecidable, such as the halting problem or automated theorem proving or the group word problem?

The way such a scheme might behave is that you declare some arbitrary conjecture/instance of other general undecidable problem as a public key, and people can use this conjecture to encrypt their messages, and only the person having the proof of the conjecture could decrypt, vice versa.

Someone Else thought of this too: http://www.cs.utsa.edu/~wagner/PKC/pkc.pdf

Some rebuttals on the practicality of such systems: https://crypto.stackexchange.com/questions/81114/updated-utilizing-a-non-computable-function-to-create-a-one-way-function/81115#81115

Source Link
Sidharth Ghoshal
Sidharth Ghoshal
  • 375
  • 1
  • 2
  • 10

Cryptosystems whose hardness depends on solving the halting problem?

There has been a lot of work on building cryptosystems whose general security guarantees are attached to famous complexity classes.

This post Gives a list of some famous cryptosystems whose underlying problem is NP-Hard problem.

While I don't expect this to have much practical merit it really does beg what I think is an interesting theoretical question. Can we construct cryptosystems whose underlying problem is undecidable, such as the halting problem or automated theorem proving or the group word problem?

The way such a scheme might behave is that you declare some arbitrary conjecture/instance of other general undecidable problem as a public key, and people can use this conjecture to encrypt their messages, and only the person having the proof of the conjecture could decrypt, vice versa.