Pat

J-GLOBAL ID：202103006998908611

秘匿ソートシステム及び方法

Inventor： 五十嵐 大 ,  濱田 浩気 ,  千田 浩司
Applicant, Patent owner： 日本電信電話株式会社
Agent (3)： 中尾 直樹 ,  中村 幸雄 ,  義村 宗洋
Gazette classification：特許公報
Application number (International application number)：2019548230
Patent number：6911929
Application date： Oct. 11, 2018
Claim (excerpt)：

【請求項1】 第1装置、第2装置、...、第M装置を含む秘匿ソートシステムであって、 ソートされるべきデータの本体をバリュー→vとして、上記ソート後の順序を決めるタグをキーとし、上記キーのビット長をL'とし、Nを所定の正の整数とし、上記キーをN個のビット列に分割したときのn+1(n=0,...,N-1)番目のビット列を→knとし、任意の値又は置換をxAとして{xA}をxAの複製秘密分散値であるとし、任意の値をxAとして[[xA]]をxAの準同型性を持つ秘密分散値であるとし、Mを2以上の所定の正の整数とし、 上記第1装置、第2装置、...、第M装置は、{→k0}のLビット安定ソートの逆置換[[σ0-1]]を得て、 上記第1装置、第2装置、...、第M装置は、[[σi-1-1]]をハイブリッド置換に変換して{σi-1-1}を得る処理と、{→ki}を{σi-1-1}で逆置換して{σi-1→ki}を得る処理と、[[σi-1→ki]]のLビット安定ソートの逆置換[[σi'-1]]を得る処理と、[[σi'-1]]に{σi-1-1}を合成して[[σi-1]]:=[[σi-1-1σi'-1]]を得る処理とをi=1,...,N-1に対して行い、[[σN-1-1]]をハイブリッド置換に変換して{σN-1-1}を得る処理を行い、 上記第1装置、第2装置、...、第M装置は、[[→v]]を{σN-1-1}で逆置換をして[[σN-1→v]]を出力する、 秘匿ソートシステム。

IPC (1)：

G09C 1/00 ( 200 6.01)

FI (3)：

G09C 1/00 660 D ,  G09C 1/00 650 Z ,  G09C 1/00 610 Z

Article cited by the Patent：

Cited by applicant (3)

• 秘匿関数計算上の線形時間ソート
• Bureaucratic protocols for secure two-party sorting, selection, and permuting
• 超高速秘密計算ソートの設計と実装