# 秘密分散とMPC閾値署名 (SSS, MPC, TSS)

## シャミアの秘密分散法 - Shamir's Secret Sharing Scheme (SSS, SSSS) [^1]

* *(k, n) 閾値秘密分散* で有名な暗号の手法。RSAの "Shamir" が作った。
* データを $n$ 個の **share** に分割する。再度 $m$-of-$n$ の share を集め無い限り、元のデータを復元できなくする暗号の手法。
* 多くの場合、暗号鍵の保護に使われる。

### ざっくり仕組み

* ラグランジュ補間定理を利用[^1]
* 多項式上の $K$ 個の点が $K-1$ 以下の次数の多項式を一意に決定することを利用。
* シークレット $S$ を $1$ byte 単位に分割し、ガロア拡大体 $GF(2^8)$ 上で演算する。
* $X$ byteのシークレットから $X$ byteの share が生成される。
* 詳細は https://www.slideshare.net/AkitoTabira/ss-56244856

[^1]: [Shamir's secret sharing - Wikipedia](https://en.wikipedia.org/wiki/Shamir%27s_secret_sharing)

### 図解

* $y$ 切片がシークレット $S$


### Proactive Secret Sharing (PSS)

* *proactive* ... 定期更新などで攻撃者がシェアを侵害する時間を *積極的に* 減らす[^2]
* 元の鍵を更新せずに、鍵の share の rotation が出来る。
* 解説動画: [https://www.youtube.com/watch?v=iOqU2DySmeU](https://www.youtube.com/watch?v=iOqU2DySmeU)
* Alice のシェアが欠損しても、Bob, Carol, Dave から新しいシェアを再計算できるようにする。
* 定期的に更新する場合もある。

[^2]: https://en.wikipedia.org/wiki/Proactive_secret_sharing

### 利用例

Web3Auth や αu wallet[^3] など、様々なところで利用例がある。

Web3Auth では、次のように SSS を利用している[^4]。
* フロントエンドで秘密鍵を生成し 3 つの ShareA, ShareB, ShareC に分割して各々異なる場所で管理する。
* ShareA: ユーザのデバイス上に保存。
* ShareB: 更に複数に分割した状態でコンソーシアムの Auth network に分散。Social login で取得可能。
* ShareC: 別デバイス保存、ユーザのパスワード等から Recovery される Share。


[^3]: https://twitter.com/niwatako/status/1642428508378124289
[^4]: https://web3auth.io/option-1-generate-private-key.html でシミュレートできる。技術詳細は https://docs.tor.us/key-infrastructure/overview#base-torus-key-infrastructure-guarantees や最新の document を参照

## MPC ((Secure) Multi-party Computation)

* **秘密計算(Secure Computation)** の一種[^5][^6]
* $N$ 人参加者が入力値 $x_1, ... x_N$ を秘匿したまま、多入力関数の値 $f(x_1, ... x_N)$ のみ計算できる暗号学的な手法 [^7]。

[^5]: https://www.nri.com/-/media/Corporate/jp/Files/PDF/knowledge/publication/kinyu_itf/2021/11/itf_202111_6.pdf?la=ja-JP&hash=B75299BC3BD923E51C716912E43FE569BF8B6913
[^6]: https://www.jstage.jst.go.jp/article/isciesci/63/2/63_64/_pdf/-char/ja
[^7]: [マルチパーティ計算の情報理論的解析](https://www.taf.or.jp/files/items/572/File/036.pdf)

## 閾値署名方式 Threshold Signature Scheme (TSS)

- 閾値署名方式 (TSS) = 分散鍵生成 (DKG) + 分散署名 [^8]

[^8]: [Threshold Signatures Explained | Binance Academy](https://academy.binance.com/en/articles/threshold-signatures-explained)

### ざっくりの仕組み

加法に関する準同型性を有する準同型暗号をベースに *色々頑張ったら* MPCで高速に閾値ECDSA署名が作れるようになった（難しい）。

- 有名論文: [CESC18: Fast Multiparty Threshold ECDSA with Fast Trustless Setup - Steven Goldfeder](https://www.youtube.com/watch?v=PMk2v9hjqEI)
- 解説動画
- https://www.youtube.com/watch?v=PdfDZIwuZm0
- https://gist.github.com/Haseeb-Qureshi/ecaeaa47f79b6fdf460722cfdc4b8f64 (書き起こし?)
- Paillier 暗号: 加法準同型性を有する公開鍵暗号[^9]。
- Threshold Paillier: 分散での setup が非現実的(とても遅い)で、現実的には Dealer が必要になる。
- CESC18論文の内容: 現実的な(実用的な, practical) trusted setup に基づく閾値ECDSA
- Threshold Paillier を使わずに、各々が Paillier 復号鍵を取得できる方法
- Dealerless で 1 秒未満の実行速度
- 大幅な帯域削減が可能

[^9]: https://ja.wikipedia.org/wiki/準同型暗号

### SSS vs TSS [^8]

| SSS | TSS |
| ---- | ---- |
| 鍵生成で Dealer が 1 人存在 | Dealer が不在 |
| 署名時に秘密鍵の再構築が必要 | 秘密鍵の再構築が不要 |

* TSSは秘密鍵が存在しない（知られていない）状態で署名を作れる

### MultiSig vs TSS [^8]

| MultiSig | TSS |
| ---- | ---- |
| on-chainで実行される | off-chainで実行される |
| 参加者が非対話的 | 参加者が対話的 |
| 各々が署名を作る | 全体で単一の署名を作る |
| プライバシーに弱い(署名者がバレる) | プライバシーに強い(署名者がバレない) |

#### MultiSig の問題点

- Inflexible
- 署名者の変更は on-chain でアドレスの付け替えが必要
- TSS は proactive な方法で参加者や share を入れ替えたり出来る
- Public
- on-chain 上で各々の署名者がバレて、アクセス構造が公開になる
- Large
- on-chain 上で $n$ 個の署名が必要
- TSS は 1 個

## MPC / TSS-based ウォレット

### MPCウォレットのアーキテクチャ

1. アウトソーシング
- 自分の代わりに $n$ 台のサーバにオフロードする
- サービスプロバイダに結託されるリスクがある
- **Lit Protocol の PKP** (distributed custody[^11])
2. 複数デバイスで実行する
- Iot Device, 携帯, ノートPC
- オンラインで複数デバイスを扱うのが面倒
3. ハイブリッド
- 外部のサービスプロバイダー + ユーザ所有のデバイス
- 1, 2 のいいとこ取り
- **Web3Auth MPC**[^12] など

[^11]: https://web3auth.io/mpc.html
[^12]: https://developer.litprotocol.com/pkp/intro/#what-are-programmable-key-pairs-pkps

## TSSの応用(意外な利用例)

### Multi-Hop Locks [^8]

- secure な private payment channel を構築できる Bitcoin Lightning Network の alternative
- 二者間署名を賢く使ってるらしい
- Library for ECDSA based construction for Anonymous Multi-Hop Locks
https://github.com/ZenGo-X/multi-hop-locks
- [Anonymous Multi-Hop Locks for Blockchain Scalability and Interoperability](https://eprint.iacr.org/2018/472.pdf)


### ShareLock [^8]

- Mixing に使える
- Trusted setupやTrusted thirdpartyを必要としないMixingにThreshold ECDSAが使えるらしい。
- Mixing for Cryptocurrencies from Multiparty ECDSA
https://github.com/ZenGo-X/ShareLock
- [ShareLock: Mixing for Cryptocurrencies from Multiparty ECDSA](https://eprint.iacr.org/2019/563.pdf)

## Questions

* TSSの欠点ってあるの？対話型だし、運用が大変とか？
* 多分そう。実際 ThresholdNetwork は "trust levers" の判断をユーザにある程度委ねているが、逆に言うと、ブロックチェーンのように参加者の honest majority assumption のような強い仮定のもとにリスクを 0 とするような定義、インセンティブ設計はできていないように思える。
* PKP の distributed custody ってどうなの？
* 鍵を譲渡可能な点で便利ではある
* 結託されるリスクはある
* 運用する組織が分散していないことによる法的根拠は要確認
* MPC/TSS-basedなウォレットは、秘密鍵をそのまま取り扱うより安全なんだよね?
* ハイブリット形式のアーキテクチャであれば、仮にユーザがローカルに持つshareが侵害されていても、Social loginの裏側にあるノードが持つshareは侵害されていないので、署名が作れるのはユーザのみになり、秘密鍵をそのまま持つより安全そうに思える。
* 時間経過によるshareの侵害を防ぐために定期更新などもできる。
* 異なるデバイスへの分散やリカバリーに関しても利点がある。

## TODO: 論文を解読したら追記

https://hackmd.io/@3RKQkspCSDyM3Yr6hz-hIA/SyZ8ETjWh