Timeline for Can we make cryptography signature algorithm based on hardness of isomorphism?
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Sep 21, 2020 at 12:02 | history | bounty ended | CommunityBot | ||
| S Sep 21, 2020 at 12:02 | history | notice removed | CommunityBot | ||
| Sep 19, 2020 at 5:43 | comment | added | joro | @orgesleka Interesting, thanks. | |
| Sep 18, 2020 at 16:36 | comment | added | user6671 | You might be interested in this question: mathoverflow.net/questions/242737/inverting-a-function | |
| Sep 18, 2020 at 8:58 | comment | added | joro | crossposted on crypto: crypto.stackexchange.com/questions/84023/… | |
| Sep 15, 2020 at 16:52 | comment | added | joro | @Mark Thanks. I edited with NP-hardness of FORMULA ISOMORPHISM and CIRCUIT ISOMORPHISM. | |
| Sep 15, 2020 at 13:23 | history | edited | joro | CC BY-SA 4.0 |
added formula and circuit
|
| Sep 14, 2020 at 18:22 | comment | added | Mark Schultz-Wu | As for basing cryptography on "circuit isomorphism", I've heard some practitioners express hope on basing cryptography on the "Minimum Circuit Size Problem". This is a problem asking if a certain circuit has a "small representation" (generally in terms of some size bound). The hardness of MCSP is a rather intricate story though (and there have been many developments in the last 5 years), but MCSP can be thought of better as finding a "compact normal form" for circuits than of asking if two circuits are isomorphic. | |
| Sep 14, 2020 at 18:14 | comment | added | Mark Schultz-Wu | Then you should know that there are no known constructions of public-key encryption from an NP-complete problem (despite ones that get "close but barely miss", say LWE-based protocols), so if you suggest building such a thing this would be a major result independently of this specific question. | |
| Sep 14, 2020 at 14:20 | comment | added | joro | One candidate might be Circuit Isomorphism. | |
| Sep 14, 2020 at 13:54 | comment | added | joro | @Mark I am mainly interested as trapdoor, which can also be used in encryption like RSA. | |
| Sep 14, 2020 at 4:26 | comment | added | Mark Schultz-Wu | This question seems to be asking if we can construct a trapdoor one-way function based on the hardness of some isomorphism problem (which is what $f$ appears to be), that we can use in a digital signature scheme. But it is well-known that digital signature schemes can be constructed from the weaker notion of a one-way function (note that if you were interested in public-key encryption, known techniques require trapdoor OWFs). Is your primary interest a trapdoor OWF, or a digital signature scheme? | |
| S Sep 13, 2020 at 10:25 | history | bounty started | joro | ||
| S Sep 13, 2020 at 10:25 | history | notice added | joro | Draw attention | |
| Sep 12, 2020 at 9:57 | comment | added | joro | Crossposted at cstheory: cstheory.stackexchange.com/questions/47551/… | |
| Sep 10, 2020 at 16:25 | history | asked | joro | CC BY-SA 4.0 |