削除訂正符号の限界解明

删除修正码局限性的阐明

• 批准号: 18K11159
• 负责人: 安永 憲司
• 金额: $ 2.66万
• 依托单位: Tokyo Institute of Technology (2021-2022)Osaka University (2018-2020)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2018
• 资助国家: 日本
• 起止时间: 2018-04-01 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-18K11159/
• 关键词: 誤り訂正符号; 挿入・削除訂正; 連接符号; 挿入・削除誤り

挿入・削除に対する誤り訂正問題に対し，与えられたアルファベットサイズ，符号長，訂正半径（最小 Levenshtein 距離）に対し，どの程度大きな符号を構成できるかという符号の存在性問題に取り組んだ．可能性と不可能性の両方面から新しい限界式または評価値を明らかにすることを目指した．可能性に関する結果として，通常の Hamming 距離に関してグラフ理論を用いたアプローチ（グラフの独立数問題に帰着）が有効であり，Turan の定理や，Caro-Wei 限界を用いた符号サイズの下界式を数値的に評価した．さらに，挿入削除球サイズのタイトな上界式が改善につながるため，上界式の数え上げにおいて重複を減らした式を導出し，新たな下界式を示した．これらの限界式ならびに関連研究である Sala ら (ISIT2014) が示した下界式を，アルファベットサイズ q = 2, 4 で評価した．符号長は 10-40 程度，最小距離は 4以上について数値を導出したが，ある程度の範囲では今回導出した下界式が最も良い性能を示した．Sala らの限界式は，論文においては既存のどの限界式よりも優れているとの主張であったが，数値評価したところ，Levenshtein (ISIT2002) が示した下界よりも劣る場合があることが明らかになった．新たに導出した下界式は，漸近的には Levenshtein (ISIT2002) の下界式に一致するため，数値計算でしか改善を示すことができなかった．上界式についても，球充填上界やリスト復号可能性を利用した Elias タイプの上界式について評価した．訂正半径がある程度以上であれば，Elias タイプの上界が最も良い性能を示した．

In addition, the correction problem of the symbol length, the correction radius (minimum Levenshtein distance), and the existence problem of the symbol are selected. Possibility and improbability are new and limited expressions, and evaluation is possible. Possibility is related to the result, usually Hamming distance is related to the theory of independent number problem, Turan theorem is related to Caro-Wei limit, symbol is related to the lower bound of the formula, and the value of the formula is evaluated. In addition, the upper bound formula of the upper bound formula is improved, and the upper bound formula is repeated, and the lower bound formula is derived. Sala's (ISIT2014) research on this limiting formula and related research shows that the lower bound formula is valid, and it is evaluated as follows: q = 2,4. The symbol length is 10-40 degrees, the minimum distance is more than 4 degrees, the number value is derived, the degree is derived, the lower bound formula is the best performance is shown.Sala is bounded, the paper is bounded, the existing bounded formula is optimal, the number value is evaluated, Levenshtein (ISIT2002) shows that the lower bound is not good enough. The lower bound formula of Levenshtein (ISIT2002) is consistent with the lower bound formula of Levenshtein (ISIT2002). The upper bound formula is used to evaluate the possibility of the upper bound filling. The correction radius is above the degree of

项目成果

少ない順位付けを用いるランキング手法の評価:決定性と乱択

使用少量排名评估排名方法：确定性和随机选择

• 发表时间: 2021
• 作者: 草地翔斗;安永憲司
• 通讯作者: 安永憲司

Quantifying the Security Levels of Cryptographic Primitives

量化密码原语的安全级别

• 发表时间: 2022
• 作者: YASUNAGA Kenji;YUZAWA Kosuke;安永 憲司;安永 憲司;Kenji Yasunaga
• 通讯作者: Kenji Yasunaga

暗号学的ハッシュ関数を用いた挿入・削除訂正

使用加密哈希函数进行插入/删除校正

• 发表时间: 2021
• 作者: 長谷場 保亮;安永 憲司
• 通讯作者: 安永 憲司

Error correction by structural simplicity: correcting samplable additive errors

通过结构简单进行纠错：纠正可采样的加性误差

• DOI: 10.1093/comjnl/bxy100
• 发表时间: 2019
• 期刊: The Computer Journal
• 作者: Li Xinjun;Sundquist Jan;Hamano Tsuyoshi;Sundquist Kristina;Kenji Yasunaga
• 通讯作者: Kenji Yasunaga

Practical Card-Based Protocol for Three-Input Majority

适用于三输入多数的实用卡基协议

• DOI: 10.1587/transfun.2020eal2025
• 发表时间: 2020
• 期刊: IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
• 作者: 有子山俊平;辻 和希;N. Naoya and A. Takizawa;山岡吉生;Jun-nosuke Teramae;YASUNAGA Kenji
• 通讯作者: YASUNAGA Kenji