Friday, October 11, 2019

graph isomorphism as encryption tool



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.

No comments:

Post a Comment