A Note on the Post-Quantum Security of (Ring) Signatures
- URL: http://arxiv.org/abs/2112.06078v1
- Date: Sat, 11 Dec 2021 21:51:41 GMT
- Title: A Note on the Post-Quantum Security of (Ring) Signatures
- Authors: Rohit Chatterjee, Kai-Min Chung, Xiao Liang, Giulio Malavolta
- Abstract summary: This work revisits the security of classical signatures and ring signatures in a quantum world.
We focus on the arguably preferable security notion of blind-unforgeability recently proposed by Alagic et al.
We present two short signature schemes achieving this notion.
- Score: 17.284592769143075
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: This work revisits the security of classical signatures and ring signatures
in a quantum world. For (ordinary) signatures, we focus on the arguably
preferable security notion of blind-unforgeability recently proposed by Alagic
et al. (Eurocrypt'20). We present two short signature schemes achieving this
notion: one is in the quantum random oracle model, assuming quantum hardness of
SIS; and the other is in the plain model, assuming quantum hardness of LWE with
super-polynomial modulus. Prior to this work, the only known blind-unforgeable
schemes are Lamport's one-time signature and the Winternitz one-time signature,
and both of them are in the quantum random oracle model.
For ring signatures, the recent work by Chatterjee et al. (Crypto'21)
proposes a definition trying to capture adversaries with quantum access to the
signer. However, it is unclear if their definition, when restricted to the
classical world, is as strong as the standard security notion for ring
signatures. They also present a construction that only partially achieves
(even) this seeming weak definition, in the sense that the adversary can only
conduct superposition attacks over the messages, but not the rings. We propose
a new definition that does not suffer from the above issue. Our definition is
an analog to the blind-unforgeability in the ring signature setting. Moreover,
assuming the quantum hardness of LWE, we construct a compiler converting any
blind-unforgeable (ordinary) signatures to a ring signature satisfying our
definition.
Related papers
- A General Quantum Duality for Representations of Groups with Applications to Quantum Money, Lightning, and Fire [8.714677279673738]
We show that manipulating quantum states in one basis is equivalent to extracting values in a complementary basis.
We present the first secure quantum lightning construction based on a plausible cryptographic assumption.
We show equivalence among four security notions: quantum lightning security, worst-case and average-case cloning security, and security against preparing a canonical state.
arXiv Detail & Related papers (2024-11-01T11:56:11Z) - (Quantum) Indifferentiability and Pre-Computation [50.06591179629447]
Indifferentiability is a cryptographic paradigm for analyzing the security of ideal objects.
Despite its strength, indifferentiability is not known to offer security against pre-processing attacks.
We propose a strengthening of indifferentiability which is not only composable but also takes arbitrary pre-computation into account.
arXiv Detail & Related papers (2024-10-22T00:41:47Z) - On black-box separations of quantum digital signatures from pseudorandom
states [1.9254132307399263]
We show that there $textitdoes not$ exist a black-box construction of a quantum digital signatures scheme.
Our result complements that of Morimae and Yamakawa (2022), who described a $textitone-time$ secure QDS scheme with classical signatures.
arXiv Detail & Related papers (2024-02-13T03:36:35Z) - Revocable Quantum Digital Signatures [57.25067425963082]
We define and construct digital signatures with revocable signing keys from the LWE assumption.
In this primitive, the signing key is a quantum state which enables a user to sign many messages.
Once the key is successfully revoked, we require that the initial recipient of the key loses the ability to sign.
arXiv Detail & Related papers (2023-12-21T04:10:07Z) - How to Sign Quantum Messages [0.0]
We introduce the concept of time-dependent (TD) signatures, where the signature of a quantum message depends on the time of signing.
We then consider the bounded quantum storage model, where adversaries are limited with respect to their quantum memories.
We show that quantum messages can be signed with information-theoretic security in this model.
arXiv Detail & Related papers (2023-04-13T08:05:19Z) - Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical.
We show that tests of quantumness that follow a certain template, which captures recent proposals such as (Kalai et al., 2022) can in fact do much more.
Namely, the same protocols can be used for certifying a qubit, a building-block that stands at the heart of applications such as certifiable randomness and classical delegation of quantum computation.
arXiv Detail & Related papers (2023-03-02T14:18:17Z) - Revocable Cryptography from Learning with Errors [61.470151825577034]
We build on the no-cloning principle of quantum mechanics and design cryptographic schemes with key-revocation capabilities.
We consider schemes where secret keys are represented as quantum states with the guarantee that, once the secret key is successfully revoked from a user, they no longer have the ability to perform the same functionality as before.
arXiv Detail & Related papers (2023-02-28T18:58:11Z) - Quantum Proofs of Deletion for Learning with Errors [91.3755431537592]
We construct the first fully homomorphic encryption scheme with certified deletion.
Our main technical ingredient is an interactive protocol by which a quantum prover can convince a classical verifier that a sample from the Learning with Errors distribution in the form of a quantum state was deleted.
arXiv Detail & Related papers (2022-03-03T10:07:32Z) - A Unified Framework For Quantum Unforgeability [0.0]
We develop a general and parameterised quantum game-based security model unifying unforgeability for both classical and quantum constructions.
We prove how our definitions subsume previous ones while considering more fine-grained adversarial models.
We show that the strongest level of unforgeability, namely existential unforgeability, can only be achieved if only to previously queried messages are considered to be forgeries.
arXiv Detail & Related papers (2021-03-25T17:31:59Z) - Quantum-secure message authentication via blind-unforgeability [74.7729810207187]
We propose a natural definition of unforgeability against quantum adversaries called blind unforgeability.
This notion defines a function to be predictable if there exists an adversary who can use "partially blinded" access to predict values.
We show the suitability of blind unforgeability for supporting canonical constructions and reductions.
arXiv Detail & Related papers (2018-03-10T05:31:38Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.