VDOO: A Short, Fast, Post-Quantum Multivariate Digital Signature Scheme

• URL: http://arxiv.org/abs/2312.09535v1
• Date: Fri, 15 Dec 2023 04:58:10 GMT
• Title: VDOO: A Short, Fast, Post-Quantum Multivariate Digital Signature Scheme
• Authors: Anindya Ganguly, Angshuman Karmakar, Nitin Saxena,
• Abstract summary: We present a post-quantum digital signature algorithm based on solving multivariate equations. We show that our carefully chosen parameters can resist all existing state-of-the-art attacks. This is the smallest signature size among all known post-quantum signature schemes of similar security.
• Score: 0.8643517734716606
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Hard lattice problems are predominant in constructing post-quantum cryptosystems. However, we need to continue developing post-quantum cryptosystems based on other quantum hard problems to prevent a complete collapse of post-quantum cryptography due to a sudden breakthrough in solving hard lattice problems. Solving large multivariate quadratic systems is one such quantum hard problem. Unbalanced Oil-Vinegar is a signature scheme based on the hardness of solving multivariate equations. In this work, we present a post-quantum digital signature algorithm VDOO (Vinegar-Diagonal-Oil-Oil) based on solving multivariate equations. We introduce a new layer called the diagonal layer over the oil-vinegar-based signature scheme Rainbow. This layer helps to improve the security of our scheme without increasing the parameters considerably. Due to this modification, the complexity of the main computational bottleneck of multivariate quadratic systems i.e. the Gaussian elimination reduces significantly. Thus making our scheme one of the fastest multivariate quadratic signature schemes. Further, we show that our carefully chosen parameters can resist all existing state-of-the-art attacks. The signature sizes of our scheme for the National Institute of Standards and Technology's security level of I, III, and V are 96, 226, and 316 bytes, respectively. This is the smallest signature size among all known post-quantum signature schemes of similar security.

Related papers

• Masking Gaussian Elimination at Arbitrary Order, with Application to Multivariate- and Code-Based PQC [4.655421225385125]
  We provide a masking scheme for Gaussian Elimination (GE) with back substitution to defend against first- and higher-order attacks. We propose a masked algorithm for transforming a system of linear equations into row-echelon form. We evaluate the overhead of our countermeasure for several post-quantum candidates and their different security levels.
  arXiv  Detail & Related papers  (2024-10-31T14:01:02Z)
• Shadow Quantum Linear Solver: A Resource Efficient Quantum Algorithm for Linear Systems of Equations [0.8437187555622164]
  We present an original algorithmic procedure to solve the Quantum Linear System Problem (QLSP) on a digital quantum device. The result is a quantum algorithm avoiding the need for large controlled unitaries, requiring a number of qubits that is logarithmic in the system size. We apply this to a physical problem of practical relevance, by leveraging decomposition theorems from linear algebra to solve the discretized Laplace Equation in a 2D grid.
  arXiv  Detail & Related papers  (2024-09-13T15:46:32Z)
• ZKFault: Fault attack analysis on zero-knowledge based post-quantum digital signature schemes [0.32248805768155825]
  We show that we can recover the entire secret key of LESS and CROSS using as little as a single fault. In this work, we first analyze the LESS signature scheme and devise our attack. Furthermore, we showed how this attack can be extended to the CROSS signature scheme.
  arXiv  Detail & Related papers  (2024-09-11T09:54:45Z)
• 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 Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• From the Hardness of Detecting Superpositions to Cryptography: Quantum Public Key Encryption and Commitments [8.834776091974218]
  We show the first public key encryption scheme from cryptographic emphnon-abelian group actions. We construct the scheme through a new abstraction called swap-trapdoor function pairs. We give a simple and efficient compiler that converts the flavor of quantum bit commitments.
  arXiv  Detail & Related papers  (2022-10-12T07:40:05Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• Quantum Fully Homomorphic Encryption by Integrating Pauli One-time Pad with Quaternions [4.182969308816531]
  Quantum fully homomorphic encryption (QFHE) allows to evaluate quantum circuits on encrypted data. We present a novel QFHE scheme, which extends Pauli one-time pad encryption by relying on the quaternion of SU(2).
  arXiv  Detail & Related papers  (2020-12-08T04:54:02Z)
• Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
  We introduce a quantum copy-protection scheme for a class of evasive functions known as " compute-and-compare programs" We prove that our scheme achieves non-trivial security against fully malicious adversaries in the quantum random oracle model (QROM) As a complementary result, we show that the same scheme fulfils a weaker notion of software protection, called "secure software leasing"
  arXiv  Detail & Related papers  (2020-09-29T08:41:53Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)
• Backflash Light as a Security Vulnerability in Quantum Key Distribution Systems [77.34726150561087]
  We review the security vulnerabilities of quantum key distribution (QKD) systems. We mainly focus on a particular effect known as backflash light, which can be a source of eavesdropping attacks.
  arXiv  Detail & Related papers  (2020-03-23T18:23:12Z)

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.