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

Static and Dynamic Coherence Fraction in the bernstein-vazirani algorithm

ADVANCED QUANTUM TECHNOLOGIES 2025年第0期

作者： Zhou, Si-Qi Liang, Jin-Min Peng, Jiayin Chen, Zhihua Fei, Shao-Ming Ma, Zhihao Shanghai Jiao Tong Univ Sch Math Sci MOE LSC Shanghai 200240 Peoples R China Shanghai Seres Informat Technol Co Ltd Shanghai 200040 Peoples R China Southern Univ Sci & Technol Shenzhen Inst Quantum Sci & Engn Shenzhen 518055 Peoples R China Peking Univ Frontiers Sci Ctr Nanooptoelectron Sch Phys State Key Lab Mesoscop Phys Beijing 100871 Peoples R China Peking Univ Collaborat Innovat Ctr Quantum Matter Beijing 100871 Peoples R China Neijiang Normal Univ Sch Math Inform Sci Neijiang 641100 Sichuan Peoples R China Jimei Univ Sch Sci Xiamen 361021 Peoples R China Capital Normal Univ Sch Math Sci Beijing 100048 Peoples R China Max Planck Inst Math Sci D-04103 Leipzig Germany

Quantum entanglement and coherence are crucial resources in quantum information theory. In some scenarios, however, it is not necessary to directly estimate entanglement or coherence measures to quantify the capabilities of a state in quantum information processing. Instead, fully entangled fraction and coherence fraction are two alternatives for entanglement and coherence in specific quantum tasks. Here, a link is established between the coherence fraction and the bernstein-vazirani algorithm, which has several potential applications including cryptography and database search. It is showed that the success probability of the generalized bernstein-vazirani algorithm depends only on the coherence fraction of the initial state rather than its entanglement or coherence. Moreover, the coherence fraction dynamics are discussed and a relation is established between the operator's coherence fraction and the algorithm's success probability. These findings highlight how quantum coherence fraction influences the efficiency of quantum algorithms.

关键词： bernstein-vazirani algorithm state coherence fraction operator coherence fraction

来源：评论

学校读者我要写书评

暂无评论

QUANTUM PERIOD FINDING BASED ON THE bernstein-vazirani algorithm

引用

QUANTUM INFORMATION & COMPUTATION 2020年第1-2期20卷 65-84页

作者： Hao, Xuexuan Zhang, Fengrong Wei, Yongzhuang Zhou, Yong China Univ Min & Technol Sch Comp Sci & Technol Xuzhou 221116 Jiangsu Peoples R China State Key Lab Cryptol POB 5159 Beijing 100878 Peoples R China China Univ Min & Technol Minist Educ Peoples Republ China Mine Digitizat Engn Res Ctr Xuzhou 221116 Jiangsu Peoples R China Guilin Univ Elect Technol Guangxi Key Lab Cryptog & Informat Secur Guilin 541004 Guangxi Peoples R China

Quantum period finding algorithms have been used to analyze symmetric cryptography. For instance, the 3-round Feistel construction and the Even-Mansour construction could be broken in polynomial time by using quantum period finding algorithms. In this paper, we firstly provide a new algorithm for finding the nonzero period of a vectorial function with 0(n) quantum queries, which uses the bernstein-vazirani algorithm as one step of the subroutine. Afterwards, we compare our algorithm with Simon's algorithm. In some scenarios, such as the Even-Mansour construction and the function satisfying Simon's promise, etc, our algorithm is more efficient than Simon's algorithm with respect to the tradeoff between quantum memory and time. On the other hand, we combine our algorithm with Grover's algorithm for the key-recovery attack on the FX construction. Compared with the Grover-Meets-Simon algorithm proposed by Leander and May at Asiacrypt 2017, the new algorithm could save the quantum memory.

关键词： quantum cryptanalysis symmetric cryptography bernstein-vazirani algorithm Simon's algorithm FX construction

来源：评论

学校读者我要写书评

暂无评论

Quantum key-recovery attack on Feistel constructions: bernstein-vazirani meet Grover algorithm

引用

QUANTUM INFORMATION PROCESSING 2021年第10期20卷 330-330页

作者： Zhou, Bao-Min Yuan, Zheng Univ Sci & Technol China Coll Cybersecur Hefei 230026 Peoples R China Beijing Elect Sci Technol Inst Beijing 100070 Peoples R China Beijing Univ Posts & Telecommun Coll Cybersecur Beijing 100876 Peoples R China

The development of quantum computers has urged the cryptographic community to prepare cryptographic primitives for the eventual arrival of the post-quantum world. At Asiacrypt 2017, Leander and May combined Grover's and Simon's quantum algorithms to break the FX-based block ciphers. Technically this result is based on the combination of the quantum algorithms of Grover's and Simon's for the first time in the cryptographic setting. In this study, we using bernstein-vazirani's and Grover's algorithms to generate a new quantum key-recovery attacks on different rounds of Feistel constructions. An advantage of our attack is the keys can be divided into multiple blocks to enter the S-box and realize the process of recovery;this method greatly reduces the complexity of key recovery. Hence, it has strong practicability for key recovery (e.g., DES, Camellia, etc.). In order to show that, a detailed process has been provided in this paper.

关键词： Key-recovery attacks Feistel constructions bernstein-vazirani algorithm Grover algorithm

来源：评论

学校读者我要写书评

暂无评论

Solving bernstein and vazirani's Problem with the 2-bit Permutation Function

引用

QUANTUM INFORMATION PROCESSING 2022年第1期21卷 1-14页

作者： Chen, Chien-Yuan Chang, Chung-Yao Hsueh, Chih-Cheng Natl Univ Kaohsiung Dept Comp Sci & Informat Engn Kaohsiung Univ Rd 700 Kaohsiung Taiwan Aletheia Univ Dept Comp Sci & Informat Engn 32 Zhen Li St New Taipei Taiwan

In this paper, we propose a novel quantum algorithm, based on the bernstein-vazirani algorithm, for finding a if the function f (x) = a . pi(x), where a, x is an element of {0, 1}(2) and pi(x) is a 2-bit permutation function. Note that thebernstein-vazirani algorithm cannot find a when we select the function f (x) = a . pi(x), where pi(x) = ((2013) (0123)). Our algorithm can be further applied to Nagata et al.'s problem. Our algorithm will output g(A(1)) and g(A(0)) if the function f (x) = (g(A(1))g(A(0)))(2) . pi(x), where A(1), A(0) is an element of {0, 1}(m), x is an element of {0, 1}(2) and g : {0, 1}(m) -> {0, 1}.

关键词： Quantum algorithm bernstein-vazirani algorithm

来源：评论

学校读者我要写书评

暂无评论

Zero-correlation linear analysis for block ciphers based on the bernstein-vazirani and Grover algorithms

引用

QUANTUM INFORMATION PROCESSING 2024年第8期23卷 289-289页

作者： Zhang, Kun Shang, Tao Tang, Yao Liu, Jianwei Beihang Univ Sch Cyber Sci & Technol Beijing 100083 Peoples R China

With the rapid development of quantum computing technology, the traditional cryptosystem will face a significant threat. It is an urgent security issue to study the security impact of quantum computing on classical cryptosystems and provide reliable cryptographic primitives for the post-quantum era. A powerful way to solve this problem is to quantize the classical cryptanalysis tools and use the improved versions for cryptanalysis. In this paper, we propose a quantum Zero-correlation analysis algorithm based on the bernstein-vazirani and Grover algorithms. It can find zero-correlation linear hulls for Feistel and SPN structures. We prove the correctness of the algorithm and analyze its complexity. Compared with the classical algorithms, the proposed quantum algorithm has significant advantages when the number of encryption rounds of block ciphers is large. Moreover, compared with the existing quantum Zero-correlation linear analysis, the proposed algorithm is more efficient and does not depend on the algebraic characteristics of the target cipher, which makes the algorithm has more flexible application scenarios. With the development of quantum computers, we discuss the threat of quantum cryptanalysis algorithms to classical security.

关键词： Quantum cryptography Quantum computing Block cipher bernstein-vazirani algorithm Grover algorithm

来源：评论

学校读者我要写书评

暂无评论

引用

QUANTUM INFORMATION PROCESSING 2024年第7期23卷 269-269页

作者： Wu, Hongyu Feng, Xiaoning Harbin Engn Univ Coll Comp Sci & Technol Harbin 150001 Peoples R China

Quantum computation models have profoundly impacted cryptanalysis. Differential cryptanalysis is one of the most fundamental methods in cryptanalysis of block ciphers, and one of the variations of this attack is related-key differential cryptanalysis. In this paper, quantum related-key differential cryptanalysis is implemented in two main stages of classical version. We employ bernstein-vazirani algorithm to find related-key differential characteristics in the first stage. Building on this basis, the second stage combines quantum maximum algorithm and quantum counting algorithm to recover correct key pair by quantum random access memory model. Compared to classical related-key differential cryptanalysis, the first stage achieves exponential acceleration, while the second stage accelerates at O(K), where K2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K<^>2$$\end{document} represents the number of candidate key pairs.

关键词： Quantum cryptanalysis Related-key differential analysis Quantum counting algorithm Quantum maximum algorithm bernstein-vazirani algorithm

来源：评论

学校读者我要写书评

暂无评论

Quantum algorithms for learning the algebraic normal form of quadratic Boolean functions

引用

QUANTUM INFORMATION PROCESSING 2020年第8期19卷 1-22页

作者： Hao, Xuexuan Zhang, Fengrong Xia, Shixiong Zhou, Yong China Univ Min & Technol Sch Comp Sci & Technol Xuzhou 221116 Jiangsu Peoples R China Guilin Univ Elect Technol Guangxi Key Lab Cryptog & Informat Secur Guilin 541004 Peoples R China China Univ Min & Technol Mine Digitizat Engn Res Ctr Minist Educ Xuzhou 221116 Jiangsu Peoples R China

Quantum algorithms for the analysis of Boolean functions have received a lot of attention over the last few years. The algebraic normal form (ANF) of a linear Boolean function can be recovered by using the bernstein-vazirani (BV) algorithm. No research has been carried out on quantum algorithms for learning the ANF of general Boolean functions. In this paper, quantum algorithms for learning the ANF of quadratic Boolean functions are studied. We draw a conclusion about the influences of variables on quadratic functions, so that the BV algorithm can be run on them. We study the functions obtained by inversion and zero-setting of some variables in the quadratic function and show the construction of their quantum oracle. We introduce the concept of "club" to group variables that appear in quadratic terms and study the properties of clubs. Furthermore, we propose a bunch of algorithms for learning the full ANF of quadratic Boolean functions. The most efficient algorithm, among those we propose, provides anO(n) speedup over the classical one, and the number of queries is independent of the degenerate variables.

关键词： bernstein-vazirani algorithm Boolean function Quantum cryptanalysis Quantum computation

来源：评论

学校读者我要写书评

暂无评论

On a poset of quantum exact promise problems

引用

QUANTUM INFORMATION PROCESSING 2021年第6期20卷 1-17页

作者： Combarro, Elias F. Vallecorsa, Sofia Meglio, Alberto Di Pinera, Alejandro Rua, Ignacio Fernandez Univ Oviedo Comp Sci Dept Oviedo Spain CERN CERN Openlab Geneva Switzerland Univ Oviedo Math Dept Oviedo Spain

Two of the most well-known quantum algorithms, those introduced by Deutsch-Jozsa and bernstein-vazirani, can solve promise problems with just one function query, showing an oracular separation with deterministic classical algorithms. In this work, we generalise those methods to study a family of quantum algorithms that can, with just one query, exactly solve promise problems stated over Boolean functions. We also show that these problems can be naturally ordered, inducing a partially ordered set of promise problems. We study the properties of such a poset, showing that the Deutsch-Jozsa and bernstein-vazirani problems are, in a certain sense, extremal problems in it, determining some of its automorphisms and proving that it is connected. We also prove that, for the problems in the poset, the corresponding classical query complexities can take any value between 1 and 2(n-1) + 1.

关键词： Quantum algorithms Posets Query complexity Deutsch-Jozsa algorithm bernstein-vazirani algorithm

来源：评论

学校读者我要写书评

暂无评论

An improved quantum algorithm for the quantum learning with errors problem

引用

QUANTUM INFORMATION PROCESSING 2022年第5期21卷 1-14页

作者： Wang, Yaru Jiang, Haodong Ma, Zhi Wang, Hong Duan, Qianheng State Key Lab Math Engn & Adv Comp Zhengzhou 450001 Peoples R China State Key Lab Cryptol POB 5159 Beijing 100878 Peoples R China

LWE (learning with errors)-based cryptography, whose security relies on the hardness of the underlying LWE problem, is one of the most promising candidates for post-quantum cryptography that is designed to be secure even when the adversaries can access the quantum computers. The quantum LWE problem is a quantum version of the LWE problem, where the solving algorithm can query the LWE oracle in a quantum way. For this quantum LWE problem, Grilo, Kerenidis and Zijlstra (GKZ) recently showed an efficient quantum solving algorithm, together with a test candidate algorithm which judges whether the solution returned by solving algorithm is correct. In this paper, we first present an improved version of the GKZ solving algorithm, which can support a higher error rate, and meanwhile achieve a higher success probability. In particular, for the high error rate case, our algorithm can almost increase the success probability by a factor q than the original GKZ solving algorithm, where q is the module of the LWE problem. Second, for the GKZ test algorithm, we show a quadratic speed-up in running time by introducing amplitude amplification.

关键词： Quantum LWE bernstein-vazirani algorithm Amplitude amplification Quantum Fourier transform

来源：评论

学校读者我要写书评

暂无评论

Fiber optics protocols for quantum communication

引用

QUANTUM INFORMATION PROCESSING 2006年第6期5卷 441-449页

作者： Massar, Serge Free Univ Brussels Lab Informat Quant B-1050 Brussels Belgium

We show how the techniques developed for long distance quantum key distribution in optical fibers can be used to demonstrate other quantum information processing and communication protocols. We present a fiber optics realization of the Deutsch-Jozsa and bernstein-vazirani algorithms. We describe a method, called "error filtration", for reducing errors in quantum communication channels, and present an experimental implementation thereof. We discuss the cryptographic primitive of string flipping, and present an experimental implementation which has higher security than achievable using any classical protocol.

关键词： quantum information quantum communication optical fibers Deutsch-Jozsa algorithm bernstein-vazirani algorithm error filtration quantum coin tossing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：