Coding in theoretical computer science
This thesis contains three topics, list decoding of rank-metric codes, local decoding of Reed-Muller codes and the design of tampering detection codes and its generalization non-malleable codes. The first two topics are the central problems in theoretical computer science and the last one has crypto...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | English |
| Published: |
2018
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/10356/73170 |
| _version_ | 1811690786717171712 |
|---|---|
| author | Chen, Yuan |
| author2 | Xing Chaoping |
| author_facet | Xing Chaoping Chen, Yuan |
| author_sort | Chen, Yuan |
| collection | NTU |
| description | This thesis contains three topics, list decoding of rank-metric codes, local decoding of Reed-Muller codes and the design of tampering detection codes and its generalization non-malleable codes. The first two topics are the central problems in theoretical computer science and the last one has cryptographic background. They are all focused on the design or decoding of codes with certain properties. In the first topic, we present an explicit construction of rank-metric codes with constant ratio. Such codes are list decoded beyond unique decoding radius which answers an open problem in~\cite{Guru2015}. The ratio of our rank-metric codes can reach $1/2$. Our construction can be seen as a step toward the list decoding of square rank metric codes. These results appear in Chapter 2. In Chapter 3, we further develop a combinatorial tool contributed to this issue, namely subspace design set. Our result can be treated as a generalization of the construction in~\cite{Guru2013B}. In the second topic, we design an local decoding algorithm of Reed-Muller codes based on algebraic geometry codes. The traditional local decoding algorithm of Reed-Muller codes are based on the line decoding, i.e., the decoding of Reed-Solomon codes. If we want to recover multiple points, we have to run this line decoding multiple rounds. To overcome this drawback, we propose a curve decoding via algebraic geometry codes. Our local decoding algorithm can recover as many points as possible in one round. Moreover, our algorithm outperforms the previous local decoding algorithm in both the error probability and query length. %Based on this local decoding algorithm, we present a local list-decoder of Reed-Muller codes. Our local list-decoder runs in sub-linear time in code length and list decode Reed-Muller codes up to the radius $1-\sqrt{\frac{2d}{q}}$. Our result improves the best known local list-decoder over large field~\cite{STV2001}. %All these results can be found in Chapter 4. In our last topic, we focus on the design of tampering detection codes or non-malleable codes resistant to large families of tampering function. Our first result answers the open problem in~\cite{CPX15} by constructing asymptotic optimal systematic Algebraic Manipulation Detection codes. Our second result yields optimal-rate tampering detection codes resistant to the family of linearized polynomials with certain degree. Both of the results are included in Chapter 5. In Chapter 6, we design a class of linear-time encoding and decoding non-malleable codes which is resistant to the family of bit-wise tampering and permutation functions. Our codes extend the non-malleable codes in~\cite{CDD16} which are only resistant to the family of bit-wise tampering functions. |
| first_indexed | 2024-10-01T06:09:32Z |
| format | Thesis |
| id | ntu-10356/73170 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T06:09:32Z |
| publishDate | 2018 |
| record_format | dspace |
| spelling | ntu-10356/731702023-02-28T23:48:37Z Coding in theoretical computer science Chen, Yuan Xing Chaoping School of Physical and Mathematical Sciences DRNTU::Science::Mathematics::Discrete mathematics::Cryptography DRNTU::Engineering::Computer science and engineering::Data::Coding and information theory DRNTU::Science::Mathematics::Discrete mathematics::Combinatorics This thesis contains three topics, list decoding of rank-metric codes, local decoding of Reed-Muller codes and the design of tampering detection codes and its generalization non-malleable codes. The first two topics are the central problems in theoretical computer science and the last one has cryptographic background. They are all focused on the design or decoding of codes with certain properties. In the first topic, we present an explicit construction of rank-metric codes with constant ratio. Such codes are list decoded beyond unique decoding radius which answers an open problem in~\cite{Guru2015}. The ratio of our rank-metric codes can reach $1/2$. Our construction can be seen as a step toward the list decoding of square rank metric codes. These results appear in Chapter 2. In Chapter 3, we further develop a combinatorial tool contributed to this issue, namely subspace design set. Our result can be treated as a generalization of the construction in~\cite{Guru2013B}. In the second topic, we design an local decoding algorithm of Reed-Muller codes based on algebraic geometry codes. The traditional local decoding algorithm of Reed-Muller codes are based on the line decoding, i.e., the decoding of Reed-Solomon codes. If we want to recover multiple points, we have to run this line decoding multiple rounds. To overcome this drawback, we propose a curve decoding via algebraic geometry codes. Our local decoding algorithm can recover as many points as possible in one round. Moreover, our algorithm outperforms the previous local decoding algorithm in both the error probability and query length. %Based on this local decoding algorithm, we present a local list-decoder of Reed-Muller codes. Our local list-decoder runs in sub-linear time in code length and list decode Reed-Muller codes up to the radius $1-\sqrt{\frac{2d}{q}}$. Our result improves the best known local list-decoder over large field~\cite{STV2001}. %All these results can be found in Chapter 4. In our last topic, we focus on the design of tampering detection codes or non-malleable codes resistant to large families of tampering function. Our first result answers the open problem in~\cite{CPX15} by constructing asymptotic optimal systematic Algebraic Manipulation Detection codes. Our second result yields optimal-rate tampering detection codes resistant to the family of linearized polynomials with certain degree. Both of the results are included in Chapter 5. In Chapter 6, we design a class of linear-time encoding and decoding non-malleable codes which is resistant to the family of bit-wise tampering and permutation functions. Our codes extend the non-malleable codes in~\cite{CDD16} which are only resistant to the family of bit-wise tampering functions. Doctor of Philosophy (SPMS) 2018-01-08T07:09:00Z 2018-01-08T07:09:00Z 2018 Thesis Chen, Y. (2018). Coding in theoretical computer science. Doctoral thesis, Nanyang Technological University, Singapore. http://hdl.handle.net/10356/73170 10.32657/10356/73170 en 152 p. application/pdf |
| spellingShingle | DRNTU::Science::Mathematics::Discrete mathematics::Cryptography DRNTU::Engineering::Computer science and engineering::Data::Coding and information theory DRNTU::Science::Mathematics::Discrete mathematics::Combinatorics Chen, Yuan Coding in theoretical computer science |
| title | Coding in theoretical computer science |
| title_full | Coding in theoretical computer science |
| title_fullStr | Coding in theoretical computer science |
| title_full_unstemmed | Coding in theoretical computer science |
| title_short | Coding in theoretical computer science |
| title_sort | coding in theoretical computer science |
| topic | DRNTU::Science::Mathematics::Discrete mathematics::Cryptography DRNTU::Engineering::Computer science and engineering::Data::Coding and information theory DRNTU::Science::Mathematics::Discrete mathematics::Combinatorics |
| url | http://hdl.handle.net/10356/73170 |
| work_keys_str_mv | AT chenyuan codingintheoreticalcomputerscience |