Semigroup-homomorphic Signature

• URL: http://arxiv.org/abs/2503.17137v1
• Date: Fri, 21 Mar 2025 13:38:07 GMT
• Title: Semigroup-homomorphic Signature
• Authors: Heng Guo, Kun Tian, Fengxia Liu, Zhiyong Zheng,
• 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

• 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)
• 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.