文字列(1,2)-紛失通信からRabin型紛失通信への直接帰着

摘要

文字列(1,2)-紛失通信とRabin型紛失通信が等価であることは良く知られている。しかしながら、Rabin型紛失通信から文字列(1,2)-紛失通信への既知の帰着は二段階となっている。 第一段階はRabin型紛失通信からビット(1,2)-紛失通信の構成であり、第二段階はビット(1,2)-紛失通信からの文字列(1,2)-紛失通信の構成である。 この論文では、決定性乱数抽出器を利用して文字列(1,2)-紛失通信からRabin型紛失通信の直接的な帰着を与える。我々の帰着は従来の二段階帰着よりも効率的となっている。