| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2026-07-13 10:15 完全準同型暗号FHEWに対するリアクション攻撃のクエリ回数について ○小泉侑輝・楫 勇一（名大）  ISEC2026-12 SITE2026-8 BioX2026-35 HWS2026-8 ICSS2026-27 EMM2026-19 |
|
| 抄録 | （和） | 完全準同型暗号FHEWはLWE問題に基づく安全性を持つが, 復号の成功・失敗という1ビットの応答から秘密鍵を特定する「リアクション攻撃」に対し構造的な脆弱性を持つことが知られている. 先行研究の攻撃手法は, ノイズの許容範囲を単純に半分に絞り込む「空間的な二分探索」を用いていた. しかしFHEWのノイズはガウス分布に従うため, この手法では1クエリあたりの獲得情報量が最大化されていなかった. 本研究では, 情報理論の手法を用いて, 鍵復元に必要となる最小クエリ数の理論的下界を導出した. また, 分割後の2つの部分区間の確率が等分となるよう分割点を選択する「均衡二分探索」に基づく攻撃法を提案し, 提案法が理論的下界を漸近的に達成すること, すなわち, クエリ数に対し最適であることを証明した. さらに, 非漸近的な代表例である参照実装に対する評価実験を行い, 提案手法が従来手法より少ないクエリ数で秘密鍵を完全に特定でき, 実際の攻撃回数が導出した理論的下界とほぼ一致することを確認した. |
| （英） | Fully Homomorphic Encryption (FHEW) relies on the LWE problem for its security, but it is known to be vulnerable to ``reaction attacks," which identify the secret key from single-bit responses indicating decryption success or failure. Previous attack methods employed a ``spatial binary search" that simply halved the allowable noise range at the midpoint between its upper and lower bounds. However, because the noise in FHEW follows a Gaussian distribution, this method did not maximize the information gained per query. In this study, we derived the theoretical lower bound of the minimum number of queries required for key recovery using an information-theoretic approach. Furthermore, we proposed a new ``balanced binary search'' algorithm that halves the noise range at the point where the probabilities of the two subsections are equal, and showed that it asymptotically achieves the lower bound, meaning it is optimal in terms of the number of queries. Through an attack experiment on a reference implementation, which is an example of non-asymptotic construction, it is confirmed that the proposed method can completely recover the secret key with fewer queries than conventional methods, and the actual number of queries closely matches the derived theoretical lower bound. | |
| キーワード | （和） | 完全準同型暗号 / FHEW / リアクション攻撃 / LWE問題 / 情報理論 / / / |
| （英） | Fully Homomorphic Encryption / FHEW / Reaction Attack / LWE Problem / Information Theory / / / | |
| 文献情報 | 信学技報, vol. 126, no. 107, ISEC2026-12, pp. 1-8, 2026年7月. | |
| 資料番号 | ISEC2026-12 | |
| 発行日 | 2026-07-06 (ISEC, SITE, BioX, HWS, ICSS, EMM) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | ISEC2026-12 SITE2026-8 BioX2026-35 HWS2026-8 ICSS2026-27 EMM2026-19 |
|
| 研究会情報 | |
| 研究会 | BioX HWS ISEC SITE ICSS EMM IPSJ-CSEC IPSJ-SPT |
| 開催期間 | 2026-07-13 - 2026-07-15 |
| 開催地（和） | 札幌コンベンションセンター |
| 開催地（英） | Sapporo Convention Center |
| テーマ（和） | セキュリティ、一般 （セキュリティサマーサミット2026） |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | ISEC |
| 会議コード | 2026-07-BioX-HWS-ISEC-SITE-ICSS-EMM-CSEC-SPT-SEC |
| 本文の言語 | 日本語 |
| タイトル（和） | 完全準同型暗号FHEWに対するリアクション攻撃のクエリ回数について |
| サブタイトル（和） | |
| タイトル（英） | On the number of queries necessary for the reaction attack on fully-homomorphic encryption FHEW |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 完全準同型暗号 / Fully Homomorphic Encryption |
| キーワード(2)（和/英） | FHEW / FHEW |
| キーワード(3)（和/英） | リアクション攻撃 / Reaction Attack |
| キーワード(4)（和/英） | LWE問題 / LWE Problem |
| キーワード(5)（和/英） | 情報理論 / Information Theory |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 小泉 侑輝 / Yuki Koizumi / コイズミ ユウキ |
| 第1著者 所属（和/英） | 名古屋大学 (略称： 名大) Nagoya University (略称： Nagoya Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 楫 勇一 / Yuichi Kaji / カジ ユウイチ |
| 第2著者 所属（和/英） | 名古屋大学 (略称： 名大) Nagoya University (略称： Nagoya Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2026-07-13 10:15:00 |
| 発表時間 | 25分 |
| 申込先研究会 | ISEC |
| 資料番号 | ISEC2026-12, SITE2026-8, BioX2026-35, HWS2026-8, ICSS2026-27, EMM2026-19 |
| 巻番号（vol） | vol.126 |
| 号番号（no） | no.107(ISEC), no.108(SITE), no.109(BioX), no.110(HWS), no.111(ICSS), no.112(EMM) |
| ページ範囲 | pp.1-8 |
| ページ数 | 8 |
| 発行日 | 2026-07-06 (ISEC, SITE, BioX, HWS, ICSS, EMM) |
[研究会発表申込システムのトップページに戻る]