カードベース暗号に基づく新しい秘密計算の実現

秘密計算の一種であるゼロ知識証明に関する成果を、著名な国際論文誌Theoretical Computer Science誌で公表できた。この成果は、ペンシルパズルの解に対するゼロ知識証明プロトコルに関するものであり、本研究課題が推進してきた研究分野の1つである。本論文では、世界的に有名なペンシルパズルであるSlitherlinkの「1つの輪っかを作る」という制約に注目し、そのような制約を持つパズルに対する一般的なゼロ知識証明プロトコルの構成を示した。その構成は、予め証明者が準備した解を検証者が検証するという従来通りの方式ではなく、盤面と同じ大きさの輪っかの面積を証明者が輪っかの外側から1マスずつ減らすことによって、輪っかの性質が保証された解を証明者に作って貰うというアイデアに基づいている。この構成に加えて、本論文では同じ制約を持つペンシルパズルであるMasyuに対する具体的なゼロ知識証明プロトコルを構築した。以上の成果は、フランス共和国Clermont Auvergne大のLafourcade准教授及びRobert氏との共同成果である。このように本研究課題の一部を国際共同研究として推進できたのは、ひとえに本科学研究費助成事業のおかげである。本年度は上述したペンシルパズルに加え、3彩色問題と同型問題にも取り組み、それらに対するゼロ知識証明プロトコルを査読付き国際会議ProvSec 2021で代表者が発表した。この研究成果の背景には、Goldreichらによって1991年に示された古典的な成果がある。彼らは成果を分かりやすく示すために、物理的な金庫を用いるゼロ知識証明プロトコルを記述している。本研究では、その既存プロトコルに対して代表者らがこれまで培ってきたゼロ知識証明に関するテクニックを動員し、効率化を行った。その結果、健全性エラーが存在しない効率的なプロトコルを構築できた。

秘密計算の一種であるゼロ知識証明に関する成果を、著名な国際論文誌Theoretical Computer Science誌で公表できた。この成果は、ペンシルパズルの解に対するゼロ知識証明プロトコルに関するものであり、本研究課題が推進してきた研究分野の1つである。本論文では、世界的に有名なペンシルパズルであるSlitherlinkの「1つの輪っかを作る」という制約に注目し、そのような制約を持つパズルに対する一般的なゼロ知識証明プロトコルの構成を示した。その構成は、予め証明者が準備した解を検証者が検証するという従来通りの方式ではなく、盤面と同じ大きさの輪っかの面積を証明者が輪っかの外側から1マスずつ減らすことによって、輪っかの性質が保証された解を証明者に作って貰うというアイデアに基づいている。この構成に加えて、本論文では同じ制約を持つペンシルパズルであるMasyuに対する具体的なゼロ知識証明プロトコルを構築した。以上の成果は、フランス共和国Clermont Auvergne大のLafourcade准教授及びRobert氏との共同成果である。このように本研究課題の一部を国際共同研究として推進できたのは、ひとえに本科学研究費助成事業のおかげである。本年度は上述したペンシルパズルに加え、3彩色問題と同型問題にも取り組み、それらに対するゼロ知識証明プロトコルを査読付き国際会議ProvSec 2021で代表者が発表した。この研究成果の背景には、Goldreichらによって1991年に示された古典的な成果がある。彼らは成果を分かりやすく示すために、物理的な金庫を用いるゼロ知識証明プロトコルを記述している。本研究では、その既存プロトコルに対して代表者らがこれまで培ってきたゼロ知識証明に関するテクニックを動員し、効率化を行った。その結果、健全性エラーが存在しない効率的なプロトコルを構築できた。