A Zero-Knowledge Proof for the Hidden Subset Sum Problem - Barros, Charles F. de (Anais do Simpósio Brasileiro de Cibersegurança (SBSeg); 2017: Anais do XVII Simpósio Brasileiro de Segurança da Informação e de Sistemas Computacionais, 2017)
In this paper, we propose a zero-knowledge proof for a special case of the hidden subset sum problem. This problem was presented by [Boyko et al. 1998] as the underlying problem of methods for generating random pairs of the form (x, g x (mod p)) using precomputations. The proof we propose is an adaptation of a zero-knowledge protocol for the subset sum problem presented by [Blocki 2009].