{"id":233353,"updated":"2025-01-19T10:07:26.445528+00:00","links":{},"created":"2025-01-19T01:34:44.660540+00:00","metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00233353","sets":["1164:2836:11471:11524"]},"path":["11524"],"owner":"44499","recid":"233353","title":["完全準同型暗号における計数ソートベースのソートプロトコル"],"pubdate":{"attribute_name":"公開日","attribute_value":"2024-03-11"},"_buckets":{"deposit":"57b73856-5293-4bdc-953e-4144c6ad8f06"},"_deposit":{"id":"233353","pid":{"type":"depid","value":"233353","revision_id":0},"owners":[44499],"status":"published","created_by":44499},"item_title":"完全準同型暗号における計数ソートベースのソートプロトコル","author_link":["633639","633642","633641","633643","633638","633640"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"完全準同型暗号における計数ソートベースのソートプロトコル"},{"subitem_title":"Oblivious Radix Sort Based on Fully Homomorphic Encryption","subitem_title_language":"en"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"暗号2","subitem_subject_scheme":"Other"}]},"item_type_id":"4","publish_date":"2024-03-11","item_4_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"東京大学"},{"subitem_text_value":"東京大学"},{"subitem_text_value":"東京大学"}]},"item_4_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"The University of Tokyo","subitem_text_language":"en"},{"subitem_text_value":"The University of Tokyo","subitem_text_language":"en"},{"subitem_text_value":"The University of Tokyo","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/233353/files/IPSJ-DPS24198069.pdf","label":"IPSJ-DPS24198069.pdf"},"date":[{"dateType":"Available","dateValue":"2026-03-11"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-DPS24198069.pdf","filesize":[{"value":"1.1 MB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"660","billingrole":"5"},{"tax":["include_tax"],"price":"330","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"34"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"2625114a-0c9d-4ee5-a2c8-9c13273584ec","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2024 by the Information Processing Society of Japan"}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"西村, 拓海"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"戸澤, 一成"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"定兼, 邦彦"}],"nameIdentifiers":[{}]}]},"item_4_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Takumi, Nishimura","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Kazunari, Tozawa","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Kunihiko, Sadakane","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_4_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AN10116224","subitem_source_identifier_type":"NCID"}]},"item_4_textarea_12":{"attribute_name":"Notice","attribute_value_mlt":[{"subitem_textarea_value":"SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc."}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_18gh","resourcetype":"technical report"}]},"item_4_source_id_11":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"2188-8906","subitem_source_identifier_type":"ISSN"}]},"item_4_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"完全準同型暗号は，データを暗号化したまま計算する秘密計算の実現方式の一つであり，サーバー一台で計算が完結するが計算時間に課題がある．本稿では，完全準同型暗号の一方式である TFHE において計数ソートベースのソートプロトコルを構成した．既存方式では配列長 N に対して，Bootstrap と呼ばれるサブルーチンを漸近的に O(N log2 N) 回呼び出すことが必要であったが，提案方式により O(N) 回の Bootstrap でのソートを可能にした．この提案方式は適用可能な配列長に上限があるが，上限を超える場合についても，漸近的な呼び出し回数は O(N log2 N) 回のまま変わらないものの，既存方式より高速にソート可能になる方法を示す．また，ライブラリを用いてこれらの提案方式の実装を行い，既存方式との比較を行った．特に，長さ 16 の 4 ビット符号なし整数配列のソートについては既存手法より 2.9 倍高速であることを確認し，提案方式の適用可能な配列長の上限を超える場合にも既存方式より高速にソート可能であることを確認した．","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"Fully homomorphic encryption realizes secure computation in which operations are performed under encryption. Computations can be completed on a single server, but there is a problem with computation time. In this paper, we construct a sorting protocol based on radix sort in TFHE, one of the fully homomorphic encryption schemes. Our protocol achieves sorting with asymptotic O(N) Bootstrap calls for an array length N, whereas existing methods require O(N log2 N) calls. Although our proposed method has an upper limit on the applicable array length, we propose methods which require O(N log2 N) Bootstrap calls but is faster than the existing sorting methods when the upper limit is exceeded. We also implemented the proposed methods using a library and compared them with existing methods. We confirmed that the proposed method is 2.9 times faster than the existing methods for sorting 4-bit unsigned integer arrays of length 16, and that the proposed method is also faster than the existing methods for sorting arrays exceeding the upper limit of the applicable array length.","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"8","bibliographic_titles":[{"bibliographic_title":"研究報告マルチメディア通信と分散処理（DPS）"}],"bibliographicPageStart":"1","bibliographicIssueDates":{"bibliographicIssueDate":"2024-03-11","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"69","bibliographicVolumeNumber":"2024-DPS-198"}]},"relation_version_is_last":true,"weko_creator_id":"44499"}}