少パーティの秘密分散ベース秘密計算のためのO(l)ビット通信ビット分解およびO(|p′|)ビット通信Modulus変換法

五十嵐, 大, 濱田, 浩気, 菊池, 亮, 千田, 浩司

秘密計算における最も重要な演算の一つとして, ビット分解がある.ビット分解はlビットの数値が格納された1つの秘密分散値を, 1ビットの真偽値の暗号文/秘密分散値から成る長さlの列に変換する操作である.またModulus変換は秘密分散値の法をあるpから別のp'に変更する操作である.本稿ではパーティ数の小さい(k, n)-秘密分散ベース秘密計算において,非常に高速なビット分解およびModulus変換を提案する.通信量はシェアのビット長|p|, |p'|(すなわちl ≦ |p|)としてO(|p|^2)ビット, O(|p|^2 + |p'|^2)ビットが従来最良であったのに対して, 提案手法はO(l)ビット, O(|p'|)となる.

As one of the most significant operations in the field of secure computation, it decomposition is known.Bit decomposition is an operation that converts one encrypted or shared value whose plaintext is a l-bit numerical value into l encrypted / shared values whose plaintexts are 1-bit truth-values. Modulus conversion is a conversion which change mod p shares into mod p' shares.The paper proposes a highly efficient bit decomposition and modulus conversion for secure computations based on (k,n) secret sharing schemes with small k.The communication complexity of proposed protocols are O(l) bits and O(|p'|) bits, while O(|p|^2) and O(|p|^2 + |p'|^2) were the best in existing protocols, where |p| and |p'| are the bit length of the underlying secret sharing scheme (i.e., l <= |p|).

少パーティの秘密分散ベース秘密計算のための<i>O</i>(<i>l</i>)ビット通信ビット分解および<i>O</i>(|<i>p′</i>|)ビット通信Modulus変換法

書誌事項

抄録

収録刊行物

キーワード

詳細情報詳細情報について

書き出し

問題の指摘