t_wの輪郭

　私も当初よりハッシュ化したメールアドレスをキーにする方法を考えていたのですが、結論から言うと難しいです。おっしゃる通り、ハッシュ化したメールアドレスをキーにすれば一見問題ないように思えたのですが、以下の理由から低い計算コストで実現するのは難しいと判断しました。

• メールアドレスをハッシュ化するSALTは値が毎回変わる
• 「ハッシュ化したメールアドレス」と「メールアドレスをハッシュ化するSALT」のペアは利用者の数だけ存在する
• そのため、「利用者認証時に入力されたメールアドレス」をハッシュ化する適切なSALTを、O(1)で見つける方法が存在しない
  • 以下の手順を用いれば計算コストO(N)で「利用者認証時に入力されたメールアドレス」をハッシュ化する適切なSALTを見つけることができる
    1. DBから全ての「ハッシュ化したメールアドレス」と「メールアドレスをハッシュ化するSALT」を取り出す
    2. 取り出した全ての「メールアドレスをハッシュ化するSALT」で、入力されたメールアドレスをハッシュ化する
    3. 「DBから取り出したSALTでハッシュ化したメールアドレス」と、「DBから取り出したハッシュ化したメールアドレス」を全て突合する
• また、利用者登録時にもメールアドレスの重複を検査する必要があるため、『「利用者認証時に入力されたメールアドレス」をハッシュ化する適切なSALTを、O(1)で見つける方法が存在しない』という問題になる

処理の流れ

メールアドレスとパスワードを入力し、利用者を登録する（メールアドレス・パスワードをハッシュ化してDBに保存する）

1. メールアドレス用のSALTを作成する
   • 作成するたびに値が変わる
   • mailaddress_salt_dbとする
2. メールアドレスをハッシュ化する
   • mailaddress_hashed_dbとする
3. パスワード用のSALTを作成する
   • 作成するたびに値が変わる
   • password_salt_dbとする
4. パスワードをハッシュ化する
   • password_hashed_dbとする
5. 利用者情報（mailaddress_hashed_db(主キー)、mailaddress_salt_db、password_hashed_db、password_hashed_db）をDBに保存する

メールアドレスとパスワードを入力し、利用者を認証する（メールアドレスでDBに保存したハッシュ化したパスワードを取り出し、入力されたパスワードと照合する）

1. メールアドレス用のSALTを取得する
   • mailaddress_saltとする
   • ここで不都合が生じる。SALTは生成する度に値が異なる かつ 利用者情報のレコードが複数存在する 場合、DBに保存した際のメールアドレス用のSALTを計算コストO(1)で取得することができない。
2. メールアドレスをハッシュ化する
3. ハッシュ化したメールアドレスで利用者情報（ハッシュ化したメールアドレス、メールアドレス用のSALT、ハッシュ化したパスワード(password_hashed_dbとする)、パスワード用のSALT）を取得する
4. 入力されたパスワードをDBのパスワード用のSALT でハッシュ化する(password_hashedとする)
5. password_hashed_dbとpassword_hashedが一致していれば認証成功とし、一致していなければ認証失敗とする

メールアドレスのハッシュ化に乱数のSALTを用いると、O(N)の走査が必要でメールアドレスをキーとして扱えないと思ったが、O(N)のNがユーザー数でその頻度がログインやサインアップ程度ならば、O(N)が許容される気がしてきた。