Problem
Suppose there is an entity with some users. The users are split into subsets (determined by the entity) and the entity needs to create public commitments to these subsets such that only a user can determine which set they are in. The sets need to be some minimum size, $m$.
More formally
Let $U$ be a set of user IDs--we want some flexibility here so the definition is left loose for now. Only the entity knows $U$, and each user only knows their ID. Let $\mathbb{V}$ be the power set of $U$: $\mathbb{V}=\mathcal{P}(U)=\{V:V \subseteq U\}$, and let $\mathbb{V}^* \subset \mathbb{V}$ be the subset split chosen by the entity. We need 2 functions:
$$
\begin{align*}
f&:\mathbb{V}^*\to K \\
g&:K \times U \to \mathbb{Z}_2
\end{align*}
$$
where $K$ some finite space. $f$ is the commitment function that is used by the entity to create a commitment $k$ to a specific subset of users. $k$ is made public. $g$ is the function that the user would use to check if they are in a given subset.
$f$ and $g$ need to have the following properties:
- $\forall \space V \in \mathbb{V}^* \quad f(V)=k \implies g(v,k)=1 \space \forall \space v \in V$
- $\forall \space V \in \mathbb{V}^* \quad f(V)=k \implies g(u,k)=0 \space \forall \space u \in U-V$
- [not sure about the wording here] If an adversary has access to $k=f(V)$ then they are not able to determine any of the following in polynomial time with non-negligible probability:
- any $v \in V$
- any $u \in U \text{ s.t. } u \notin V$
- $|V|$
Find $f, g, K$.
One possible solution
We can make a start on $f, g, K$ by using polynomials. First, construct the disjoint split of the users:
$$
\mathbb{V}^*= \{ V_1, V_2, ... V_n : V_i \in \mathbb{V}, V_i \text{ disjoint}, \cup_{i}V_i=U, V_i \neq \emptyset \}
$$
Let $k_i=f(V_i)$ and $v_{i,j} \in V_i$ be the $j^{th}$ element of $V_i$. We define our polynomial $p$ like so:
$$
\begin{align*}
p(x)=&\prod_{i=1}^{n}\prod_{j=1}^{|V_i|}(x-k_iv_{i,j})
\end{align*}
$$
and our $g$ like so:
$$
g(u,k)=
\begin{cases}
1 : p(uk)=0 \\
0 : \text{otherwise}
\end{cases}
$$
and our $f$ can be a cryptographic hash function, which defines $K$. Depending on which space we want $p$ & $v$ to live in we would have to adjust the definition of $p$ & $g$ so $k_iv_{i,j}$ is well defined.
A first look at our setup tells us we have properties #1 & #2, as long as our space chosen for $p$ is sufficiently large such that $\text{Pr}[k_av_{a,b}=k_cv_{c,d}, a \neq c] < \epsilon$. Property #3 is not achieved because any adversary that can factor the polynomial at least once will be able to access a users identity and know which subset they are in, in polynomial time.
It may be possible to achieve #3 by embedding the polynomial into an elliptic curve group via the function $p \to G^p$ where $G$ is a generator of the group. The intractability of the discrete logarithm problem there could be what gives us #3.
