Sparse Subset Sum Problem

Question

In Gentry's seminal results on FHE (https://dl.acm.org/doi/10.1145/1536414.1536440), it is assumed that the sparse subset set problem is hard. It looks like there is a follow up paper on the concrete parameter of the subset size (https://eprint.iacr.org/2011/567.pdf), which mentions that Gentry's choice of subset size is too aggressive (e.g., 15). But in its section 5 (Discussion), it also mentioned that the real assumption used Gentry's paper is the Hidden Sparse Subset Problem and its analysis does not apply.

So, regarding the choice of subset size, what is regarded as a "safe" parameter for the hidden sparse subset problem right now (e.g., given the size of the entire set of weights be 32k used in Gentry's paper)?

Answer 1

There have been stronger attacks against Gentry's FHE scheme, in particular I believe the 2016 work of Biasse + Song (quantumly) breaks it in polynomial time (and classically in sub-exponential time). Given this relative weakness compared to other FHE schemes, I have not seen people try to concretely instantiate Gentry's work (say in the last ~5 years --- of course there was early work along these lines).

Discussion of this can be found in Bernstein's work, for example this. In general, if you are worrying about concrete parameter sizes for FHE implementations, I would direct you to the Homomorphic Encryption Standard. It does not include Gentry's scheme, likely due to the aforementioned attacks. This is to explicitly say that it is unclear if there is a "safe" parameterization cryptographers would agree on --- most try to work with the standard problems of LWE/SIS (and their algebraic variants) now instead.