8
$\begingroup$

Are there any cryptography schemes having correctness relying on Graph Isomorphism not being in P? If I should ask this question in the CS Theory area, I will migrate it.

Thanks.

$\endgroup$
6
  • 3
    $\begingroup$ Nope, not that I know of. GI is not a great problem from which to build primitives, because it's been known for several decades that many (most) classes of graphs have a poly-time algorithm for deciding isomorphism. $\endgroup$
    – pg1989
    Apr 2, 2016 at 22:17
  • $\begingroup$ Interestingly, though, graph non-isomorphism is a standard example of an interactive zero-knowledge proof for a language not in NP. If GI collapses to P, I think GNI goes with it, so we'll need a new example in our crypto textbooks. $\endgroup$
    – pg1989
    Apr 2, 2016 at 22:21
  • $\begingroup$ As I understand it, GI is collapsed to P: dharwadker.org/tevet/isomorphism $\endgroup$ Apr 2, 2016 at 23:01
  • 2
    $\begingroup$ @BrentKirkpatrick You may want to read cstheory.stackexchange.com/questions/32237/… before putting faith in random papers on the internet :) $\endgroup$
    – Thomas
    Apr 2, 2016 at 23:13
  • 3
    $\begingroup$ Indeed, the paper at dharwadker.org/tevet/isomorphism is not credible. However, Babai - a highly respected theoretical computer scientist - has shown that Graph Isomorphism is in quasi-polynomial time arxiv.org/abs/1512.03547. This makes it very unsuitable for cryptographic applications (especially since the feeling is that it may very well be in $P$). $\endgroup$ Apr 3, 2016 at 6:32

3 Answers 3

5
$\begingroup$

There is an elegant example of zero knowledge proof for graph isomorphism. The prover sends a randomly relabled graph and the verifier requests mapping to one of the originals. It is a very simple to understand and prove zero knowledge proof. However I don't believe anyone ever used this for authentication or such. Obviously we now know graph isomorphism isn't hard after all making all these not very useful.

$\endgroup$
1
$\begingroup$

We got a cryptographic algorithm and computer implementation based on graph isomorphism.

An isomorphism between two graphs is a bijection between their vertices that pre serves the edges.

For a graph $G$, let $M(G)$ denote the adjacency matrix of $G$.

Two graphs $G,H$ are isomorphic iff there exist permutation matrix $P$ such that $P M(G) P^{-1}=P M(G) P^T=M(H)$.

Observe that $P$ need not be unique.

Consider the following Diffie Hellman key exchange scheme based on graph isomorphism.

Public parameters: graph $G$ of order $n$ with $A=M(G)$ and $n \times n$ permutation matrix $P_0$.

Alice chooses positive integer $X_A$ and set the private key the matrix $privA=P_0^{X_A}$. Alice make public her public key the matrix

$pubA=privA \cdot A \cdot privA^T=P_0^{X_A} A P_0^{-X_A}$.

Bob chooses positive integer $X_B$ and set the private key the matrix $privB=P_0^{X_B}$. Bob make public his public key the matrix $pubB=privB \cdot A \cdot privB^T$.

To compute shared secret, Allice computes $M_1=privA \cdot pubB \cdot privA^T=P_0^{X_A+X_B} A P_0^{-X_A-X_B}$.

To compute shared secret, Bob computes $M_2=privB \cdot pubA \cdot privB^T=P_0^{X_A+X_B} A P_0^{-X_A-X_B}$.

Since powers of permutation matrices commute, Allice and Bob know the shared secret $M_1=M_2$.

The public keys $pubA,pubB$ are adjacency matrices of isomorphic graphs, each of which is isomorphic to the public $G$.

Multiplicative discrete logarithm of permutation matrices is efficient since the group order is $n$-smooth, but we believe to break the algorithm adversary must solve $X A X^T=pubA$ for permutation matrix $X$

Q1 Is this algorithm at least as hard as graph isomorphism?

For permutation matrix $X$, the equation $X A X^T = pubA$ might have many solutions, which are isomorphism of the graph $G$ to itself. For example take $G$ to be the complete graph of order $n$. Then for all $X$, we have $X A X^T=pubA=A$. This case is trivial since the shared secret is $A$.

When experimenting, we got $G=PaleyGraph(5)$ and $P_0$ such that we had $X A X^T=pubA$, but the shared secret was incorrect.

Q2 are there choices of $G$, $P_0$ such the algorithm is harder than graph isomorphism?

$\endgroup$
4
  • $\begingroup$ Crossposted to MO: mathoverflow.net/questions/408757/… $\endgroup$
    – joro
    Nov 17, 2021 at 13:14
  • $\begingroup$ This key exchange is insecure. The graph $M_{2}=(V_{2},E_{2})$ can be recovered since the edge sets $E_{2}\cap\{\{r,s\}\mid r\in R,s\in S\}$ can easily be produced by from the public information whenever $R,S$ are cycles in the permutation $P_{0}$. $\endgroup$ Nov 17, 2021 at 18:53
  • $\begingroup$ On MO, I also posted an attack where a more general key exchange is broken using linear algebra. $\endgroup$ Nov 23, 2021 at 17:18
  • $\begingroup$ mathoverflow.net/a/409594/22277 On MO, I have posted another attack that translates the problem of finding $X_{A}$ into a problem of solving a system of linear congruence equations. $\endgroup$ Nov 29, 2021 at 1:43
0
$\begingroup$

As far as I know there is no cryptographic scheme based on Graph isomorphism. The following is the key reasons.

The security of a cryptographic scheme largely depend on one-wayness of the underlying function. For a function to be one-way it's not just need to be hard for few NP instances but must be hard for a random instance. In other words it is very easy to find problems that are hard for very instance but easy for majority of instances . Such problems may not come under P but they arn't one way functions either. One such good example is the encryption scheme based on subset-sum problem, which was eventually broken due to the above specified reason.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.