Randomness and Structure in Error-Correcting Codes

纠错码中的随机性和结构

• 批准号: 23700010
• 负责人: YASUNAGA Kenji
• 金额: $ 2.33万
• 依托单位: Kanazawa University (2012-2013)(財)九州先端科学技術研究所 (2011)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2011
• 资助国家: 日本
• 起止时间: 2011 至 2013
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-23700010/
• 关键词: 誤り訂正符号; 多項式時間計算; 加法的通信路; 誤り訂正能力; 加法的誤り; 多項式時間計算可能

We have introduced samplable additive-error channels, and studied the possibilities and limitations of error correction in the channels. "Samplable" means that the errors are efficiently computable, and "additive" means that the errors are added to input codewords without the knowledge of the code or the codewords. If samplable distributions form linear subspaces, we can correct the errors by linear codes. In the situations relativized by oracles, there are samplable errors with low entropy for which no efficient syndrome decoding exists. If samplable distributions are of small-bias, there is a relation between the magnitude of the bias and the information rate on which the errors are correctable.

我们引入了可采样加性误差通道，并研究了在通道中纠错的可能性和局限性。“可采样”意味着错误是可有效计算的，并且“可加”意味着错误被添加到输入码字而不知道代码或码字。如果可抽样分布构成线性子空间，我们可以用线性码纠正错误。在预言机相对化的情况下，存在具有低熵的可采样错误，对于这些错误不存在有效的伴随式解码。如果可抽样分布是小偏差的，则偏差的大小与错误可纠正的信息率之间存在关系。

项目成果

Error correction in computationally bounded channels

计算有限通道中的纠错

• 发表时间: 2013
• 作者: Haruna Higo;Keisuke Tanaka;and Kenji Yasunaga;三浦 一之;A. Kawamura;Kenji Yasunaga
• 通讯作者: Kenji Yasunaga

Correctability of efficiently computable additive errors

有效计算附加误差的可校正性

• 发表时间: 2012
• 作者: Haruna Higo;Keisuke Tanaka;and Kenji Yasunaga;河村彰星;三浦 一之;Kenji Yasunaga
• 通讯作者: Kenji Yasunaga

Game-Theoretic Security for Bit Commitment

• DOI: 10.1007/978-3-642-41383-4_20
• 发表时间: 2013-11
• 作者: Haruna Higo;Keisuke Tanaka;Kenji Yasunaga

Leakage-Resilience of Stateless/Stateful Public-Key Encryption from Hash Proofs

来自哈希证明的无状态/有状态公钥加密的泄漏恢复能力

• DOI: 10.1587/transfun.e96.a.1100
• 发表时间: 2013
• 期刊: IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
• 作者: Manh Ha Nguyen;Kenji Yasunaga;Keisuke Tanaka
• 通讯作者: Keisuke Tanaka

Randomness Leakage in the KEM/DEM Framework

• DOI: 10.1007/978-3-642-24316-5_22
• 发表时间: 2011-10
• 期刊: IEICE Trans. Fundam. Electron. Commun. Comput. Sci.
• 作者: Hitoshi Namiki;Keisuke Tanaka;Kenji Yasunaga