2
$\begingroup$

In Evaluating 2-DNF Formulas on Ciphertexts stated that

decryption in this system takes polynomial time in the size of the message space T. Therefore, the system as described above can only be used to encrypt short messages

Is there any other extension with the same properties of (any number of addition and one multiplication operation on the ciphertext) but also allows bigger message space?

In my search, I encounter only in Converting Pairing-Based Cryptosystems from Composite-Order Groups to Prime-Order Groups, but it does not solve that limitation.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ What is [2] here? It says actually, when the message space come bigger, the decryption time become much longer. $\endgroup$ – kelalaka Feb 21 '19 at 20:45
  • $\begingroup$ I edited and added [2] $\endgroup$ – user1387682 Feb 21 '19 at 23:03
  • $\begingroup$ Is there a specific need for 2-DNF? $\endgroup$ – kelalaka Feb 21 '19 at 23:09
  • $\begingroup$ Yes, but I need to extract only whether the result of the 2-DNF is equal to 0 or anything else. (Thus, I multiply it with random r in my scheme to obfuscate the exact value and hence need a bigger message space). $\endgroup$ – user1387682 Feb 21 '19 at 23:18
  • $\begingroup$ 2-DNF is already semantically secure therefore to see it is 0 you need to decrypt. isn't FHE is better for you where you can compare? Note: there is no unbounded message space. $\endgroup$ – kelalaka Feb 21 '19 at 23:32
1
$\begingroup$

There is a scheme whose purpose is exactly that, the LWE-based BGN-like encryption scheme. In general, we do not know how to achieve large message space for homomorphic encryption using discrete-log-style crypto; all known current solutions require lattice-based cryptography.

EDIT: reading the comments on your question, it seems you want to leak only whether the output is zero or not, by masking with a large random $r$ multiplicatively. But the standard BGN cryptosystem already allows that: the parties can always decrypt $g_t^{\mathsf{DFN(x)}}$ with BGN ($g_t$ is a generator of the target group), only the discrete logarithm at the end requires the message space to be small. However, seeing $g_t^{r\cdot\mathsf{DFN(x)}}$ for a large random $r$ already allows to see efficiently whether $\mathsf{DFN(x)} = 0$ or not: if it is equal to zero, then $g_t^{r\cdot\mathsf{DFN(x)}} = 1$; otherwise, $g_t^{r\cdot\mathsf{DFN(x)}}$ is just a random group element since $r$ is random.

Improve this answer
$\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.