Sparse Subset Sum Problem

Sean

6/26/23, 5:50 PM

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)?

108

0 + 0

homomorphic-encryption

Score:1

Crypto

Mark

6/28/23, 10:19 PM

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.

0 + 0

Sean

6/28/23, 10:23 PM

Thanks a lot for the information!

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Sparse Subset Sum Problem

TH: ปัญหาผลรวมย่อยกระจัดกระจาย

RO: Problema sumei submulțimii rare

RU: Проблема суммы разреженных подмножеств

VI: Bài toán tổng tập hợp con thưa thớt

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.