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.
$\begingroup$
$\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$– pg1989Apr 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$– pg1989Apr 2, 2016 at 22:21
-
$\begingroup$ As I understand it, GI is collapsed to P: dharwadker.org/tevet/isomorphism $\endgroup$– Brent KirkpatrickApr 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$– ThomasApr 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$– Yehuda LindellApr 3, 2016 at 6:32
|
Show 1 more comment
3 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
4
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?
-
$\begingroup$ Crossposted to MO: mathoverflow.net/questions/408757/… $\endgroup$– joroNov 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
$\begingroup$
$\endgroup$
1
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.
-
2$\begingroup$ The subset-sum problem can be thought of as a precursor to lattice cryptography. See here for how subset some is treated as an NP-Complete problem: web.stevens.edu/algebraic/Files/SubsetSum/p229-lagarias.pdf $\endgroup$ Apr 25, 2017 at 4:45