Score:2

Can direct sums be used for deniable encryption?

jp flag

So I've recently become acquainted with deniable encryption and I got to thinking, wouldn't a way to do this involve using a group that can be decomposed into direct summands which already have well-established cryptosystems using a one-way projection map.

A one-way projection map is:

  1. Easy to compute with a trapdoor
  2. Hard to compute without this trapdoor
  3. Idempotent, repeated applications lead to no change.

So, $G$ is taken to be direct sum of two groups $G_1$ and $G_2$, which means that it comes equipped with non-unique projection maps which map surjectively from $G$ to $G_x$ (a special tough-to-compute one can be chosen).

The idea is then that cryptosystems can considered on the two groups independently because of these projection map. A general message exchange then looks like the following:

  1. Bob securely sends Alice $G=G_1\oplus G_2$ and $Enc_{pub}^1$ and $Enc_{pub}^2$.
  2. Alice encrypts $m_1$ and $m_2$ to $Enc_{pub}^1(m_1)\oplus Enc_{pub}^2(m_2)=c$
  3. Bob can then use $m_1=Denc_1(c_1) = Denc_1\circ\pi_1(c)$
  4. Or Bob can use $m_2=Denc_2(c_2) = Denc_2\circ\pi_2(c)$

Where $\pi_1$ and $\pi_2$ are projection maps to $G_1$ and $G_2$ respectively and the encrypting function on the original groups are $Enc_{pub}^x:G_x\to G_x$. Only Bob has access to $Denc_i$ and $\pi_i$.

The "under coercion" scenario is then that the appropriate decryption projection map can be surrendered and allow the cryptographer to escape having actually revealed the more valuable message.

Could this setup be considered "deniable"?

Patriot avatar
cn flag
@T Pluck Welcome to SE Crypto! You might want to edit your question and make it explicit.
poncho avatar
my flag
It appears that your idea can be summarized as "encrypt two different messages, concatenate the two ciphertext together, depending on which plaintext you want, decrypt the corresponding ciphertext and ignore the other". Is this correct?
ph flag
That's largely how I read it, though there is room for encode(G+G) to be different from encode(G) || encode(G)
T Pluck avatar
jp flag
Not quite, I've tried to pad out the question a little more to help ease understanding. For two plaintexts m_1 and m_2 the encryption stage encrypts both to a single g in G, it is up to receiver to either decrypt g to either m_1 or m_2 with the appropriate projection map.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.