2024-03-28T19:17:46Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:001030952022-10-21T05:24:51Z00581:07397:07668
部分的に小さな法を用いたマルチパーティ計算のビット演算効率化Accelerating Bit-wise Calculation in Multi-party Computation by Partially Using Small Primejpn[特集:新しいリスクに対応するコンピュータセキュリティ技術] 秘密分散法,マルチパーティ計算,法変換http://id.nii.ac.jp/1001/00103071/Journal Articlehttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=103095&item_no=1&attribute_id=1&file_no=1Copyright (c) 2014 by the Information Processing Society of Japan電気通信大学情報理工学研究科筑波大学システム情報系電気通信大学情報理工学研究科加藤, 遼西出, 隆志吉浦, 裕マルチパーティ計算(MPC)の1つの問題点は参加者間で膨大な通信を必要とする点である.MPCの通信量は,シェアのビット数,つまり秘密分散の法pのビット数に比例することから,小さな法を用いることで通信量を低減する手法を提案する.大小比較や等号判定など多くのプロトコルがビットの状態の演算(ビット演算)を多用している点に着目し,これらのビット演算の共通パターンを見い出す.そして,プロトコルの入出力データの法pおよびそのビット数lpに対して,このビット演算パターンをp' > max(T',「√lp〓 + 1,n)となるような法p'で実行し,元のプロトコルの機能と安全を維持しながら,通信量を削減する.ただし,T'はビット演算における秘密値の上限であり,nはMPCにおける参加者数である.この手法により,(2,3)閾値法で法pが64ビットの場合,大小比較,等号判定,区間判定の通信量を各々80パーセント,70パーセント,80パーセント程度削減できる.The problem with secure multi-party computation (MPC) is that the parties have to transfer a large amount of data to each other. The amount of data transferred is proportional to the number of bits of shares, i.e., the number of bits of the prime p that is used in secret sharing. A scheme is presented here that reduces the amount of data transferred by partially using a small prime. Common patterns of bit calculations are found in many MPC protocols such as comparison and equality testing. Bit-wise calculation of any of these patterns can maintain the correctness and security of the original protocol by using a prime p' that satisfies p' > max(T',「√lp〓 + 1,n), where lp is the number of bits of the prime p used for the original protocol, T' is the upper bound of secret values in the bit-wise calculation, and n is the number of parties. For Shamir's (2,3) secret sharing with a prime of 64bits, the amount of data transferred in comparison, equality-testing, and interval-testing protocols can be reduced by 80, 70, and 80% respectively. AN00116647情報処理学会論文誌559197119912014-09-151882-77642014-09-10