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

On the Hardness of Sparsely learning parity with noise

COMPUTER JOURNAL 2022年第8期65卷 1939-1947页

作者： Yan, Di Liu, Hanlin Zhao, Shuoyao Yu, Yu Shanghai Jiao Tong Univ Dept Comp Sci & Engn Shanghai 200240 Peoples R China

The learning parity with noise (LPN) problem represents the average-case analogue of the NP-Complete problem "decoding linear codes", and it has been extensively studied in learning theory, coding theory and cryptography with applications to quantum-resistant cryptographic schemes. However, LPN also suffers from large public key size which is the common drawback that hinders code-based cryptography from being practical. In this paper, we study a sparse variant of LPN whose public matrix consists of sparse vectors instead of following uniform distribution. We show a win-win argument that at least one of the following assumption is true: (i) either the hardness of sparse LPN is implied by that of the standard LPN under the same noise rate;(ii) or there exists new black-box constructions of public-key encryption schemes and oblivious transfer protocols from standard LPN. Since the second assumption relies on the infeasible noise regimes for LPN-based public-key cryptography, we believe that the first assumption is more likely to hold, i.e. sparse LPN is as hard as standard LPN. Finally, we give a (heuristic) method to further compress the sparse public matrix by evaluating pseudorandom functions with keys made public, whose security again resorts to the aforementioned win-win technique.

关键词： learning parity with noise Sparsely learning parity with noise win-win argument public-key encryption oblivious transfer privacy amplification pseudorandom functions

来源：评论

学校读者我要写书评

暂无评论

Improved Zero-Knowledge Proofs for Commitments from learning parity with noise 21

Improved Zero-Knowledge Proofs for Commitments from Learning...

引用

21st IEEE International Conference on Trust, Security and Privacy in Computing and Communications (IEEE TrustCom)

作者： Wang, Mengfan Huang, Guifang Gao, Hongmin Hu, Lei Chinese Acad Sci Inst Informat Engn Beijing Peoples R China Univ Chinese Acad Sci Sch Cyber Secur Beijing Peoples R China

ISBN: (纸本)9781665494250

Zero-knowledge proof for any relation amongst committed values is crucial and widely applicable in the design of high level cryptographic schemes, especially in privacy-preserving protocols. Besides quantum resistance, efficiency is what we are most concerned about, including asymptotic efficiency and concrete efficiency. Jain et al. proposed a simple string commitment scheme based on the learning parity with noise (LPN) problem (JKPT12), and then designed zero-knowledge proofs for valid opening, linear relation and multiplicative relation of committed values. As a result, they got an efficient zero-knowledge proof for any circuit C, with communication complexity O(t|C|l log l), where t is a security parameter measuring soundness and l is the secret length of the LPN problem. In this work, we improve the concrete communication complexity by combining some commitments in JKPT12 together. The proofs of linear relation and multiplicative relation are shortened by (6 alpha + 4)l and (42 alpha+28)l respectively, where l is the size of LPN secret. As a result, the communication cost of the protocol proving arbitrary relation is reduced by a constant level.

关键词： zero-knowledge proof learning parity with noise commitment scheme

来源：评论

学校读者我要写书评

暂无评论

Side-channel analysis of a learning parity with physical noise processor

引用

JOURNAL OF CRYPTOGRAPHIC ENGINEERING 2021年第2期11卷 171-179页

作者： Kamel, Dina Bellizia, Davide Bronchain, Olivier Standaert, Francois-Xavier Univ Catholique Louvain UCLouvain Ottignies Belgium

learning parity with physical noise (LPPN) has been proposed as an assumption on which to build authentication protocols based on the learning parity with noise (LPN) problem. Its first advantage is to reduce the randomness requirements of standard LPN-based protocols, by directly performing erroneous computations so that no (e.g. Bernoulli-distributed) errors have to be generated on chip. At ASHES 2018, an LPPN processor was presented and confirmed the possibility to efficiently generate erroneous computations with the appropriate error rate. Since LPPN computations are key-homomorphic, they are good candidates for improved side-channel security thanks to masking, since they could theoretically lead to masked implementations with overheads that are linear in the number of shares, the analysis of which was left as an open problem. In this paper, we confirm this good potential by analyzing the side-channel security of an LPPN processor. We (1) evaluate the leakage of different parts of the erroneous computations, (2) conclude that intermediate computations that can be targeted with a divide-and-conquer Gaussian template attack are a sweet spot for side-channel attacks, and (3) show that LPPN computations naturally reach a level of noise that makes masking effective, despite further noise addition could be beneficial to reach higher security at lower implementation cost.

关键词： learning parity with noise Side-channel analysis Authentication Probabilistic computation

来源：评论

学校读者我要写书评

暂无评论

On the Robustness of learning parity with noise 18th

On the Robustness of Learning Parity with Noise

引用

18th International Conference on Information and Communications Security (ICICS)

作者： Yao, Nan Yu, Yu Li, Xiangxue Gu, Dawu Shanghai Jiao Tong Univ Dept Comp Sci & Engn Shanghai Peoples R China China Normal Univ Dept Comp Sci & Technol Shanghai Peoples R China Westone Cryptol Res Ctr Beijing Peoples R China Natl Engn Lab Wireless Secur XUPT Xian Peoples R China

ISBN: (纸本)9783319500119;9783319500102

The learning parity with noise (LPN) problem is well understood in learning theory and cryptography and has been found quite useful in constructing various lightweight cryptographic primitives. There exists non-trivial evidence that the problem is robust on highentropy secrets (and even given hard-to-invert leakages), and the justified results by Dodis, Kalai and Lovett (STOC 2009) were established under non-standard hard learning assumptions. The recent progress by Suttichaya and Bhattarakosol (Information Processing Letters, Volume 113, Issues 14-16) claimed that LPN remains provably secure (reducible from the LPN assumption itself) as long as the secret is sampled from any linear min-entropy source, and thereby resolves the long-standing open problem. In the paper, we point out that their proof is flawed and their understanding about LPN is erroneous. We further offer a remedy with some slight adaption to the setting of Suttichaya and Bhattarakosol.

关键词： learning parity with noise High-entropy secrets Provable security Leftover Hash Lemma

来源：评论

学校读者我要写书评

暂无评论

Solving the learning parity with noise's open question

引用

INFORMATION PROCESSING LETTERS 2013年第14-16期113卷 562-566页

作者： Suttichaya, Vasin Bhattarakosol, Pattarasinee Mahidol Univ Dept Comp Engn Fac Engn Nakhon Pathom 73170 Thailand Chulalongkorn Univ Innovat Network & Software Engn Technol INSET Lab Dept Math & Comp Sci Fac Sci Bangkok 10330 Thailand

The classical cryptographic primitives are constructed on the assumptions that the private key is securely kept and uniformly distributed. learning parity with noise is a famous problem used to construct several cryptographic primitives. This research studies the open question about the hardness of the learning parity with noise assumption when the secret vector is not uniform and has sufficient min-entropy. The proofs show that the standard learning parity with noise implies that it is secure even if the secret vector is sampled from an arbitrary distribution with sufficient entropy. Furthermore, this paper shows that the symmetric encryption scheme from learning parity with noise is secure even if the secret key has min-entropy at least k. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Computational complexity Cryptography learning parity with noise Min-entropy

来源：评论

学校读者我要写书评

暂无评论

Quantum Search-to-Decision Reduction for the LWE Problem∗

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2025年第2期E108A卷 104-116页

作者： Sudo, Kyohei Hara, Keisuke Tezuka, Masayuki Yoshida, Yusuke Osaka Univ Toyonaka 5600831 Japan Natl Inst Adv Ind Sci & Tech nol AIST Tokyo 1350064 Japan Yokohama Natl Univ Yokohama 2400067 Japan Tokyo Inst Technol Tokyo 152 Japan

The learning with errors (LWE) problem is one of the fundamental problems in cryptography and it has many applications in post-quantum cryptography. There are two variants of the problem, the decisional-LWE problem, and the search-LWE problem. LWE search-to decision reduction shows that the hardness of the search-LWE problem can be reduced to the hardness of the decisional-LWE problem. The efficiency of the reduction can be regarded as the gap in difficulty between the problems. We initiate a study of quantum search-to-decision reduction for the LWE problem and propose a reduction that satisfies sample-preserving. In sample-preserving reduction, it preserves all parameters even the number of instances. Especially, our quantum reduction invokes the distinguisher only 2 times to solve the search-LWE problem, while classical reductions require a polynomial number of invocations. Furthermore, we give a way to amplify the success probability of the reduction algorithm. Our amplified reduction is incomparable to the classical reduction in terms of sample complexity and query complexity. Our reduction algorithm supports a wide class of error distributions and also provides a search-to-decision reduction for the learning parity with noise problem. In the process of constructing the search-to-decision reduction, we give a quantum Goldreich-Levin theorem over Zq where q is a prime. In short, this theorem states that, if a hardcore predicate a s (mod q) can be predicted with probability distinctly greater than 1/q with respect to a uniformly random a is an element of Znq, then it is possible to determine s is an element of

关键词： key learning with errors learning parity with noise search decision reduction Goldreich-Levin theorem quantum reduction complexity sample complexity

来源：评论

学校读者我要写书评

暂无评论

A Key-recovery Attack on the LCMQ Authentication Protocol

A Key-recovery Attack on the LCMQ Authentication Protocol

引用

IEEE International Symposium on Information Theory (ISIT)

作者： Vu Nguyen Johansson, Thomas Guo, Qian Lund Univ Dept Elect & Informat Technol Lund Sweden

ISBN: (纸本)9798350382853;9798350382846

We present a simple key-recovery attack on the LCMQ Authentication Protocol, an RFID authentication protocol proposed by Li, Gong, and Qin in 2013. We show that a successful attack is performed by solving a learning parity with noise instance in a not-too-large dimension. For the proposed LCMQ parameters, the attack requires only a few invocations with the tag under attack. When there is no restriction on the number of invocations, state-of-the-art LPN solvers recover the keys with complexity below 2(51) and 2(86), when attacking LCMQ parameters for security levels 80-bit and 128-bit, respectively. To the best of our knowledge, this is the first attack on LCMQ with complexity below exhaustive key search.

关键词： Authentication RFID learning parity with noise Syndrome Decoding Information-Set Decoding BKW

来源：评论

学校读者我要写书评

暂无评论

Methods for solving equations with errors based on the HHL algorithm

引用

The Journal of China Universities of Posts and Telecommunications 2022年第4期29卷 9-20页

作者： LüLihui Wang Hong Ma Zhi Duan Qianheng Fei Yangyang Meng Xiangdong State Key Laboratory of Mathematical Engineering and Advanced Computing Zhengzhou 450001China Henan Key Laboratory of Network Cryptography Technology Zhengzhou 450001China

To solve polynomial systems,Harrow,Hassidim,and Lloyd(HHL)proposed a quantum algorithm called HHL *** on the HHL algorithm,Chen et *** an algorithm,the solving the Boolean solutions of polynomial systems(PoSSoB)***,Ding et *** the Boolean Macaulay matrix and analyzed the lower bound on the condition *** by Ding et al.’s research,several related algorithms are proposed in this ***,the improved PoSSoB algorithm using the Boolean Macaulay matrix is proved to have lower ***,for solving equations with errors,a quantum algorithm for the max-polynomial system solving(Max-PoSSo)problem is proposed based on the improved PoSSoB ***,the Max-PoSSo algorithm is extended to the learning with errors(LWE)problem and its special case,the learning parity with noise(LPN)problem,providing a quantitative criterion,the condition number,for the security of these basic problems.

关键词： Harrow Hassidim and Lloyd polynomial system solving max-polynomial system solving learning parity with noise learning with errors

来源：评论

学校读者我要写书评

暂无评论

Quantum Search-to-Decision Reduction for the LWE Problem 1

引用

14th International Conference on the Theory and Application of Cryptographic Techniques in Africa (AFRICACRYPT)

作者： Sudo, Kyohei Tezuka, Masayuki Hara, Keisuke Yoshida, Yusuke Osaka Univ Osaka Japan Tokyo Inst Technol Tokyo Japan Natl Inst Adv Ind Sci & Technol Tokyo Japan Yokohama Natl Univ Yokohama Japan

ISBN: (数字)9783031376795

ISBN: (纸本)9783031376788;9783031376795

The learning with errors (LWE) problem is one of the fundamental problems in cryptography and it has many applications in post-quantum cryptography. There are two variants of the problem, the decisional-LWE problem, and the search-LWE problem. LWE search-to-decision reduction shows that the hardness of the search-LWE problem can be reduced to the hardness of the decisional-LWE problem. The efficiency of the reduction can be regarded as the gap in difficulty between the problems. We initiate a study of quantum search-to-decision reduction for the LWE problem and propose a reduction that satisfies sample-preserving. In sample-preserving reduction, it preserves all parameters even the number of instances. Especially, our quantum reduction invokes the distinguisher only 2 times to solve the search-LWE problem, while classical reductions require a polynomial number of invocations. Furthermore, we give a way to amplify the success probability of the reduction algorithm. Our amplified reduction works with fewer LWE samples compared to the classical reduction that has a high success probability. Our reduction algorithm supports a wide class of error distributions and also provides a search-to-decision reduction for the learning parity with noise problem. In the process of constructing the search-to-decision reduction, we give a quantum Goldreich-Levin theorem over Z(q) where q is prime. In short, this theorem states that, if a hardcore predicate a center dot s (mod q) can be predicted with probability distinctly greater than 1/q with respect to a uniformly random a epsilon Z(q)(n), then it is possible to determine s epsilon Z(q)(n)

关键词： learning with errors learning parity with noise Search-to-decision reduction Goldreich-Levin theorem Quantum reduction Query complexity Sample complexity

来源：评论

学校读者我要写书评

暂无评论

Physical layer authentication for automotive cyber physical systems based on modified HB protocol

引用

Frontiers of Computer Science 2021年第3期15卷 207-214页

作者： Ahmer Khan JADOON Jing LI Licheng WANG State key laboratory of Networking and Switching Technology Beijing University of Posts and TelecommunicationsBeijing 100876China School of Computer Science Guangzhou UniversityGuangzhou 510006China

Automotive cyber physical systems(CPSs)are ever more utilizing wireless technology for V2X communication as a potential way out for challenges regarding collision detection,wire strap up troubles and collision ***,security is constrained as a result of the energy and performance limitations of modem wireless ***,the need for efficient secret key generation and management mechanism for secured communication among computationally weak wireless devices has motivated the introduction of new authentication ***,there has been a great interest in physical layer based secret key generation schemes by utilizing channel ***,it is observed that the sequence generated by two communicating parties contain mismatched bits which need to be reconciled by exchanging information over a public *** can be an immense security threat as it may let an adversary attain and recover segments of the key in known channel *** proposed Hopper-Blum based physical layer(HB-PL)authentication scheme in which an enhanced physical layer key generation method integrates the Hopper-Blum(HB)authentication *** information collected from the shared channel is used as secret keys for the HB protocol and the mismatched bits are used as the induced noise for learning parity with noise(LPN)*** proposed scheme aims to provide a way out for bit reconciliation process without leakage of information over a public ***,HB protocol is computationally efficient and simple which helps to reduce the number of exchange messages during the authentication *** have performed several experiments which show that our proposed design can generate secret keys with improved security strength and high performance in comparison to the current authentication *** scheme requires less than 55 exchange messages to achieve more than 95%of correct authentication.

关键词： cyber physical systems secret key generation learning parity with noise Hopper and Blum protocol

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：