コロナ対策へ向けプライバシーを保護したデバイス追跡技術CEN Protocol

コロナウイルス感染者が潜伏期間中に接触した可能性のある人を追跡することは感染症蔓延を防ぐために有効な手段である。この追跡は従来、感染者への直接の面談により行われてきたが、スマホなどのデバイスを用いてテクノロジー的に追跡技術を活用することで、より効率的にかつ正確に実現する可能性がある。

しかし、このような接触情報を直接扱うことの代表的な問題がプライバシーであるが、この課題に対しいくつかのプロジェクトが発足し、実際に開発も進められている。

DP-3T(Decentralized Privacy-Preserving Proximity Tracing)と呼ばれるプロジェクトは欧州の８大学を中心としたアカデミアグループにより進められ、[White Paper](https://github.com/DP-3T/documents)がgithub上に公開されている。
また、[CoEpi](https://www.coepi.org/)と[Covid-Watch](https://www.covid-watch.org/)のジョイントプロジェクトとして進められていたCEN Protocolの開発には匿名暗号通貨の開発組織として有名なZcash Foundationも[コラボレーションする形となった。](https://www.zfnd.org/blog/private-contact-tracing-protocols-compared/)

この記事では、サーバーへ送るデータサイズがより小さく、実装もすでに公開しているCEN Protocolの内容を紹介する。

# 概要
DP-3TもCEN Protocolもユーザーが所有しているスマホデバイスを使ったBluetoothのブロードキャストを利用する。Bluetoothを介して短期間のみ利用可能な擬似乱数値をブロードキャストし、近くのスマホデバイスはそれを保存する。
これはあくまでも擬似乱数なのでユーザーのアイデンティティや位置情報などのセンシティブな情報には一切関係しない。

その後、コロナウイルスの感染が発覚したユーザーはサーバーに生成した擬似乱数値を含めたレポートを送信する。一方で、ユーザーは過去に接触したデバイスから受け取った擬似乱数値がサーバーにアップロードしていないかチェックを定常的に行う。

まとめると以下の３つのフェーズが存在することになる。

* ブロードキャストフェーズ
    * ユーザーは擬似乱数値を生成し近くのデバイスへBluetoothを介しブロードキャストする
* レポートフェーズ
    * 感染者がある一定期間において接触した可能性のある全てのユーザーへ通知するために、サーバーへレポートを送信する
* スキャンフェーズ
    * 自身に該当するレポートを受け取っているかユーザーがサーバーへ確認

## 理想的なプロパティ
このBluetoothを介した追跡技術におけるプライバシーとセキュリティを保証するためにプロトコルとして望ましい性質を整理する。

* サーバーに対するプライバシー
    * サーバーはあらゆるユーザーの位置情報などの個人情報を取得できないようにするべき
* ソース情報の完全性
    * ユーザーは接触していないユーザーへレポートは送れないようにするべき
* ブロードキャストにおける完全性
    * ユーザーは自身が生成していない擬似乱数値をブロードキャストできないようにするべき
* No Passive Tracking
    * レポートを送っていないユーザーの位置情報などに関するデータは他のユーザーに知られない
* レポート受信者に対するプライバシー
    * レポートを受け取るユーザーは第三者に個人情報を公開できない
* レポート送信者に対するプライバシー
    * 特定の期間、特定の接触範囲に該当するユーザー以外にはレポート送信者に関する一切の情報を知られない

例えば、これらの性質のうち、「サーバーに対するプライバシー」は上述したナイーブな手法で実現可能だ。異なるランダムな値を送るので、（他のユーザーと結託しない限り）、アイデンティティや位置情報と相関させることはできない。

CEN Protocolでは「ブロードキャストにおける完全性」を除いた全てのプロパティを満たすように設計されている。「ブロードキャストにおける完全性」は、他のユーザーから得た擬似乱数値を再度ブロードキャストするような攻撃は物理レイヤーでの検証が必要になり防ぐのは困難であることが分かる。

さらに、CEN Protocol開発者からはDP-3Tでは「レポート送信者に対するプライバシー」「ソース情報の完全性」のプロパティが不十分であるという点が[指摘されている。](https://www.zfnd.org/blog/private-contact-tracing-protocols-compared/)


## CEN Protocol

公開されている[CEN ProtocolのRust実装](https://github.com/Co-Epi/CEN)も含め、鍵生成周りやレポートデータ周りの扱いを見ていく。

### 鍵導出

レポート送信時にデバイスに保存してある全ての擬似乱数値を送信する必要がないように、そしてレポートに対して署名を加えてソース情報の完全性のプロパティを与えられるように以下ではいくつかの種類の鍵を定義し、それらの導出方法を整理する。

ここで登場する鍵と擬似乱数値は以下があげられる。

* rak(Report Authorization Key)
    * レポートの署名をする秘密鍵と`cek_0`の導出に使われる
* rvk（Report Verification Key）
    * レポートの署名を検証する公開鍵
* cek(Contact Event Key)
    * 複数のcenを決定的に導出するための鍵
* cen(Contact Event Number)
    * Bluetoothでブロードキャストされる擬似乱数値（ランダムオラクルモデル下）

#### レポート鍵生成
ユーザーはレポートへの署名をする鍵ペア`rak（Report Authorization Key）`、`rvk（Report Verification Key）`を生成。（実装上は、ed25519による署名）

CEK(Contact Event Key)は`ReportAuthorizationKey`のハッシュにより生成される。以下の`cek_bytes`がそのハッシュ値に該当する。`index`は後述するratchetで利用するインデックスに使われる。

```rust
pub struct ContactEventKey {
    pub(crate) index: u16,
    pub(crate) rvk: ed25519_zebra::PublicKeyBytes,
    pub(crate) cek_bytes: [u8; 32],
}
```

実際に、`ReportAuthorizationKey`から`ContactEventKey`を生成する方法は以下の通り。

```rust
#[derive(Copy, Clone, Debug)]
pub struct ReportAuthorizationKey {
    // We don't store rvk explicitly because it's cached inside the SecretKey.
    pub(crate) rak: ed25519_zebra::SecretKey,
}

impl ReportAuthorizationKey {
    ...

    /// Compute the initial contact event key derived from this report authorization key.
    pub fn initial_contact_event_key(&self) -> ContactEventKey {
        let rvk = ed25519_zebra::PublicKeyBytes::from(&self.rak);

        let cek_bytes = {
            // There's a bit of an awkward dance to get digests into fixed-size
            // arrays because Rust doesn't have const generics (yet).
            let mut bytes = [0; 32];
            bytes.copy_from_slice(
                &Sha256::default()
                    .chain(H_CEK_DOMAIN_SEP)
                    .chain(&self.rak)
                    .result()[..],
            );
            bytes
        };

        ContactEventKey {
            index: 0,
            rvk,
            cek_bytes,
        }
    }
}
```

#### CEK Ratchet

`ContactEventKey`のindexをインクリメントするためには以下のように`cek_bytes`のハッシュ値を計算することにより進めることができる。この処理をratchetとここでは表現する。ratchetは時間に依存しているのではなく(DP-3Tは1日ごとなどの時間依存）、`CEN`からユーザーを相関するLinkability攻撃を防ぐためにBluetoothレイヤーのMACアドレスローテーションに同期してratchetする。

```rust
pub struct ContactEventKey {
    pub(crate) index: u16,
    pub(crate) rvk: ed25519_zebra::PublicKeyBytes,
    pub(crate) cek_bytes: [u8; 32],
}

impl ContactEventKey {    
    /// Ratchet the key forward, producing a new key for a new contact event
    /// number.    
    pub fn ratchet(self) -> Option<ContactEventKey> {
        let ContactEventKey {
            index,
            rvk,
            cek_bytes,
        } = self;

        if let Some(next_index) = index.checked_add(1) {
            let next_cek_bytes = {
                let mut bytes = [0; 32];
                bytes.copy_from_slice(
                    &Sha256::default()
                        .chain(H_CEK_DOMAIN_SEP)
                        .chain(&cek_bytes)
                        .result()[..],
                );
                bytes
            };
            Some(ContactEventKey {
                rvk,
                index: next_index,
                cek_bytes: next_cek_bytes,
            })
        } else {
            None
        }
    }
}
```

#### CEN生成
実際にBluetoothを介して他デバイスへブロードキャストする擬似乱数CEN(Contact Event Number)は以下のようにCEKからハッシュ計算により導出。

```rust
pub fn contact_event_number(&self) -> ContactEventNumber {
    let mut bytes = [0; 16];
    bytes.copy_from_slice(
        &Sha256::default()
            .chain(H_CEN_DOMAIN_SEP)
            .chain(&self.index.to_le_bytes()[..])
            .chain(&self.cek_bytes)
            .result()[..16],
    );
    ContactEventNumber(bytes)
}
```

そして、これまで扱った`ReportAuthorizationKey`、`ReportVerificationKey`、`ContactEventKey `から`ContactEventNumber`の導出、そして、`ContactEventNumber`のindexを進めるratchetプロセス(ratchet実装処理はここでは割愛、indexをインクリメントし`cek`のハッシュ計算を行なっている)をまとめると以下のように最終的な`ContactEventNumber`群を生成することができる。

```
             ┌───┐
  ┌─────────▶│rvk│────────┬──────────┬──────────┬──────┬──────────┐
  │          └───┘        │          │          │      │          │
  │                       │          │          │      │          │
┌───┐             ┌─────┐ │  ┌─────┐ │  ┌─────┐ │      │  ┌─────┐ │
│rak│────────────▶│cek_0│─┴─▶│cek_1│─┴─▶│cek_2│─┴─▶...─┴─▶│cek_n│─┴─▶...
└───┘             └─────┘    └─────┘    └─────┘           └─────┘
                     │          │          │                 │
                     ▼          ▼          ▼                 ▼
                  ┌─────┐    ┌─────┐    ┌─────┐           ┌─────┐
                  │cen_0│    │cen_1│    │cen_2│           │cen_n│
                  └─────┘    └─────┘    └─────┘           └─────┘
```
引用：https://github.com/Co-Epi/CEN

これにより、`rvk`と`cek_i`がレポートとして送信されれば、それ以降の`cek_j`と`cen_j`(j >= i)は導出可能であることが分かる。
このようにすることで、全てのCENのリストを送る必要はなく、単純に以下のような最初のシード値と導出範囲をレポートに含めて送れば良いことになる。

### レポート
実際のレポートは以下のようなデータ構造になっており、`j_1`から`j_2`の範囲で導出される`CEN`が感染者がBluetoothによりブロードキャストした擬似乱数値として扱われる。なので、他のユーザーはこのレポートから計算される`CEN`群に一致する`CEN`を自分が受信してデバイスに保存されていないかチェックすることで感染者との接触可能性をチェックすることが可能になっている。

```rust
pub struct Report {
    pub(crate) rvk: ed25519_zebra::PublicKeyBytes,
    pub(crate) cek_bytes: [u8; 32],
    pub(crate) j_1: u16,
    pub(crate) j_2: u16,
    pub(crate) memo_type: MemoType,
    pub(crate) memo_data: Vec<u8>,
}
```

そして、このレポートは`ReportAuthorizationKey`により署名されているので、以下のように`ReportVerificationKey`で署名を検証することにより、確かに接触したユーザーから送られてきたレポートデータであることが検証できる。（`ReportVerificationKey`から最初の(Index 0の）`ContactEventKey`が導出されるので。）

```rust
pub struct SignedReport {
    pub(crate) report: Report,
    pub(crate) sig: ed25519_zebra::Signature,
}

impl SignedReport {
    /// Verify the source integrity of this report, producing `Ok(Report)` if successful.
    pub fn verify(self) -> Result<Report, Error> {
        use std::io::Cursor;
        let mut report_bytes = Vec::with_capacity(self.report.size_hint());
        self.report.write(Cursor::new(&mut report_bytes))?;

        match ed25519_zebra::PublicKey::try_from(self.report.rvk)
            .and_then(|pk| pk.verify(&self.sig, &report_bytes))
        {
            Ok(_) => Ok(self.report),
            Err(_) => Err(Error::ReportVerificationFailed),
        }
    }
}
```


### References
* [Private Contact Tracing Protocols Compared: DP-3T and CEN](https://www.zfnd.org/blog/private-contact-tracing-protocols-compared/)
* [Decentralized Privacy-Preserving Proximity Tracing](https://github.com/DP-3T/documents/tree/6ac18840fce3dd1c5e8f101dda7f036cffcbccee)
* [Specification and reference implementation of the CEN Protocol for decentralized, privacy-preserving contact tracing](https://github.com/Co-Epi/CEN)
* [Unified research on privacy-preserving contact tracing and exposure notification for COVID-19](https://docs.google.com/document/d/16Kh4_Q_tmyRh0-v452wiul9oQAiTRj8AdZ5vcOJum9Y/edit#)
* [EU privacy experts push a decentralized approach to COVID-19 contacts tracing](https://techcrunch.com/2020/04/06/eu-privacy-experts-push-a-decentralized-approach-to-covid-19-contacts-tracing/)