A public key encryption scheme based on idempotent semirings
Mariana Durcheva, Martin Rachev · AIP conference proceedings · 2015
The problem of solving two sided linear equations in the idempotent semirings R¯max and R¯min has been proved to be reducible to the problem mean payoff game which is of the NP∩ coNP type. In the present paper, we use the mentioned security results and construct a new public key encryption scheme based on the hardness of the problem of solving two sided linear equations in the idempotent semirings.