Patent ID: 10074293

Abstract:
Secret calculation including secret sorting is performed at high speed. Permutation data generation step S10 generates permutation data <πi> and <π′i> so as to generate permutation data <πL>. Random ID column generation step S12 generates a random ID column [r→i] so as to generate a random ID column [r→L]. Secret random permutation step S14 performs secret random permutation of a set composed of a random ID column [r→i−1], a key column [k→i], and the random ID column [r→i] with the permutation data <πi>. Flag creation step S16 sets a flag [fj,h] by using a key [kj]=([kj,0], . . . , [kj,L−1]). Order table creation step S18 creates an order table [s→] by using the flag [fj,h]. Sort permutation generation step S20 generates sort permutation σπ−1L by using the random ID column [r→i], the order table [s→], a post-permutation key column [πik→i], and a post-permutation random ID column [πir→i].