第三者を介在せずに「抽選」を行う方法

Facebookに記事を書いたように、機材の販売先を決める抽選が必要になりそうです。第三者に立ち会ってもらって公正にするということは可能でしょうけど、それでも不正の確率は0になりません。頼まれた方もいい迷惑(笑)。なんかいい方法がないか考えました。こんなのはどうでしょう。

基本的な手法

  1. 当せん決定者は、何か1文字を思い浮かべるが、公表しない
  2. 複数の抽選参加者は、何か1文字を思い浮かべて公表する
  3. Unicode のエンコードで、決定者の文字に一番近い参加者が当せんとする

しかし、いろいろ問題があります。決定者が、参加者の公表よりも後になって、思い浮かべた文字を変えてしまうということをしても検出する方法がありません。つまり、決定者は、誰かが当せんするように、意図的に文字を思い浮かべ、それを事前に思い浮かべたものとしてしてしまうと不正が成立します。

では、決定者が文字を思い浮かべた時点で、第三者に伝達する方法があります。しかし、これは決定者と第三者、あるいは参加者と第三者が、裏で結託していると、やはり不正が成立します。

不正を防止する手段

しかしながら、以下のような、ダイジェスト(あるいはハッシュ)を利用する方法をすれば、第三者の介在なしに、不正ができないと考えますがどうでしょう。

  1. 当せん決定者は何か1文字を思い浮かべる:その文字をcとする
  2. 当せん決定者は、別の適当な文言を思い浮かべる。何文字かは公表しない:文章をsとする
  3. s+cのダイジェストd1を求めて公表する
  4. sのダイジェストd2を求めて公表する

こうして2つのダイジェストを求めますが、当然ながら、決定者はファイル等で、sとcを残しておきます。これらのファイルや文字列が、最終決定までに漏えいしないことが前提です。

2つのダイジェストを公表したのちに、参加者は、期限までに「自分が思い浮かべた1文字」を公表します。他人の表明を見ての変更もありとしてもいいかと思います。

最初cのダイジェストを求めればいいかと思ったのですが、Unicodeで1文字程度なら、全部チェックで比較的短時間でわかってしまうという懸念があります。もちろん、公表から10分以内という手もありますが、セキュリティホールの確率が下がるだけです。そこで、不定長の文字列と組み合わせることを考えつきました。

データの作成例

以下は、具体例です。sha1は、「openssl sha1 (ファイル名)」で得られます。公開/非公開は、参加者の表明が終わるまでの間の扱いです。

s="サンプルテキストです:"(非公開)
c="A"(非公開)
sのsha1→34591a094e22f43fb1ba99426265383993599c96(公開)
s+cのsha1→1c19e4ce3a0d49b6dff756e2bf62bdd605355051(公開)

ここで、公表するのはsha1のダイジェスト値のみです。従って、この2つのバイナリデータから、「A」を推測するのは難しいです。cのダイジェストならば数万回程度の試行で元の文字列が分かるかもしれないけど、上記のd1とd2は「不定数の文字列のダイジェスト」なので、ブルートフォース攻撃の必要アタック数は桁違いに高くなります。決定者がAないしはsを変えてしまって、同一のダイジェスト値を得るのは、ほぼ無理と考えれば、不正が入る余地はありません。もちろん、sha1ではなく、sha512などを本番では使うべきでしょうね。

sもcも決定前には未公開なので、参加者は偶然に当ててしまった場合でも、当たったかどうかは分からないはずです。

なお、抽選者が3人以上の場合、「文字コード上で一定以上の距離を空ける」というルールは必要でしょうね。例えば、ある人が「F」と言ったとします。別の2人が「E」と「G」と宣言して、最初の人の当せん確率を限りなく0にすることが可能です。つまり、別の2人が結託している状況です。まあ、これは監視されている上なので、普通はやらないとは思いますが、厳密にはそのルールが必要かと思います。

抽選者にとって、確率は同一になるかどうか? ここはアイデアが固まっていません。抽選者にとってはcは未知なので、Unicodeのコード空間上、どこにあるかは分からないという点では均一なのかもしれません。しかし、cが空間の端の場合とど真ん中の場合で抽選者に影響はあるのかどうかという点も気になります。cを複数設定して、参加者の1文字は一番近いcを採用するといったようなランダム化は必要なのかもしれません。しかし、この問題は、ちょっと難しそうなので、cは1つということにします。

いかがでしょうか?