Weakly Sublinear Compact FE from Succinct FE and XiO

I'm confused about a problem these days and I decided to seek an answer here. The question is about the section 4.1 of the paper LPST16. Let me recall the weakly sublinear compact FE scheme $\textrm{FE}$ from succinct functional encryption scheme $\textrm{sFE}$ and XiO.

• $(msk, pk) \gets \textrm{FE.Setup}(1^\lambda)$: it runs $(msk,pk) \gets \textrm{sFE.Setup}(1^\lambda)$
• $\textrm{ct} \gets \textrm{FE.Enc}(pk, m)$: it samples a puncturable PRF key and outputs $\textrm{ct} \gets \textrm{XiO}(1^\lambda, G_{pk,K,m})$ where $G_{pk,K,m}$ is a circuit with input length $n = \log s$ and $s$ is the max output length of the circuit $C$, and circuit $G_{pk,K,m}$ works as follows $$G_{pk,K,m}(i) = \textrm{sFE.Enc}(pk,(m,i); \textrm{PRF.Eval}(K,i))$$
• $sk_C \gets \textrm{FE.KeyGen}(msk; C)$ outputs $\textrm{sFE.KeyGen}(msk,C')$ where $C'$ on input $(m,i)$ outputs the $i$th bit of $C(m)$
• $y \gets \textrm{FE.Dec}(sk_C, \textrm{ct})$: $\textrm{ct}_i \gets \textrm{ct}(i)$ and $y_i \gets \textrm{sFE.Dec}(sk_C, \textrm{ct}_i)$ for each $i$ and outputs $y_1,\cdots,y_{2^n}$

Now I have two questions:

1. The paper speficies the circuit size of $G_{pk,K,m}$ is bounded by $poly(\lambda, |m|, \log s)$, how can we get this? to the best of my knowledge, I thinks the size of a circuit should be only related to the elements that are hardwired, is that correct? If this is correct, why the size is also polylog in $s$? More broadly, I also want to know how to calculate a circuit size.
2. Assume that the circuit size is also related to $s$ and $\log s$ is because of the puncturing, the second question is from my imagination. What if the circuit $G_{pk,K,m}$ outputs two encryptions, where one is over $(m,i)$ and another one is over $m$, and what is the circuit size of $G_{pk,K,m}$ now?

Replay

Category: complexity Time: 2016-07-28 Views: 0