[發(fā)明專利]一種基于秘密分享的多鍵排序方法和系統(tǒng)

有效

• 申請(qǐng)?zhí)枺?/td>: 202210205805.4
• 申請(qǐng)日: 2022-03-04
• 公開（公告）號(hào): CN114327371B
• 公開（公告）日: 2022-06-21
• 發(fā)明（設(shè)計(jì)）人: 方文靜;王力
• 申請(qǐng)（專利權(quán)）人: 支付寶（杭州）信息技術(shù)有限公司
• 主分類號(hào): G06F7/76
• 分類號(hào): G06F7/76
• 代理公司: 成都七星天知識(shí)產(chǎn)權(quán)代理有限公司 51253
• 代理人: 袁春曉

1.一種基于秘密分享的多鍵排序方法，其中，第一方擁有一個(gè)或多個(gè)第一信息項(xiàng)分別對(duì)應(yīng)的一個(gè)或多個(gè)第一數(shù)據(jù)列；第二方擁有一個(gè)或多個(gè)第二信息項(xiàng)分別對(duì)應(yīng)的一個(gè)或多個(gè)第二數(shù)據(jù)列；所述第一數(shù)據(jù)列和所述第二數(shù)據(jù)列按行對(duì)齊；所述方法由第一方執(zhí)行，包括：

將所述一個(gè)或多個(gè)第一信息項(xiàng)分別作為排序鍵對(duì)所述一個(gè)或多個(gè)第一數(shù)據(jù)列進(jìn)行迭代排序，得到第一結(jié)果序列；

基于所述第一結(jié)果序列獲得第一分組標(biāo)記列，所述第一分組標(biāo)記列的元素指示所述一個(gè)或多個(gè)第一數(shù)據(jù)列中的對(duì)位元素依據(jù)所述一個(gè)或多個(gè)第一信息項(xiàng)的聯(lián)合分組信息；

將所述第一分組標(biāo)記列作為待排序序列，與第二方將第二排序向量作為排序向量，進(jìn)行秘密分享向量排序，得到經(jīng)過(guò)排序的第一分組標(biāo)記列的第一分片，第二方得到經(jīng)過(guò)排序的第一分組標(biāo)記列的第二分片；其中，所述第二排序向量用于標(biāo)識(shí)將所述一個(gè)或多個(gè)第二信息項(xiàng)作為排序鍵分別對(duì)等長(zhǎng)序列進(jìn)行多鍵排序的操作，所述第二排序向量的元素指示該等長(zhǎng)序列中對(duì)位元素在結(jié)果序列中的位置；

基于所述經(jīng)過(guò)排序的第一分組標(biāo)記列的第一分片，與第二方基于所述經(jīng)過(guò)排序的第一分組標(biāo)記列的第二分片，進(jìn)行秘密分享基數(shù)排序，得到第三排序向量的第一分片，第二方得到第三排序向量的第二分片；

基于所述第三排序向量的第一分片，與第二方基于所述第三排序向量的第二分片以及所述第二排序向量，進(jìn)行秘密分享合并，得到多方排序向量的第一分片，第二方得到多方排序向量的第二分片；其中，所述多方排序向量用于標(biāo)識(shí)分別將所述一個(gè)或多個(gè)第一信息項(xiàng)以及所述一個(gè)或多個(gè)第二信息項(xiàng)作為排序鍵對(duì)等長(zhǎng)序列進(jìn)行多鍵排序的操作，所述多方排序向量的元素指示該等長(zhǎng)序列中對(duì)位元素在結(jié)果序列中的位置；

基于所述多方排序向量的第一分片，與第二方基于所述多方排序向量的第二分片，對(duì)待排序數(shù)據(jù)列進(jìn)行秘密分享向量排序，得到目標(biāo)數(shù)據(jù)列的第一分片，第二方得到目標(biāo)數(shù)據(jù)列的第二分片；所述目標(biāo)數(shù)據(jù)列等于分別將所述一個(gè)或多個(gè)第一信息項(xiàng)以及所述一個(gè)或多個(gè)第二信息項(xiàng)作為排序鍵對(duì)所述待排序數(shù)據(jù)列進(jìn)行多鍵排序的結(jié)果。

2.如權(quán)利要求1所述的方法，所述基于所述第一結(jié)果序列獲得第一分組標(biāo)記列包括：

基于所述第一結(jié)果序列獲得待重排的分組標(biāo)記列，所述待重排的分組標(biāo)記列的元素指示所述第一結(jié)果序列中對(duì)位元素依據(jù)所述一個(gè)或多個(gè)第一信息項(xiàng)的聯(lián)合分組信息；

獲得第一排序向量的逆；其中，所述第一排序向量用于標(biāo)識(shí)分別將所述一個(gè)或多個(gè)第一信息項(xiàng)作為排序鍵對(duì)等長(zhǎng)序列進(jìn)行迭代排序的操作，所述第一排序向量的元素指示該等長(zhǎng)序列中對(duì)位元素在結(jié)果序列中的位置；排序向量的逆用于標(biāo)識(shí)對(duì)基于排序向量對(duì)等長(zhǎng)序列進(jìn)行排序得到的結(jié)果序列進(jìn)行還原的操作，其元素指示所述結(jié)果序列中對(duì)位元素在原序列中的位置；

以所述第一排序向量的逆為排序向量，對(duì)所述待重排的分組標(biāo)記列進(jìn)行排序，得到所述第一分組標(biāo)記列。

3.如權(quán)利要求1所述的方法，所述基于所述多方排序向量的第一分片，與第二方基于所述多方排序向量的第二分片，對(duì)待排序數(shù)據(jù)列進(jìn)行秘密分享向量排序，得到目標(biāo)數(shù)據(jù)列的第一分片，第二方得到目標(biāo)數(shù)據(jù)列的第二分片，包括：

基于所述多方排序向量的第一分片、所述待排序數(shù)據(jù)列的第一分片，與第二方基于所述多方排序向量的第二分片、所述待排序數(shù)據(jù)列的第二分片，進(jìn)行秘密分享向量排序，得到目標(biāo)數(shù)據(jù)列的第一分片，第二方得到目標(biāo)數(shù)據(jù)列的第二分片。