情報処理学会 第73回全国大会講演要旨

紛失通信は現代暗号における基礎的なプリミティブのひとつである。
紛失通信のプロトコルを構成するためには何らかの計算量的な仮定を置く
必要があることが知られている。しかしながらこれらの仮定は将来的に、
効率的な解法が発見されるなど間違っていることが証明される可能性がある。
このため紛失通信のプロトコルを可能な限り弱い仮定から構成する
ことが重要である。われわれは正規の通信者と不正な通信者の計算リソース
の間に2乗程度のギャップが存在する場合について研究を行った。
通常、これらの間には超多項式のギャップが存在する。
このような弱いセッティングにおいてプロトコルが安全である場合、
このプロトコルはquadratic secureであると呼ばれる。われわれは
現在の構成方法で用いられる仮定よりも弱いものを用いて、
quadratic securityを達成する紛失通信のプロトコルを構成した。