1,720,974 research outputs found
A New Approach to Generic Lower Bounds: Classical/Quantum MDL, Quantum Factoring, and More
Full text linkThis paper studies the limitations of the generic approaches to solving cryptographic problems in classical and quantum settings in various models.
- In the classical generic group model (GGM), we find simple alternative proofs for the lower bounds of variants of the discrete logarithm (DL) problem: the multiple-instance DL and one-more DL problems (and their mixture). We also re-prove the unknown-order GGM lower bounds, such as the order finding, root extraction, and repeated squaring.
- In the quantum generic group model (QGGM), we study the complexity of variants of the discrete logarithm. We prove the logarithm DL lower bound in the QGGM even for the composite order setting. We also prove an asymptotically tight lower bound for the multiple-instance DL problem. Both results resolve the open problems suggested in a recent work by Hhan, Yamakawa, and Yun.
- In the quantum generic ring model we newly suggested, we give the logarithmic lower bound for the order-finding algorithms, an important step for Shor\u27s algorithm. We also give a logarithmic lower bound for a certain generic factoring algorithm outputting relatively small integers, which includes a modified version of Regev\u27s algorithm.
- Finally, we prove a lower bound for the basic index calculus method for solving the DL problem in a new idealized group model regarding smooth numbers.
The quantum lower bounds in both models allow certain (different) types of classical preprocessing.
All of the proofs are significantly simpler than the previous proofs and are through a single tool, the so-called compression lemma, along with linear algebra tools. Our use of this lemma may be of independent interest
양자 컴퓨터에 대한 암호학적 알고리즘
Full text link학위논문(박사) -- 서울대학교대학원 : 자연과학대학 수리과학부, 2022. 8. 이훈희.The advent of a quantum mechanical computer presents a clear threat to existing cryptography. On the other hand, the quantum computer also suggests the possibility of a new cryptographic protocol through the properties of quantum mechanics. These two perspectives, respectively, gave rise to a new field called post-quantum cryptography as a countermeasure against quantum attacks and quantum cryptography as a new cryptographic technology using quantum mechanics, which are the subject of this thesis.
In this thesis, we reconsider the security of the current post-quantum cryptography through a new quantum attack, model, and security proof. We present the fine-grained quantum security of hash functions as cryptographic primitives against preprocessing adversaries. We also bring recent quantum information theoretic research into cryptography, creating new quantum public key encryption and quantum commitment. Along the way, we resolve various open problems such as limitations of quantum algorithms with preprocessing computation, oracle separation problems in quantum complexity theory, and public key encryption using group action.양자역학을 이용한 컴퓨터의 등장은 쇼어의 알고리즘 등을 통해 기존 암호학에 명백한 위협을 제시하며, 양자역학의 성질을 통한 새로운 암호프로토콜의 가능성 또한 제시한다. 이러한 두 가지 관점은 각각 이 학위 논문의 주제가 되는 양자공격에 대한 대응책으로써의 대양자암호와 양자역학을 이용한 암호기술인 양자암호라고 불리는 새로운 분야를 발생시켰다.
이 학위 논문에서는 현재 대양자암호의 안전성을 새로운 양자암호 공격 알고리즘과 모델, 안전성 증명을 통해 재고한다. 특히 암호학적 해쉬함수의 일방향함수, 암호학적 의사난수생성기로서의 대양자 암호 안전성의 구체적인 평가를 제시한다. 또한 최근 양자역학의 연구를 양자암호에 도입함으로써 새로운 양자 공개키암호와 양자 커밋먼트 등의 새로운 발견을 제시한다. 이 과정에서 전처리 계산을 포함한 양자알고리즘의 한계, 양자 복잡계들의 오라클분리 문제, 군의 작용을 이용한 공개키 암호 등의 여러 열린문제들의 해결을 제시한다.1 Introduction 1
1.1 Contributions 3
1.2 Related Works 11
1.3 Research Papers 13
2 Preliminaries 14
2.1 Quantum Computations 15
2.2 Quantum Algorithms 20
2.3 Cryptographic Primitives 21
I Post-Quantum Cryptography: Attacks, New Models, and Proofs 24
3 Quantum Cryptanalysis 25
3.1 Introduction 25
3.2 QROM-AI Algorithm for Function Inversion 26
3.3 Quantum Multiple Discrete Logarithm Problem 34
3.4 Discussion and Open problems 39
4 Quantum Random Oracle Model with Classical Advice 42
4.1 Quantum ROM with Auxiliary Input 44
4.2 Function Inversion 46
4.3 Pseudorandom Generators 56
4.4 Post-quantum Primitives 58
4.5 Discussion and Open Problems 59
5 Quantum Random Permutations with Quantum Advice 62
5.1 Bound for Inverting Random Permutations 64
5.2 Preparation 64
5.3 Proof of Theorem 68
5.4 Implication in Complexity Theory 74
5.5 Discussion and Open Problems 77
II Quantum Cryptography: Public-key Encryptions and Bit Commitments 79
6 Equivalence Theorem 80
6.1 Equivalence Theorem 81
6.2 Non-uniform Equivalence Theorem 83
6.3 Proof of Equivalence Theorem 86
7 Quantum Public Key Encryption 89
7.1 Swap-trapdoor Function Pairs 90
7.2 Quantum-Ciphertext Public Key Encryption 94
7.3 Group Action based Construction 99
7.4 Lattice based Construction 107
7.5 Discussion and Open Problems 113
7.6 Deferred Proof 114
8 Quantum Bit Commitment 119
8.1 Quantum Commitments 120
8.2 Efficient Conversion 123
8.3 Applications of Conversion 126
8.4 Discussion and Open Problems 137박
Pseudorandom Function-like States from Common Haar Unitary
Full text linkRecent active studies have demonstrated that cryptography without one-way functions (OWFs) could be possible in the quantum world. Many fundamental primitives that are natural quantum analogs of OWFs or pseudorandom generators (PRGs) have been introduced, and their mutual relations and applications have been studied. Among them, pseudorandom function-like state generators (PRFSGs) [Ananth, Qian, and Yuen, Crypto 2022] are one of the most important primitives. PRFSGs are a natural quantum analogue of pseudorandom functions (PRFs), and imply many applications such as IND-CPA secret-key encryption (SKE) and EUF-CMA message authentication code (MAC). However, only known constructions of (many-query-secure) PRFSGs are ones from OWFs or pseudorandom unitaries (PRUs).
In this paper, we construct classically-accessible adaptive secure PRFSGs in the invertible quantum Haar random oracle (QHRO) model which is introduced in [Chen and Movassagh, Quantum]. The invertible QHRO model is an idealized model where any party can access a public single Haar random unitary and its inverse, which can be considered as a quantum analog of the random oracle model. Our PRFSG constructions resemble the classical Even-Mansour encryption based on a single permutation, and are secure against any unbounded polynomial number of queries to the oracle and construction. To our knowledge, this is the first application in the invertible QHRO model without any assumption or conjecture. The previous best construction in the idealized model is PRFSGs secure up to o(λ/ log λ) queries in the common Haar state model [Ananth, Gulati, and Lin, TCC 2024].
We develop new techniques on Haar random unitaries to prove the selective and adaptive security of our PRFSGs. For selective security, we introduce a new formula, which we call the Haar twirl approximation formula. For adaptive security, we show the unitary reprogramming lemma and the unitary resampling lemma. These have their own interest, and may have many further applications. In particular, by using the approximation formula, we give an alternative proof of the non-adaptive security of the PFC ensemble [Metger, Poremba, Sinha, and Yuen, FOCS 2024] as an additional result.
Finally, we prove that our construction is not PRUs or quantum-accessible non-adaptive PRFSGs by presenting quantum polynomial time attacks. Our attack is based on generalizing the hidden subgroup problem where the relevant function outputs quantum states
Oracle Recording for Non-Uniform Random Oracles, and its Applications
Full text linkIn Crypto 2019, Zhandry showed how to define compressed oracles, which record quantum superposition queries to the quantum random oracle. In this paper, we extend Zhandry\u27s compressed oracle technique to non-uniformly distributed functions with independently sampled outputs. We define two quantum oracles and , which are indistinguishable to the non-uniform quantum random oracle where quantum access is given to a random function whose images are sampled from a probability distribution independently for each . We show that these compressed oracles record the adversarial quantum superposition queries. Also, we re-prove the optimality of Grover search and the collision resistance of non-uniform random functions, using our extended compressed oracle technique
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Full text link“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Full text linkWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
Cryptanalysis of Middle Lattice on the Overstretched NTRU Problem for General Modulus Polynomial
Full text linkThe overstretched NTRU problem, which is the NTRU problem with super-polynomial size q in n,
is one of the most important candidates for higher level cryptography.
Unfortunately, Albrecht et al. in Crypto 2016 and Cheon et al. in ANTS 2016 proposed so-called subfield attacks
which demonstrate that the overstretched NTRU problems with power-of-two cyclotomic modulus are not secure enough
with given parameters in GGH multilinear map and YASHE/LTV fully homomorphic encryption.
Moreover, Kirchner and Fouque presented new cryptanalysis of the overstretched NTRU problem over general modulus in Eurocrypt 2017.
They showed that a lattice basis reduction algorithm upon middle lattice, which is first presented by Howgrave-Graham
in Crypto 2007,
experimentally recover secret parameters of the overstretched NTRU problem.
In this paper, we revisit the middle lattice technique on the overstretched NTRU problem.
This analysis show that the optimized middle lattice technique has same complexity to subfield attacks,
but threaten more general base ring with poly(n) expansion factor
as common in suggested schemes like original GGH, YASHE scheme and NTRU prime rings.
Our new analysis implies that cryptosystem related to the overstretched NTRU problem cannot be secured by changing base ring.
In addition, we present an extended (trace/norm) subfield attack for the power-of-two cyclotomic modulus, which is also one
of the middle lattice technique.
This extended subfield attack has a similar asymptotic complexity to the previous subfield attacks, but with smaller constant in the exponent term
From the Hardness of Detecting Superpositions to Cryptography: Quantum Public Key Encryption and Commitments
Full text linkRecently, Aaronson et al. (arXiv:2009.07450) showed that detecting interference between two orthogonal states is as hard as swapping these states. While their original motivation was from quantum gravity, we show its applications in quantum cryptography.
1. We construct the first public key encryption scheme from cryptographic non-abelian group actions. Interestingly, ciphertexts of our scheme are quantum even if messages are classical. This resolves an open question posed by Ji et al. (TCC ’19). We construct the scheme through a new abstraction called swap-trapdoor function pairs, which may be of independent interest.
2. We give a simple and efficient compiler that converts the flavor of quantum bit commitments. More precisely, for any prefix X, Y {computationally,statistically,perfectly}, if the base scheme is X-hiding and Y-binding, then the resulting scheme is Y-hiding and X-binding. Our compiler calls the base scheme only once. Previously, all known compilers call the base schemes polynomially many times (Crépeau et al., Eurocrypt ’01 and Yan, Asiacrypt ’22). For the security proof of the conversion, we generalize the result of Aaronson et al. by considering quantum auxiliary inputs
- …
