1
$\begingroup$

To my best of knowledge, I have kown there exists randomized encoding scheme whose encoding circuit is in $NC^1$, fully homomorphic encryption scheme whose decryption circuit is in $NC^1$, and functional encryption scheme for $NC^1$ functions. Now I'm curious about is there any functional encryption scheme whose key generation circuit is in $NC^1$ ?

$\endgroup$
1
$\begingroup$

Attribute-Based Encryption schemes (ABE) are definitionally a sub-category of FE. Furthermore, non-monotonic ABEs (NM-ABE) can encode decisions from $NC^1$, so yes, there are FE-schemes that are restricted to $NC^1$.

There are both ciphertext-policy ABEs (CP-ABE), key-policy ABEs (KP-ABE) and mixtures of them (dual-policy, or DP-ABEs), so it is possible to embed the circuit of desired complexity into both ciphertext and key (or key generation).

The most general FE schemes can encode decisions from the whole of $NC$, so they are also able to encode circuits in $NC^1$. FE-schemes also exist in both KP- and CP-flavors.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.