MASAZUMI KURIHARA
| Department of Computer and Network Engineering | Assistant Professor |
| Cluster II (Emerging Multi-interdisciplinary Engineering) | Assistant Professor |
Researcher Information
Degree
- B.S.(Bachelor of Science) in Mathematics at Tokyo Metropolitan University, Tokyo Metropolitan University
- M.E.(Master of Engineering) in Computer Science and Information Mathematics at University of Electro, The University of Electro-Communications
- Ph.D. in Computer Science and Information Mathematics at University of Electro-Communications, The University of Electro-Communications
Educational Background
Research Activity Information
Paper
- Construction of Distributed Multi-User Secret Sharing : II
Shun Kariya; Masazumi Kurihara
IEICE Technical Report, vol.124, 147, 42-47, Aug. 2024
Symposium, Japanese - A Study of Feature Point Extraction Methods Suitable for Non-Referenced Local Watermarking in Still Images
Kota Sasaki; Siyi Shang; Masazumi Kurihara; Kazuhiko Yamaguchi
IEICE Technical Report, vol.123, no.424, 12-19, Mar. 2024
Symposium, Japanese - Construction of Distributed Multi-User Secret Sharing : I
Shun Kariya; Masazumi Kurihara
IEICE Technical Report, vol.123, no.338, 39-44, Jan. 2024
Symposium, Japanese - Private Information Retrieval Using MBR and MSR Codes Against Colluding, Byzantine, and Unresponsive Servers
Masazumi KURIHARA
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences, J106-A, 1, 5-20, Jan. 2023, Peer-reviwed
Scientific journal, Japanese - On a Multi-Message Private Information Delivery
Masazumi Kurihara
IEICE Trans. on Fundamentals of Electronics, Communications and Computer Sciences, IEICE, J105-A, 1, 6-17, 01 Jan. 2022, Peer-reviwed
Scientific journal, Japanese - Multi-Data Private Information Retrieval from Cyclic Reed-Solomon Coded Data in Distributed Storage Systems
Masazumi Kurihara
IEICE Trans. on Fundamentals of Electronics, Communications and Computer Sciences, IEICE, J103-A, 12, 321-337, 01 Dec. 2020, Peer-reviwed
Scientific journal, Japanese - Coded Caching Method to Construct a Transmitted Signal Based on the Distribution of the Number of Requests
Masazumi Kurihara
IEICE Trans. on Fundamentals of Electronics, Communications and Computer Sciences, The Institute of Electronics, Information and Communication Engineers(IEICE), J103A, 2, 43-54, 01 Feb. 2020, Peer-reviwed
Scientific journal, Japanese - Secure Regenerating Codes Using Linear Regenerating Codes and the All-or-Nothing Transform
Hidenori Kuwakado; Masazumi Kurihara
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, E100D, 3, 483-495, Mar. 2017, Peer-reviwed, This paper proposes secure regenerating codes that are composed of non-secure regenerating codes and a new all-or-nothing transform. Unlike the previous analysis of secure regenerating codes, the security of the proposed codes is analyzed in the sense of the indistinguishability. The advantage of the proposed codes is that the overhead caused by the security against eavesdropping is much less than that of previous secure regenerating codes. The security of the proposed codes against eavesdropping mainly depends on the new all-or-nothing transform.
Scientific journal, English - Secure Regenerating Codes Using Linear MBR/MSR Codes and the All-or-Nothing Transform
Hidenori Kuwakado; Masazumi Kurihara
2014 INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY AND ITS APPLICATIONS (ISITA), IEEE, 221-225, 2014, Peer-reviwed, This paper proposes new secure regenerating codes that combine non-secure regenerating codes with an all-or-nothing transform. Unlike the previous analysis of secure regenerating codes, the security of the proposed codes is analyzed in the sense of the indistinguishability. The advantage of the proposed codes is that the storage-size overhead is much less than that of previous secure regenerating codes.
International conference proceedings, English - 修復可能な分散ストレージシステムにおける最小ストレージ再生成符号に基づく秘密分散法
Masazumi Kurihara; Hidenori Kuwakado
Lead, 電子情報通信学会 和文論文誌Ａ（基礎・境界ソサイエティ）, The Institute of Electronics, Information and Communication Engineers, J96-A, 4, 166-174, Apr. 2013, Peer-reviwed, 修復可能な分散ストレージシステムにおける最小ストレージ再生成符号に基づく秘密分散法を提案する.再生成符号は,ストレージノードの故障により失われた分散データであるシェアを効率良く再生成する機能をもつ分散符号化の一つである.再生成符号では,メッセージを分散符号化したシェアと失われたシェアと同じシェアを再生成するための再生成用データの2種類のデータがネットワーク中に存在する.秘密情報が盗聴者に漏れないようにするためには,シェアと再生成用データのそれぞれに対する安全性を確保する必要がある.特に,秘密情報を漏らすことなくシェアを再生成する安全な再生成の機能は,重要で特徴的な機能となる.本論文では,最小ストレージ再生成符号に基づく秘密分散法の構成法を提案し,その安全性を示す.そして,最小ストレージ再生成符号に基づく秘密分散法で安全な再生成を保証するShahらの符号との違いを示す.更に,提案符号は,再生成符号を用いた場合に安全にネットワーク中に保存できるストレージ容量の上界を達成する最適な性能をもつことも示す.
Scientific journal, Japanese - Secure regenerating codes based on rashmi-shah-kumar MBR codes
Masazumi Kurihara; Hidenori Kuwakado
Lead, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Institute of Electronics, Information and Communication, Engineers, IEICE, E96-A, 2, 635-648, 2013, Peer-reviwed, In this paper, we present a construction of (n, k, d,m) secure regenerating codes for distributed storage systems against eavesdroppers that can observe either data stored in at most m storage nodes or downloaded data for repairing at most m failed nodes in a network where m <
k ≤ d ≤ n - 1. The (n, k, d,m) secure regenerating code is based on an (n, k, d) minimum bandwidth regenerating (MBR) code, which was proposed by Rashmi, Shah and Kumar as optimal exact-regenerating codes, for all values of the parameters (n, k, d). The (n, k, d,m) secure regenerating codes have the security as a secret sharing scheme such that even if an eavesdropper knows either data stored in at most m storage nodes or downloaded data for repairing at most m failed nodes, no information about data leaks to the eavesdropper. Copyright © 2013 The Institute of Electronics, Information and Communication Engineers.
Scientific journal, English - Secret Sharing Schemes Based on Minimum Bandwidth Regenerating Codes
Masazumi Kurihara; Hidenori Kuwakado
2012 INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY AND ITS APPLICATIONS (ISITA 2012), IEEE, 255-259, 2012, Peer-reviwed, In this paper, we propose a construction of secure regenerating codes for distributed storage systems against passive eavesdroppers that can observe either data stored in storage nodes or downloaded data for repairing failed nodes in a network, and evaluate the security of them. The proposed secure regenerating code is based on a minimum bandwidth regenerating(MBR) code, which was proposed by Rashmi, Shah and Kumar as optimal exact-regenerating codes. The proposed secure regenerating code has the security of a ramp secret sharing scheme.
International conference proceedings, English - Multicast Error Correcting Codes for Network Coding
Masazumi Kurihara
電子情報通信学会 和文論文誌Ａ（基礎・境界ソサイエティ）, The Institute of Electronics, Information and Communication Engineers, J93-A, 4, 312-320, Apr. 2010, Peer-reviwed, 本論文では,ネットワークコーディングにおけるマルチキャスト誤り訂正符号とその生成行列を提案する.そして,マルチキャスト誤り訂正符号はシングルトン限界を達成することが可能である.マルチキャスト誤り訂正符号は,マルチキャスト通信を可能とする既存の情報伝送用ネットワークコーディングを利用する新しい誤り訂正符号である.
Scientific journal, Japanese - A note on a relation between a metric and error correcting codes: An extending a concept of metric from Coding Theory to Network Coding
Masazumi Kurihara
The IEICE Transactions, The Institute of Electronics, Information and Communication Engineers, J92-A, 7, 513-520, Jul. 2009, Peer-reviwed, 本論文では,ネットワークコーディングでの誤り訂正における誤りをとらえる距離の概念が,従来の符号理論での誤り訂正におけるランダム誤りをとらえるハミング距離の自然な拡張になっていることを示す.この拡張した距離をテンプレート距離と呼ぶ.そして,ネットワークコーディングにおける誤り訂正符号の誤り訂正能力を,テンプレート距離で測った符号の最小距離により評価することができる.また,符号の最小距離の上界も示すことができる.更に,テンプレート距離を用いることで,ネットワークコーディングにおける誤り訂正符号の復号として,最小距離復号やリスト復号などの距離構造を利用する復号が理論的に実行可能となり,テンプレート距離はネットワークコーディングでの誤り訂正において有効な基礎概念となる.
Scientific journal, Japanese - Decoding algorithm for iterated codes correcting compound errors
M Kurihara
ELECTRONICS AND COMMUNICATIONS IN JAPAN PART III-FUNDAMENTAL ELECTRONIC SCIENCE, SCRIPTA TECHNICA-JOHN WILEY & SONS, 89, 1, 60-72, 2006, This paper discusses codes, and a decoding method, that can correct compound errors containing a mix of random and burst errors. Specifically, the paper provides a minimum compound distance that represents a compound error correcting capacity for iterated codes, proposes a compound error correcting decoding algorithm for the code, and demonstrates that the decoding algorithm is capable of correcting compound errors up to half the minimum compound distance of the code. The proposed decoding algorithm is a generalized decoding method in which the decoding method for iterated codes indicated by Reddy and Robinson is a particular case. By this generalization, the proposed decoding algorithm can correct compound errors that cannot be corrected by conventional decoding methods. (c) 2005 Wiley Periodicals, Inc.
Scientific journal, English - Systolic array architecture implementing Berlekamp-Massey-Sakata algorithm for decoding codes on a class of algebraic curves
Hajime Matsui; Shojiro Sakata; Masazumi Kurihara; Seiichi Mita
IEEE TRANSACTIONS ON INFORMATION THEORY, IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC, 51, 11, 3856-3871, Nov. 2005, Peer-reviwed, We construct a two-dimensional systolic array implementing the Berlekamp-Massey-Sakata (BMS) algorithm to provide error-locator polynomials for codes on selected algebraic curves. This array is constructed by introducing some new polynomials in order to increase the parallelism of the algorithm. The introduced polynomials are used in the majority logic scheme by Sakata et al. to correct errors up to the designed minimum distance without affecting its high speed. The arrangement of the nearest local connection of processing units in the systolic array is obtained for the general case. Furthermore, shortened systolic arrays that reduce the circuit scale and have the same function are constructed with only a slight modification of the connections and controls; this enables the adjustment of the circuit scale for different types of systems.
Scientific journal, English - Decoding algorithm for iterated codes correcting compound-errors
栗原正純
電子情報通信学会 和文論文誌Ａ（基礎・境界ソサイエティ）, The Institute of Electronics, Information and Communication Engineers, J84-A, 5, 642-654, May 2001, Peer-reviwed, 本論文ではランダム誤りとバースト誤りが混在する複合誤りを訂正可能な符号及びその復号法について議論される。具体的には、繰り返し符号に対する複合誤り訂正能力を表す最小複合距離が示され、その複合誤り訂正復号アルゴリズムが提案される。この復号アルゴリズムは符号の最小複合距離の半分までの複合誤りを訂正可能であることが示される。そして、この復号アルゴリズムはReddy-Robinsonが示した繰り返し符号に対する復号法を特別な場合として含む一般化された復号法になる。この一般化により、従来の復号法では訂正できない複合誤りの訂正が可能となる。
Scientific journal, Japanese - A Concept of Correcting Compound-Errors
栗原正純
IEICE Trans., J83-A, 6, 771-780, Jun. 2000, Peer-reviwed
Scientific journal, Japanese - On generalized Hyperbolic Cascaded Reed-Solomon codes
M Kurihara
ELECTRONICS AND COMMUNICATIONS IN JAPAN PART III-FUNDAMENTAL ELECTRONIC SCIENCE, SCRIPTA TECHNICA-JOHN WILEY & SONS, 82, 11, 18-27, Nov. 1999, In this paper, a generalized version of the Hyperbolic Cascaded Reed-Solomon (HCRS) code proposed by K. Saints and C. Heegard is considered. The lower bound of the minimum distance (the design distance) is investigated. This is a linear code that can be expressed as (n, k, d(min) greater than or equal to 6) on GF(q). Here, n, k, d(min), and d are the code length, dimension, minimum distance, and design distance, respectively. The proposed code has more degrees of freedom in selection of the code length than the HCRS code. Codes with various code length can be constructed easily. However, in the m-dimensional space on GF(q), the selectable code length is less than q(m). When the proposed code with a code length less than q(m) is compared with the shortened code with the same code length obtained by shortening the nt-dimensional HCRS code with a code length of q(m) [or (q - 1)(m)], the design distances are identical, whereas the proposed code has an equal or greater dimension compared with the HCRS code. Also, from the proposed code, it is relatively easy to construct a code of the same code length as the algebraic geometric code (geometric Goppa code) and the improved geometric Goppa code proposed by Feng and Rao. Further, when the performance (parameters) is compared at a high coding rate (k/n), the proposed code sometimes has equal or better performance. (C) 1999 Scripta Technica.
Scientific journal, English - On Some Compound-Error-Correcting Codes
栗原正純
IEICE Trans., The Institute of Electronics, Information and Communication Engineers, J81-A, 3, 415-424, Mar. 1999, Peer-reviwed, 本論文では, 多重ランダム誤りと多重バースト誤りが発生する通信路での複合誤りを訂正する効率の良い符号を提案する. この提案する符号は, 2種類の符号系をテンソル積とその積重ね行列を用いて組み合わせることで得られる線形ブロック符号である. 複合誤り訂正符号として実際に幅広く応用されている積符号との比較においては, 符号が定義される体, 符号長, 複合誤り訂正能力のいずれも同じ場合, 提案する符号の次元の方が大きく符号化率の高い効率の良い符号となることが示される. また, ランダム誤りやバースト誤り訂正を目的として提案された代数幾何符号やインタリーブ方式による符号とのある種の比較において, 提案する符号はその次元を調節することでバースト誤り, 又はランダム誤り訂正能力を有効に向上させることができることが示される.
Scientific journal, Japanese - On generalized Hyperbolic Cascaded Reed-Solomon codes
栗原正純
IEICE Trans., J81-A, 4, 763-772, Apr. 1998, Peer-reviwed
Scientific journal, Japanese - On a class of byte-error-correcting codes from algebraic curves and their fast decoding algorithm
Masazumi Kurihara; Shojiro Sakata; Kingo Kobayashi
Lead, IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG, E79A, 9, 1298-1304, Sep. 1996, Peer-reviwed, In this paper we propose a class of byte-error-correcting codes derived from algebraic curves which is a generalization of the Reed-Solomon codes, and present their fast parallel decoding algorithm. Our algorithm can correct up to [ (m + b - theta)/2b] byte-errors for the byte length b, where m + b - theta + 1 greater than or equal to d(G) for the Goppa designed distance d(G). This decoding algorithm can be parallelized. In this algorithm, for our code over the finite field GF (q), the total complexity for finding byte-error locations is O(bt(t + q - 1)) with time complexity O(t(t + q - 1)) and space complexity O(b), and the total complexity for finding error values is O(bt(b + q - 1)) with time complexity O(b(b + q - 1)) and space complexity O(t), where t less than or equal to [ (m + b - theta)/2b]. Our byte-error-correcting algorithm is superior to the conventional fast decoding algorithm for random-errors in regard to the number of correcting byte-errors in several cases.
Scientific journal, English - On the construction and decoding of hyperelliptic codes
Masazumi Kurihara
BULLETIN OF THE UNIVERSITY OF ELECTRO-COMMUNICATIONS, The University of Electro-Communications, 6, 1, 21-28, Jun. 1993
Research institution, English - Fast Algorithm of Finding an Error Locator Function for Algebraic-Geometric Codes from Elliptic and Hyperelliptic Curves : O(n^2)
栗原正純; 水野弘文
BULLETIN OF THE UNIVERSITY OF ELECTRO-COMMUNICATIONS, 電気通信大学, 5, 1, 1-11, Jun. 1992
Research institution, Japanese - A Method for Constructing and Decoding Some Parvicular Algebraic Geometric Codes
栗原正純; 水野弘文; 安藤清
BULLETIN OF THE UNIVERSITY OF ELECTRO-COMMUNICATIONS, 電気通信大学, 4, 1, 77-85, Jun. 1991
Research institution, Japanese
MISC
- New coding schemes for distributed storage systems: Regenerating codes and pyramid codes
Hidenori Kuwakado; Masazumi Kurihara
Institute of Electronics Information Communication Engineers, 01 Feb. 2015, Journal of the Institute of Electronics, Information and Communication Engineers, 98, 2, 130-137, Japanese, Book review, 0913-5693, 84929894284 - FAST PARALLEL DECODING ON SYSTOLIC ARRAY ARCHITECTURE FOR CODES ON A CLASS OF ALGEBRAIC CURVES (Algebraic Aspects of Coding Theory and Cryptography)
Matsui Hajime; Sakata Shojiro; Kurihara Masazumi
Kyoto University, Apr. 2005, RIMS Kokyuroku, 1420, 193-205, English, 1880-2818, 110001147299, AN00061013
Books and other publications
- A Course in Error-Correcting Codes (EMS Textbooks in Mathematics) 2nd Edition
阪田省二郎; 栗原正純; 松井一; 藤沢匡哉
Japanese, Joint translation, 第８章 符号の組合せ、第９章 リード・ソロモン符号とBCH符号の復号、第１０章 反復的復号、付録B、D, 森北出版株式会社, 25 Apr. 2019, 9784627817128 - 誤り訂正符号入門
阪田省二郎; 栗原正純; 松井一; 藤沢匡哉
Japanese, Joint translation, 第９章 畳込み符号の最尤復号、第１０章 符号の組合せ、第１１章 ユークリッド法を用いたRS符号とBCH符号の復号、付録A、参考文献, 森北出版株式会社, 2005
Lectures, oral presentations, etc.
- Coded caching and a subspace based on the distribution of the number of requests
Masazumi Kurihara
Oral presentation, Japanese, 電子情報通信学会情報理論研究会, Domestic conference
07 Mar. 2019 - Secure Cooperative Regenerating Codes for Distributed Function Against Eavesdropping and Collusion Attack
Yosuke TANAKA; Masazumi Kurihara
Oral presentation, Japanese, 平成 29 年度電子情報通信学会東京支部学生会研究発表会（第２３回）
03 Mar. 2018 - On Secure Regenerating Codes with Rushing Cheater Detection
Kazuhiro Shimoe; Masazumi Kurihara
Oral presentation, Japanese, 平成 28 年度電子情報通信学会東京支部学生会研究発表会（第２２回）
04 Mar. 2017 - On Secret Sharing Schemes based on Regenerating Codeds
M.Kurihara
Invited oral presentation, English, 1012 IEICE General Conference, IEICE
Mar. 2012 - 最小バンドワイド再生成符号を用いたランプ型秘密分散法
Masazumi Kurihara; Hidenori Kuwakado
Oral presentation, Japanese, Technical Committee on Information Theory, The Institute of Electronics, Information and Communication Engineering (IEICE)
Nov. 2011 - Computationally-Secure Regenerating Code
Hidenori Kuwakado; Masazumi Kurihara
Oral presentation, English, IPSJ
Oct. 2011 - 修復可能な分散ストレージシステムにおけるランプ型秘密分散法
Masazumi Kurihara; Hidenori Kuwakado
Oral presentation, Japanese, Technical Committee on Information Theory, The Institute of Electronics, Information and Communication Engineering (IEICE)
Jul. 2011 - On an extended version of Rashmi-Shah-Kumar regenerating codes and secret sharing for distributed storage
Masazumi Kurihara; Hidenori Kuwakado
Oral presentation, Japanese, Technical Committee on Information Theory, The Institute of Electronics, Information and Communication Engineering (IEICE)
Mar. 2011 - On regenerating codes and secret sharing for distributed storage
Masazumi Kurihara; Hidenori Kuwakado
Oral presentation, Japanese, Technical Committee on Information Theory, The Institute of Electronics, Information and Communication Engineering (IEICE)
Jan. 2011 - Video watermarking based on erasure decoding using reliability information
齋藤真吾; 栗原正純; 山口和彦
Oral presentation, Japanese, 電子情報通信学会 信学技報,情報セキュリティ研究会
Dec. 2010 - Multicast-Error-Correcting-Codes and their Construction for Network Coding
Masazumi Kurihara
Oral presentation, Japanese, IEICE Technical Report
Jul. 2009 - On decoding error-correcting codes for linear network coding
Masazumi KURIHARA
Public symposium, Japanese, 第31回情報理論とその応用シンポジウム, 情報理論とその応用学会, 栃木県鬼怒川
Oct. 2008 - On the linear network codes and their novel construction methods
Masazumi KURIHARA
Invited oral presentation, Japanese, 電子情報通信学会2007年ソサイエティ大会, IEICE
Sep. 2007 - A note on secure network coding algorithms
Masazumi KURIHARA
Public symposium, Japanese, 情報理論とその応用シンポジウム, 情報理論とその応用学会, 函館
Dec. 2006 - ネットワーク符号化を用いた効率的なファイル配布法
青柳真一; 栗原正純; 小林欣吾
Public symposium, Japanese, 情報理論とその応用シンポジウム, 情報理論とその応用学会, 函館
Nov. 2006 - ネットワーク符号化とある種の線型変換
栗原正純
Oral presentation, Japanese, 電子情報通信学会技術研究報告,情報理論研究会
Jul. 2006 - 組合せネットワーク上のルーティング制御とその応用
栗原正純; 楯岡孝道
Oral presentation, Japanese, 電子情報通信学会技術報告,情報理論研究会
Mar. 2006 - Reed-Solomon符号の最尤復号に関する検討
正津宗幸; 栗原正純; 杉村立夫
Oral presentation, Japanese, 電子情報通信学会技術報告
Sep. 2005 - Fast parallel decoding on systolic array architecture for codes on an class of algebraic curves
Hajime Matsui; Shojiro Sakata; Masazumi Kurihara
Oral presentation, English, Kokyuroku, RIMS Kyoto Univ
Apr. 2005 - The low complexity side information source code
バトチュルーン デミチッグ; 小林欣吾; 栗原正純
Oral presentation, Japanese, Proc of 27-th SITA 2004
Dec. 2004 - MDS codes and their decoding algorithm
栗原正純
Oral presentation, Japanese, Technial Report of IEICE
Mar. 2004 - A study on context tree weight method for non-stationary source
久富達也; 小林欣吾; 栗原正純
Oral presentation, Japanese, Technial Report of IEICE
Mar. 2004 - Erasures and compound-errors control
栗原正純
Oral presentation, Japanese, Technial Report of IEICE
Mar. 2003
Courses
- 情報通信工学実験/電子情報学実験(B1・B2)
2018 - Present - Computer Literacy
2017 - Present - Computer Literacy
2010 - Present - Discrete Mathematics
Oct. 2007 - Mar. 2010
Hosei University - 情報通信工学実験/電子情報学実験(B1・B2)
The University of Electro-Communications - 情報通信工学実験/電子情報学実験(B1・B2)
電気通信大学 - 情報通信工学実/験電子情報学実験(B1・B2)
The University of Electro-Communications - コンピュータリテラシ
The University of Electro-Communications - 情報通信工学実/験電子情報学実験(B1・B2)
The University of Electro-Communications - 情報通信工学実/験電子情報学実験(B1・B2)
電気通信大学 - コンピュータリテラシ
The University of Electro-Communications - コンピュータリテラシ
電気通信大学 - 情報通信システム実験第二B / 電子情報システム実験第二B
The University of Electro-Communications - 情報通信システム実験第二B / 電子情報システム実験第二B
電気通信大学 - computer literacy
The University of Electro-Communications - コンピューターリテラシー
電気通信大学
Research Themes
- On fast decoding of multipoint codes from algebraic curves
SHOJIRO Sakata; MASAZUMI Kurihara; MASAYA Fujisawa
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, The University of Electro-Communications, Grant-in-Aid for Scientific Research (C), 本研究は、今まで本研究代表者が着々と実施してきた1点代数曲線符号の効率的な復号法の研究をさらに発展させ、より広い符号クラスである多点代数曲線符号に対し、高速な復号法を導入することが目的である。本研究の成果として、代数幾何符号を構成するのに使われる代数曲線の中で最も重要なHermite曲線を考え、その上で定義できる2点代数曲線符号について、その高速な復号法を確立した。特に、1点代数曲線符号の復号法の拡張として、2点Hermite曲線符号の訂正半径までの誤り訂正を可能とする多数決論理を組み込んだ高速復号法を与えた。, 19560369
2007 - 2008 - Studies towards the Network Coding Theory Based on Multi user Information Theory and Cryptography
KOBAYASHI Kingo; SAKATA Shojiro; OHTA Kazuo; YAMAGUCHI Kazuhiko; BRIAN Kurkoski; KURIHARA Masazumi
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, The University of Electro-Communications, Grant-in-Aid for Scientific Research (B), マルチユーザ情報理論と暗号理論の視点から, ネットワーク符号化におけるロバスト性とセキュア性の両立を意識して, 線形ネットワーク符号の新しい構成法, ネットワーク誤り訂正符号の復号に関する基本概念の確立と, 具体的復号アルゴリズムの提案, および, 計算量の評価を行った。さらに, 多重アクセス・ブロードキャスト・ネットワークに適するセキュリティ・プロトコル, 安全なコンテンツ配信のための電子透かし法等の提案をした。, 18360179
2006 - 2008 - Fast decoding methods of algebraic geometry codes and generalized algebraic geometry codes
SAKATA Shojiro; KURIHARA Masazumi; FUJISAWA Masaya
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, The University of Electro-Communications, Grant-in-Aid for Scientific Research (C), The objective of this research is to develop efficient algorithms for decoding not only algebraic geometric (AG) codes but also generalized algebraic geometric (GAG) codes and furthermore aim at systematizing past and new research results of fast decoding methods for those codes so that these decoding methods can be used practically in digital communication systems in the highly information-technological world in near future. As outcomes of our researches, we have clarified several relations among fast decoding methods of those codes. In particular, we have shown that the parallel Berlekamp-Massey (BM) algorithm and Euclidean algorithm for decoding are identical, and that the multiple-sequence BM algorithm can be replaced by a succession of single-sequence BM algorithm. Furthermore, we have shown that the Welch-Belekamp algorithim can be realized as a vectorial version of BM algorithm. We presented these results in the 2004 International Symposium on Information Theory and Applications (ISITA-2004), in Parma, Italy, October 10-13, 2004, in the IEEE 2005 International Symposium on Information Theory, in Adelaide, Australia, September 4-9, 2005, and in the 2006 International Symposium on Information Theory and Applications (ISITA-2006), in Seoul, Korea, October 29-November 1, 2006, respectively. Related to the research, we published a textbook on Coding Theory entitled Introduction to Error-Correcting Codes which is a Japanese translation of A Course in Error-Correcting Codes by J.Justesen, and T.Hoeholdt published by European Mathematical Society, in 2004, as well as a paper entitled "Systolic array architecture implementing Berlekamp-Massey-Sakata algorithm for decoding codes on a class of algebraic curves" in IEEE Transactions on Information Theory, in 2005. In 2006, we had several tutorial lectures to give a grand survey of past and new results of our researches on fast decoding of AG codes., 16560323
2004 - 2006 - A Study of Universal Coding for Enumerable Discrete Information Structures
KOBAYASHI Kingo; YAMAGUCHI Kazuhiko; KURIHARA Masazumi
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, The University of Electro-Communications, Grant-in-Aid for Scientific Research (C), The theme of this research project is on a study of universal coding of enumerative discrete information structures, such as integers, trees, graphs and Young tableaux that frequently appear in the computer science, as well as finite discrete data representing letters of text, sampled quantized voice data, and data of brightness and chroma in pictures. We have completed the analysis of coding of binary trees, and extended our method to k-ary trees and vector k-ary trees, the use of which should be powerful for universal coding. Furthermore, we moved a step towards the study of Young tableaux containing the class of trees as a subset of them. We can correspond a binary tree to a 2 x n rectangular Young tableaux. But we cannot correspond k-ary tree and vector k-ary tree to a standard Young tableaux in general. However, we show that by an extended Young tableaux defined by a poset in the integer lattice, it is possible to represent them. These results suggest attractive idea on constructing new code for general trees. Furthermore, we got many aspects on the meaning of Hook formula and the bumping algorithm by generalizing the standard Young tableaux to multi-dimensional tableaux. We presented these results at several international conference(IEEE ISIT 2002,2004,ISITA2004 at Parma, Conferences on General information transfer and combinatorics at Bielefeld university). As well as the above theoretical study, we researched experimentally the performance of watermark and steganography. In the study of watermark for copyright protection and steganography that is considered as a generalized version of hiding information, we performed experiments with respect to the fundamental efficiencies of watermark on resistance against coalition, and steganography using frequency region by considering the structure of relevant data., 14550351
2002 - 2004 - Synthesis of liner feedback shift register allowing give pairs of input and output arrays
SAKATA Shojiro; KURIHARA Masazumi
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, University of Electro-Communications, Grant-in-Aid for Scientific Research (C), The objective of this research is to develop an efficient algorithm for solving the problem of synthesizing linear feedback shift register allowing given pairs of input and output arrays by expanding our research results on fast decoding of algebraic geometric (AG) codes. The problem is an extension of the problem of synthesizing linear feedback shit register capable of generating given output arrays, which is closely related to fast decoding methods of practical algebraic codes such as RS codes, BCH codes and next-generation error-correcting codes, i.e. AG codes. The present problem treats nonhomogeneous Toeplitz and block-Toeplitz equations and their multidimensional extensions, while the former problem treats homogeneous Toeplitz and block-Toeplitz equations and their multidimensional extensions. Our problem is known as Wiener-Hoph equations in the field of linear system theory. As an outcome of our research, we have given an efficient method of solving our problem in case of pairs of one-dimensional input and output arrays, and presented our result in the IEEE 2002 International Symposium on Information Theory, in Lausanne, Switzerland, Jun 30-July 5,2000. Next, we have made clear that our method can be applied to fast factorization of polynomials over rational function field in the second stage of list decoding of polynomials over algebraic function field in the second stage of list decoding of AG codes, and presented these results in the Third Asian-European Workshop on Information Theory, in Awakamogawa, Jun 25-28, 2003, and in the IEEE 2003 International Symposium on Information Theory, in Yokohama, Jun 29-July 4, 2003, respectively. In the beginning of this research we undertook to solve the problem from a standpoint of system theory so that we have succeeded to show that our method can be applied to fast list decoding of RS codes and AG codes, which was one of our aims for more efficient decoding method. Related to the research, we published papers on parallel decoding of AG codes and compound-error-correcting codes in IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, J85-A, 4, 460-470, 2002 (in Japanese), and E86-A, 7, 1813-1819, 2003 (in English)., 14550350
2002 - 2003 - Efficient List Decoding of Codes from Algebraic Curves
SAKATA Shojiro; KURIHARA Masazumi
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, The University of Electro-Communications, Grant-in-Aid for Scientific Research (C), The objective of this research is to develop an efficient algorithm for list decoding of algebraic geometric (AG) codes or codes from algebraic curves. An algebraic list decoding method has been introduced recently by M. Sudan. It consists of two major procedures, where the first is to find an interpolation polynomial having a set of zeros specified by the pair of the received word and the information positions, and the second is to factorize the interpolation polynomial. This Sudan algorithm (Sudan-1) has been improved to another version (Sudan-2) by Guruswami and Sudan, where Sudan-1 can work only for coding rate less than 1/3, but the latter even for larger coding rate. As an outcome of our research, we have given efficient methods of finding the interpolation polynomials for both Sudan-1 and Sudan-2 list decoding algorithms of RS codes, and published a paper (in Japanese) treating these subjects in IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol.J83-A, No.11, 2000. Therein, based on the observation that the problem of finding the interpolation polynomial is reduced to finding the Grobner basis of a polynomial ideal having the specified zeros, we have given the efficient interpolation methods by applying the BMS algorithm which we invented before for fast realization of the conventional bounded-distance decoding of AG codes. Furthermore, we have made clear that the BMS algorithm can be adapted naturally to fast Sudan-1 interpolation for AG codes, the result of which we presented in the IEEE 2000 International Symposium on Information Theory, in Sorrento, Italy, June 25-30, 2000. On the other hand, it was difficult to adapt the BMS algorithm to fast Sudan-2 interpolation for AG codes, because this problem, do1 not have such a nice structure as the previous. But, we have given a solution to it by using a different formulation based on the defining arrays of a polynomial ideal. We presented the result in the international ' conference AAECC-14, Melbourne, Australia, November 26-30, 2001, and published in Applied Algebra, Algebraic Algorithms and Error-Correcting Codes: Proc. AAECC-14 (Eds. S. Boztas, I.E. Shparlinski), Springer Verlag, 2001., 12650368
2000 - 2001 - Mathematical Study on Information Transform for Data Compression and Information Security
KOBAYASHI Kingo; KURIHARA Masazumi; YAMAGUCHI Kazuhiko
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, The University of Electro-Communications, Grant-in-Aid for Scientific Research (C), The theme of this research project is on a study of novel transform of information for the efficient data compression and the secure data transmission. With respect to the information transform for data compression, we have first provided some interesting properties of the fix-free cock. Next, we need an efficient expression of the ordered tree for the date compression .and storage/ Therefore, we analyzed the performance of coding of ordered trees, and established the optimal codeword length function. Furthermore, we had studied the Bernoulli splitting process with biased probabilities, and gave asymptotically the expected branch number and depth of the trie by using the Mellin transform. Here, we encounter the entropy function in the residue of the related generating function. This phenomenon could be found in a case where the generalized amplitudes and frequencies are in the relation of multinomial coefficients and products of probabilities, respectively, in the generalized harmonic series. Furthermore, we proposed the Catalan code for integers by a combination of the pre-order coding and the enumerative coding of binary trees, and compared the performance of the code with that of Elias omega code. The transform for secure data transmission is studied from two aspects, that is, from the error-correcting coding and the data security points of views. Specifically, by introducing the theoretical framework of protection of data suffered from the compound errors, that is, the mixture of random errors and burst errors, we gave a new efficient decoding method of iterated codes for the compound error correction. On the other hand, for the study of data security we concentrated on synthesizing a new method which can protect against the attack of removing the watermarks. Here, we considered the relation to the error control code, and investigated the various kind of attacks. We have realized a method having both of the convenience for the user and of the strength against the collision and repeat attack., 11650373
1999 - 2001 - Fast GMD Decoding of Codes from Algebraic Curves
SAKATA Shojiro; KURIHARA Masazumi
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, The University of Electro-Communications, Grant-in-Aid for Scientific Research (C), The objective of this research is to extend our previous method for fast decoding of one-point algebraic geometric codes (codes from algebraic curves or surfaces) to a fast GMD (generalized minimum distance) decoding of these codes. For fast GMD decoding of conventional algebraic codes including RS codes, several alternative methods have been given by other researchers. On the other hand, based on the recognition that algebraic geometric codes are a natural extention of conventional algebraic codes from one dimension to n dimension, we published some survey papers in volumes Grobner Bases and Applications and Codes, Curves and Signals as well as in journals Journal of IEICE and Mathematical Science. First, in this broad perspective, we published a paper on another version of fast GMD decoding of one-dimensional algebraic codes in IEICE Transactions. Next, we published a paper on fast erasure-and-error decoding method of one-point algebraic geometric codes jointly with American and Danish researchers in IEEE Transactions on Information Theory, the contents of which should be a core of fast GMD decoding method of these codes based on BMS algorithm. But, there still remains a difficult problem of how we can dispense with many redundant iterations of these erasure-and-error decoding procedures which are required by majority logic in determining the unknown syndrome values necessary for error correction up to the designed distance. To settle this problem, we have proposed a pair of GMD procedures, i.e. erasure-addition and erasure-deletion which can be combined with each other in many alternative ways during a fast GMD decoding process. At present we are trying to construct a kind of heuristic algorithm for fast GMD decoding method. Together with these research works we have published several relevant papers on fast decoding of algebraic geometric codes and its parallel implementation, etc., 10650354
1998 - 1999 - Fast Parallel Implementation of Bounded-Distance Decoding of Codes from Argebraic Curves with Systolic Array Achitecture
SAKATA Shojiro; KURIHARA Masazumi; KODA Hiromu
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, University of Electro-Communications, Grant-in-Aid for Scientific Research (C), Before we gave a fast decoding algorithm for one-point algebraic geometric codes up to the designed distance, which can be implemented in serial form on conventional computers of von Neumann type. Now we have etablished a method for implementing the decoding algorithm in parallel form with a sytolic array architecture for the parallel processing. Parts of our results were presented in several international conferences : (1) Our bsic idea for paralleliztion of the original fast decoding algorithm at the conference IMAX-ACA,Line, Austria, in July, 1996 ; (2) A vector version of the fast algorithm which is the kernel of our parallel decoding method at the conference AAECC-12, Toulouse, France, June, 1997 ; published in Lecture Notes in Computer Science (LNSC), Vol.1255 (Eds.Mora et al.), Springer, 1997 ; (3) A method for efficient scheduling of the whole cells (processors) in implementing our parallel decoding algorithm with a systolic array architecture at the IEEE International Symposium on Information Theory, Ulm, Germany, July, 1997. For the codelength n, our method has time complexity of order O (n), which is better than O (n^2) obtained by [R.Kotter, A fast parallel implementation of a BM algoritm for AG codes, On Algebraic Decoding of AG Godes and Cyclic Codes, Dissertation, Linkoping Univ., (section) 3,1996]. In addition, we have proceeded to investigate several relevant themes such as a soft decision decoding method for correcting both erasures and errors, which can be parallelized (Part is contained in the paper published in LNSC-1255). A fast generalized minimum distance (GMD) decoding method was presented in the Allerton Conference on Communication, Control and Computation, Illinois, USA,September, 1997, and a lecture on the Berlekamp-Massey-Sakata algorithm was given at the special conference BlahutFest just before the Allerton Conference. A tutorial paper on Grobner bases and coding theory is published in Grobner Bases and Applications (Eds.Buchberger et al.), Cambridge Univ.Press, 1998., 08650424
1996 - 1997 - Fast Decodicng Method of Any One-Point Algebraic-Geometric Codes up to the Feng-Rao Bound
SAKATA Shojiro; KURIHARA Masazumi
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, University of Electro-Communications, Grant-in-Aid for General Scientific Research (C), We have established a fast decoding algorithm of any one-point algebraic-geometric (AG) code, which is defined on an arbitrary algebraic curve, up to the Feng-Rao designed distance. For the codelength n, our method has computational complexity of order O (n^<7/>) and of order less than O (n^3) to decode a one-point AG code defined on a Hermitian plane curve and on any algebraic curve of higher dimension, respectively, while the fundamental Feng-Rao method has complexity of order O (n^3). In regard to efficiency, out method is the best among all the known decoding methods of any one-point AG code. These results were presented in part at the 1994 IEEE Int. Symp. Inform. Theory, at the 1994 IEEE Int. Worshop Inform. Theory, and at some other conferences. The contents were published partially in Finite Fields and Their Applications, Vol.1,1995, and the main part will appear in the forthcoming Special Issue of IEEE Trans. Inform. Theory. The details of our theory were published in Bullet. Unv.Elect. -Comm., Vol.8,1995. In parallel to the above theoretical work, we made some computer experiment. We implemented a software system (C-program) for our decoding method, and by applying it to two kinds of codes defined on a Hermitian plane curve and on its three-dimensional extension, we investigated the actual efficiency of our method. As a result of simulation on many random error-patterns, it was shown that both the number of arithmetics over the finite field and the actual computing time have a tendency quite similar to the theoretical computational complexity, which gives an additional evidence to our theory and a guideline for practical use in future. Furthermore, it was made sure that our method can decode beyond the designed distance in some cases. On the other hand, we published a paper containing a general review on a broader class of AG codes in Bullet. Jap.Soc.Ind.Appl.Math., Vol.4,1994. In addition, we have proceeded to investigate parallel processor architecture for hardware implementation of our method and fast error-and-erasure decoding as extensions of the present research. Some results of the research were presented at the AAECC-11 Conference and at the 1995 IEEE Int.Symp.Inform.Theory, and in some other conferences., 06650412
1994 - 1995
