視覚復号型秘密分散法 実装編

## はじめに

前回の記事で視覚復号型秘密分散法の説明をしました。

https://qiita.com/SiZK/items/ca4b246e47d99dfe585c

今回は、視覚復号型秘密分散法を Rust で実装していきます。

## 視覚復号型秘密分散法の実装

### バイナリ画像の読み書き

まずは、バイナリ画像を読み込んだり書き込んだりできるようにします。
この辺りは各言語適当なライブラリを使えば良いので、適当に読み飛ばしてもらって問題ありません。

読み込んだ画像を二値の白黒画像に変換し、それを boolean 配列にする関数を定義します。
このとき true が黒で、false が白となるようにしています。

```rust
fn read_image(path: &Path) -> Array2<bool> {
    let img = image::ImageReader::open(path).unwrap().decode().unwrap();
    let mut img = img.grayscale().to_luma8();
    image::imageops::dither(&mut img, &image::imageops::BiLevel);

    let height = img.height().try_into().unwrap();
    let width = img.width().try_into().unwrap();
    Array::from_shape_vec(
        (height, width),
        img.into_vec().iter().map(|&pixel| pixel == 0).collect(),
    )
    .unwrap()
}
```

逆に boolean の配列を二値の白黒画像とみなして、画像を書き出す関数も定義しておきます。

```rust
fn write_image(img: &Array2<bool>, path: &Path) {
    let height = img.nrows().try_into().unwrap();
    let width = img.ncols().try_into().unwrap();
    let buf = img
        .flatten()
        .map(|&flag| if flag { 0 } else { 255 })
        .to_vec();

    image::save_buffer(path, &buf, width, height, image::ExtendedColorType::L8).unwrap();
}
```

これで秘密分散を行うための準備ができました。

### サブピクセルの定義

まずは $(k, n)$ 視覚復号型秘密分散法を表す構造体 `VisualSecretSharing` を定義します。

```rust
struct VisualSecretSharing<const K: usize, const N: usize> {}
```

今回は任意の $(k, n)$ に対応するわけではないので、サブピクセルの trait を定義して、それを実装している型のみで、秘密分散を行えるようにしていきます。

```rust
trait Subpixel {
    const C0: LazyCell<Array2<bool>>;
    const C1: LazyCell<Array2<bool>>;
    const M_ROW: usize;
    const M_COL: usize;

    fn subpixel(&self, secret: bool) -> Array2<bool> {
        let subpixel = if secret { &*Self::C1 } else { &*Self::C0 };

        random_permutation(subpixel)
    }
}
```

`C0` と `C1` が定義してあれば `subpixel` メソッドを呼び出せるようにしています。
また `M_ROW` と `M_COL` は、サブピクセルの行数と列数です。

あとは `random_permutation` を定義して、サブピクセルの列をランダムに入れ替えるようにます。

```rust
fn random_permutation(matrix: &Array2<bool>) -> Array2<bool> {
    let mut rng = rand::thread_rng();
    let mut perm: Vec<usize> = (0..matrix.ncols()).collect();
    perm.shuffle(&mut rng);

    matrix.select(Axis(1), &perm)
}
```


$(2, 2)$ と $(3, 4)$ の違いはサブピクセルの部分だけなので、異なる部分の実装をここで一気に終わらせます。

#### (2, 2) 視覚復号型秘密分散法のサブピクセルの実装

`VisualSecretSharing<2, 2>` に対して `Subpixel` trait を実装します。

```rust
impl Subpixel for VisualSecretSharing<2, 2> {
    const C0: LazyCell<Array2<bool>> =
        LazyCell::new(|| ndarray::arr2(&[[false, true], [false, true]]));
    const C1: LazyCell<Array2<bool>> =
        LazyCell::new(|| ndarray::arr2(&[[false, true], [true, false]]));
    const M_ROW: usize = 1;
    const M_COL: usize = 2;
}
```

#### (3, 4) 視覚復号型秘密分散法のサブピクセルの実装

同様に `VisualSecretSharing<2, 2>` に対して `Subpixel` trait を実装します。

```rust
impl Subpixel for VisualSecretSharing<3, 4> {
    const C0: LazyCell<Array2<bool>> = LazyCell::new(|| {
        ndarray::arr2(&[
            [false, false, false, true, true, true],
            [false, false, true, false, true, true],
            [false, false, true, true, false, true],
            [false, false, true, true, true, false],
        ])
    });
    const C1: LazyCell<Array2<bool>> = LazyCell::new(|| {
        ndarray::arr2(&[
            [true, true, true, false, false, false],
            [true, true, false, true, false, false],
            [true, true, false, false, true, false],
            [true, true, false, false, false, true],
        ])
    });
    const M_ROW: usize = 2;
    const M_COL: usize = 3;
}
```

### シェアの生成

サブピクセルの実装が終わっていれば、シェアの生成は難しくありません。

一つ一つのピクセルに対して `subpixel` メソッドを実行していくだけです。
したがって、元の画像の大きさを $H \times W$ とすると、シェア画像の大きさは $H M_{ROW} \times W M_{COL}$ になります。

```rust
impl<const K: usize, const N: usize> VisualSecretSharing<K, N>
where
    Self: Subpixel,
{
    fn generate_shares(&self, secret: &Array2<bool>) -> Array3<bool> {
        let (height, width) = secret.dim();

        let mut shares = Array::from_elem((N, Self::M_ROW * height, Self::M_COL * width), false);

        for ((x, y), &pixel) in secret.indexed_iter() {
            shares
                .slice_mut(ndarray::s![
                    ..,
                    Self::M_ROW * x..Self::M_ROW * (x + 1),
                    Self::M_COL * y..Self::M_COL * (y + 1)
                ])
                .assign(
                    &self
                        .subpixel(pixel)
                        .to_shape((N, Self::M_ROW, Self::M_COL))
                        .unwrap(),
                );
        }

        shares
    }
}
```

### 秘密情報の再構成

再構成は、計算機が無くてもできるようになっており、計算機での処理もかなり簡単です。
シェア画像で同じ位置にあるピクセルの論理和を取れば良いだけです。

:::note info
実世界で再構成をする場合は、シェア画像を透明なシートに印刷して、そのシート同士を重ね合わせるというのが一般的です。
:::


```rust
impl<const K: usize, const N: usize> VisualSecretSharing<K, N>
where
    Self: Subpixel,
{
    fn reconstruct(&self, shares: &Array3<bool>) -> Array2<bool> {
        let (_, height, width) = shares.dim();
        let mut img = Array::from_elem((height, width), false);

        for share in shares.outer_iter() {
            img.zip_mut_with(&share, |x, &y| {
                *x |= y;
            });
        }

        img
    }
}
```

### 動作確認

ここでは $(3, 4)$ の方で見ていきます。

```rust
let secret = read_image(Path::new("secret.bmp"));

let vss = VisualSecretSharing::<3, 4> {};

let shares = vss.generate_shares(&secret);
for (i, share) in shares.outer_iter().enumerate() {
    write_image(
        &share.to_owned(),
        Path::new(&format!("share_{:02}.bmp", i + 1)),
    );
}
```

秘密情報 `secret.bmp` として以下の画像を使いました。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3774343/c1c09b02-dc4a-c1de-f5a6-2651c30ca51f.png)

そうすると、シェア画像は以下のように出力されました。

| 1 つ目 | 2 つ目 | 3 つ目 | 4 つ目 |
|---|---|---|---|
| ![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3774343/ee5506df-b1f2-3fd2-f852-219a9dbab717.png) | ![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3774343/e2daf085-be41-0df4-c594-92632d4f4d3b.png) | ![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3774343/87de8df5-b7b2-3a75-f507-f6028c32547a.png) | ![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3774343/3af68a57-6d86-65ed-888d-bc5cb0788201.png) |

少なくとも、人の目でみたときに元の情報は分かりません。
2 つのシェアを重ねたものがどうなるかを見てみます。

```rust
let reconstructed_secret_from_2_shares = vss.reconstruct(&shares.select(Axis(0), &[0, 1]));
write_image(
    &reconstructed_secret_from_2_shares,
    Path::new("reconstructed_secret_from_2_shares.bmp"),
);
```

先ほどのシェア画像の 1, 2 番目を重ねたものが以下です。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3774343/faaa1293-742c-ee33-aef3-9f4a4eb79382.png)

これも、まだ元の情報は分かりません。
$(3, 4)$ 視覚復号型秘密分散法なので、今のところ挙動は正しそうです。

3 つのシェアを重ねたときに、元の情報が分かるようになれば良さそうです。

```rust
let reconstructed_secret_from_3_shares = vss.reconstruct(&shares.select(Axis(0), &[0, 1, 2]));
write_image(
    &reconstructed_secret_from_3_shares,
    Path::new("recontructed_secret_from_3_shares.bmp"),
);
```

先ほどのシェア画像の 1, 2, 3 番目を重ねたものが以下です。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3774343/f7bad6d8-3c7f-4fee-8dba-e88e378e0e4c.png)

相対差が小さいですが、元の情報が読み取れるようになっています。

4 つのシェアを重ねた場合も見てみます。

```rust
let reconstructed_secret_from_all_shares = vss.reconstruct(&shares);
write_image(
    &reconstructed_secret_from_all_shares,
    Path::new("recontructed_secret_from_all_shares.bmp"),
);
```

先ほどのシェア画像を全部重ねたものが以下です。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3774343/124a6255-390f-960a-75e1-0dc206f5b2bb.png)

先ほどより、くっきりと黒が見えるようになっています。
理論的には、3 つ重ねた場合の相対差が 1 で、4 つ重ねた場合の相対差が 2 なので、実際にそのようになっていそうなことが分かります。

<details><summary>全体のコード</summary>

```rust
use ndarray::{Array, Array2, Array3, Axis};
use rand::seq::SliceRandom;
use std::{cell::LazyCell, path::Path};

fn read_image(path: &Path) -> Array2<bool> {
    let img = image::ImageReader::open(path).unwrap().decode().unwrap();
    let mut img = img.grayscale().to_luma8();
    image::imageops::dither(&mut img, &image::imageops::BiLevel);

    let height = img.height().try_into().unwrap();
    let width = img.width().try_into().unwrap();
    Array::from_shape_vec(
        (height, width),
        img.into_vec().iter().map(|&pixel| pixel == 0).collect(),
    )
    .unwrap()
}

fn write_image(img: &Array2<bool>, path: &Path) {
    let height = img.nrows().try_into().unwrap();
    let width = img.ncols().try_into().unwrap();
    let buf = img
        .flatten()
        .map(|&flag| if flag { 0 } else { 255 })
        .to_vec();

    image::save_buffer(path, &buf, width, height, image::ExtendedColorType::L8).unwrap();
}

fn random_permutation(matrix: &Array2<bool>) -> Array2<bool> {
    let mut rng = rand::thread_rng();
    let mut perm: Vec<usize> = (0..matrix.ncols()).collect();
    perm.shuffle(&mut rng);

    matrix.select(Axis(1), &perm)
}

struct VisualSecretSharing<const K: usize, const N: usize> {}

trait Subpixel {
    const C0: LazyCell<Array2<bool>>;
    const C1: LazyCell<Array2<bool>>;
    const M_ROW: usize;
    const M_COL: usize;

    fn subpixel(&self, secret: bool) -> Array2<bool> {
        let subpixel = if secret { &*Self::C1 } else { &*Self::C0 };

        random_permutation(subpixel)
    }
}

impl Subpixel for VisualSecretSharing<2, 2> {
    const C0: LazyCell<Array2<bool>> =
        LazyCell::new(|| ndarray::arr2(&[[false, true], [false, true]]));
    const C1: LazyCell<Array2<bool>> =
        LazyCell::new(|| ndarray::arr2(&[[false, true], [true, false]]));
    const M_ROW: usize = 1;
    const M_COL: usize = 2;
}

impl Subpixel for VisualSecretSharing<3, 4> {
    const C0: LazyCell<Array2<bool>> = LazyCell::new(|| {
        ndarray::arr2(&[
            [false, false, false, true, true, true],
            [false, false, true, false, true, true],
            [false, false, true, true, false, true],
            [false, false, true, true, true, false],
        ])
    });
    const C1: LazyCell<Array2<bool>> = LazyCell::new(|| {
        ndarray::arr2(&[
            [true, true, true, false, false, false],
            [true, true, false, true, false, false],
            [true, true, false, false, true, false],
            [true, true, false, false, false, true],
        ])
    });
    const M_ROW: usize = 2;
    const M_COL: usize = 3;
}

impl<const K: usize, const N: usize> VisualSecretSharing<K, N>
where
    Self: Subpixel,
{
    fn generate_shares(&self, secret: &Array2<bool>) -> Array3<bool> {
        let (height, width) = secret.dim();

        let mut shares = Array::from_elem((N, Self::M_ROW * height, Self::M_COL * width), false);

        for ((x, y), &pixel) in secret.indexed_iter() {
            shares
                .slice_mut(ndarray::s![
                    ..,
                    Self::M_ROW * x..Self::M_ROW * (x + 1),
                    Self::M_COL * y..Self::M_COL * (y + 1)
                ])
                .assign(
                    &self
                        .subpixel(pixel)
                        .to_shape((N, Self::M_ROW, Self::M_COL))
                        .unwrap(),
                );
        }

        shares
    }

    fn reconstruct(&self, shares: &Array3<bool>) -> Array2<bool> {
        let (_, height, width) = shares.dim();
        let mut img = Array::from_elem((height, width), false);

        for share in shares.outer_iter() {
            img.zip_mut_with(&share, |x, &y| {
                *x |= y;
            });
        }

        img
    }
}

fn main() {
    let secret = read_image(Path::new("secret.bmp"));

    let vss = VisualSecretSharing::<3, 4> {};

    let shares = vss.generate_shares(&secret);
    for (i, share) in shares.outer_iter().enumerate() {
        write_image(
            &share.to_owned(),
            Path::new(&format!("share_{:02}.bmp", i + 1)),
        );
    }

    let reconstructed_secret_from_2_shares = vss.reconstruct(&shares.select(Axis(0), &[0, 1]));
    write_image(
        &reconstructed_secret_from_2_shares,
        Path::new("reconstructed_secret_from_2_shares.bmp"),
    );

    let reconstructed_secret_from_3_shares = vss.reconstruct(&shares.select(Axis(0), &[0, 1, 2]));
    write_image(
        &reconstructed_secret_from_3_shares,
        Path::new("recontructed_secret_from_3_shares.bmp"),
    );

    let reconstructed_secret_from_all_shares = vss.reconstruct(&shares);
    write_image(
        &reconstructed_secret_from_all_shares,
        Path::new("recontructed_secret_from_all_shares.bmp"),
    );
}
```

</details>

## おわりに

この記事では、Rust による視覚復号型秘密分散法の実装をしました。
$(2, 2)$ の方でも試してみたり、色々な画像で試したりしてみると、面白いかもしれません。