Advanced attribute-based protocol based on the modified secret sharing scheme

As it is noted in [6], that we are unable to realize most monotone access structures with a standard SS scheme. However, one can modify the structures that can be realized efficiently, such that each trustee holds only one secret value, which we refer as a master key. With the use of the master key, a trustee is able to calculate all required shares.

We define the scheme with the use of the roles as defined above.

Let us begin with an illustrative example. Assume that a dealer wants to share a secret $s\in\mathbb{Z}_{q}$ between trustees Alice ($A$), Bob ($B$), Charlie ($C$), and David ($D$) according to the following access formula:

where $X_{p,j}$ is a Boolean variable that represents a trustee $p$ and appeared $j^{\rm th}$ time in the formula. Let us introduce an address for each variable as its position in the formula as follows:

Thus, $X_{A,1}.{\rm address}=0$, $X_{B,1}.{\rm address}=1$, $X_{B,2}.{\rm address}=2$, and so on.

To share a secret, the dealer first gives each trustee $p\in\{A,B,C,D\}$ a value ${\rm mk}_{p}$, which is chosen uniformly at random from some domain $\mathcal{K}$. Next we refer to ${\rm mk}_{p}$ as a master key belonging to a trustee $p$.

Let us then assume that the dealer and trustees have access to independent random oracles family $\{{\rm RO}_{i}:i\in\mathbb{Z}_{q}\}$ with an output domain in $\mathbb{Z}_{q}$. In order to generate a share that corresponds to a variable $X_{p,j}$, a trustee $p$ has to query the random oracle ${\rm RO}_{{\rm mk}_{p}}$ with $X_{p,j}.{\rm address}$. For example, the shares for the defined access formula are computed in this way:

Since each random oracle is independent, every share is a random value from $\mathbb{Z}_{q}$. As a result, a sum of shares, e.g. $s^{\prime}:=(s_{A,1}+s_{B,2})({\rm mod}\ q)$, is also a uniformly random variable from $\mathbb{Z}_{q}$. To make it possible to reconstruct a secret $s$ by trustees $A$ and $B$, we add a publicly known value $y_{1}$ to this bracket, such that $(y_{1}+s^{\prime})({\rm mod}\ q)=s$.

Consequently, we modify our access formula into the following form:

where $Y_{i}$ are Boolean variables that correspond to fictitious trustees, whose shares $y_{i}$ are considered to be publicly known to every actual trustee. The value of $y_{i}$ is computed in such a way that a reconstruction of secret becomes possible. We note that $y_{i}$ is computed by the dealer, since he knows all the master keys.

Below we present our scheme in a more formal and efficient way.

Let $n$ be a security parameter, $\mathbb{F}_{q}=\{f_{k}:k\in\mathcal{K}\}$ be a PRF family, where $q\geq 2^{n}$ and $f_{k}:\mathbb{Z}_{q}\rightarrow\mathbb{Z}_{q}$ with $|\mathcal{K}|=q$. Here we chose $f_{k}:\mathcal{D}\rightarrow\mathcal{E}$ with $\mathcal{D}=\mathbb{Z}_{q}$, but one can choose another domain. Note that $\mathcal{E}=\mathbb{Z}_{q}$, so we are able to sum the shares in $\mathbb{Z}_{q}$. Let $H_{q}$ be a family of all functions $\mathbb{Z}_{q}\rightarrow\mathbb{Z}_{q}$. Let $l={\rm poly}(n)$ be the maximum size of monotone formula that we can use efficiently and let $l^{\prime}:=l/2$. Hereby the size of the monotone formula is the number of times that variables occur in the formula.

The roles for the scheme (dealer, trustees, and party) are defined in the previous subsection.

First, we define a modifying function $g_{s}(\phi)$, where $\phi$ is an access formula, whose size is less than $l^{\prime}+1$ and it is written in $j$-notation, and $s\in\mathbb{Z}_{q}$. Let $X_{p,j}$ be a variable, which represents a trustee $p$ and it is appeared $j^{\rm th}$ time in the formula. Let $X_{p,j}.{\rm address}$ represents the position of the variable in $\phi$. Let ${\rm mk}_{p}\in\mathcal{K}$ be the value of $p$’s master key. We denote $Y_{i}$ as a variable that corresponds to a fictitious trustee and $y_{i}$ as the value of his share. We use $\phi_{i}$ as subformula. Since every formula can be written in the following form:

where $\circ$ stands for either $\land$ or $\lor$.

Let is introduce a global counter $\alpha$, which is initialized with $1$. There are three separate cases to look at:

• •

  $g_{s}(X_{p_{1},k_{1}}\land\ldots\land X_{p_{t},k_{t}})=(X_{p_{1},k_{1}}\land\ldots\land X_{p_{t},k_{t}}\land Y_{\alpha})$,
  where $t\geq 1$ and $y_{i}=s-f_{{\rm mk}_{p_{1}}}(X_{p_{1},k_{1}}.{\rm address})-\ldots-f_{{\rm mk}_{p_{t}}}(X_{p_{t},k_{t}}.{\rm address})({\rm mod}\ q)$, and the counter $\alpha$ is incremented $\alpha:=\alpha+1$.

• •

  $g_{s}(X_{p_{1},k_{1}}\land\ldots\land X_{p_{t},k_{t}}\land\phi_{1}\land\ldots\land\phi_{j})=(X_{p_{1},k_{1}}\land\ldots\land X_{p_{t},k_{t}}\land g_{s_{1}}(\phi_{1})\land\ldots\land g_{s_{j}}(\phi_{j}))$, where $j\geq 1$, $\phi_{i}=\lor(\cdot)$ with at least one operator, $s_{i}\stackrel{{\scriptstyle\$}}{{\leftarrow}}\mathbb{Z}_{q}$ for $i\in\{1,\ldots,j-1\}$ and $s_{j}:=s-f_{{\rm mk}_{p_{1}}}(X_{p_{1},k_{1}}.{\rm address})-\ldots-f_{{\rm mk}_{p_{t}}}(X_{p_{t},k_{t}}.{\rm address})-s_{1}-\ldots-s_{j-1}\ ({\rm mod}~{}q)$.

• •

  $g_{s}(X_{p_{1},k_{1}}\lor\ldots\lor X_{p_{t},k_{t}}\lor\phi_{1}\lor\ldots\lor\phi_{j})=(g_{s}(X_{p_{1},k_{1}})\lor\ldots\lor g_{s}(X_{p_{t},k_{t}})\lor g_{s}(\phi_{1})\lor g_{s}(\phi_{2})\lor\ldots\lor g_{s}(\phi_{j}))$.

Let us clarify that the address of a variable is the number of the position of that variable in the formula $\phi$ (conventionally, we count from left to right).

Now we can describe our advanced SS scheme. To share a secret the dealer should follow these steps:

1. 1.

   Choose a secret $s\stackrel{{\scriptstyle\$}}{{\leftarrow}}\mathbb{Z}_{q}$.

2. 2.

   Choose a master key for each trustee in the union $\mathcal{P}$ uniformly at random from $\mathcal{K}$ (for each $p\in\mathcal{P}:{\rm mk}_{p}\stackrel{{\scriptstyle\$}}{{\leftarrow}}\mathcal{K}$).

3. 3.

   Choose a monotone formula $\phi$ of size less or equal to $l^{\prime}$, which represents an access structure.

4. 4.

   Evaluate $\phi^{\prime}=g_{s}(\phi)$.

5. 5.

   Publish $\phi^{\prime}$, so that the values $y_{i}$ are available for everyone.

To reconstruct a secret a party should follow these steps:

1. 1.

   Each trustee $p$ in the party has to evaluate their shares:
   $s_{p,j}=f_{{\rm mk}_{p}}(X_{p,j}.{\rm address})$.

2. 2.

   Using the corresponding shares and public values $y_{i}$, a verified party can calculate the secret $s$ according to the way it is shared.

Here we introduce a notion of the security model that is used for our scheme, which is similar to the Selective-Id model [7, 8, 9].

Consider a group of users, where each user posses a list of attributes. Let $\mathcal{P}$ be a set of all existing attributes. Let us call a community a subgroup of users, who possess a particular attribute $p\in\mathcal{P}$. In what follows, we refer to the community $p$ as a subgroup of users that possess an attribute $p$. We note that a user can belong to several communities if he has more than one attribute.

Let $n\in\mathbb{N}$ be a security parameter, $G$ be a multiplicative group of a prime order $q$, where $2^{n}<q<2^{n+1}$ in which DDH assumption is considered to be true, $g$ is a generator of that group, $H_{q}$ is a family of all functions $\mathbb{Z}_{q}\rightarrow\mathbb{Z}_{q}$, and $\mathbb{F}_{q}=\{f_{k}:\mathbb{Z}_{q}\rightarrow\mathbb{Z}_{q}\}_{k\in G}$ is a PRF family. We construct the advanced ABE scheme based on the advanced SS scheme in the following form.

Setup:

Each community $p$ in the universe $\mathcal{P}$ generates their secret key ${\rm sk}_{p}\stackrel{{\scriptstyle\$}}{{\leftarrow}}\mathbb{Z}_{q}$ and a correspong public key ${\rm pk}=g^{{\rm sk}_{p}}$. Then the public key is shared among the whole group of users. So that the set of public keys $PK=\{{\rm pk}_{p}=g^{{\rm sk}_{p}}:p\in\mathcal{P}\}$ is assumed to be known to every user in the group.

Encryption $(M,PK,\phi,\mathbb{F}_{q})$:

To encrypt a message $M\in\mathbb{Z}_{q}$ under public keys $PK$ and formula $\phi$, which represents some monotone access structure, one generates $s\stackrel{{\scriptstyle\$}}{{\leftarrow}}\mathbb{Z}_{q},e\stackrel{{\scriptstyle\$}}{{\leftarrow}}\mathbb{Z}_{q}$ and computes the ciphertext in the following form $E=\{E^{\prime}=M+s({\rm mod}\ q),g^{e},\phi^{\prime}=g_{s}(\phi),y_{1},\ldots,y_{t}\}$, where $g_{s}(\cdot),y_{1},\ldots,y_{t}$ come from the advanced SS scheme based on PRF family $\mathbb{F}_{q}$ and the corresponding master keys are calculated as ${\rm mk}_{p}=g^{{\rm sk}_{p}\cdot e}$.

Decryption $(E,SK,Attr,\mathbb{F}_{q})$:

, where $SK$ is a set of all secret keys known to a concrete user and $Attr$ is a set of attributes he posseses. For each ${\rm sk}_{p}\in SK$, a user calculates the master key ${\rm mk}_{p}=(g^{e})^{{\rm sk}_{p}}$. Then if $Attr$ satisfies the access structure, then the secret $s$ can be reconstructed using $MK=\{{\rm mk}_{p}\}$, $\phi^{\prime}$ and $y_{1},\ldots,y_{t}$. The message is obtained from $E^{\prime}$ as $M=E^{\prime}-s({\rm mod}\ q)$.

In order to provide a formal security analysis of the advanced ABE scheme, we introduce the following definition.

Below we prove that the security of our scheme in the attribute-based Selective-Set model reduces to the hardness of the DDH challenge and pseudorandomness of the function family.