Semigroup-homomorphic Signature

• URL: http://arxiv.org/abs/2503.17137v1
• Date: Fri, 21 Mar 2025 13:38:07 GMT
• Title: Semigroup-homomorphic Signature
• Abstract summary: We introduce, for the first time, a semigroup-homomorphic signature scheme.<n>Under certain conditions, we prove that the security of this scheme is based on the hardness of the Short Solution (SIS) problem.<n>We extend it to a linear semigroup-homomorphic signature scheme over lattices, and this scheme can also ensure privacy.
• Score: 7.911831986965765
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In 2002, Johnson et al. posed an open problem at the Cryptographers' Track of the RSA Conference: how to construct a secure homomorphic signature on a semigroup, rather than on a group. In this paper, 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 Integer Solution (SIS) problem and is tightly secure. Furthermore, we extend it to a linear semigroup-homomorphic signature scheme over lattices, and this scheme can also ensure privacy.

Related papers

• CryptanalysisBench: Can LLMs do Cryptanalysis? [76.79639292270497]
  We introduce CryptanalysisBench, 191 tasks across six families of cryptographic primitives.<n>Our benchmark consists of three tiers: (i) primitives with known practical breaks; (ii) primitives with no known practical break, evaluated both at full strength and as scaled-down variants.<n>Five frontier models break 65%-86% of Tier 1 schemes, 6-12 Tier-2 schemes at full strength, and 24-61 across all scaled-down variants.
  arXiv  Detail & Related papers  (2026-07-20T22:09:40Z)
• Introducing GRAFHEN: Group-based Fully Homomorphic Encryption without Noise [0.0]
  We present GRAFHEN, a new cryptographic scheme which offers Fully Homomorphic Encryption without the need for bootstrapping (or in other words, without noise)<n>We achieve this using encodings in groups. The groups are represented on a machine using rewriting systems.<n>In this way the subgroup membership problem, which an attacker would have to solve in order to break the scheme, becomes maximally hard, while performance is preserved.
  arXiv  Detail & Related papers  (2025-10-24T14:07:36Z)
• DiffGRM: Diffusion-based Generative Recommendation Model [63.35379395455103]
  Generative recommendation (GR) is an emerging paradigm that represents each item via a tokenizer as an n-digit semantic ID (SID)<n>We propose DiffGRM, a diffusion-based GR model that replaces the autoregressive decoder with a masked discrete diffusion model (MDM)<n> Experiments show consistent gains over strong generative and discriminative recommendation baselines on multiple datasets.
  arXiv  Detail & Related papers  (2025-10-21T03:23:32Z)
• 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)
• Secured Encryption scheme based on the Ree groups [0.0]
  An improved design of a cryptosystem based on small Ree groups is proposed. We have changed the encryption algorithm and propose to use a logarithmic signature for the entire Ree group.
  arXiv  Detail & Related papers  (2025-04-24T20:21:02Z)
• Encryption scheme based on Automorphism Group of Hermitian Function Field with Homomorphic Encryption [0.0]
  We enhance the Hermitian function field-based encryption scheme with homomorphic encryption capabilities. Both the attack complexity and the encrypted message size are directly correlated with the order of the group.
  arXiv  Detail & Related papers  (2025-04-14T22:39:40Z)
• Nearly Optimal Sample Complexity of Offline KL-Regularized Contextual Bandits under Single-Policy Concentrability [49.96531901205305]
  We propose the emphfirst algorithm with $tildeO(epsilon-1)$ sample complexity under single-policy concentrability for offline contextual bandits.<n>Our proof leverages the strong convexity of the KL regularization, and the conditional non-negativity of the gap between the true reward and its pessimistic estimator.<n>We extend our algorithm to contextual dueling bandits and achieve a similar nearly optimal sample complexity.
  arXiv  Detail & Related papers  (2025-02-09T22:14:45Z)
• Linearly Homomorphic Signature with Tight Security on Lattice [7.911831986965765]
  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.
  arXiv  Detail & Related papers  (2024-12-02T15:51:57Z)
• Cloning Games, Black Holes and Cryptography [50.022147589030304]
  We introduce a new toolkit for analyzing cloning games.<n>This framework allows us to analyze a new cloning game based on binary phase states.<n>We show that the binary phase variantally optimal bound offers quantitative insights into information scrambling in idealized models of black holes.
  arXiv  Detail & Related papers  (2024-11-07T14:09:32Z)
• CodeChameleon: Personalized Encryption Framework for Jailbreaking Large Language Models [49.60006012946767]
  We propose CodeChameleon, a novel jailbreak framework based on personalized encryption tactics. We conduct extensive experiments on 7 Large Language Models, achieving state-of-the-art average Attack Success Rate (ASR) Remarkably, our method achieves an 86.6% ASR on GPT-4-1106.
  arXiv  Detail & Related papers  (2024-02-26T16:35:59Z)
• 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]
  The paper redefines the foundations of asymmetric cryptography's homomorphic cryptosystems through the application of the Yoneda Lemma.<n>It demonstrates that widely adopted systems, including ElGamal, RSA, Benaloh, Regev's LWE, and NTRUEncrypt, are directly derived from the principles of the Yoneda Lemma.<n>This synthesis leads to the creation of a holistic homomorphic encryption framework, the Yoneda Encryption Scheme.
  arXiv  Detail & Related papers  (2024-01-24T06:46:26Z)
• Lattice attack on group ring NTRU: The case of the dihedral group [2.106410091047004]
  This paper shows that dihedral groups do not guarantee better security against lattice attacks on the public key of NTRU-like cryptosystems. We prove that retrieving the private key is possible by solving the SVP in two lattices with half the dimension of the original lattice generated for GR-NTRU based on dihedral groups.
  arXiv  Detail & Related papers  (2023-09-15T10:50:46Z)
• Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [69.15976031704687]
  We propose IAC (Instance-Adaptive Clustering), the first algorithm whose performance matches the instance-specific lower bounds both in expectation and with high probability.<n>IAC maintains an overall computational complexity of $ mathcalO(n, textpolylog(n) $, making it scalable and practical for large-scale problems.
  arXiv  Detail & Related papers  (2023-06-18T08:46:06Z)
• Publicly-Verifiable Deletion via Target-Collapsing Functions [81.13800728941818]
  We show that targetcollapsing enables publiclyverifiable deletion (PVD) We build on this framework to obtain a variety of primitives supporting publiclyverifiable deletion from weak cryptographic assumptions.
  arXiv  Detail & Related papers  (2023-03-15T15:00:20Z)
• 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)

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.