Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Linearly Homomorphic Signatures over Binary Fields and New Tools for Lattice-Based Signatures

Dan Boneh, David Mandell Freeman

Published Jan 1, 2011• 239 citations
Publisher
DOI
10.1007/978-3-642-19379-8_1

Related papers

A New Fully Homomorphic Signatures from Standard Lattices

Yukun Wang, Mingqiang Wang

Lecture notes in computer science•Jan 1, 2020•9 citations

Leveled Lattice-Based Linearly Homomorphic Signature Scheme in the Standard Model for Network Coding

Fenghe Wang, Shaoquan Shi, Chunxiao Wang

Communications in computer and information science•Jan 1, 2019•3 citations

Two-Round Threshold Lattice-Based Signatures from Threshold Homomorphic Encryption

Kamil Doruk Gür, Jonathan I. Katz, Tjerand Silde

Lecture notes in computer science•Jan 1, 2024•34 citations

Quantum homomorphic signature

Tao Shang, Xiaojie Zhao, Chao Wang +1 more

Quantum Information Processing•Oct 22, 2014•41 citations

Linearly Homomorphic Signatures over Binary Fields and New Tools for Lattice-Based Signatures.

Dan Boneh, David Mandell Freeman

We propose a linearly homomorphic signature scheme that authenticates vector subspaces of a given ambient space. Our system has several novel properties not found in previous proposals: • It is the first such scheme that authenticates vectors defined over binary fields; previous proposals could only authenticate vectors with large or growing coefficients. • It is the first such scheme based on the problem of finding short vectors in integer lattices, and thus enjoys the worst-case security guarantees common to lattice-based cryptosystems. Our scheme can be used to authenticate linear transformations of signed data, such as those arising when computing mean and Fourier transform or in networks that use network coding. Our construction gives an example of a cryptographic primitive — homomorphic signatures over F2 — that can be built using lattice methods, but cannot currently be built using bilinear maps or other traditional algebraic methods based on factoring or discrete log type problems. Security of our scheme (in the random oracle model) is based on a new hard problem on lattices, called k-SIS, that reduces to standard average-case and worst-case lattice problems. Our formulation of the k-SIS problem adds to the “toolbox” of lattice-based cryptography and may be useful in constructing other lattice-based cryptosystems. As a second application of the new k-SIS tool, we construct an ordinary signature scheme and prove it k-time unforgeable in the standard model assuming the hardness of the k-SIS problem. Our construction can be viewed as “removing the random oracle” from the signatures of Gentry, Peikert, and Vaikuntanathan at the expense of only allowing a small number of signatures.

•Jan 1, 2010•2 citations

A efficient lattice-based forward-secure linearly homomorphic signature scheme for network coding

Bin Wu, Caifen Wang, Yahong Li +1 more

Abstract The property that linearly homomorphic signature (LHS) enables linear computation on signed data makes this primitive commonly used to secure the network coding based application against pollution attacks. The security of LHS wholly depends on the security of secret signing keys; once a secret key is compromised, the application system’ security will be broken. However, as relatively insecure mobile devices are increasingly used in network coding application systems, the key exposure issue is becoming more prevalent. On the other hand, with the quantum technology development, some existing LHS schemes based on some traditional number-theoretic primitives are susceptible to quantum cryptanalysis. Hence, facing the dual threats of the exposure of secret keys in reality and the future effiffifficient quantum computers, we integrate forward security into LHS, and present a forward-secure identity-based LHS scheme (FSIBLHS) based on lattice assumptions, which achieves post-quantum security, and even if the current secret key is compromised, the validity of signatures of previous time periods is still guaranteed. We defifine the fifirst security model on forward security of LHS, and prove that the proposed scheme can resist adaptively chosen identity and datasets attack under lattice assumption. Moreover, compared with previous related works, the performance analysis shows that our scheme enjoys a comparable computation cost and has a lower communication cost, and provides higher security and stronger functionality.

Telecommunication Systems•Nov 25, 2024•2 citations
We propose a linearly homomorphic signature scheme that authenticates vector subspaces of a given ambient space. Our system has several novel properties not found in previous proposals: • It is the first such scheme that authenticates vectors defined over binary fields; previous proposals could only authenticate vectors with large or growing coefficients. • It is the first such scheme based on the problem of finding short vectors in integer lattices, and thus enjoys the worst-case security guarantees common to lattice-based cryptosystems. Our scheme can be used to authenticate linear transformations of signed data, such as those arising when computing mean and Fourier transform or in networks that use network coding. Our construction gives an example of a cryptographic primitive — homomorphic signatures over F2 — that can be built using lattice methods, but cannot currently be built using bilinear maps or other traditional algebraic methods based on factoring or discrete log type problems. Security of our scheme (in the random oracle model) is based on a new hard problem on lattices, called k-SIS, that reduces to standard average-case and worst-case lattice problems. Our formulation of the k-SIS problem adds to the “toolbox” of lattice-based cryptography and may be useful in constructing other lattice-based cryptosystems. As a second application of the new k-SIS tool, we construct an ordinary signature scheme and prove it k-time unforgeable in the standard model assuming the hardness of the k-SIS problem. Our construction can be viewed as “removing the random oracle” from the signatures of Gentry, Peikert, and Vaikuntanathan at the expense of only allowing a small number of signatures.
Abstract The property that linearly homomorphic signature (LHS) enables linear computation on signed data makes this primitive commonly used to secure the network coding based application against pollution attacks. The security of LHS wholly depends on the security of secret signing keys; once a secret key is compromised, the application system’ security will be broken. However, as relatively insecure mobile devices are increasingly used in network coding application systems, the key exposure issue is becoming more prevalent. On the other hand, with the quantum technology development, some existing LHS schemes based on some traditional number-theoretic primitives are susceptible to quantum cryptanalysis. Hence, facing the dual threats of the exposure of secret keys in reality and the future effiffifficient quantum computers, we integrate forward security into LHS, and present a forward-secure identity-based LHS scheme (FSIBLHS) based on lattice assumptions, which achieves post-quantum security, and even if the current secret key is compromised, the validity of signatures of previous time periods is still guaranteed. We defifine the fifirst security model on forward security of LHS, and prove that the proposed scheme can resist adaptively chosen identity and datasets attack under lattice assumption. Moreover, compared with previous related works, the performance analysis shows that our scheme enjoys a comparable computation cost and has a lower communication cost, and provides higher security and stronger functionality.