講演抄録/キーワード |
講演名 |
2021-04-12 14:15
RNS表現における除数固定の除算アルゴリズムの提案 ○川村信一(産総研/東芝)・駒野雄一(東芝) HWS2021-7 |
抄録 |
(和) |
近年公開鍵暗号の実装を応用先のひとつとして整数表現法であるRNS (Residue Number System)が研究されている. RNSでは加減乗算は要素ごとの加減乗算で実現できるが, 除算や大小比較は単純な手順では計算できなかった. 暗号応用が活発になったのは, MontgomeryリダクションのRNS版が提案されて以降であり, 大小比較(符号判定)の方法も近年になって有力な方法が提案された. しかしRNSにおいて効率的な汎用の除算は困難な問題であり決定版と見做せる方式はまだ示されていない. そこで本稿では, 一般の除算ではなく, 除数が定数という条件の下で利用できる除算アルゴリズムを提案する. 提案方式の主な構成部品はRNS版のMontgomeryリダクションとRNS版の符号判定アルゴリズムである. |
(英) |
A lot of works has been done on the research of RNS (Residue Number System), which is one of the integer representations, and the main application of which is implementation of public-key cryptography. In RNS, addition, subtraction, and multiplication can be carried out as addition, subtraction, and multiplication modulo a given basis respectively, whereas division and comparison (or sign-detection) are hard to implement with simple procedure. It was after the invention of Montgomery reduction in RNS that cryptography became one of the main applications of RNS. In addition, it was quite recent that a promising method for sign-detection was proposed. It is still a very hard problem to provide an efficient algorithm for general purpose division in RNS. Therefore, we focus on a specific case where divisor is constant. Our proposal uses RNS Montgomery reduction and RNS sign-detection as main components. |
キーワード |
(和) |
剰余演算 / RNS / 除算 / 符号判定 / / / / |
(英) |
Residue arithmetic / Residue number system / division / sign detection / / / / |
文献情報 |
信学技報, vol. 121, no. 1, HWS2021-7, pp. 27-32, 2021年4月. |
資料番号 |
HWS2021-7 |
発行日 |
2021-04-05 (HWS) |
ISSN |
Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
HWS2021-7 |
研究会情報 |
研究会 |
HWS |
開催期間 |
2021-04-12 - 2021-04-12 |
開催地(和) |
東京大学 武田先端知ビル(武田ホール)/オンライン開催 |
開催地(英) |
Tokyo University/Online |
テーマ(和) |
ハードウェアセキュリティ,一般 |
テーマ(英) |
Hardware Security |
講演論文情報の詳細 |
申込み研究会 |
HWS |
会議コード |
2021-04-HWS |
本文の言語 |
日本語 |
タイトル(和) |
RNS表現における除数固定の除算アルゴリズムの提案 |
サブタイトル(和) |
|
タイトル(英) |
A division algorithm with constant divisor in the residue number system |
サブタイトル(英) |
|
キーワード(1)(和/英) |
剰余演算 / Residue arithmetic |
キーワード(2)(和/英) |
RNS / Residue number system |
キーワード(3)(和/英) |
除算 / division |
キーワード(4)(和/英) |
符号判定 / sign detection |
キーワード(5)(和/英) |
/ |
キーワード(6)(和/英) |
/ |
キーワード(7)(和/英) |
/ |
キーワード(8)(和/英) |
/ |
第1著者 氏名(和/英/ヨミ) |
川村 信一 / Shinichi Kawamura / カワムラ シンイチ |
第1著者 所属(和/英) |
産総研/東芝 (略称: 産総研/東芝)
AIST/Toshiba (略称: AIST/Toshiba) |
第2著者 氏名(和/英/ヨミ) |
駒野 雄一 / Yuichi Komano / コマノ ユウイチ |
第2著者 所属(和/英) |
東芝 (略称: 東芝)
Toshiba (略称: Toshiba) |
第3著者 氏名(和/英/ヨミ) |
/ / |
第3著者 所属(和/英) |
(略称: )
(略称: ) |
第4著者 氏名(和/英/ヨミ) |
/ / |
第4著者 所属(和/英) |
(略称: )
(略称: ) |
第5著者 氏名(和/英/ヨミ) |
/ / |
第5著者 所属(和/英) |
(略称: )
(略称: ) |
第6著者 氏名(和/英/ヨミ) |
/ / |
第6著者 所属(和/英) |
(略称: )
(略称: ) |
第7著者 氏名(和/英/ヨミ) |
/ / |
第7著者 所属(和/英) |
(略称: )
(略称: ) |
第8著者 氏名(和/英/ヨミ) |
/ / |
第8著者 所属(和/英) |
(略称: )
(略称: ) |
第9著者 氏名(和/英/ヨミ) |
/ / |
第9著者 所属(和/英) |
(略称: )
(略称: ) |
第10著者 氏名(和/英/ヨミ) |
/ / |
第10著者 所属(和/英) |
(略称: )
(略称: ) |
第11著者 氏名(和/英/ヨミ) |
/ / |
第11著者 所属(和/英) |
(略称: )
(略称: ) |
第12著者 氏名(和/英/ヨミ) |
/ / |
第12著者 所属(和/英) |
(略称: )
(略称: ) |
第13著者 氏名(和/英/ヨミ) |
/ / |
第13著者 所属(和/英) |
(略称: )
(略称: ) |
第14著者 氏名(和/英/ヨミ) |
/ / |
第14著者 所属(和/英) |
(略称: )
(略称: ) |
第15著者 氏名(和/英/ヨミ) |
/ / |
第15著者 所属(和/英) |
(略称: )
(略称: ) |
第16著者 氏名(和/英/ヨミ) |
/ / |
第16著者 所属(和/英) |
(略称: )
(略称: ) |
第17著者 氏名(和/英/ヨミ) |
/ / |
第17著者 所属(和/英) |
(略称: )
(略称: ) |
第18著者 氏名(和/英/ヨミ) |
/ / |
第18著者 所属(和/英) |
(略称: )
(略称: ) |
第19著者 氏名(和/英/ヨミ) |
/ / |
第19著者 所属(和/英) |
(略称: )
(略称: ) |
第20著者 氏名(和/英/ヨミ) |
/ / |
第20著者 所属(和/英) |
(略称: )
(略称: ) |
講演者 |
第1著者 |
発表日時 |
2021-04-12 14:15:00 |
発表時間 |
25分 |
申込先研究会 |
HWS |
資料番号 |
HWS2021-7 |
巻番号(vol) |
vol.121 |
号番号(no) |
no.1 |
ページ範囲 |
pp.27-32 |
ページ数 |
6 |
発行日 |
2021-04-05 (HWS) |
|