0
$\begingroup$

Suppose Alice chooses a number $n\in Z_q$ and decompose it to its binary representation $b_0,b_1,...,b_d$. Then Alice encrypts these bits (can be any encryption scheme). Is it possible for Bob (who does not have Alice's decryption key) to read these encrypted bits and create a vector of size $q$ so that each entry is an encryption of $0$ except at index $n$ where there is an encryption of $1$. We cam assume that Alice can send to bob information (non interactively) of size at most log(n), while keeping the number $n$ private.

$\endgroup$

1 Answer 1

1
$\begingroup$

If you use FHE then Alice can encrypt the bits $b_i, i \in [d]$, where $d$ is about $\log q$, send it to Bob, and then have Bob run a demultiplexer circuit. The output should be $q$ ciphertexts where all of them are encryptions of $0$ except one that encrypts $1$ at index $n$. A recursive definition can be found in Protocol 2 of https://eprint.iacr.org/2014/137.pdf, although the paper is about MPC, it can also be applied for FHE since this circuit only involves addition and multiplication.

A more recent paper also has a description of the demux circuit but in a procedural form, see Section 3.2 of https://eprint.iacr.org/2022/757.pdf

$\endgroup$
1
  • $\begingroup$ That is great. Thank you very much! $\endgroup$
    – Doron
    Commented Jul 13, 2022 at 6:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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