Secure Fast Evaluation of Iterative Methods

Secure Fast Evaluation of Iterative Methods: With an Application to Secure PageRank

paper application

ページランク on SPDZ

@inproceedings{cozzo2021secure,
  title={Secure fast evaluation of iterative methods: with an application to secure pagerank},
  author={Cozzo, Daniele and Smart, Nigel P and Alaoui, Younes Talibi},
  booktitle={Cryptographers’ Track at the RSA Conference},
  pages={1--25},
  year={2021},
  organization={Springer}
  url={https://eprint.iacr.org/2021/207.pdf}
}

Abstract

セキュアサーチは、暗号化されたデータベース（場合によってはクラウドホスト）からレコードを検索して取得します。
検索を行います。近年、データベースに対する懸念が高まっていることから、研究者の間ではセキュア
近年、データベースのプライバシーに関する関心が高まっていることから
プライバシー しかし、安全な検索における（特に乗算の）同型演算の効率が低いことが問題となっています。
homomorphic operations in secure searchは、実際の展開を妨げている。この問題に対処するため、Akaviaら[CCS 2018, PETS
2019] は、検索アルゴリズムの乗算数を𝑂(𝑛
2
)から𝑂(𝑛 log2 𝑛)へ、そして
から𝑂(𝑛 log𝑛)へ、ここで𝑛はデータベースのサイズです。この論文では
我々は最初の安全な検索プロトコルである LEAF とその変種である LEAF+ を発表します。
LEAF+-は、𝑂(𝑛)個の乗算しか必要としません。具体的には
LEAF の核となるのは、我々が提案する 3 つの新しい手法です。
LEAFの核となるのは、我々が提案する3つの新しい手法で、「Localization（局所化）」、「Extraction（抽出）」、「Reconstruction（再構成）」と呼ばれるものです。加えて、LEAF
は、通信量が少なく、クライアントが復号化を行うだけで
クライアントが復号するだけなので、携帯電話のような
これは、携帯電話のような低消費電力のデバイスに導入する際の利点となります。