2026-03-08T14:33:53Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00214445 2025-01-19T16:37:47Z 6164:6165:6462:10749

最小枚数の非コミット型６入力ANDプロトコルのシャッフル回数の改善 Improvement on the Number of Shuffles for Card-Minimal Non-Committed Six-Input AND Protocol 五十鈴川, 頼宗 宮原, 大輝 水木, 敬明 Raimu, Isuzugawa Daiki, Miyahara Takaaki, Mizuki カードベース暗号，秘密計算，カード組，非コミット型，論理積 カードベース暗号では通常黒と赤の 2 枚のカードを用いて 1 ビットを表現するため，n 入力 AND 関数を 2n 枚で秘密計算するプロトコルは最小枚数の AND プロトコルと呼ばれる．本稿では，最小枚数の非コミット型 n 入力 AND プロトコルを扱い，特に必要なシャッフル回数に注目する．現状知られているシャッフル回数が少ないという意味で最良のプロトコルは，2 入力では 2012 年に Mizuki らが提案した 2 回のシャッフルのプロトコル，3 入力では 2021 年に佐々木らが提案した 2 回のシャッフルのプロトコル，4 入力以上では 2016 年に Mizuki が提案した n+1 回のシャッフルのプロトコルである．本稿では上述の佐々木らの 3 入力プロトコルを応用することで 12 枚のカードを用いた非コミット型 6 入力 AND プロトコルを新たに提案する．このプロトコルは最小枚数であり，シャッフル回数が 6.5 回（期待値）で実行でき，既存プロトコルから 0.5 回の削減に成功している．さらに 7 入力以上にプロトコルを拡張でき，シャッフル回数は n+0.5 回（期待値）であり，既存の n+1 回から削減している． Because card-based cryptography usually encodes one bit using a pair of black and red cards, the protocols that perform secure computations of n-input AND functions with 2n cards are called card-minimal AND protocols. In this paper, we deal with card-minimal non-committed n-input AND protocols and focus on the number of shuffles. The best n-input AND protocols currently known use two shuffles for n=2, two shuffles for n=3, and n+1 shuffles for n>3. In this paper, we propose a new non-committed 6-input AND protocol with 12 cards by applying the existing 3-input protocol. This protocol is card-minimal and can be executed with expectation of 6.5 shuffles, which is 0.5 times less than the existing protocol. Furthermore, the protocol can be extended to 7 or more inputs, and the number of shuffles is n+0.5 in expectation, which is a reduction from n+1 shuffles the existing protocol requires. 情報処理学会 2021-10-19 jpn conference paper https://ipsj.ixsq.nii.ac.jp/records/214445 コンピュータセキュリティシンポジウム2021論文集 328 335 https://ipsj.ixsq.nii.ac.jp/record/214445/files/IPSJCSS2021045.pdf application/pdf 2.3 MB 2023-10-19