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

An efficient post-quantum one-time signature scheme 22nd

22nd International Conference on Selected Areas in Cryptography, SAC 2015

作者： Kalach, Kassem Safavi-Naini, Reihaneh Department of Combinatorics and Optimization and Institute for Quantum Computing University of Waterloo WaterlooON Canada Department of Computer Science University of Calgary Calgary Canada

ISBN: (纸本)9783319313009

One-time signature (OTS) schemes are important cryptographic primitives that can be constructed using one-way functions, and provide post-quantum security. They have found diverse applications including forward security and broadcast authentication. OTS schemes are time-efficient, but their space complexity is high: the sizes of signatures and keys are linear in the message size. Regular schemes (e.g., based on discrete logarithm or factoring problems, and their variants), however, have very low space complexity but are not time-efficient. Therefore, in particular, they are not suitable for resource-constraint devices. Many widely used signature schemes are not post-quantum. In this paper, we give a signature scheme that has the advantages of the previous two approaches. It provides constant-size short signatures, and is much more time-efficient than schemes in the second approach. We prove that our scheme is post-quantum secure as long as the SVP in ideal lattices is hard in the presence of a quantum computer. We use SWIFFT: a family of provable collision-resistant functions, which have efficient implementations, comparable with that of SHA-256, hence our proposed scheme could be used on resource-constrained devices. © Springer International Publishing Switzerland 2016.

关键词： quantum computers

来源：评论

学校读者我要写书评

暂无评论

Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields 27

Efficient quantum algorithms for computing class groups and ...

引用

27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016

作者： Biasse, Jean-François Song, Fang Department of Mathematics and Statistics University of South Florida United States Department of Combinatorics Optimization and Institute for Quantum Computing University of Waterloo Canada

ISBN: (纸本)9781510819672

This paper gives polynomial time quantum algorithms for computing the ideal class group (CGP) under the Generalized Riemann Hypothesis and solving the principal ideal problem (PIP) in number fields of arbitrary degree. These are are fundamental problems in number theory and they are connected to many unproven conjectures in both analytic and algebraic number theory. Previously the best known algorithms by Hallgren [20] only allowed to solve these problems in quantum polynomial time for number fields of constant degree. In a recent breakthrough, Eisentrager et al. [11] showed how to compute the unit group in arbitrary fields, thus opening the way to the resolution of CGP and PIP in the general case. For example, Biasse and Song [3] pointed out how to directly apply this result to solve PIP in classes of cyclotomic fields of arbitrary degree. The methods we introduce in this paper run in quantum polynomial time in arbitrary classes of number fields. They can be applied to solve other problems in computational number theory as well including computing the ray class group and solving relative norm equations. They are also useful for ongoing cryptanalysis of cryptographic schemes based on ideal lattices [5, 10]. Our algorithms generalize the quantum algorithm for computing the (ordinary) unit group [11]. We first show that CGP and PIP reduce naturally to the computation of S-unit groups, which is another fundamental problem in number theory. Then we show an efficient quantum reduction from computing 5-units to the continuous hidden subgroup problem introduced in [11]. This step is our main technical contribution, which involves careful analysis of the metrical properties of lattices to prove the correctness of the reduction. In addition, we show how to convert the output into an exact compact representation, which is convenient for further algebraic manipulations.

关键词： Number theory

来源：评论

学校读者我要写书评

暂无评论

CY Aquarii: A Triple System with Twin Companions

arXiv

引用

arXiv 2025年

作者： Lian, Ming Niu, Jia-Shu Xue, Hui-Fang Institute of Theoretical Physics Shanxi University Taiyuan030006 China State Key Laboratory of Quantum Optics Technologies and Devices Shanxi University Taiyuan030006 China Collaborative Innovation Center of Extreme Optics Shanxi University Taiyuan030006 China Department of Physics Taiyuan Normal University Jinzhong030619 China Institute of Computational and Applied Physics Taiyuan Normal University Jinzhong030619 China Shanxi Key Laboratory for Intelligent Optimization Computing and Blockchain Technology Jinzhong030619 China

In this study, we conducted a comprehensive analysis of the SX Phoenicis (SX Phe) type star CY Aquarii (CY Aqr). Our investigation included a detailed O−C analysis based on a 90-year observational dataset, augmented by 1,367 newly determined times of maximum light. The O − C diagram reveals that (i) the primary star of CY Aqr exhibits a linear period variation rate of (1/P0)(dP/dt) = (2.132 ± 0.002)×10−8 yr−1 for its dominant pulsation mode;(ii) the primary star is disturbed by two companions and part of a triple system;(iii) Companion A has an orbital period of approximately 60.2 years and Companion B has an orbital period of approximately 50.8 years. It is highly probable that both Companion A and B are white dwarfs, with Companion A’s elliptical orbit displaying an eccentricity of e = 0.139 ± 0.002, which is the lowest confirmed value in similar binary and triple systems to date. Most notably, Companion A and B have masses that are identical within the uncertainties, with a mass ratio exceeding 0.99. Whether this is considered a coincidental event or the result of an underlying mechanism, CY Aqr is an exceptionally rare case that broadens our understanding of multiple star systems and offers a unique opportunity to delve into the enigmatic evolutionary histories of such configurations. Further intriguing characteristics of this system warrant investigation in future studies, based on additional observational data. © 2025, CC BY.

关键词： White dwarfs

来源：评论

学校读者我要写书评

暂无评论

Unified point addition formulæ and side-channel attacks

引用

8th International Workshop on Cryptographic Hardware and Embedded Systems, CHES 2006

作者： Stebila, Douglas Theriault, Nicolas Institute for Quantum Computing University of Waterloo Waterloo Ont. Canada Department of Combinatorics and Optimization University of Waterloo Waterloo Ont. Canada

ISBN: (纸本)3540465596

The successful application to elliptic curve cryptography of side-channel attacks, in which information about the secret key can be recovered from the observation of side channels like power consumption, timing, or electromagnetic emissions, has motivated the recent development of unified formulæ for elliptic curve point operations. In this paper, we show how an attack introduced by Walter can be improved and used against the unified formulæ of Brier, Déchène and Joye when it relies on a standard field arithmetic implementation, both in affine and projective coordinates. We also describe how the field arithmetic might be implemented to obtain more uniform operations that avoid this type of attack. © International Association for Cryptologic Research 2006.

关键词： Security of data

来源：评论

学校读者我要写书评

暂无评论

quantum property testing for bounded-degree graphs 1

引用

Lecture Notes in Computer Science

作者： Ambainis, Andris Childs, Andrew M. Liu, Yi-Kai Faculty of Computing University of Latvia Latvia Department of Combinatorics and Optimization Institute for Quantum Computing University of Waterloo Canada Department of Computer Science University of California Berkeley CA United States

ISBN: (数字)9783642229350

ISBN: (纸本)9783642229343

We study quantum algorithms for testing bipartiteness and expansion of bounded-degree graphs. We give quantum algorithms that solve these problems in time Õ(N1/3), beating the Ω(√N) classical lower bound. For testing expansion, we also prove an Ω(N1/4) quantum query lower bound, thus ruling out the possibility of an exponential quantum speedup. Our quantum algorithms follow from a combination of classical property testing techniques due to Goldreich and Ron, derandomization, and the quantum algorithm for element distinctness. The quantum lower bound is obtained by the polynomial method, using novel algebraic techniques and combinatorial analysis to accommodate the graph structure. © 2011 Springer-Verlag.

关键词： Testing

来源：评论

学校读者我要写书评

暂无评论

A note on quantum security for post-quantum cryptography

Lecture Notes in Computer Science (including subseries Lectu...

引用

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 2014年 8772卷 246-265页

作者： Song, Fang Department of Combinatorics and Optimization Institute for Quantum Computing University of Waterloo Canada

Shor‘s quantum factoring algorithm and a few other efficient quantum algorithms break many classical crypto-systems. In response, people proposed post-quantum cryptography based on computational problems that are believed hard even for quantum computers. However, security of these schemes against quantum attacks is elusive. This is because existing security analysis (almost) only deals with classical attackers and arguing security in the presence of quantum adversaries is challenging due to unique quantum features such as *** work proposes a general framework to study which classical security proofs can be restored in the quantum setting. Basically, we split a security proof into (a sequence of) classical security reductions, and investigate what security reductions are ‘quantum-friendly’. We characterize sufficient conditions such that a classical reduction can be ‘lifted’ to the quantum *** then apply our lifting theorems to post-quantum signature schemes. We are able to show that the classical generic construction of hash-tree based signatures from one-way functions and and a more efficient variant proposed in [10] carry over to the quantum setting. Namely, assuming existence of (classical) oneway functions that are resistant to efficient quantum inversion algorithms, there exists a quantum-secure signature scheme. We note that the scheme in [10] is a promising (post-quantum) candidate to be implemented in practice and our result further justifies it. Actually, to obtain these result, we formalize a simple criteria, which is motivated by many classical proofs in the literature and is straightforward to check. This makes our lifting theorem easier to apply, and it should be useful elsewhere to prove quantum security of proposed post-quantum cryptographic schemes. Finally we demonstrate the generality of our framework by showing that several existing works (Full-Domain hash in the quantum random-oracle model [47] and the simple hybrid arguments

关键词： quantum computers

来源：评论

学校读者我要写书评

暂无评论

Beyond product state approximations for a quantum analogue of max cut 15

Beyond product state approximations for a quantum analogue o...

引用

15th Conference on the Theory of quantum Computation, Communication and Cryptography, TQC 2020

作者： Anshu, Anurag Gosset, David Morenz, Karen Institute for Quantum Computing University of Waterloo Canada Department of Combinatorics and Optimization University of Waterloo Canada Perimeter Institute for Theoretical Physics Waterloo Canada Department of Chemistry University of Toronto Canada

ISBN: (纸本)9783959771467

We consider a computational problem where the goal is to approximate the maximum eigenvalue of a two-local Hamiltonian that describes Heisenberg interactions between qubits located at the vertices of a graph. Previous work has shed light on this problems approximability by product states. For any instance of this problem the maximum energy attained by a product state is lower bounded by the Max Cut of the graph and upper bounded by the standard Goemans-Williamson semidefinite programming relaxation of it. Gharibian and Parekh described an efficient classical approximation algorithm for this problem which outputs a product state with energy at least 0.498 times the maximum eigenvalue in the worst case, and observe that there exist instances where the best product state has energy 1/2 of optimal. We investigate approximation algorithms with performance exceeding this limitation which are based on optimizing over tensor products of few-qubit states and shallow quantum circuits. We provide an efficient classical algorithm which achieves an approximation ratio of at least 0.53 in the worst case. We also show that for any instance defined by a 3 or 4-regular graph, there is an efficiently computable shallow quantum circuit that prepares a state with energy larger than the best product state (larger even than its semidefinite programming relaxation). © Anurag Anshu, David Gosset, and Karen Morenz.

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Authentication of quantum messages

Authentication of quantum messages

引用

Applications of Lasers for Sensing and Free Space Communications, LSC 2011

作者： Hayden, Patrick Leung, Debbie Mayers, Dominic School of Computer Science McGill University Montreal QC Canada Department of Combinatorics and Optimization Institute for Quantum Computing University of Waterloo Waterloo ON Canada Institute for Quantum Information Caltech Pasadena CA United States

ISBN: (纸本)9781557529145

Message authentication is a cryptographic task that allows the receiver to reject a message that is forged or has been tampered with. A protocol to authenticate quantum messages was proposed by Barnum, Crépeau, Gottesman, Tapp, and Smith [1] and stand-alone security was proved. Here, we are concerned with universal composable security (which requires a protocol to be essentially indistinguishable from the ideal functionality and ensures overall security when the protocol is part of any larger scheme). We show that the protocol in [1] is universal composably secure, and that most of the required key can be reused with universal composable security. © 2011 Optical Society of America.

关键词： Authentication

来源：评论

学校读者我要写书评

暂无评论

A compressed classical description of quantum states 14

A compressed classical description of quantum states

引用

14th Conference on the Theory of quantum Computation, Communication and Cryptography, TQC 2019

作者： Gosset, David Smolin, John IBM T. J. Watson Research Center Yorktown Heights United States Department of Combinatorics and Optimization and Institute for Quantum Computing University of Waterloo Canada

ISBN: (纸本)9783959771122

We show how to approximately represent a quantum state using the square root of the usual amount of classical memory. The classical representation of an n-qubit state ψ consists of its inner products with O(√2n) stabilizer states. A quantum state initially specified by its 2n entries in the computational basis can be compressed to this form in time O(2npoly(n)), and, subsequently, the compressed description can be used to additively approximate the expectation value of an arbitrary observable. Our compression scheme directly gives a new protocol for the vector in subspace problem with randomized one-way communication complexity that matches (up to polylogarithmic factors) the optimal upper bound, due to Raz. We obtain an exponential improvement over Raz’s protocol in terms of computational efficiency. © David Gosset and John Smolin.

关键词： Computational efficiency

来源：评论

学校读者我要写书评

暂无评论

Post-quantum Key Exchange for the Internet and the Open quantum Safe Project 23rd

Post-quantum Key Exchange for the Internet and the Open Quan...

引用

23rd International Conference on Selected Areas in Cryptography, SAC 2016

作者： Stebila, Douglas Mosca, Michele Department of Computing and Software McMaster University HamiltonON Canada Institute for Quantum Computing and Department of Combinatorics and Optimization University of Waterloo WaterlooON Canada Perimeter Institute for Theoretical Physics WaterlooON Canada Canadian Institute for Advanced Research TorontoON Canada

ISBN: (纸本)9783319694528

Designing public key cryptosystems that resist attacks by quantum computers is an important area of current cryptographic research and standardization. To retain confidentiality of today’s communications against future quantum computers, applications and protocols must begin exploring the use of quantum-resistant key exchange and encryption. In this paper, we explore post-quantum cryptography in general and key exchange specifically. We review two protocols for quantum-resistant key exchange based on lattice problems: BCNS15, based on the ring learning with errors problem, and Frodo, based on the learning with errors problem. We discuss their security and performance characteristics, both on their own and in the context of the Transport Layer Security (TLS) protocol. We introduce the Open quantum Safe project, an open-source software project for prototyping quantum-resistant cryptography, which includes liboqs, a C library of quantum-resistant algorithms, and our integrations of liboqs into popular open-source applications and protocols, including the widely used OpenSSL library. © 2017, Springer International Publishing AG.

关键词： Application programs

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：