Linearly Homomorphic Signature with Tight Security on Lattice

• URL: http://arxiv.org/abs/2412.01641v3
• Date: Sat, 15 Mar 2025 05:25:44 GMT
• Title: Linearly Homomorphic Signature with Tight Security on Lattice
• Authors: Heng Guo, Kun Tian, Fengxia Liu, Zhiyong Zheng,
• Abstract summary: This paper constructs the first lattice-based linearly homomorphic signature scheme that achieves tight security against existential unforgeability under chosen-message attacks (EUF-CMA) in the standard model.
• Score: 7.911831986965765
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: At present, in lattice-based linearly homomorphic signature schemes, especially under the standard model, there are very few schemes with tight security. This paper constructs the first lattice-based linearly homomorphic signature scheme that achieves tight security against existential unforgeability under chosen-message attacks (EUF-CMA) in the standard model. Furthermore, among existing schemes, the scheme proposed in this paper also offers certain advantages in terms of public key size, signature length, and computational cost.

Related papers

• Analytic Rényi Entropy Bounds for Device-Independent Cryptography [0.0]
  Device-independent (DI) cryptography represents the highest level of security.<n>We provide a simple method to obtain tighter finite-size security proofs for protocols based on the CHSH game.
  arXiv  Detail & Related papers  (2025-07-10T01:15:28Z)
• Linearly Homomorphic Ring Signature Scheme over Lattices [7.911831986965765]
  Homomorphic ring signature schemes combine the strong anonymity of ring signatures with the computability of homomorphic signatures.<n>No feasible homomorphic ring signature scheme currently exists.<n>We propose the first lattice-based linearly homomorphic ring signature scheme.
  arXiv  Detail & Related papers  (2025-07-03T03:43:40Z)
• Provably Secure Public-Key Steganography Based on Admissible Encoding [66.38591467056939]
  The technique of hiding secret messages within seemingly harmless covertext is known as provably secure steganography (PSS) PSS evolves from symmetric key steganography to public-key steganography, functioning without the requirement of a pre-shared key. This paper proposes a more general elliptic curve public key steganography method based on admissible encoding.
  arXiv  Detail & Related papers  (2025-04-28T03:42:25Z)
• LaSDVS : A Post-Quantum Secure Compact Strong-Designated Verifier Signature [0.47768369720936266]
  Strong-Designated Verifier Signature (SDVS) offers control by allowing the signer to specify and restrict the verifier of a signature. We propose an efficient post-quantum SDVS based on ideal lattices under the hardness assumptions of the Ring-SIS and Ring-LWE problems. LaSDVS achieves advanced security properties including strong unforgeability under chosen-message attacks, non-transferability, non-delegatability, and signer anonymity.
  arXiv  Detail & Related papers  (2025-04-23T09:48:18Z)
• Syzygy of Thoughts: Improving LLM CoT with the Minimal Free Resolution [59.39066657300045]
  Chain-of-Thought (CoT) prompting enhances the reasoning of large language models (LLMs) by decomposing problems into sequential steps.<n>We propose Syzygy of Thoughts (SoT)-a novel framework that extends CoT by introducing auxiliary, interrelated reasoning paths.<n>SoT captures deeper logical dependencies, enabling more robust and structured problem-solving.
  arXiv  Detail & Related papers  (2025-04-13T13:35:41Z)
• Semigroup-homomorphic Signature [7.911831986965765]
  We introduce, for the first time, a semigroup-homomorphic signature scheme. Under certain conditions, we prove that the security of this scheme is based on the hardness of the Short Solution (SIS) problem. We extend it to a linear semigroup-homomorphic signature scheme over lattices, and this scheme can also ensure privacy.
  arXiv  Detail & Related papers  (2025-03-21T13:38:07Z)
• GRIFFIN: Effective Token Alignment for Faster Speculative Decoding [52.905060461479856]
  GRIFFIN is a framework that incorporates a token-alignable training strategy and a token-alignable draft model. Experiments on LLaMA-series and Vicuna models demonstrate that GRIFFIN achieves an average acceptance length improvement of over 7% and a speedup ratio exceeding 8%.
  arXiv  Detail & Related papers  (2025-02-16T07:06:00Z)
• Deliberative Alignment: Reasoning Enables Safer Language Models [64.60765108418062]
  We introduce Deliberative Alignment, a new paradigm that teaches the model safety specifications and trains it to explicitly recall and accurately reason over the specifications before answering.<n>We used this approach to align OpenAI's o-series models, and achieved highly precise adherence to OpenAI's safety policies, without requiring human-written chain-of-thoughts or answers.
  arXiv  Detail & Related papers  (2024-12-20T21:00:11Z)
• Methods with Local Steps and Random Reshuffling for Generally Smooth Non-Convex Federated Optimization [52.61737731453222]
  Non-Machine Learning problems typically do not adhere to the standard smoothness assumption.<n>We propose and analyze new methods with local steps, partial participation of clients, and Random Random Reshuffling.<n>Our theory is consistent with the known results for standard smooth problems.
  arXiv  Detail & Related papers  (2024-12-03T19:20:56Z)
• Conformal Generative Modeling with Improved Sample Efficiency through Sequential Greedy Filtering [55.15192437680943]
  Generative models lack rigorous statistical guarantees for their outputs. We propose a sequential conformal prediction method producing prediction sets that satisfy a rigorous statistical guarantee. This guarantee states that with high probability, the prediction sets contain at least one admissible (or valid) example.
  arXiv  Detail & Related papers  (2024-10-02T15:26:52Z)
• 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)
• The Foundations of Tokenization: Statistical and Computational Concerns [51.370165245628975]
  Tokenization is a critical step in the NLP pipeline. Despite its recognized importance as a standard representation method in NLP, the theoretical underpinnings of tokenization are not yet fully understood. The present paper contributes to addressing this theoretical gap by proposing a unified formal framework for representing and analyzing tokenizer models.
  arXiv  Detail & Related papers  (2024-07-16T11:12:28Z)
• Generalized Quantum-assisted Digital Signature [2.187441808562386]
  This paper introduces an improved version of a recently proposed scheme whose information theoretic security is inherited by adopting QKD keys for digital signature purposes. Its security against forging is computed considering a trial-and-error approach taken by the malicious forger and GQaDS parameters are optimized via an analytical approach balancing between forgery and repudiation probabilities.
  arXiv  Detail & Related papers  (2024-06-28T15:04:38Z)
• An L-BFGS-B approach for linear and nonlinear system identification under $\ell_1$- and group-Lasso regularization [0.0]
  We propose a very efficient numerical method for identifying linear and nonlinear discrete-time state-space models. A Python implementation of the proposed identification method is available in the package jax-sysid.
  arXiv  Detail & Related papers  (2024-03-06T16:17:34Z)
• Coding-Based Hybrid Post-Quantum Cryptosystem for Non-Uniform Information [53.85237314348328]
  We introduce for non-uniform messages a novel hybrid universal network coding cryptosystem (NU-HUNCC) We show that NU-HUNCC is information-theoretic individually secured against an eavesdropper with access to any subset of the links.
  arXiv  Detail & Related papers  (2024-02-13T12:12:39Z)
• Constructing a fully homomorphic encryption scheme with the Yoneda Lemma [0.0]
  This paper redefines the foundations of asymmetric cryptography's homomorphic cryptosystems through the application of the Yoneda Lemma. It explicitly illustrates that widely adopted systems, including ElGamal, RSA, Benaloh, Regev's LWE, and NTRUEncrypt, directly derive from the principles of the Yoneda Lemma.
  arXiv  Detail & Related papers  (2024-01-24T06:46:26Z)
• A Robustness Analysis of Blind Source Separation [91.3755431537592]
  Blind source separation (BSS) aims to recover an unobserved signal from its mixture $X=f(S)$ under the condition that the transformation $f$ is invertible but unknown. We present a general framework for analysing such violations and quantifying their impact on the blind recovery of $S$ from $X$. We show that a generic BSS-solution in response to general deviations from its defining structural assumptions can be profitably analysed in the form of explicit continuity guarantees.
  arXiv  Detail & Related papers  (2023-03-17T16:30:51Z)
• In and Out-of-Domain Text Adversarial Robustness via Label Smoothing [64.66809713499576]
  We study the adversarial robustness provided by various label smoothing strategies in foundational models for diverse NLP tasks. Our experiments show that label smoothing significantly improves adversarial robustness in pre-trained models like BERT, against various popular attacks. We also analyze the relationship between prediction confidence and robustness, showing that label smoothing reduces over-confident errors on adversarial examples.
  arXiv  Detail & Related papers  (2022-12-20T14:06:50Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  We introduce the expected co-coercivity condition, explain its benefits, and provide the first last-iterate convergence guarantees of SGDA and SCO. We prove linear convergence of both methods to a neighborhood of the solution when they use constant step-size. Our convergence guarantees hold under the arbitrary sampling paradigm, and we give insights into the complexity of minibatching.
  arXiv  Detail & Related papers  (2021-06-30T18:32:46Z)
• Stabilizing Equilibrium Models by Jacobian Regularization [151.78151873928027]
  Deep equilibrium networks (DEQs) are a new class of models that eschews traditional depth in favor of finding the fixed point of a single nonlinear layer. We propose a regularization scheme for DEQ models that explicitly regularizes the Jacobian of the fixed-point update equations to stabilize the learning of equilibrium models. We show that this regularization adds only minimal computational cost, significantly stabilizes the fixed-point convergence in both forward and backward passes, and scales well to high-dimensional, realistic domains.
  arXiv  Detail & Related papers  (2021-06-28T00:14:11Z)
• MINA: Convex Mixed-Integer Programming for Non-Rigid Shape Alignment [77.38594866794429]
  convex mixed-integer programming formulation for non-rigid shape matching. We propose a novel shape deformation model based on an efficient low-dimensional discrete model.
  arXiv  Detail & Related papers  (2020-02-28T09:54:06Z)

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.