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

Quantum algorithms for learning Walsh spectra of multi-output boolean functions

QUANTUM INFORMATION PROCESSING 2019年第6期18卷 1-31页

作者： Cui, Jingyi Guo, Jiansheng Xu, Linhong Li, Mingming Informat Sci & Technol Inst Zhengzhou Henan Peoples R China

In classical cryptography, many cryptographic primitives could be treated as multi-output boolean functions. The analysis of such functions is of great interest for cryptologists owing to their wide ranges of applications. Since each multi-output boolean function can be uniquely determined by its Walsh transform, the Walsh spectra could reveal the properties of multi-output boolean functions. In this paper, several quantum algorithms for learning Walsh spectra of multi-output boolean functions are proposed. Firstly, with the usage of the amplitude estimation algorithm based on the Monte Carlo method, we present a quantum algorithm that allows one to estimate the Walsh coefficient of a multi-output boolean function at a specified point with an additive error E and probability at least 1-. The corresponding query complexity is O(E-1log-1). There is an almost quadratic speedup over the classical algorithm. Secondly, we propose a generalized phase kick-back technique for multi-output boolean functions to encode multiple Walsh coefficients on the amplitudes of states. Based on this generalized technique, a quantum Goldreich-Levin algorithm for arbitrary multi-output boolean function F:{0,1}n{0,1}m where m,nZ is proposed to find those Walsh coefficients satisfying the threshold boundary condition with probability at least 1-. The whole query complexity is O2m+5+n/23 log2m+5n2. Finally, by using the same idea of the swap-test circuit, the query complexity of the modified quantum Goldreich-Levin algorithm could be lowered to O achieving a further speedup when is no less than O(2-n/2+6n). Those two quantum Goldreich-Levin algorithms have their own advantages in implementation and query complexity.

关键词： Quantum computation Quantum learning algorithm multi-output boolean function Walsh spectrum Goldreich-Levin theorem

来源：评论

学校读者我要写书评

暂无评论

Quantum cryptographic property testing of multi-output boolean functions

引用

QUANTUM INFORMATION PROCESSING 2019年第6期18卷 1-56页

作者： Cui, Jingyi Guo, Jiansheng Informat Sci & Technol Inst Zhengzhou Henan Peoples R China

Compared with boolean functions, multi-output boolean functions (a.k.a. vectorial boolean functions) are commonly used in classical cryptography. More generally, many cryptographic primitives can be treated as multi-output boolean functions. Hence, the research on property testing of multi-output boolean functions is meaningful for the design and cryptanalysis of symmetric cryptography. This paper mainly focuses on the cryptographic property testing of multi-output boolean functions in the quantum world. Firstly, the generalized Deutsch-Jozsa algorithm is proposed to distinguish balanced multi-output boolean functions from constant ones with a single query. This algorithm has a wider scope of applications with arbitrary ancillary inputs. The first generalized Bernstein-Vazirani algorithm suitable for multi-output boolean functions is presented to recover the linear coefficients of linear functions. Then, combined with the generalized Deutsch-Jozsa algorithm, the quantum algorithm for estimating Walsh coefficients of multi-output boolean functions is proposed with the same idea of quantum approximate counting algorithm, accompanied with an algorithm for computing the Walsh coefficient at a specified point based on quantum exact counting algorithm. Finally, with the usage of algorithms mentioned above, the cryptographic property testing of multi-output boolean functions is studied. In order to describe the distances from having the certain properties, Euclidean distance and Manhattan distance are introduced as complements of Hamming distance. According to the definition, the first balance testing of multi-output boolean functions is presented by testing the uniformity of images. The second algorithm exploits the relationship between balance and the Walsh coefficients at the point 0 which could be easily extended to k-order resiliency testing. We also briefly analyze the query complexities of strict avalanche criterion testing and k-order propagation criteria testing.

关键词： Quantum computation multi-output boolean function Property testing Walsh spectrum Generalized Deutsch-Jozsa algorithm Amplitude estimation

来源：评论

学校读者我要写书评

暂无评论

New characterizations for the multi-output correlation-immune boolean functions

引用

DISCRETE MATHEMATICS 2020年第11期343卷 112082-112082页

作者： Chai, Jinjin Mesnager, Sihem Wang, Zilong Xidian Univ Sch Cyber Engn State Key Lab Integrated Serv Networks Xian Shaanxi Peoples R China Univ Paris VIII Dept Math Paris France

Correlation-immune (CI) multi-output boolean functions have the property of keeping the same output distributions when some input variables are fixed. Recently, a new application of CI functions has appeared in the system of resisting side-channel attacks (SCA). In this paper, three new methods are proposed to characterize the tth-order CI multi-output (n-input and m-output) boolean functions. The first characterization is to regard the multi-output boolean functions as the corresponding generalized boolean functions. It is shown that a generalized boolean function f(g) is a tth-order CI function if and only if the Walsh transform of f(g) defined here vanishes at all points with Hamming weights between 1 and t. The last two methods are generalized from Fourier spectral characterizations. Especially, Fourier spectral characterizations are efficient to characterize the symmetric multi-output CI boolean functions. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Side-channel attacks multi-output boolean function Generalized boolean function Correlation immunity Walsh transform Discrete Fourier transform

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：