HammR: A ZKP Protocol for Fixed Hamming-Weight Restricted-Entry Vectors

Felice Manganiello; Freeman Slaughter

Paper 2025/475

HammR: A ZKP Protocol for Fixed Hamming-Weight Restricted-Entry Vectors

Felice Manganiello

, Clemson University

Freeman Slaughter

, Clemson University

Abstract

In this paper, we introduce $HammR$ , a generic Zero-Knowledge Proof (ZKP) protocol demonstrating knowledge of a secret vector that has a fixed Hamming weight with entries taken from a shifted multiplicative group. As special cases, we are able to directly apply this protocol to restricted vectors and to rank-1 vectors, which are vectors with entries that lie in a dimension one subspace of . We show that these proofs can be batched with low computational overhead, and further prove that this general framework is complete, sound, and zero-knowledge, thus truly a genuine ZKP. Finally, we present applications of to various Syndrome Decoding Problems, including the Regular and Restricted SDPs, as well as other implementations such as lookup instances, proof of proximity, and electronic voting protocols.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Contact author(s): manganm @ clemson edu
fslaugh @ g clemson edu
History: 2025-03-14: approved; 2025-03-12: received; See all versions
Short URL: https://ia.cr/2025/475
License: CC BY

BibTeX

@misc{cryptoeprint:2025/475,
      author = {Felice Manganiello and Freeman Slaughter},
      title = {{HammR}: A {ZKP} Protocol for Fixed Hamming-Weight Restricted-Entry Vectors},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/475},
      year = {2025},
      url = {https://eprint.iacr.org/2025/475}
}