Showing 1–50 of 58 results for author: Matsumoto, R

Breeding protocols are advantageous for finite-length entanglement distillation

Authors: Ryutaroh Matsumoto

Abstract: Bennett et al. proposed a family of protocols for entanglement distillation, namely, hashing, recurrence and breeding protocols. The last one is inferior to the hashing protocol in the asymptotic regime and has been investigated little. In this paper, we propose a framework of converting a stabilizer quantum error-correcting code to a breeding protocol, which is a generalization of the previous co… ▽ More Bennett et al. proposed a family of protocols for entanglement distillation, namely, hashing, recurrence and breeding protocols. The last one is inferior to the hashing protocol in the asymptotic regime and has been investigated little. In this paper, we propose a framework of converting a stabilizer quantum error-correcting code to a breeding protocol, which is a generalization of the previous conversion methods by Luo-Devetak and Wilde. Then, show an example of a stabilizer that gives a breeding protocol better than hashing protocols, in which the finite number of maximally entangled pairs are distilled from the finite number of partially entangled pairs. △ Less

Submitted 1 February, 2024; v1 submitted 4 January, 2024; originally announced January 2024.

Comments: 9 pages, latex2e, no figure, 1 table, v2 added the two important citations (see the acknowledgment)

Steane enlargement of Entanglement-Assisted Quantum Error-Correcting Codes

Authors: Carlos Galindo, Fernando Hernando, Ryutaroh Matsumoto

Abstract: We introduce a Steane-like enlargement procedure for entanglement-assisted quantum error-correcting codes (EAQECCs) obtained by considering Euclidean inner product. We give formulae for the parameters of these enlarged codes and apply our results to explicitly compute the parameters of enlarged EAQECCs coming from some BCH codes. We introduce a Steane-like enlargement procedure for entanglement-assisted quantum error-correcting codes (EAQECCs) obtained by considering Euclidean inner product. We give formulae for the parameters of these enlarged codes and apply our results to explicitly compute the parameters of enlarged EAQECCs coming from some BCH codes. △ Less

Submitted 6 March, 2023; originally announced March 2023.

MSC Class: 81P73 94Bxx

Journal ref: Comp. Appl. Math. 42, 275 (2023)

Advance sharing of quantum shares for classical secrets

Authors: Rina Miyajima, Ryutaroh Matsumoto

Abstract: Secret sharing schemes for classical secrets can be classified into classical secret sharing schemes and quantum secret sharing schemes. Classical secret sharing has been known to be able to distribute some shares before a given secret. On the other hand, quantum mechanics extends the capabilities of secret sharing beyond those of classical secret sharing. We propose quantum secret sharing with th… ▽ More Secret sharing schemes for classical secrets can be classified into classical secret sharing schemes and quantum secret sharing schemes. Classical secret sharing has been known to be able to distribute some shares before a given secret. On the other hand, quantum mechanics extends the capabilities of secret sharing beyond those of classical secret sharing. We propose quantum secret sharing with the capabilities in designing of access structures more flexibly and realizing higher efficiency beyond those of classical secret sharing, that can distribute some shares before a given secret. △ Less

Submitted 17 September, 2022; v1 submitted 3 August, 2022; originally announced August 2022.

Comments: 11 pages, 1 figure, 1 table. Publisher's open access PDF. Results unchanged. This research was in part presented at QCrypt 2022, Taipei City, Taiwan, August 29-September 2, 2022

MSC Class: 94A62 (Primary) 81P94 (Secondary)

Journal ref: IEEE Access, vol.10, pp. 94458-94468, Sept. 2022

Explicit method to make shortened stabilizer EAQECC from stabilizer QECC

Authors: Daiki Ueno, Ryutaroh Matsumoto

Abstract: In the previous research by Grassl, Huber and Winter, they proved a theorem which can make entanglement-assisted quantum error-correcting codes (EAQECC) from general quantum error-correcting codes (QECC). In this paper, we prove that the shortened EAQECC is a stabilizer code if the original EAQECC is a stabilizer code. In the previous research by Grassl, Huber and Winter, they proved a theorem which can make entanglement-assisted quantum error-correcting codes (EAQECC) from general quantum error-correcting codes (QECC). In this paper, we prove that the shortened EAQECC is a stabilizer code if the original EAQECC is a stabilizer code. △ Less

Submitted 26 May, 2022; originally announced May 2022.

Comments: 5 pages, article.cls, no figure

Lee Weight for Nonbinary Quantum Error Correction

Authors: Ryutaroh Matsumoto

Abstract: We propose the quantum Lee weight for quantum errors, provide a Gilbert-Varshamov type bound, and a code construction for the proposed weight. We propose the quantum Lee weight for quantum errors, provide a Gilbert-Varshamov type bound, and a code construction for the proposed weight. △ Less

Submitted 26 May, 2021; originally announced May 2021.

Comments: LaTeX2e, 8 pages, 1 figure

Constructions of $\ell$-Adic $t$-Deletion-Correcting Quantum Codes

Authors: Ryutaroh Matsumoto, Manabu Hagiwara

Abstract: We propose two systematic constructions of deletion-correcting codes for protecting quantum information. The first one works with qudits of any dimension, but only one deletion is corrected and the constructed codes are asymptotically bad. The second one corrects multiple deletions and can construct asymptotically good codes. The second one also allows conversion of stabilizer-based quantum codes… ▽ More We propose two systematic constructions of deletion-correcting codes for protecting quantum information. The first one works with qudits of any dimension, but only one deletion is corrected and the constructed codes are asymptotically bad. The second one corrects multiple deletions and can construct asymptotically good codes. The second one also allows conversion of stabilizer-based quantum codes to deletion-correcting codes, and entanglement assistance. △ Less

Submitted 21 April, 2021; v1 submitted 8 February, 2021; originally announced February 2021.

Comments: LaTeX2e, 6 pages, no figure, version 2 only corrects typos

Journal ref: IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol.E105-A, no.3, pp.571-575, March 2022

Adversarial Patch Attacks on Monocular Depth Estimation Networks

Authors: Koichiro Yamanaka, Ryutaroh Matsumoto, Keita Takahashi, Toshiaki Fujii

Abstract: Thanks to the excellent learning capability of deep convolutional neural networks (CNN), monocular depth estimation using CNNs has achieved great success in recent years. However, depth estimation from a monocular image alone is essentially an ill-posed problem, and thus, it seems that this approach would have inherent vulnerabilities. To reveal this limitation, we propose a method of adversarial… ▽ More Thanks to the excellent learning capability of deep convolutional neural networks (CNN), monocular depth estimation using CNNs has achieved great success in recent years. However, depth estimation from a monocular image alone is essentially an ill-posed problem, and thus, it seems that this approach would have inherent vulnerabilities. To reveal this limitation, we propose a method of adversarial patch attack on monocular depth estimation. More specifically, we generate artificial patterns (adversarial patches) that can fool the target methods into estimating an incorrect depth for the regions where the patterns are placed. Our method can be implemented in the real world by physically placing the printed patterns in real scenes. We also analyze the behavior of monocular depth estimation under attacks by visualizing the activation levels of the intermediate layers and the regions potentially affected by the adversarial attack. △ Less

Submitted 6 October, 2020; originally announced October 2020.

Comments: Publisher's Open Access PDF with the CC-BY copyright. Associated video, data and programs are available at https://www.fujii.nuee.nagoya-u.ac.jp/Research/MonoDepth/

ACM Class: I.4.8

Journal ref: IEEE Access, vol.8, pp.179094-179104, October 2020

Machine Learning Guided Discovery of Gigantic Magnetocaloric Effect in HoB$_{2}$ Near Hydrogen Liquefaction Temperature

Authors: Pedro Baptista de Castro, Kensei Terashima, Takafumi D Yamamoto, Zhufeng Hou, Suguru Iwasaki, Ryo Matsumoto, Shintaro Adachi, Yoshito Saito, Peng Song, Hiroyuki Takeya, Yoshihiko Takano

Abstract: Magnetic refrigeration exploits the magnetocaloric effect which is the entropy change upon application and removal of magnetic fields in materials, providing an alternate path for refrigeration other than the conventional gas cycles. While intensive research has uncovered a vast number of magnetic materials which exhibits large magnetocaloric effect, these properties for a large number of compound… ▽ More Magnetic refrigeration exploits the magnetocaloric effect which is the entropy change upon application and removal of magnetic fields in materials, providing an alternate path for refrigeration other than the conventional gas cycles. While intensive research has uncovered a vast number of magnetic materials which exhibits large magnetocaloric effect, these properties for a large number of compounds still remain unknown. To explore new functional materials in this unknown space, machine learning is used as a guide for selecting materials which could exhibit large magnetocaloric effect. By this approach, HoB$_{2}$ is singled out, synthesized and its magnetocaloric properties are evaluated, leading to the experimental discovery of gigantic magnetic entropy change 40.1 J kg$^{-1}$ K$^{-1}$ (0.35 J cm$^{-3}$ K$^{-1}$) for a field change of 5 T in the vicinity of a ferromagnetic second-order phase transition with a Curie temperature of 15 K. This is the highest value reported so far, to our knowledge, near the hydrogen liquefaction temperature thus it is a highly suitable material for hydrogen liquefaction and low temperature magnetic cooling applications. △ Less

Submitted 12 May, 2020; originally announced May 2020.

Comments: 12 pages including 3 figures and 1 table + 11 pages of supplementary information. Published version available at: https://rdcu.be/b36ep

Journal ref: NPG Asia Materials 12:35 (2020)

Improved Gilbert-Varshamov Bound for Entanglement-Assisted Asymmetric Quantum Error Correction by Symplectic Orthogonality

Authors: Ryutaroh Matsumoto

Abstract: We propose and prove an existential theorem for entanglement-assisted asymmetric quantum error correction. Then we demonstrate its superiority over the conventional one. We propose and prove an existential theorem for entanglement-assisted asymmetric quantum error correction. Then we demonstrate its superiority over the conventional one. △ Less

Submitted 20 May, 2020; v1 submitted 2 March, 2020; originally announced March 2020.

Comments: Publisher's Open Access PDF

MSC Class: 81P73 94B65

Journal ref: IEEE Transactions on Quantum Engineering, vol. 1, Art no. 4100604, 2020

Asymmetric entanglement-assisted quantum error-correcting codes and BCH codes

Authors: Carlos Galindo, Fernando Hernando, Ryutaroh Matsumoto, Diego Ruano

Abstract: The concept of asymmetric entanglement-assisted quantum error-correcting code (asymmetric EAQECC) is introduced in this article. Codes of this type take advantage of the asymmetry in quantum errors since phase-shift errors are more probable than qudit-flip errors. Moreover, they use pre-shared entanglement between encoder and decoder to simplify the theory of quantum error correction and increase… ▽ More The concept of asymmetric entanglement-assisted quantum error-correcting code (asymmetric EAQECC) is introduced in this article. Codes of this type take advantage of the asymmetry in quantum errors since phase-shift errors are more probable than qudit-flip errors. Moreover, they use pre-shared entanglement between encoder and decoder to simplify the theory of quantum error correction and increase the communication capacity. Thus, asymmetric EAQECCs can be constructed from any pair of classical linear codes over an arbitrary field. Their parameters are described and a Gilbert-Varshamov bound is presented. Explicit parameters of asymmetric EAQECCs from BCH codes are computed and examples exceeding the introduced Gilbert-Varshamov bound are shown. △ Less

Submitted 14 January, 2020; v1 submitted 22 November, 2019; originally announced November 2019.

MSC Class: 81P70 (Primary); 94B65; 94B05 (Secondary)

Journal ref: IEEE Access, vol.8, pp.18571-18579, January 2020

Message Randomization and Strong Security in Quantum Stabilizer-Based Secret Sharing for Classical Secrets

Authors: Ryutaroh Matsumoto

Abstract: We improve the flexibility in designing access structures of quantum stabilizer-based secret sharing schemes for classical secrets, by introducing message randomization in their encoding procedures. We generalize the Gilbert-Varshamov bound for deterministic encoding to randomized encoding of classical secrets. We also provide an explicit example of a ramp secret sharing scheme with which multiple… ▽ More We improve the flexibility in designing access structures of quantum stabilizer-based secret sharing schemes for classical secrets, by introducing message randomization in their encoding procedures. We generalize the Gilbert-Varshamov bound for deterministic encoding to randomized encoding of classical secrets. We also provide an explicit example of a ramp secret sharing scheme with which multiple symbols in its classical secret are revealed to an intermediate set, and justify the necessity of incorporating strong security criterion of conventional secret sharing. Finally, we propose an explicit construction of strongly secure ramp secret sharing scheme by quantum stabilizers, which can support twice as large classical secrets as the McEliece-Sarwate strongly secure ramp secret sharing scheme of the same share size and the access structure. △ Less

Submitted 13 September, 2020; v1 submitted 24 April, 2019; originally announced April 2019.

Comments: Publisher's Open Access PDF. arXiv admin note: text overlap with arXiv:1811.05217

MSC Class: 94A62 81P70 94B65

Journal ref: Designs, Codes and Cryptography, vol.88, no.9, pp.1893-1907, Sept. 2020

Rate-Distortion-Perception Tradeoff of Variable-Length Source Coding for General Information Sources

Authors: Ryutaroh Matsumoto

Abstract: Blau and Michaeli recently introduced a novel concept for inverse problems of signal processing, that is, the perception-distortion tradeoff. We introduce their tradeoff into the rate distortion theory of variable-length lossy source coding in information theory, and clarify the tradeoff among information rate, distortion and perception for general information sources. We also discuss the fixed-le… ▽ More Blau and Michaeli recently introduced a novel concept for inverse problems of signal processing, that is, the perception-distortion tradeoff. We introduce their tradeoff into the rate distortion theory of variable-length lossy source coding in information theory, and clarify the tradeoff among information rate, distortion and perception for general information sources. We also discuss the fixed-length coding with average distortion criterion that was missing in the previous letter. △ Less

Submitted 30 November, 2018; originally announced December 2018.

Comments: comex.cls, 5 pages, no figure. This is a continuation of the previous letter arXiv:1808.07986

Journal ref: IEICE Communications Express, vol.8, no.2, pp.38-42, Feb. 2019

Entanglement-assisted quantum error-correcting codes over arbitrary finite fields

Authors: Carlos Galindo, Fernando Hernando, Ryutaroh Matsumoto, Diego Ruano

Abstract: We prove that the known formulae for computing the optimal number of maximally entangled pairs required for entanglement-assisted quantum error-correcting codes (EAQECCs) over the binary field hold for codes over arbitrary finite fields as well. We also give a Gilbert-Varshamov bound for EAQECCs and constructions of EAQECCs coming from punctured self-orthogonal linear codes which are valid for any… ▽ More We prove that the known formulae for computing the optimal number of maximally entangled pairs required for entanglement-assisted quantum error-correcting codes (EAQECCs) over the binary field hold for codes over arbitrary finite fields as well. We also give a Gilbert-Varshamov bound for EAQECCs and constructions of EAQECCs coming from punctured self-orthogonal linear codes which are valid for any finite field. △ Less

Submitted 27 January, 2021; v1 submitted 13 December, 2018; originally announced December 2018.

MSC Class: 81P70; 94B65; 94B05

Journal ref: Quantum Information Processing, vol.18, article ID 116, April 2019

Classical Access Structures of Ramp Secret Sharing Based on Quantum Stabilizer Codes

Authors: Ryutaroh Matsumoto

Abstract: In this paper we consider to use the quantum stabilizer codes as secret sharing schemes for classical secrets. We give necessary and sufficient conditions for qualified and forbidden sets in terms of quantum stabilizers. Then we give a Gilbert-Varshamove-type sufficient condition for existence of secret sharing schemes with given parameters, and by using that sufficient condition, we show that rou… ▽ More In this paper we consider to use the quantum stabilizer codes as secret sharing schemes for classical secrets. We give necessary and sufficient conditions for qualified and forbidden sets in terms of quantum stabilizers. Then we give a Gilbert-Varshamove-type sufficient condition for existence of secret sharing schemes with given parameters, and by using that sufficient condition, we show that roughly 19% of participants can be made forbidden independently of the size of classical secret, in particular when an $n$-bit classical secret is shared among $n$ participants having 1-qubit share each. We also consider how much information is obtained by an intermediate set and express that amount of information in terms of quantum stabilizers. All the results are stated in terms of linear spaces over finite fields associated with the quantum stabilizers. △ Less

Submitted 26 November, 2019; v1 submitted 13 November, 2018; originally announced November 2018.

Comments: Publisher's Open Access PDF with copyright held by the author

Journal ref: Quantum Information Processing, vol.19, no.1, article ID 9, January 2020

Introducing the Perception-Distortion Tradeoff into the Rate-Distortion Theory of General Information Sources

Authors: Ryutaroh Matsumoto

Abstract: Blau and Michaeli recently introduced a novel concept for inverse problems of signal processing, that is, the perception-distortion tradeoff. We introduce their tradeoff into the rate distortion theory of lossy source coding in information theory, and clarify the tradeoff among information rate, distortion and perception for general information sources. Blau and Michaeli recently introduced a novel concept for inverse problems of signal processing, that is, the perception-distortion tradeoff. We introduce their tradeoff into the rate distortion theory of lossy source coding in information theory, and clarify the tradeoff among information rate, distortion and perception for general information sources. △ Less

Submitted 23 August, 2018; originally announced August 2018.

Comments: comex.cls, 5 pages, no figure. Accepted for publication in IEICE Communications Express. Article DOI has not been activated as of 24 August 2018. The author was given the right to upload this manuscript to arxiv.org as stated at the footnote 2 in page 13 of http://www.ieice.org/eng/copyright/files/copyright.pdf

Journal ref: IEICE Communications Express, vol.7, no.11, pp.427-431, Nov. 2018

Exploring Quantum Supremacy in Access Structures of Secret Sharing by Coding Theory

Authors: Ryutaroh Matsumoto

Abstract: We consider secret sharing schemes with a classical secret and quantum shares. One example of such schemes was recently reported whose access structure cannot be realized by any secret sharing schemes with classical shares. In this paper, we report further quantum secret sharing schemes whose access structures cannot be realized by any classical secret sharing schemes. We consider secret sharing schemes with a classical secret and quantum shares. One example of such schemes was recently reported whose access structure cannot be realized by any secret sharing schemes with classical shares. In this paper, we report further quantum secret sharing schemes whose access structures cannot be realized by any classical secret sharing schemes. △ Less

Submitted 27 March, 2018; originally announced March 2018.

Comments: IEEEtran.cls, 3 pages, no figure

Journal ref: Proceedings of 2018 International Symposium on Information Theory and Its Applications, pp. 331-333, October 28-31, 2018, Singapore

Quasi-Cyclic Constructions of Quantum Codes

Authors: Carlos Galindo, Fernando Hernando, Ryutaroh Matsumoto

Abstract: We give sufficient conditions for self-orthogonality with respect to symplectic, Euclidean and Hermitian inner products of a wide family of quasi-cyclic codes of index two. We provide lower bounds for the symplectic weight and the minimum distance of the involved codes. Supported in the previous results, we show algebraic constructions of good quantum codes and determine their parameters. We give sufficient conditions for self-orthogonality with respect to symplectic, Euclidean and Hermitian inner products of a wide family of quasi-cyclic codes of index two. We provide lower bounds for the symplectic weight and the minimum distance of the involved codes. Supported in the previous results, we show algebraic constructions of good quantum codes and determine their parameters. △ Less

Submitted 19 December, 2017; originally announced December 2017.

MSC Class: 94B65; 94B15; 81P70

Journal ref: Finite Fields and Their Applications, vol.52, pp.261-280, July 2018

Two Gilbert-Varshamov Type Existential Bounds for Asymmetric Quantum Error-Correcting Codes

Authors: Ryutaroh Matsumoto

Abstract: In this note we report two versions of Gilbert-Varshamov type existential bounds for asymmetric quantum error-correcting codes. In this note we report two versions of Gilbert-Varshamov type existential bounds for asymmetric quantum error-correcting codes. △ Less

Submitted 19 October, 2017; v1 submitted 11 May, 2017; originally announced May 2017.

Comments: To be published in Quantum Information Processing. svjour3.cls, 6 pages, no figure

MSC Class: 94B65

Journal ref: Quantum Information Processing, vol.16, article 285, 2017

Quantum Optimal Multiple Assignment Scheme for Realizing General Access Structure of Secret Sharing

Authors: Ryutaroh Matsumoto

Abstract: The multiple assignment scheme is to assign one or more shares to single participant so that any kind of access structure can be realized by classical secret sharing schemes. We propose its quantum version including ramp secret sharing schemes. Then we propose an integer optimization approach to minimize the average share size. The multiple assignment scheme is to assign one or more shares to single participant so that any kind of access structure can be realized by classical secret sharing schemes. We propose its quantum version including ramp secret sharing schemes. Then we propose an integer optimization approach to minimize the average share size. △ Less

Submitted 3 February, 2017; originally announced February 2017.

Comments: ieice.cls, 3 pages, no figure

Journal ref: IEICE Trans. Fundamentals, vol. E100-A, no. 2, pp. 726-728 (Feb. 2017)

Quantum Stabilizer Codes Can Realize Access Structures Impossible by Classical Secret Sharing

Authors: Ryutaroh Matsumoto

Abstract: We show a simple example of a secret sharing scheme encoding classical secret to quantum shares that can realize an access structure impossible by classical information processing with limitation on the size of each share. The example is based on quantum stabilizer codes. We show a simple example of a secret sharing scheme encoding classical secret to quantum shares that can realize an access structure impossible by classical information processing with limitation on the size of each share. The example is based on quantum stabilizer codes. △ Less

Submitted 11 January, 2017; originally announced January 2017.

Comments: LaTeX2e, 5 pages, no figure. Comments from readers are welcome

Journal ref: IEICE Trans. Fundamentals, vol.E100-A, no.12, pp. 2738-2739, Dec. 2017

Unitary Reconstruction of Secret for Stabilizer Based Quantum Secret Sharing

Authors: Ryutaroh Matsumoto

Abstract: We propose a unitary procedure to reconstruct quantum secret for a quantum secret sharing scheme constructed from stabilizer quantum error-correcting codes. Erasure correcting procedures for stabilizer codes need to add missing shares for reconstruction of quantum secret while unitary reconstruction procedures for certain class of quantum secret sharing are known to work without adding missing sha… ▽ More We propose a unitary procedure to reconstruct quantum secret for a quantum secret sharing scheme constructed from stabilizer quantum error-correcting codes. Erasure correcting procedures for stabilizer codes need to add missing shares for reconstruction of quantum secret while unitary reconstruction procedures for certain class of quantum secret sharing are known to work without adding missing shares. The proposed procedure also works without adding missing shares. △ Less

Submitted 5 July, 2017; v1 submitted 8 January, 2017; originally announced January 2017.

Comments: svjour3.cls, 8 pages, no figure. To be published in Quantum Information Processing

MSC Class: 81P94; 94A62 ACM Class: E.3

Journal ref: Quantum Information Processing, vol.16, no.8, article 202, August 2017

Relative generalized matrix weights of matrix codes for universal security on wire-tap networks

Authors: Umberto Martínez-Peñas, Ryutaroh Matsumoto

Abstract: Universal security over a network with linear network coding has been intensively studied. However, previous linear codes and code pairs used for this purpose were linear over a larger field than that used on the network, which restricts the possible packet lengths of optimal universal secure codes, does not allow to apply known list-decodable rank-metric codes and requires performing operations o… ▽ More Universal security over a network with linear network coding has been intensively studied. However, previous linear codes and code pairs used for this purpose were linear over a larger field than that used on the network, which restricts the possible packet lengths of optimal universal secure codes, does not allow to apply known list-decodable rank-metric codes and requires performing operations over a large field. In this work, we introduce new parameters (relative generalized matrix weights and relative dimension/rank support profile) for code pairs that are linear over the field used in the network, and show that they measure the universal security performance of these code pairs. For one code and non-square matrices, generalized matrix weights coincide with the existing Delsarte generalized weights, hence we prove the connection between these latter weights and secure network coding, which was left open. As main applications, the proposed new parameters enable us to: 1) Obtain optimal universal secure linear codes on noiseless networks for all possible packet lengths, in particular for packet lengths not considered before, 2) Obtain the first universal secure list-decodable rank-metric code pairs with polynomial-sized lists, based on a recent construction by Guruswami et al, and 3) Obtain new characterizations of security equivalences of linear codes. Finally, we show that our parameters extend relative generalized Hamming weights and relative dimension/length profile, respectively, and relative generalized rank weights and relative dimension/intersection profile, respectively. △ Less

Submitted 25 August, 2017; v1 submitted 6 December, 2016; originally announced December 2016.

Comments: 21 pages, LaTeX; Parts of this manuscript have been presented at the 54th Annual Allerton Conference on Communication, Control, and Computing, Monticello, IL, USA, 2016. Conference version available at arXiv:1607.01263

MSC Class: 15A03; 15B33; 94B05; 94C99

Journal ref: IEEE Trans. Inform. Theory, vol.64, no.4, pp.2529-2549, Apr. 2018

Unifying notions of generalized weights for universal security on wire-tap networks

Authors: Umberto Martínez-Peñas, Ryutaroh Matsumoto

Abstract: Universal security over a network with linear network coding has been intensively studied. However, previous linear codes used for this purpose were linear over a larger field than that used on the network. In this work, we introduce new parameters (relative dimension/rank support profile and relative generalized matrix weights) for linear codes that are linear over the field used in the network,… ▽ More Universal security over a network with linear network coding has been intensively studied. However, previous linear codes used for this purpose were linear over a larger field than that used on the network. In this work, we introduce new parameters (relative dimension/rank support profile and relative generalized matrix weights) for linear codes that are linear over the field used in the network, measuring the universal security performance of these codes. The proposed new parameters enable us to use optimally universal secure linear codes on noiseless networks for all possible parameters, as opposed to previous works, and also enable us to add universal security to the recently proposed list-decodable rank-metric codes by Guruswami et al. We give several properties of the new parameters: monotonicity, Singleton-type lower and upper bounds, a duality theorem, and definitions and characterizations of equivalences of linear codes. Finally, we show that our parameters strictly extend relative dimension/length profile and relative generalized Hamming weights, respectively, and relative dimension/intersection profile and relative generalized rank weights, respectively. Moreover, we show that generalized matrix weights are larger than Delsarte generalized weights. △ Less

Submitted 5 December, 2016; v1 submitted 5 July, 2016; originally announced July 2016.

Comments: 8 pages, LaTeX; the current version will appear in the Proceedings of the 54th Annual Allerton Conference on Communication, Control, and Computing, Monticello, IL, USA, 2016

MSC Class: 15A03; 15B33; 94B05; 94C99

Journal ref: Proc. 2016 54th Annual Allerton Conference on Communication, Control, and Computing, pp.800-807, Monticello, Illinois, USA, September 27-30, 2016

Key Rate of the B92 Quantum Key Distribution Protocol with Finite Qubits

Authors: Hiroaki Sasaki, Ryutaroh Matsumoto, Tomohiko Uyematsu

Abstract: The key rate of the B92 quantum key distribution protocol had not been reported before this research when the number of qubits is finite. We compute it by using the security analysis framework proposed by Scarani and Renner in 2008. The key rate of the B92 quantum key distribution protocol had not been reported before this research when the number of qubits is finite. We compute it by using the security analysis framework proposed by Scarani and Renner in 2008. △ Less

Submitted 21 April, 2015; originally announced April 2015.

Comments: 4 pages, 2 figures, IEEEtran.cls. Some overlap with arXiv:1301.5083. Accepted for presentation in 2015 IEEE International Symposium on Information Theory, Hong Kong, June 14-19, 2015

On asymptotically good ramp secret sharing schemes

Authors: Olav Geil, Stefano Martin, Umberto Martínez-Peñas, Ryutaroh Matsumoto, Diego Ruano

Abstract: Asymptotically good sequences of linear ramp secret sharing schemes have been intensively studied by Cramer et al. in terms of sequences of pairs of nested algebraic geometric codes. In those works the focus is on full privacy and full reconstruction. In this paper we analyze additional parameters describing the asymptotic behavior of partial information leakage and possibly also partial reconstru… ▽ More Asymptotically good sequences of linear ramp secret sharing schemes have been intensively studied by Cramer et al. in terms of sequences of pairs of nested algebraic geometric codes. In those works the focus is on full privacy and full reconstruction. In this paper we analyze additional parameters describing the asymptotic behavior of partial information leakage and possibly also partial reconstruction giving a more complete picture of the access structure for sequences of linear ramp secret sharing schemes. Our study involves a detailed treatment of the (relative) generalized Hamming weights of the considered codes. △ Less

Submitted 2 February, 2017; v1 submitted 19 February, 2015; originally announced February 2015.

MSC Class: 94A62; 94B27; 94B65

Journal ref: IEICE Trans. Fundamentals. vol. E100-A, no. 12, pages 2699-2708 (2017)

Strongly Secure Quantum Ramp Secret Sharing Constructed from Algebraic Curves over Finite Fields

Authors: Ryutaroh Matsumoto

Abstract: The first construction of strongly secure quantum ramp secret sharing by Zhang and Matsumoto had an undesirable feature that the dimension of quantum shares must be larger than the number of shares. By using algebraic curves over finite fields, we propose a new construction in which the number of shares can become arbitrarily large for fixed dimension of shares. The first construction of strongly secure quantum ramp secret sharing by Zhang and Matsumoto had an undesirable feature that the dimension of quantum shares must be larger than the number of shares. By using algebraic curves over finite fields, we propose a new construction in which the number of shares can become arbitrarily large for fixed dimension of shares. △ Less

Submitted 19 October, 2014; originally announced October 2014.

Comments: svjour3.cls, 8 pages, no figure

MSC Class: 81P94 (Primary) 94A62; 94B27 (Secondary)

Journal ref: Advances in Mathematics of Communications, vol. 13, no. 1, pp. 1-10, February 2019

Coding Theoretic Construction of Quantum Ramp Secret Sharing

Authors: Ryutaroh Matsumoto

Abstract: We show a construction of a quantum ramp secret sharing scheme from a nested pair of linear codes. Necessary and sufficient conditions for qualified sets and forbidden sets are given in terms of combinatorial properties of nested linear codes. An algebraic geometric construction for quantum secret sharing is also given. We show a construction of a quantum ramp secret sharing scheme from a nested pair of linear codes. Necessary and sufficient conditions for qualified sets and forbidden sets are given in terms of combinatorial properties of nested linear codes. An algebraic geometric construction for quantum secret sharing is also given. △ Less

Submitted 20 December, 2014; v1 submitted 1 May, 2014; originally announced May 2014.

Comments: svjour3.cls, 12 pages, no figure. Version 5 added citations to relevant prior papers that were missing in previous versions. Contents unchanged

MSC Class: 81P94 (Primary) 94A62; 94B27 (Secondary) ACM Class: E.3

Journal ref: IEICE Trans. Fundamentals, vol.E101-A, no.8, pp.1215-1222, Aug. 2018

New Asymptotic Metrics for Relative Generalized Hamming Weight

Authors: Ryutaroh Matsumoto

Abstract: It was recently shown that RGHW (relative generalized Hamming weight) exactly expresses the security of linear ramp secret sharing scheme. In this paper we determine the true value of the asymptotic metric for RGHW previously proposed by Zhuang et al. in 2013. Then we propose new asymptotic metrics useful for investigating the optimal performance of linear ramp secret sharing scheme constructed fr… ▽ More It was recently shown that RGHW (relative generalized Hamming weight) exactly expresses the security of linear ramp secret sharing scheme. In this paper we determine the true value of the asymptotic metric for RGHW previously proposed by Zhuang et al. in 2013. Then we propose new asymptotic metrics useful for investigating the optimal performance of linear ramp secret sharing scheme constructed from a pair of linear codes. We also determine the true values of the proposed metrics in many cases. △ Less

Submitted 1 April, 2014; originally announced April 2014.

Comments: 3 pages, 1 figure, IEEEtran.cls. To be presented at 2014 IEEE International Symposium on Information Theory, June 29-July 4, 2014 Hawai'i Convention Center, Honolulu, HI, USA

MSC Class: 94B65

Journal ref: Proc. 2014 IEEE International Symposium on Information Theory, pp. 3142-3144

Relative generalized Hamming weights of one-point algebraic geometric codes

Authors: Olav Geil, Stefano Martin, Ryutaroh Matsumoto, Diego Ruano, Yuan Luo

Abstract: Security of linear ramp secret sharing schemes can be characterized by the relative generalized Hamming weights of the involved codes. In this paper we elaborate on the implication of these parameters and we devise a method to estimate their value for general one-point algebraic geometric codes. As it is demonstrated, for Hermitian codes our bound is often tight. Furthermore, for these codes the r… ▽ More Security of linear ramp secret sharing schemes can be characterized by the relative generalized Hamming weights of the involved codes. In this paper we elaborate on the implication of these parameters and we devise a method to estimate their value for general one-point algebraic geometric codes. As it is demonstrated, for Hermitian codes our bound is often tight. Furthermore, for these codes the relative generalized Hamming weights are often much larger than the corresponding generalized Hamming weights. △ Less

Submitted 24 July, 2014; v1 submitted 31 March, 2014; originally announced March 2014.

Journal ref: IEEE Transactions on Information Theory, vol. 60, no. 10, pp. 5938-5949, October 2014

Relative Generalized Rank Weight of Linear Codes and Its Applications to Network Coding

Authors: Jun Kurihara, Ryutaroh Matsumoto, Tomohiko Uyematsu

Abstract: By extending the notion of minimum rank distance, this paper introduces two new relative code parameters of a linear code C_1 of length n over a field extension and its subcode C_2. One is called the relative dimension/intersection profile (RDIP), and the other is called the relative generalized rank weight (RGRW). We clarify their basic properties and the relation between the RGRW and the minimum… ▽ More By extending the notion of minimum rank distance, this paper introduces two new relative code parameters of a linear code C_1 of length n over a field extension and its subcode C_2. One is called the relative dimension/intersection profile (RDIP), and the other is called the relative generalized rank weight (RGRW). We clarify their basic properties and the relation between the RGRW and the minimum rank distance. As applications of the RDIP and the RGRW, the security performance and the error correction capability of secure network coding, guaranteed independently of the underlying network code, are analyzed and clarified. We propose a construction of secure network coding scheme, and analyze its security performance and error correction capability as an example of applications of the RDIP and the RGRW. Silva and Kschischang showed the existence of a secure network coding in which no part of the secret message is revealed to the adversary even if any dim C_1-1 links are wiretapped, which is guaranteed over any underlying network code. However, the explicit construction of such a scheme remained an open problem. Our new construction is just one instance of secure network coding that solves this open problem. △ Less

Submitted 14 May, 2015; v1 submitted 23 January, 2013; originally announced January 2013.

Comments: IEEEtran.cls, 25 pages, no figure, accepted for publication in IEEE Transactions on Information Theory

Improved Asymptotic Key Rate of the B92 Protocol

Authors: Ryutaroh Matsumoto

Abstract: We analyze the asymptotic key rate of the single photon B92 protocol by using Renner's security analysis given in 2005. The new analysis shows that the B92 protocol can securely generate key at 6.5% depolarizing rate, while the previous analyses cannot guarantee the secure key generation at 4.2% depolarizing rate. We analyze the asymptotic key rate of the single photon B92 protocol by using Renner's security analysis given in 2005. The new analysis shows that the B92 protocol can securely generate key at 6.5% depolarizing rate, while the previous analyses cannot guarantee the secure key generation at 4.2% depolarizing rate. △ Less

Submitted 22 January, 2013; originally announced January 2013.

Comments: IEEEtran.sty, 3 pages, 1 figure. Submitted to IEEE ISIT 2013

Journal ref: Proc. 2013 IEEE International Symposium on Information Theory, pp. 351-353

Feng-Rao decoding of primary codes

Authors: Olav Geil, Ryutaroh Matsumoto, Diego Ruano

Abstract: We show that the Feng-Rao bound for dual codes and a similar bound by Andersen and Geil [H.E. Andersen and O. Geil, Evaluation codes from order domain theory, Finite Fields Appl., 14 (2008), pp. 92-123] for primary codes are consequences of each other. This implies that the Feng-Rao decoding algorithm can be applied to decode primary codes up to half their designed minimum distance. The technique… ▽ More We show that the Feng-Rao bound for dual codes and a similar bound by Andersen and Geil [H.E. Andersen and O. Geil, Evaluation codes from order domain theory, Finite Fields Appl., 14 (2008), pp. 92-123] for primary codes are consequences of each other. This implies that the Feng-Rao decoding algorithm can be applied to decode primary codes up to half their designed minimum distance. The technique applies to any linear code for which information on well-behaving pairs is available. Consequently we are able to decode efficiently a large class of codes for which no non-trivial decoding algorithm was previously known. Among those are important families of multivariate polynomial codes. Matsumoto and Miura in [R. Matsumoto and S. Miura, On the Feng-Rao bound for the L-construction of algebraic geometry codes, IEICE Trans. Fundamentals, E83-A (2000), pp. 926-930] (See also [P. Beelen and T. Høholdt, The decoding of algebraic geometry codes, in Advances in algebraic geometry codes, pp. 49-98]) derived from the Feng-Rao bound a bound for primary one-point algebraic geometric codes and showed how to decode up to what is guaranteed by their bound. The exposition by Matsumoto and Miura requires the use of differentials which was not needed in [Andersen and Geil 2008]. Nevertheless we demonstrate a very strong connection between Matsumoto and Miura's bound and Andersen and Geil's bound when applied to primary one-point algebraic geometric codes. △ Less

Submitted 31 October, 2012; v1 submitted 24 October, 2012; originally announced October 2012.

Comments: elsarticle.cls, 23 pages, no figure. Version 3 added citations to the works by I.M. Duursma and R. Pellikaan

MSC Class: 94B65 (Primary) 94B35 (Secondary)

Journal ref: Finite Fields and Their Applications, vol. 23, pp. 35-52, September 2013

New Parameters of Linear Codes Expressing Security Performance of Universal Secure Network Coding

Authors: Jun Kurihara, Tomohiko Uyematsu, Ryutaroh Matsumoto

Abstract: The universal secure network coding presented by Silva et al. realizes secure and reliable transmission of a secret message over any underlying network code, by using maximum rank distance codes. Inspired by their result, this paper considers the secure network coding based on arbitrary linear codes, and investigates its security performance and error correction capability that are guaranteed inde… ▽ More The universal secure network coding presented by Silva et al. realizes secure and reliable transmission of a secret message over any underlying network code, by using maximum rank distance codes. Inspired by their result, this paper considers the secure network coding based on arbitrary linear codes, and investigates its security performance and error correction capability that are guaranteed independently of the underlying network code. The security performance and error correction capability are said to be universal when they are independent of underlying network codes. This paper introduces new code parameters, the relative dimension/intersection profile (RDIP) and the relative generalized rank weight (RGRW) of linear codes. We reveal that the universal security performance and universal error correction capability of secure network coding are expressed in terms of the RDIP and RGRW of linear codes. The security and error correction of existing schemes are also analyzed as applications of the RDIP and RGRW. △ Less

Submitted 29 September, 2012; v1 submitted 8 July, 2012; originally announced July 2012.

Comments: IEEEtran.cls, 8 pages, no figure. To appear in Proc. 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton 2012). Version 2 added an exact expression of the universal error correction capability in terms of the relative generalized rank weight

Journal ref: Proceedings of 2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp.533 -- 540, 1--5 Oct. 2012

Generalization of the Lee-O'Sullivan List Decoding for One-Point AG Codes

Authors: Ryutaroh Matsumoto, Diego Ruano, Olav Geil

Abstract: We generalize the list decoding algorithm for Hermitian codes proposed by Lee and O'Sullivan based on Gröbner bases to general one-point AG codes, under an assumption weaker than one used by Beelen and Brander. Our generalization enables us to apply the fast algorithm to compute a Gröbner basis of a module proposed by Lee and O'Sullivan, which was not possible in another generalization by Lax. We generalize the list decoding algorithm for Hermitian codes proposed by Lee and O'Sullivan based on Gröbner bases to general one-point AG codes, under an assumption weaker than one used by Beelen and Brander. Our generalization enables us to apply the fast algorithm to compute a Gröbner basis of a module proposed by Lee and O'Sullivan, which was not possible in another generalization by Lax. △ Less

Submitted 7 March, 2013; v1 submitted 27 March, 2012; originally announced March 2012.

Comments: article.cls, 14 pages, no figure. The order of authors was changed. To appear in Journal of Symbolic Computation. This is an extended journal paper version of our earlier conference paper arXiv:1201.6248

MSC Class: 94B35 (Primary) 13P10; 94B27; 14G50 (Secondary) ACM Class: E.4; F.2.1; I.1.2; I.1.4

Journal ref: Journal of Symbolic Computation, vol. 55, pp. 1-9, August 2013

List Decoding Algorithm based on Voting in Groebner Bases for General One-Point AG Codes

Authors: Ryutaroh Matsumoto, Diego Ruano, Olav Geil

Abstract: We generalize the unique decoding algorithm for one-point AG codes over the Miura-Kamiya Cab curves proposed by Lee, Bras-Amorós and O'Sullivan (2012) to general one-point AG codes, without any assumption. We also extend their unique decoding algorithm to list decoding, modify it so that it can be used with the Feng-Rao improved code construction, prove equality between its error correcting capabi… ▽ More We generalize the unique decoding algorithm for one-point AG codes over the Miura-Kamiya Cab curves proposed by Lee, Bras-Amorós and O'Sullivan (2012) to general one-point AG codes, without any assumption. We also extend their unique decoding algorithm to list decoding, modify it so that it can be used with the Feng-Rao improved code construction, prove equality between its error correcting capability and half the minimum distance lower bound by Andersen and Geil (2008) that has not been done in the original proposal except for one-point Hermitian codes, remove the unnecessary computational steps so that it can run faster, and analyze its computational complexity in terms of multiplications and divisions in the finite field. As a unique decoding algorithm, the proposed one is empirically and theoretically as fast as the BMS algorithm for one-point Hermitian codes. As a list decoding algorithm, extensive experiments suggest that it can be much faster for many moderate size/usual inputs than the algorithm by Beelen and Brander (2010). It should be noted that as a list decoding algorithm the proposed method seems to have exponential worst-case computational complexity while the previous proposals (Beelen and Brander, 2010; Guruswami and Sudan, 1999) have polynomial ones, and that the proposed method is expected to be slower than the previous proposals for very large/special inputs. △ Less

Submitted 18 February, 2016; v1 submitted 27 March, 2012; originally announced March 2012.

Comments: Accepted for publication in J. Symbolic Computation. LaTeX2e article.cls, 42 pages, 4 tables, no figures. Ver. 6 added an illustrative example of the algorithm execution

MSC Class: 94B35 (Primary); 13P10; 94B27; 14G50 (Secondary) ACM Class: E.4; F.2.1; I.1.2; I.1.4

Journal ref: J. Symbolic Computation, vol.79, pp.384-410, 2017

Secure Multiplex Coding with Dependent and Non-Uniform Multiple Messages

Authors: Masahito Hayashi, Ryutaroh Matsumoto

Abstract: The secure multiplex coding (SMC) is a technique to remove rate loss in the coding for wire-tap channels and broadcast channels with confidential messages caused by the inclusion of random bits into transmitted signals. SMC replaces the random bits by other meaningful secret messages, and a collection of secret messages serves as the random bits to hide the rest of messages. In the previous resear… ▽ More The secure multiplex coding (SMC) is a technique to remove rate loss in the coding for wire-tap channels and broadcast channels with confidential messages caused by the inclusion of random bits into transmitted signals. SMC replaces the random bits by other meaningful secret messages, and a collection of secret messages serves as the random bits to hide the rest of messages. In the previous researches, multiple secret messages were assumed to have independent and uniform distributions, which is difficult to be ensured in practice. We remove this restrictive assumption by a generalization of the channel resolvability technique. We also give practical construction techniques for SMC by using an arbitrary given error-correcting code as an ingredient, and channel-universal coding of SMC. By using the same principle as the channel-universal SMC, we give coding for the broadcast channel with confidential messages universal to both channel and source distributions. △ Less

Submitted 1 February, 2016; v1 submitted 6 February, 2012; originally announced February 2012.

Comments: We made several changes to improve the presentation

Journal ref: IEEE Transactions on Information Theory, Volume 62, Issue 5, 2355 - 2409 (2016)

List Decoding Algorithms based on Groebner Bases for General One-Point AG Codes

Authors: Olav Geil, Ryutaroh Matsumoto, Diego Ruano

Abstract: We generalize the list decoding algorithm for Hermitian codes proposed by Lee and O'Sullivan based on Gröbner bases to general one-point AG codes, under an assumption weaker than one used by Beelen and Brander. By using the same principle, we also generalize the unique decoding algorithm for one-point AG codes over the Miura-Kamiya $C_{ab}$ curves proposed by Lee, Bras-Amorós and O'Sullivan to gen… ▽ More We generalize the list decoding algorithm for Hermitian codes proposed by Lee and O'Sullivan based on Gröbner bases to general one-point AG codes, under an assumption weaker than one used by Beelen and Brander. By using the same principle, we also generalize the unique decoding algorithm for one-point AG codes over the Miura-Kamiya $C_{ab}$ curves proposed by Lee, Bras-Amorós and O'Sullivan to general one-point AG codes, without any assumption. Finally we extend the latter unique decoding algorithm to list decoding, modify it so that it can be used with the Feng-Rao improved code construction, prove equality between its error correcting capability and half the minimum distance lower bound by Andersen and Geil that has not been done in the original proposal, and remove the unnecessary computational steps so that it can run faster. △ Less

Submitted 23 April, 2012; v1 submitted 30 January, 2012; originally announced January 2012.

Comments: IEEEtran.cls, 5 pages, no figure. To appear in Proc. 2012 IEEE International Symposium on Information Theory, July 1-6, 2012, Boston, MA, USA. Version 4 corrected wrong description of the work by Lee, Bras-Amorós and O'Sullivan, and added four references

MSC Class: 94B35 (Primary) 13P10; 94B27; 14G50 (Secondary) ACM Class: E.4; F.2.1; I.1.2; I.1.4

Journal ref: Proc. 2012 IEEE International Symposium on Information Theory, July 1-6, 2012, Boston, MA, USA, pages 86-90

Universal Secure Multiplex Network Coding with Dependent and Non-Uniform Messages

Authors: Ryutaroh Matsumoto, Masahito Hayashi

Abstract: We consider the random linear precoder at the source node as a secure network coding. We prove that it is strongly secure in the sense of Harada and Yamamoto and universal secure in the sense of Silva and Kschischang, while allowing arbitrary small but nonzero mutual information to the eavesdropper. Our security proof allows statistically dependent and non-uniform multiple secret messages, while a… ▽ More We consider the random linear precoder at the source node as a secure network coding. We prove that it is strongly secure in the sense of Harada and Yamamoto and universal secure in the sense of Silva and Kschischang, while allowing arbitrary small but nonzero mutual information to the eavesdropper. Our security proof allows statistically dependent and non-uniform multiple secret messages, while all previous constructions of weakly or strongly secure network coding assumed independent and uniform messages, which are difficult to be ensured in practice. △ Less

Submitted 12 April, 2017; v1 submitted 17 November, 2011; originally announced November 2011.

Comments: 10 pages, 1 figure, IEEEtrans.cls. Online published in IEEE Trans. Inform. Theory

Secure Multiplex Coding Over Interference Channel with Confidential Messages

Authors: Xiaolin Li, Ryutaroh Matsumoto

Abstract: In this paper, inner and outer bounds on the capacity region of two-user interference channels with two confidential messages have been proposed. By adding secure multiplex coding to the error correction method in [15] which achieves the best achievable capacity region for interference channel up to now, we have shown that the improved secure capacity region compared with [2] now is the whole Han-… ▽ More In this paper, inner and outer bounds on the capacity region of two-user interference channels with two confidential messages have been proposed. By adding secure multiplex coding to the error correction method in [15] which achieves the best achievable capacity region for interference channel up to now, we have shown that the improved secure capacity region compared with [2] now is the whole Han-Kobayashi region. In addition, this construction not only removes the rate loss incurred by adding dummy messages to achieve security, but also change the original weak security condition in [2] to strong security. Then the equivocation rate for a collection of secret messages has also been evaluated, when the length of the message is finite or the information rate is high, our result provides a good approximation for bounding the worst case equivocation rate. Our results can be readily extended to the Gaussian interference channel with little efforts. △ Less

Submitted 19 September, 2011; v1 submitted 19 September, 2011; originally announced September 2011.

Comments: 10 pages, 6 figures

Universally Attainable Error and Information Exponents, and Equivocation Rate for the Broadcast Channels with Confidential Messages

Authors: Masahito Hayashi, Ryutaroh Matsumoto

Abstract: We show universally attainable exponents for the decoding error and the mutual information and universally attainable equivocation rates for the conditional entropy for the broadcast channels with confidential messages. The error exponents are the same as ones given by Korner and Sgarro for the broadcast channels with degraded message sets. We show universally attainable exponents for the decoding error and the mutual information and universally attainable equivocation rates for the conditional entropy for the broadcast channels with confidential messages. The error exponents are the same as ones given by Korner and Sgarro for the broadcast channels with degraded message sets. △ Less

Submitted 3 October, 2011; v1 submitted 21 April, 2011; originally announced April 2011.

Comments: IEEEtran.sty, 6 pages, resubmitted to Allerton Conference. Ver. 1 incorrectly stated \exp(ψ) is concave in Prop. 7, which is corrected in V2. V3 changed the title and the proof argument. The results are the same in all versions

Secure Multiplex Network Coding

Authors: Ryutaroh Matsumoto, Masahito Hayashi

Abstract: In the secure network coding for multicasting, there is loss of information rate due to inclusion of random bits at the source node. We show a method to eliminate that loss of information rate by using multiple statistically independent messages to be kept secret from an eavesdropper. The proposed scheme is an adaptation of Yamamoto et al.'s secure multiplex coding to the secure network coding. In the secure network coding for multicasting, there is loss of information rate due to inclusion of random bits at the source node. We show a method to eliminate that loss of information rate by using multiple statistically independent messages to be kept secret from an eavesdropper. The proposed scheme is an adaptation of Yamamoto et al.'s secure multiplex coding to the secure network coding. △ Less

Submitted 5 June, 2011; v1 submitted 15 February, 2011; originally announced February 2011.

Comments: IEEEtran.sty, 7 pages, no figure, Version 2 will appear in Proc. NetCod 2011, Beijing, China. Version 3 adds an appendix proving that the mutual information can be made exactly zero

Secure Multiplex Coding with a Common Message

Authors: Ryutaroh Matsumoto, Masahito Hayashi

Abstract: We determine the capacity region of the secure multiplex coding with a common message, and evaluate the mutual information and the equivocation rate of a collection of secret messages to the second receiver (eavesdropper), which were not evaluated by Yamamoto et al. We determine the capacity region of the secure multiplex coding with a common message, and evaluate the mutual information and the equivocation rate of a collection of secret messages to the second receiver (eavesdropper), which were not evaluated by Yamamoto et al. △ Less

Submitted 24 May, 2011; v1 submitted 20 January, 2011; originally announced January 2011.

Comments: 5 pages, no figure, IEEEtran.sty, final version to appear in Proc. ISIT 2011

Journal ref: Proc. 2011 IEEE ISIT, pp. 1965-1969, Saint Petersburg, Russia, July 31-August 5, 2011

Strong security and separated code constructions for the broadcast channels with confidential messages

Authors: Ryutaroh Matsumoto, Masahito Hayashi

Abstract: We show that the capacity region of the broadcast channel with confidential messages does not change when the strong security criterion is adopted instead of the weak security criterion traditionally used. We also show a construction method of coding for the broadcast channel with confidential messages by using an arbitrary given coding for the broadcast channel with degraded message sets. We show that the capacity region of the broadcast channel with confidential messages does not change when the strong security criterion is adopted instead of the weak security criterion traditionally used. We also show a construction method of coding for the broadcast channel with confidential messages by using an arbitrary given coding for the broadcast channel with degraded message sets. △ Less

Submitted 24 May, 2011; v1 submitted 4 October, 2010; originally announced October 2010.

Comments: LaTeX2e, two column, 9 pages, no figure, improved version registered as arXiv:1101.4036

A construction of universal secure network coding

Authors: Ryutaroh Matsumoto

Abstract: We construct a universal secure network coding. Our construction just modifies the transmission scheme at the source node and works with every linear coding at an intermediate node. We relax the security criterion such that the mutual information between the message and the eavesdropped signal is sufficiently small instead of strictly zero. Our construction allows the set of eavesdropped links to… ▽ More We construct a universal secure network coding. Our construction just modifies the transmission scheme at the source node and works with every linear coding at an intermediate node. We relax the security criterion such that the mutual information between the message and the eavesdropped signal is sufficiently small instead of strictly zero. Our construction allows the set of eavesdropped links to change at each time slot. △ Less

Submitted 15 February, 2011; v1 submitted 24 June, 2010; originally announced June 2010.

Comments: This paper has been withdrawn by the author. The proof technique in this paper does not ensure the existence of a coding scheme that is secure against all the eavesdropping matrices of rank less than or equal to μ, which means that the proof does not prove the universal security as originally claimed. A much extended and corrected version of this paper was registered as arXiv:1102.3002. The author appreciates the helpful comment by Dr. Jun Muramatsu

Vulnerability of MRD-Code-based Universal Secure Network Coding against Stronger Eavesdroppers

Authors: Eitaro Shioji, Ryutaroh Matsumoto, Tomohiko Uyematsu

Abstract: Silva et al. proposed a universal secure network coding scheme based on MRD codes, which can be applied to any underlying network code. This paper considers a stronger eavesdropping model where the eavesdroppers possess the ability to re-select the tapping links during the transmission. We give a proof for the impossibility of attaining universal security against such adversaries using Silva et al… ▽ More Silva et al. proposed a universal secure network coding scheme based on MRD codes, which can be applied to any underlying network code. This paper considers a stronger eavesdropping model where the eavesdroppers possess the ability to re-select the tapping links during the transmission. We give a proof for the impossibility of attaining universal security against such adversaries using Silva et al.'s code for all choices of code parameters, even with restricted number of tapped links. We also consider the cases with restricted tapping duration and derive some conditions for this code to be secure. △ Less

Submitted 1 November, 2010; v1 submitted 9 March, 2010; originally announced March 2010.

Comments: 7 pages, no figure, ieice.cls, a part of this paper was presented in 2010 IEEE International Symposium on Information Theory. The proofs in V2 became more readable than V1, but the results unchanged

Journal ref: IEICE Trans. Fundamentals, vol. 93, no. 11, pp. 2026-2033, Nov. 2010

Construction of wiretap codes from ordinary channel codes

Authors: Masahito Hayashi, Ryutaroh Matsumoto

Abstract: From an arbitrary given channel code over a discrete or Gaussian memoryless channel, we construct a wiretap code with the strong security. Our construction can achieve the wiretap capacity under mild assumptions. The key tool is the new privacy amplification theorem bounding the eavesdropped information in terms of the Gallager function. From an arbitrary given channel code over a discrete or Gaussian memoryless channel, we construct a wiretap code with the strong security. Our construction can achieve the wiretap capacity under mild assumptions. The key tool is the new privacy amplification theorem bounding the eavesdropped information in terms of the Gallager function. △ Less

Submitted 8 January, 2010; originally announced January 2010.

Comments: 5 pages, no figure, IEEEtran.cls. Submitted to 2010 IEEE ISIT

Journal ref: Proc. 2010 IEEE ISIT, pp. 2538-2542, Austin, Texas, USA, June 13-18, 2010

Problems in application of LDPC codes to information reconciliation in quantum key distribution protocols

Authors: Ryutaroh Matsumoto

Abstract: The information reconciliation in a quantum key distribution protocol can be studied separately from other steps in the protocol. The problem of information reconciliation can be reduced to that of distributed source coding. Its solution by LDPC codes is reviewed. We list some obstacles preventing the LDPC-based distributed source coding from becoming a more favorable alternative to the Cascade… ▽ More The information reconciliation in a quantum key distribution protocol can be studied separately from other steps in the protocol. The problem of information reconciliation can be reduced to that of distributed source coding. Its solution by LDPC codes is reviewed. We list some obstacles preventing the LDPC-based distributed source coding from becoming a more favorable alternative to the Cascade protocol for information reconciliation in quantum key distribution protocols. This exposition does not require knowledge of the quantum theory. △ Less

Submitted 13 September, 2009; v1 submitted 14 August, 2009; originally announced August 2009.

Comments: 10 pages, 1 figure. short survey article

Report number: IT2009-41

Strongly Secure Privacy Amplification Cannot Be Obtained by Encoder of Slepian-Wolf Code

Authors: Shun Watanabe, Ryutaroh Matsumoto, Tomohiko Uyematsu

Abstract: The privacy amplification is a technique to distill a secret key from a random variable by a function so that the distilled key and eavesdropper's random variable are statistically independent. There are three kinds of security criteria for the key distilled by the privacy amplification: the normalized divergence criterion, which is also known as the weak security criterion, the variational distan… ▽ More The privacy amplification is a technique to distill a secret key from a random variable by a function so that the distilled key and eavesdropper's random variable are statistically independent. There are three kinds of security criteria for the key distilled by the privacy amplification: the normalized divergence criterion, which is also known as the weak security criterion, the variational distance criterion, and the divergence criterion, which is also known as the strong security criterion. As a technique to distill a secret key, it is known that the encoder of a Slepian-Wolf (the source coding with full side-information at the decoder) code can be used as a function for the privacy amplification if we employ the weak security criterion. In this paper, we show that the encoder of a Slepian-Wolf code cannot be used as a function for the privacy amplification if we employ the criteria other than the weak one. △ Less

Submitted 7 March, 2011; v1 submitted 14 June, 2009; originally announced June 2009.

Comments: 10 pages, no figure, A part of this paper will be presented at 2009 IEEE International Symposium on Information Theory in Seoul, Korea. Version 2 is a published version. The results are not changed from version 1. Explanations are polished and some references are added. In version 3, only style and DOI are edited

Journal ref: IEICE Trans. Fundamentals, vol. 93, no. 9, pp. 1650-1659, September 2010

On the Energy Benefit of Network Coding for Wireless Multiple Unicast

Authors: Jasper Goseling, Ruytaroh Matsumoto, Tomohiko Uyematsu, Jos H. Weber

Abstract: We consider the energy savings that can be obtained by employing network coding instead of plain routing in wireless multiple unicast problems. We establish lower bounds on the benefit of network coding, defined as the maximum of the ratio of the minimum energy required by routing and network coding solutions, where the maximum is over all configurations. It is shown that if coding and routing sol… ▽ More We consider the energy savings that can be obtained by employing network coding instead of plain routing in wireless multiple unicast problems. We establish lower bounds on the benefit of network coding, defined as the maximum of the ratio of the minimum energy required by routing and network coding solutions, where the maximum is over all configurations. It is shown that if coding and routing solutions are using the same transmission range, the benefit in $d$-dimensional networks is at least $2d/\lfloor\sqrt{d}\rfloor$. Moreover, it is shown that if the transmission range can be optimized for routing and coding individually, the benefit in 2-dimensional networks is at least 3. Our results imply that codes following a \emph{decode-and-recombine} strategy are not always optimal regarding energy efficiency. △ Less

Submitted 18 August, 2011; v1 submitted 16 January, 2009; originally announced January 2009.

Journal ref: EURASIP Journal on Wireless Communications and Networking, Vol. 2010 (2010), Art.ID 605421

On Field Size and Success Probability in Network Coding

Authors: Olav Geil, Ryutaroh Matsumoto, Casper Thomsen

Abstract: Using tools from algebraic geometry and Groebner basis theory we solve two problems in network coding. First we present a method to determine the smallest field size for which linear network coding is feasible. Second we derive improved estimates on the success probability of random linear network coding. These estimates take into account which monomials occur in the support of the determinant o… ▽ More Using tools from algebraic geometry and Groebner basis theory we solve two problems in network coding. First we present a method to determine the smallest field size for which linear network coding is feasible. Second we derive improved estimates on the success probability of random linear network coding. These estimates take into account which monomials occur in the support of the determinant of the product of Edmonds matrices. Therefore we finally investigate which monomials can occur in the determinant of the Edmonds matrix. △ Less

Submitted 27 June, 2008; originally announced June 2008.

Comments: 16 pages, 3 figures, 2 tables. Accepted for publication at International Workshop on the Arithmetic of Finite Fields, WAIFI 2008

Journal ref: Proceedings of the 2nd International Workshop on the Arithmetic of Finite Fields, WAIFI 2008, pp. 157-173