(Signal)テクノロジープレビュー：Signalのプライベート連絡先発見機能

Created On2025年10月27日

Last Updated On2025年10月27日

bytoshi

moxie0 2017年9月26日

Signalでは、プライベートな連絡先発見の難しさについて長年考えてきた。現行設計を改善する戦略を模索し、本日新たなプライベート連絡先発見サービスを公開した。

このサービスを利用することで、Signalクライアントは、アドレス帳の連絡先をSignalサービスに開示することなく、効率的かつスケーラブルに、アドレス帳の連絡先がSignalユーザーであるかどうかを判断できるようになる。

背景

Signalはソーシャルソフトウェアである。私たちは、プライバシーが禁欲的なものであるとか、共有とコミュニケーションの文化がプライバシーの終焉を意味するとは考えていない。私たちはその豊かで表現力豊かなオンライン上の社会的交流を可能にすると同時に、意図した受信者だけが通信内容を見られるようにしたいと考えている。

これはテクノロジーと意図を一致させるものだ。誰かが友人と写真を共有する場合、その意図は友人たちと共有することにある。サービス運営者や広告ネットワーク、ハッカー、政府ではない。

ソーシャルソフトウェアにはソーシャルグラフが必要だ

ほぼ全てのソーシャルソフトウェアの基盤となるのはソーシャルグラフである。人々が行う Signal のようなソフトウェアの利用には、友人や同僚に Signal で連絡を取る方法を知っている必要がある。

これにより二つの関連する懸念が生じる：

ソーシャルグラフの構築は容易ではない。ソーシャルネットワークの価値はその規模に比例するため、参加者は未だ大規模になっていない新たなソーシャルネットワークに参加する動機を持たない。ほとんどの人は、コミュニケーションアプリをインストールし、初めて投稿画面を開いたときに、連絡可能な相手が誰もいない空のリストを目の当たりにしたくない。
SignalサービスがSignalユーザーのソーシャルグラフを把握できる状態は望ましくない。Signalは常に可能な限り「ゼロ知識」を目指しており、全ユーザーの友人や連絡先を私たちのサーバーに永続的に記録することは明らかにプライバシー保持に反する。

ほぼ全てのソーシャルソフトウェアは第一の課題に対処する必要がある。大半はFacebook（「Facebookで署名」）のような既存のソーシャルグラフを活用して解決するが、それはソーシャルグラフがFacebookに「所有」されることを意味する。

代わりにSignalは、既に全ての端末に存在するソーシャルグラフ、すなわちアドレス帳の利用から始めた。他者が所有する中央集権的なソーシャルグラフではなく、アドレス帳は分散型でユーザー自身が所有するものである。私たちはさらに、ソーシャルグラフが既にデバイス上に存在するため、Signalサービスはそのコピーを保存する必要がない。ユーザーがSignalをインストールまたは再インストールする際、ソーシャルグラフは常にローカルで利用可能だ。

連絡先の発見

デバイスのアドレス帳をSignalのソーシャルグラフに変換するには、Signalクライアントがデバイスの連絡先の中からSignalユーザーを特定できる必要がある。つまり、クライアントはサービスに「これが私の連絡先全員だ。このうちシグナルユーザーは誰か？」と質問をする必要がある。

私たちとしては、Signalサービスがクライアントのアドレス帳の内容を知ることを望まないため、この質問はプライバシーを保護する形でなされる必要がある。

従来、Signalにおけるこのプロセスは以下のように行われてきた：

クライアントはデバイスのアドレス帳にある各電話番号の切り詰めSHA256ハッシュtruncated SHA256 hash を計算する。
クライアントはそれらの切り詰めハッシュをSignalサービスに送信する。
Signalサービスは登録済みユーザーのハッシュ値セットから検索を行う。
Signalサービスは登録済みユーザーの共通部分（intersection）を返す。

この方法の明らかな問題は、ユーザー識別子のハッシュがほぼ常に復元可能だということだ。識別子が電話番号であれ、名前であれ、メールアドレスであれ、全ての識別子の「鍵空間」が小さすぎる。

こうした欠点から、この連絡先発見方法は理想的ではない。しかし少なくとも Signal サービスの設計は、ユーザーのソーシャルグラフの知識に依存せずに機能する。これは、Signalサービスが公開されているサーバーソースコードを実行していると信頼する場合、サービスがハッキングされたり召喚状を受け取ったりしても、ユーザーのソーシャルグラフに関する永続的な知識を保持しないことを意味する。

信頼するが検証せよ

もちろん、実際に実行されているソースコードがそれではない可能性はどうか？結局のところ、私たちはユーザーの連絡先発見リクエストをログに記録するようサービスを密かに改変できる。たとえ私たちにその動機がなくても、Signalサービスをハッキングした者がコードを改変し、ユーザーの連絡先発見リクエストをログに記録させる可能性がある。あるいは（現行法下では可能性は低いが）政府機関などが現れて、連絡先発見リクエストを記録するようサービス変更を要求するかもしれない。より根本的には、私たちは人々が私たちをただ信頼しなければならないようにはしたくない。プライバシーの本質はそこにはない。

より良い解決策は難しい。ブルームフィルタboom filters、暗号化ブルームフィルタ、分割ブルームフィルタ、プライベート情報検索、プライベート集合検索など、うまくいかない選択肢は数多くある。代わりに、クライアントが私たちのサーバー上で実行されているコードが、自分たちが望んだコードであり、私たちや第三者が改変したものではないことを検証する方法があればどうか？

現代のインテルチップはソフトウェアガード拡張機能（SGX）をサポートしている。SGXはアプリケーションが「セキュアエンクレーブ[機密性のある飛び地]」を設定することを可能にする。これはホストOSやカーネルから隔離された領域で、ARMのTrustZoneのようなテクノロジーに類似している。SGXエンクレーブはremote attestationと呼ばれる機能もサポートする。 remote attestationはネットワーク経由で遠隔エンクレーブ内で実行されているコードの暗号的保証を提供する。

もともとDRMアプリケーション向けに設計されたSGXの事例では、クライアント側で動作するエンクレーブが想定されている。これによりサーバーは、メディアを要求するクライアントソフトウェアが「真正な」ソフトウェアであり、ネットワークAPI呼び出しをリバースエンジニアリングしたカスタムソフトウェア（メディアをトレントとして公開する可能性のあるもの）ではなく、メディアを一度だけ再生することを保証した状態で、クライアントエンクレーブへメディアコンテンツをストリーミングできる。

しかし、従来のSGXの役割を逆転させ、サーバー上でセキュアなエンクレーブを実行することも可能だ。サーバー側のSGXエンクレーブを利用すれば、サービスは暗号化されたクライアントデータに対して計算を実行できる。データの内容や計算結果を知ることは一切ない。

SGXを利用したコンタクトディスカバリー

SGXを用いたプライベートなコンタクトディスカバリーは、高レベルでは非常に単純だ：

セキュアなSGXエンクレーブ内でコンタクトディスカバリーサービスを実行する。
コンタクト発見を実行したいクライアントは、ネットワーク経由でリモートOSからエンクレーブに至るまでの安全な接続をネゴシエートする。
クライアントはリモートアテステーションを実行し、エンクレーブ内で実行されているコードが期待される公開済みオープンソースコードと同一であることを確認する。
クライアントはアドレス帳から暗号化された識別子をエンクレーブへ送信する。
エンクレーブは登録ユーザー全体からクライアントの連絡先を検索し、結果を暗号化してクライアントに返す。

エンクレーブはリモートで実行中のソフトウェアを認証するため、またリモートサーバーとOSがエンクレーブを覗けないため、サービスはクライアントのリクエスト内容を一切把握しない。クライアントがローカルデバイスでクエリを実行しているのとほぼ同等だ。

残念ながら、SGXエンクレーブ内でのプライベートな計算は、一見したよりも難しい。

セキュアなSGXサービスの構築

SGXエンクレーブはハードウェア暗号化RAM上で動作するため、ホストOSはエンクレーブのメモリ内容（クライアントがエンクレーブに送信する連絡先情報など）を閲覧できない。しかし、OSがアクセス先のメモリ内容を直接見られなくとも、ホストOSはメモリアクセスパターンを依然として把握できる。

これは致命的な問題を数多く引き起こす。例えば、以下のように記述されたエンクレーブ関数を考えてみよう：

private List<Long> findRegisteredUsers(Set<Long> registeredUsers,

                                       List<Long> clientContacts)

  List<Long> results = new LinkedList<>();

for (long clientContact : clientContacts) {

    if (registeredUsers.contains(clientContact)) {

      results.add(clientContact);

  return results;

上記のコードは、クライアントが送信した連絡先リストを反復処理し、登録済みユーザー全体のローカルハッシュテーブルを参照して、各連絡先が登録済みユーザーかどうかを判定している。

暗号化RAMを使用している場合でも、サーバーOSはこの関数内のメモリアクセスパターンを観察することで、クライアントが送信した連絡先の平文値を特定できるだけの情報を得ることができるのだ！

OSはおそらく、登録ユーザー全員を含むハッシュテーブルのレイアウトを知っていると考えるべきだ。なぜなら、OSはハッシュテーブルの構築過程を監視できる（エンクレーブは登録ユーザー全員のリストをOSやその他の信頼できないソースから取得する必要がある）し、新規ユーザーがサインアップするたびに（これも信頼できないソースから提供される）それらの値をリアルタイムで変更できる必要があるからだ。仮にOSがハッシュテーブルのレイアウトを知らなくても、通常のエンクレーブインターフェースを通じてエンクレーブに自身のリクエストを送信し、既知の値に対してエンクレーブがハッシュテーブルのどこを読み込むかを観察することで、レイアウトを特定できる。

この知識があれば、OSはクライアントリクエストを処理する際、エンクレーブがどのハッシュテーブルメモリアドレスから読み込むかを監視するだけでよい。

さらに悪いことに！エンクレーブが利用できる暗号化RAMの容量は128MBに制限されており、登録ユーザーの大規模なデータセットを格納するには不十分だ。SGXでは登録ユーザー全体のセットをエンクレーブ外に保存し、エンクレーブ内からそのメモリにアクセスすることは可能だが、その場合OSは登録ユーザーハッシュテーブルのレイアウトを完全に把握していることになる。なぜならそれらは暗号化RAMにすら存在しないからだ。

オブリビアスRAM

上記の例から明らかなように、SGXエンクレーブ内で展開される標準的なソリューションでは、私たちが構築しようとしているものに意味のある保護を提供するには不十分だ。この種の問題はオブリビアスRAM（ORAM）という分野で研究されてきた。ORAMの目的は、CPUとRAMのインターフェースを定義することだ。これによりRAMはCPUのためにメモリを取得する点では通常のRAMのように振る舞うが、CPUのメモリアクセスパターンについては何も学習しない。

パスORAMのような洗練された汎用ORAM技術も存在するが、残念ながらこの問題にはうまく機能しない。大半の手法は、アプリケーションが比較的少数のキーと大規模な値を対応付ける場合に最適だが、私たちの場合には膨大な数のキーとゼロサイズの値を扱う。再帰的パスORAMなど、私たちのデータセット向けに汎用ORAMを提供しようとする複雑な試みは、スケーラビリティに乏しく、同時アクセス環境での構築が困難だ。

私たちが抱える問題に特化した解決策を考えるなら、単純に非効率化を図る方法がある。

private List<Long> findRegisteredUsers(List<Long> registeredUsers,
                                       List<Long> clientContacts)
{
  List<Long> results = new LinkedList<>();

  for (long clientContact : clientContacts) {
    for (long registeredUser : registeredUsers) {
      if (registeredUser == clientContact) {
	results.add(clientContact);
      }
    }
  }

  return results;
}

この関数にはまだ問題があるが、全てを線形化することで当初の懸念は解決した。登録ユーザー全体のハッシュテーブルを参照する代わりに、このコードはクライアントからの問い合わせごとに登録ユーザー全データの完全な線形走査を行う。クライアントごとにメモリ空間全体を一貫性を持って扱うため、OSはアクセスパターンから何も学習できない。しかし登録ユーザーが10億人いる場合、明らかに処理速度が極端に遅くなる。
代わりに元のアプローチを逆転させることで高速化が可能だ。

private List<Long> findRegisteredUsers(List<Long> registeredUsers,
                                       Set<Long> clientContacts)
{
  List<Long> results = new LinkedList<>();

  for (long registeredUser : registeredUsers) {
    if (clientContacts.contains(registeredUser)) {
      results.add(registeredUser);
    }
  }

  return results;
}

これははるかに高速だ。上記のコードは依然として登録ユーザー全体のセットを反復処理するが、送信されたクライアント連絡先全体のコレクションに対しては一度だけ行う。登録ユーザーデータセットに対する大規模な線形スキャンを1回にまとめることで、暗号化されていないRAMへのアクセスは「気づかれない」状態を維持できる。OSはエンクレーブが連絡先発見リクエストごとに各項目を1回ずつ参照するだけと認識するからだ。
完全な線形スキャンはかなり高いレイテンシを伴うが、多くの保留中のクライアント要求をまとめて処理することで、高いスループットを実現できる。
しかし、問題はまだ残っている。OSがclientContactsハッシュテーブルの内容やレイアウトを知っている場合、これはoblivious（無知）とは言えない。
obliviousなハッシュテーブル構築
クライアント連絡先用のハッシュテーブルを構築する「通常の」方法は以下の通りだ。

private Set<Long> constructClientContactsTable(List<Long> clientContacts) {
  Set<Long> results = new HashSet<>();

  for (long clientContact : clientContacts) {
    results.add(clientContact);
  }
}

上記のコードは、暗号化されたリクエストで受け取ったクライアント連絡先のリストを反復処理し、ハッシュテーブルに格納する。
明らかにこれは機能しない。OSに対して、どのハッシュバケットが要素を含むか（書き込みを受けたハッシュテーブルのメモリアドレス）、どのバケットが空か（書き込みを受けなかったメモリアドレス）が露呈してしまうからだ。findRegisteredUsers関数が登録済みユーザー全リストを反復処理する際、OSはエンクレーブがどの登録ユーザーを検査しているか（非暗号化メモリ上にある）を把握できる。そしてclientContactsハッシュテーブルへの読み取りが、constructClientContactsTable処理中に書き込みを確認したメモリアドレスを参照しているかどうかを監視できる。
しかし、clientContactsハッシュテーブルを忘却型で構築できれば、私たち非忘却型アクセスを気にする必要はなくなる。
エンクレーブ外部の監視者がメモリアクセスパターンを監視する主な方法は2つある。ページフォールトとメモリバススヌーピングだ。前者ではOSが全てのメモリアクセスをページフォールト化するため、メモリアドレスが属するページのアドレス（のみ）が明らかになる。これによりOSが観測可能なメモリアクセス粒度は4KBレベルとなる。しかし物理的にFPGAをメモリバスに接続すれば、キャッシュライン単位の粒度でメモリアクセスを監視できる。
ハッシュテーブル構築をオブリビオウスにするため、私たちはこのようないわゆるバケット付きハッシュテーブルを用意する。

 ________   ________         ________
|Bucket 0| |Bucket 1|  ...  |Bucket N|
 --------   --------         --------
|B01||B01| |B01||B01|       |B01||B01|
 ---  ---   ---  ---         ---  ---
|B02||B02| |B02||B02|       |B02||B02|
 ---  ---   ---  ---         ---  ---
|...||...| |...||...|       |...||...|
 ---  ---   ---  ---         ---  ---
|B64||B64| |B64||B64|       |B64||B64|
 ---  ---   ---  ---         ---  ---

ハッシュテーブルの各論理「バケット」（バケット1、バケット2、…、バケットN）は、2つのキャッシュライン（B1、B2、…B64）で構成される。1つはクライアントのクエリを格納し、もう1つは検索結果を格納する。リクエストバッチ内の全クライアント連絡先をハッシュテーブルに格納するため、エンクレーブはハッシュテーブル内の各キャッシュラインを反復処理する。


for (requestCacheLine : requestCacheLines) {
  for (clientContact : clientContacts) {
    if (getHashIndex(clientContact) == requestCacheLine) {
      requestCacheLine[nextAvailable] = clientContact;
    } else {
      requestCacheLine[dummySlot] = clientContact;
    }
  }
}

上記のコードは、クライアント連絡先を順に巡回してハッシュテーブルの適切な位置に追加するのではなく、すべてのキャッシュラインを巡回し、そこに格納すべきクライアント連絡先を後から確認する方式だ。リクエストバッチ全体のクライアント連絡先が合計N個ある場合、この処理中にハッシュテーブルの各キャッシュラインはN回の書き込みを受けることになる。
これはハッシュテーブルを構築する非常に非効率な方法だが、構築後はOSがハッシュテーブルの内容や配置を認識できなくなる。つまり、コンタクト発見検索のクリティカルパスにおいて、通常のハッシュテーブルと同様に使用でき、観察者に重要な情報を漏らさずに済む。

基本レシピ

セキュアエンクレーブ構築には他にも多くの考慮事項がある。分岐はメモリアクセスパターンを通じて観測される可能性があるため、クリティカルセクションに分岐を含めるべきではない。メモリアクセスパターンは、暗号ソフトウェアにおける「定数時間」プログラミングの考慮事項と同様の注意を払い、あらゆる結果において常に同一に見えるようにすべきである。
上記の無知ハッシュテーブル構築手法を用いることで、私たちはSGX環境においてプライベートなコンタクト発見を実行する一般的な手順を確立できる。これにより、マシンを管理する側（物理ハードウェアをメモリバスに接続した場合でも）に一切の情報を漏洩させずに済む：
コンタクト発見サービスは、暗号化されたコンタクト発見リクエストのバッチをエンクレーブに渡す。
エンクレーブはリクエストを復号し、無知ハッシュテーブル構築プロセスを用いて、提出された全コンタクトを含むハッシュテーブルを構築する。
エンクレーブは登録ユーザー全リストを反復処理する。各登録ユーザーに対し、エンクレーブはクライアント連絡先バッチを含むハッシュテーブルをインデックスし、そのキャッシュライン内の全連絡先と定数時間比較を行う。
エンクレーブは比較成功の有無に関わらず、同一ハッシュインデックスの「結果」キャッシュラインに書き込む。
登録ユーザー全体の反復処理後、エンクレーブはバッチ内の各クライアントリクエストに対応する忘却型応答リストを構築する。
エンクレーブは各要求クライアントへの適切な応答リストを暗号化し、バッチ結果をサービスに返す。
サービスは暗号化された応答を各要求クライアントに送信する。
非効率性をバッチ処理のセットアップとティアダウン部分に押し込むことで、クリティカルセクションは十分な高速性を維持し、プロセス全体が10億人以上のユーザーにスケール可能となる。
Obliviousの限界
OSは注意深い観察から些細な情報を依然として学習可能である。クライアント連絡先バッチを含むハッシュテーブルは、各バケットが12件の連絡先を格納する構成となっている。無知なハッシュテーブル構築プロセスでは、OSはバケット内の要素数（存在する場合）や要素内容を認識しない。ただし、ハッシュバケットに12件を超える連絡先が存在し得ないことはOSが把握している。
エンクレーブがバッチ処理中に全登録ユーザーセットを反復処理する際、OSは単一バケットのキャッシュラインへのエンクレーブインデックスが12回以上発生する可能性を検知する。もし同じハッシュインデックスに対応するユーザーが13人いた場合、OSはそれらのユーザーが全員クライアントリクエストに含まれていた可能性はないと認識する。なぜならハッシュバケットに収まりきらないからだ。しかしOSは、それらのユーザーの一部がクライアントリクエストに含まれていたか否かについては知ることができない。これが私たちが必要とする忘却性という特性である。
ソースを見る
これら全てを統合し、数十億ユーザーに対応可能な完全な連絡先発見サービスとして構築した。これによりSignalユーザーは、連絡先をSignalサービスに開示することなくソーシャルグラフを発見できる。私たちが構築してきたもの全てと同様に、連絡先発見サービスはオープンソースである。
エンクレーブコードは再現性のあるビルドが可能だ。したがって公開されたソースコードが、リモートエンクレーブのMRENCLAVE値と一致することを誰でも検証できる。
ぜひ確認し、ご意見をお聞かせください！これはベータ版のテクノロジープレビューだが、今後数ヶ月でテストを完了し、サービスを本番環境にデプロイし、クライアントに統合していく予定だ。
確認
重労働を担いエンクレーブコードを全て記述してくれたジェフ・グリフィン、SGXを紹介してくれたヘンリー・コリガン＝ギブス、ORAMの最新技術を説明してくれたラルカ・アダ・ポパ、システムに関する洞察を与えてくれたノーラン・リークに深く感謝する。

https://signal.org/blog/private-contact-discovery

Howdy! How can we help you?