非可換群上で定義された行列累乗関数に基づく意思決定問題について

本論文では、行列累乗関数に基づく鍵交換プロトコルの安全性にとって基本的な意思決定問題に対する統計的分析を実施します。私たちは以前に、考慮した意思決定問題がNP完全であることを証明しており、したがって私たちの提案は量子安全である可能性があります。しかし、考慮した問題の複雑性が安全性パラメータに依存するかどうかは探求しませんでした。ここでは、小さな行列の場合、公開鍵行列の成分の分布から特定の情報が得られる可能性があることを示します。一方で、行列のサイズが大きくなるにつれて、公開鍵行列は真のランダム行列と区別できないことも示します。