Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPost-Quantum Succinct Arguments: Breaking the Quantum Rewinding Barrier
225
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We prove that Kilians four-message succinct argument system is post-quantum secure in the standard model when instantiated with any probabilistically checkable proof and any collapsing hash function (which in turn exist based on the post-quantum hardness of Learning with Errors). This yields the first post-quantum succinct argument system from any falsifiable assumption. At the heart of our proof is a new quantum rewinding procedure that enables a reduction to repeatedly query a quantum adversary for accepting transcripts as many times as desired. Prior techniques were limited to a constant number of accepting transcripts.
rate research
Read More
We investigate the existence of constant-round post-quantum black-box zero-knowledge protocols for $mathbf{NP}$. As a main result, we show that there is no constant-round post-quantum black-box zero-knowledge argument for $mathbf{NP}$ unless $mathbf{NP}subseteq mathbf{BQP}$. As constant-round black-box zero-knowledge arguments for $mathbf{NP}$ exist in the classical setting, our main result points out a fundamental difference between post-quantum and classical zero-knowledge protocols. Combining previous results, we conclude that unless $mathbf{NP}subseteq mathbf{BQP}$, constant-round post-quantum zero-knowledge protocols for $mathbf{NP}$ exist if and only if we use non-black-box techniques or relax certain security requirements such as relaxing standard zero-knowledge to $epsilon$-zero-knowledge. Additionally, we also prove that three-round and public-coin constant-round post-quantum black-box $epsilon$-zero-knowledge arguments for $mathbf{NP}$ do not exist unless $mathbf{NP}subseteq mathbf{BQP}$.
Starting from the one-way group action framework of Brassard and Yung (Crypto 90), we revisit building cryptography based on group actions. Several previous candidates for one-way group actions no longer stand, due to progress both on classical algorithms (e.g., graph isomorphism) and quantum algorithms (e.g., discrete logarithm). We propose the general linear group action on tensors as a new candidate to build cryptography based on group actions. Recent works (Futorny--Grochow--Sergeichuk, Lin. Alg. Appl., 2019) suggest that the underlying algorithmic problem, the tensor isomorphism problem, is the hardest one among several isomorphism testing problems arising from areas including coding theory, computational group theory, and multivariate cryptography. We present evidence to justify the viability of this proposal from comprehensive study of the state-of-art heuristic algorithms, theoretical algorithms, and hardness results, as well as quantum algorithms. We then introduce a new notion called pseudorandom group actions to further develop group-action based cryptography. Briefly speaking, given a group $G$ acting on a set $S$, we assume that it is hard to distinguish two distributions of $(s, t)$ either uniformly chosen from $Stimes S$, or where $s$ is randomly chosen from $S$ and $t$ is the result of applying a random group action of $gin G$ on $s$. This subsumes the classical decisional Diffie-Hellman assumption when specialized to a particular group action. We carefully analyze various attack strategies that support the general linear group action on tensors as a candidate for this assumption. Finally, we establish the quantum security of several cryptographic primitives based on the one-way group action assumption and the pseudorandom group action assumption.
Quantum encryption is a well studied problem for both classical and quantum information. However, little is known about quantum encryption schemes which enable the user, under different keys, to learn different functions of the plaintext, given the ciphertext. In this paper, we give a novel one-bit secret-key quantum encryption scheme, a classical extension of which allows different key holders to learn different length subsequences of the plaintext from the ciphertext. We prove our quantum-classical scheme secure under the notions of quantum semantic security, quantum entropic indistinguishability, and recent security definitions from the field of functional encryption.
Signatures are primarily used as a mark of authenticity, to demonstrate that the sender of a message is who they claim to be. In the current digital age, signatures underpin trust in the vast majority of information that we exchange, particularly on public networks such as the internet. However, schemes for signing digital information which are based on assumptions of computational complexity are facing challenges from advances in mathematics, the capability of computers, and the advent of the quantum era. Here we present a review of digital signature schemes, looking at their origins and where they are under threat. Next, we introduce post-quantum digital schemes, which are being developed with the specific intent of mitigating against threats from quantum algorithms whilst still relying on digital processes and infrastructure. Finally, we review schemes for signing information carried on quantum channels, which promise provable security metrics. Signatures were invented as a practical means of authenticating communications and it is important that the practicality of novel signature schemes is considered carefully, which is kept as a common theme of interest throughout this review.
Googles CECPQ1 experiment in 2016 integrated a post-quantum key-exchange algorithm, newhope1024, into TLS 1.2. The Google-Cloudflare CECPQ2 experiment in 2019 integrated a more efficient key-exchange algorithm, ntruhrss701, into TLS 1.3. This paper revisits the choices made in CECPQ2, and shows how to achieve higher performance for post-quantum key exchange in TLS 1.3 using a higher-security algorithm, sntrup761. Previous work had indicated that ntruhrss701 key generation was much faster than sntrup761 key generation, but this paper makes sntrup761 key generation much faster by generating a batch of keys at once. Batch key generation is invisible at the TLS protocol layer, but raises software-engineering questions regarding the difficulty of integrating batch key exchange into existing TLS libraries and applications. This paper shows that careful choices of software layers make it easy to integrate fast post-quantum software, including batch key exchange, into TLS with minor changes to TLS libraries and no changes to applications. As a demonstration of feasibility, this paper reports successful integration of its fast sntrup761 library, via a lightly patched OpenSSL, into an unmodified web browser and an unmodified TLS terminator. This paper also reports TLS 1.3 handshake benchmarks, achieving more TLS 1.3 handshakes per second than any software included in OpenSSL.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
