4
$\begingroup$

In public key cryptography, Alice knows functions $f$ and its inverse $f^{-1}$. $f$ is public and $f^{-1}$ is secret. To sign a message $m$, she gives $(m,a=f^{-1}(m))$. To verify a signature, the verifier checks if $f(a)=f(f^{-1}(m)) ?= m$.

$f$ and $f^{-1}$ are related by some secret $S$ and it is computationally infeasible an adversary to compute $f^{-1}$ or the secret $S$.

Examples of secrets $S$ are integer factorization and discrete logarithms.

One possible approach is to take the secret $S$ to be obfuscation permutation and $f$,$f^{-1}$ to be some "objects" for which isomorphism (and the permutation $S$) is hard to compute, while still have "some properties" for signature.

The question from 2016 Finite objects for which isomorphism is NP-hard or harder? appears to give hard isomorphism.

Q Can we make cryptography signature algorithm based on hardness of isomorphism with security at least NP-hard?

There is related work based Isomorphism of Polynomials, but we believe its security is only Graph Isomorphism (could be wrong on this).

NP-hardness of Hamiltonian Cycle is used in Zero-knowledge proof

Added 2020-09-15

From answer the linked question two candidates for NP-hardness are CIRCUIT ISOMORPHISM and FORMULA ISOMORPHISM.

On p.1: The formula isomorphism problem is in $\Sigma_2^p$ , NP-hard, and unlikely to be $\Sigma_2^p$.-complete

Improve this question
$\endgroup$
10
  • $\begingroup$ Crossposted at cstheory: cstheory.stackexchange.com/questions/47551/… $\endgroup$
    – joro
    Commented Sep 12, 2020 at 9:57
  • $\begingroup$ 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? $\endgroup$
    – Mark Schultz-Wu
    Commented Sep 14, 2020 at 4:26
  • $\begingroup$ @Mark I am mainly interested as trapdoor, which can also be used in encryption like RSA. $\endgroup$
    – joro
    Commented Sep 14, 2020 at 13:54
  • $\begingroup$ One candidate might be Circuit Isomorphism. $\endgroup$
    – joro
    Commented Sep 14, 2020 at 14:20
  • $\begingroup$ 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. $\endgroup$
    – Mark Schultz-Wu
    Commented Sep 14, 2020 at 18:14

0

Reset to default

You must log in to answer this question.