检索结果-内蒙古大学图书馆

IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)

作者： Hori, Gen Asia Univ Fac Business Adm Taichung Taiwan RIKEN Brain Sci Inst Wako Saitama Japan

ISBN: (纸本)9781538646588

The decoding problem of hidden Markov model (HMM) is extended based on the L-p-norm of a vector of the log transition probabilities along the sequence of hidden states. The extended decoding problem coincides with the conventional decoding problem for p = 1, and with the minimax decoding problem for p = infinity. To solve the extended decoding problem, we introduce a family of Viterbi algorithm termed the "L-p-Viterbi algorithm" that continuously interpolates the conventional Viterbi algorithm and the minimax Viterbi algorithm. We also consider the corresponding evaluation and estimation problems. Numerical simulations show that the L-p-Viterbi algorithm with an adequately large value of p has an advantage over the minimax Viterbi algorithm.

关键词： Hidden Markov model (HMM) decoding problem Viterbi algorithm L-p-norm

来源：评论

学校读者我要写书评

暂无评论

EXTENSION OF decoding problem OF HMM BASED ON L~p-NORM

EXTENSION OF DECODING PROBLEM OF HMM BASED ON L~p-NORM

引用

IEEE International Conference on Acoustics, Speech and Signal Processing

作者： Gen Hori Faculty of Business Administration Asia University

ISBN: (纸本)9781538646595

The decoding problem of hidden Markov model (HMM) is extended based on the L~p-norm of a vector of the log transition probabilities along the sequence of hidden states. The extended decoding problem coincides with the conventional decoding problem for p = 1, and with the minimax decoding problem for p = ∞. To solve the extended decoding problem, we introduce a family of Viterbi algorithm termed the "L~p-Viterbi algorithm" that continuously interpolates the conventional Viterbi algorithm and the minimax Viterbi algorithm. We also consider the corresponding evaluation and estimation problems. Numerical simulations show that the L~p-Viterbi algorithm with an adequately large value of p has an advantage over the minimax Viterbi algorithm.

关键词： Hidden Markov model (HMM) decoding problem Viterbi algorithm L~p-norm Viterbi algorithm Hidden Markov models decoding Minimax

来源：评论

学校读者我要写书评

暂无评论

Quantum sieving for code-based cryptanalysis and its limitations for ISD

引用

DESIGNS CODES AND CRYPTOGRAPHY 2025年 1-34页

作者： Engelberts, Lynn Etinski, Simona Loyer, Johanna CWI Amsterdam Netherlands QuSoft Amsterdam Netherlands

Sieving using near-neighbor search techniques is a well-known method in lattice-based cryptanalysis, yielding the current best runtime for the shortest vector problem in both the classical and quantum setting. Recently, sieving has also become an important tool in code-based cryptanalysis. Specifically, a variant of the information-set decoding (ISD) framework, commonly used for attacking cryptographically relevant instances of the decoding problem, has been introduced that involves a sieving subroutine. The resulting sieving-based ISD framework yields complexities close to the best-performing classical algorithms for the decoding problem. It is therefore natural to ask how well quantum versions perform. In this work, we introduce the first quantum algorithms for code sieving by designing quantum variants of the aforementioned sieving subroutine. In particular, using quantum-walk techniques, we provide a speed-up over classical code sieving and over a variant using Grover's algorithm. Our quantum-walk algorithm exploits the structure of the underlying search problem by adding a layer of locality sensitive filtering, inspired by a quantum-walk algorithm for lattice sieving. We complement our asymptotic analysis of the quantum algorithms with numerical results, and observe that our quantum speed-ups for code sieving behave similarly as those observed in lattice sieving. In addition, we show that a natural quantum analog of the sieving-based ISD framework does not provide any speed-up over the first quantum ISD algorithm. Our analysis highlights that the framework should be adapted in order to outperform state-of-the-art quantum ISD algorithms.

关键词： Quantum cryptanalysis Quantum walks Near-neighbor search Code sieving decoding problem Information-set decoding

来源：评论

学校读者我要写书评

暂无评论

Syndrome decoding with MRHS solver

引用

INTERNATIONAL JOURNAL OF ELECTRONICS AND TELECOMMUNICATIONS 2025年第1期71卷 79-85页

作者： Smicik, Miloslav Zajac, Pavol Slovak Univ Technol Bratislava Fac Elect Engn & Informat Technol Bratislava Slovakia

syndrome decoding problem (SDP) is an NP-complete problem that has important applications in the development of post-quantum cryptography. Currently, the most efficient algorithms for SDP are based on the Information Set decoding (ISD) approach that leverages efficiently time-memory and probability trade-offs. In our contribution, we explore a different approach based on transforming an instance of the SDP problem into a so-called Multiple Right-Hand-Sides (MRHS) Equation system. The MRHS system is then solved with a specialized MRHS solver. We explore how difficult is to solve (small) instances of SDP in MRHS form, and which trade-offs and parametric selections lead to the best results. Although our practical results are worse than those obtained by ISD, we believe that they show a better understanding of the connection between SDP and its MRHS representation, and can be a basis for future improvements.

关键词： Cryptography decoding problem MRHS equa-tion systems

来源：评论

学校读者我要写书评

暂无评论

On the subset sum problem over finite fields

引用

FINITE FIELDS AND THEIR APPLICATIONS 2008年第4期14卷 911-929页

作者： Li, Jiyou Wan, Daqing Peking Univ Sch Math Sci Beijing 100871 Peoples R China Univ Calif Irvine Dept Math Irvine CA 92697 USA

The subset sum problem over finite fields is a well-known NP-complete problem. It arises naturally from decoding generalized Reed-Solomon codes. In this paper, we study the number of solutions of the subset sum problem from a mathematical point of view. In several interesting cases, we obtain explicit or asymptotic formulas for the solution number. As a consequence, we obtain some results on the decoding problem of Reed-Solomon codes. (C) 2008 Elsevier Inc. All rights reserved.

关键词： Subset sum problem Finite fields decoding problem Reed-Solomon codes Deep holes

来源：评论

学校读者我要写书评

暂无评论

On the Hardness of the decoding and the Minimum Distance problems for Rank Codes

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2016年第12期62卷 7245-7252页

作者： Gaborit, Philippe Zemor, Gilles Univ Limoges XLIM Res Inst F-87000 Limoges France Univ Bordeaux Inst Math Bordeaux F-33405 Talence France

We give a randomized reduction for the Rank Syndrome decoding problem and Rank Minimum Distance problem for rank codes over extension fields. Our results are based on embedding linear codes in the Hamming space into linear codes over an extension field equipped with the rank metric. We prove that if any of the previous problems for the rank metric is in ZPP = RP boolean AND coRP, then we would have NP = ZPP. We also give complexity results for the respective rank metric approximation problems.

关键词： Rank distance syndrome decoding decoding problem

来源：评论

学校读者我要写书评

暂无评论

Upper bounds on the complexity of algebraic cryptanalysis of ciphers with a low multiplicative complexity

引用

DESIGNS CODES AND CRYPTOGRAPHY 2017年第1-2期82卷 43-56页

作者： Zajac, Pavol Slovak Univ Technol Bratislava Ilkovicova 3 Bratislava 81219 Slovakia

Lightweight cipher designs try to minimize the implementation complexity of the cipher while maintaining some specified security level. Using only a small number of AND gates lowers the implementation costs, and enables easier protections against side-channel attacks. In our paper we study the connection between the number of AND gates (multiplicative complexity) and the complexity of algebraic attacks. We model the encryption with multiple right-hand sides (MRHS) equations. The resulting equation system is transformed into a syndrome decoding problem. The complexity of the decoding problem depends on the number of AND gates, and on the relative number of known output bits with respect to the number of unknown key bits. This allows us to apply results from coding theory, and to explicitly connect the complexity of the algebraic cryptanalysis to the multiplicative complexity of the cipher. This means that we can provide asymptotic upper bounds on the complexity of algebraic attacks on selected families of ciphers based on the hardness of the decoding problem.

关键词： Algebraic cryptanalysis Multiplicative complexity Lightweight cryptography decoding problem

来源：评论

学校读者我要写书评

暂无评论

Security and complexity of the McEliece cryptosystem based on quasi-cyclic low-density parity-check codes

引用

IET INFORMATION SECURITY 2013年第3期7卷 212-220页

作者： Baldi, Marco Bianchi, Marco Chiaraluce, Franco Univ Politecn Marche Dipartimento Ingn Informaz Ancona Italy

In the context of public key cryptography, the McEliece cryptosystem represents a very smart solution based on the hardness of the decoding problem, which is believed to be able to resist the advent of quantum computers. Despite this, the original McEliece cryptosystem based on Goppa codes, has encountered limited interest in practical applications, partly because of some constraints imposed by this very special class of codes. The authors have recently introduced a variant of the McEliece cryptosystem including low-density parity-check codes, that are state-of-the-art codes, now used in many telecommunication standards and applications. In this study, the authors discuss the possible use of a bit-flipping decoder in this context, which gives a significant advantage in terms of complexity. The authors also provide theoretical arguments and practical tools for estimating the trade-off between security and complexity, in such a way to give a simple procedure for the system design.

关键词： cyclic codes decoding Goppa codes parity check codes public key cryptography McEliece cryptosystem complexity quasicyclic low-density parity-check codes public key cryptography decoding problem quantum computers Goppa codes telecommunication standards bit-flipping decoder system design

来源：评论

学校读者我要写书评

暂无评论

Pseudorandomness of decoding, Revisited: Adapting OHCP to Code-Based Cryptography 29th

Pseudorandomness of Decoding, Revisited: Adapting OHCP to Co...

引用

29th Annual International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT)

作者： Bombar, Maxime Couvreur, Alain Debris-Alazard, Thomas Inst Polytech Paris LIX CNRS UMR 7161Ecole Polytech 1 Rue Honore Estienne Orves F-91120 Palaiseau France Inria Paris France

ISBN: (纸本)9789819987382;9789819987399

Recent code-based cryptosystems rely, among other things, on the hardness of the decisional decoding problem. If the search version is well understood, both from practical and theoretical standpoints, the decision version has been less studied in the literature, and little is known about its relationships with the search version, especially for structured variants. On the other hand, in the world of Euclidean lattices, the situation is rather different, and many reductions exist, both for unstructured and structured versions of the underlying problems. For the latter versions, a powerful tool called the OHCP framework (for Oracle with Hidden Center problem), which appears to be very general, has been introduced by Peikert et al. (STOC 2017) and has proved to be very useful as a black box inside reductions. In this work, we revisit this technique and extract the very essence of this framework, namely the Oracle Comparison problem (OCP), to show how to recover the support of the error, solving an Oracle with Hidden Support problem (OHSP), more suitable for code-based cryptography. This yields a new worst-case to average-case search-to-decision reduction for the decoding problem, as well as a new average-case to average-case reduction. We then turn to the structured versions and explain why this is not as straightforward as for Euclidean lattices. If we fail to give a search-to-decision reduction for structured codes, we believe that our work opens the way towards new reductions for structured codes, given that the OHCP framework proved to be so powerful in lattice-based cryptography. Furthermore, we also believe that this technique could be extended to codes endowed with other metrics, such as the rank metric, for which no reduction is known.

关键词： decoding problem OHCP Search-to-Decision Reductions Worst-Case to Average-Case

来源：评论

学校读者我要写书评

暂无评论

An Upper-Bound on the decoding Failure Probability of the LRPC Decoder 19th

An Upper-Bound on the Decoding Failure Probability of the LR...

引用

19th IMA International Conference on Cryptography and Coding (IMACC)

作者： Burle, Etienne Otmani, Ayoub Univ La Havre Normandie Univ Rouen Normandie Normandie Univ INSA Rouen NormandieLITIS UR 4108 F-76000 Le Havre France

ISBN: (纸本)9783031478178;9783031478185

Low Rank Parity Check (LRPC) codes form a class of rankmetric error-correcting codes that was purposely introduced to design public-key encryption schemes. An LRPC code is defined from a parity check matrix whose entries belong to a relatively low dimensional vector subspace of a large finite field. This particular algebraic feature can then be exploited to correct with high probability rank errors when the parameters are appropriately chosen. In this paper, we present theoretical upper-bounds on the probability that the LRPC decoding algorithm fails.

关键词： Rank metric decoding problem LRPC code Homogeneous matrix

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：