Physicists Develop Quantum Version of Public Key Encryption - Technology Review: Their system is based on the problem of distinguishing between two ensembles of quantum states. This is similar to the problem of determining whether two graphs are identical, ie whether they correspond vertex-for-vertex and edge-for-edge.
A related problem, called the graph automorphism problem, is known to be hard even for a quantum computer and it is this that Kawachi and co base their system..
The thinking is that increasing the complexity of the graph can always make this problem practically impossible for a quantum computer to solve in a reasonable time.
However, if the structure of some subset of the graph is known, the problem can be solved easily. So the trick is to keep this structure secret. This then serves as the private key for decoding messages, while the graph itself is made public for encoding the message.
Post a Comment