Orthogonal Lock

Question

Is there a cryptographic function that employs two locks: first 'Lock A', and then on top of that 'Lock B' but it permits unlocking 'Lock A' before 'Lock B' to read the message?

Answer 1

Sure, you can build something like this using lattices. The high level idea is to note that a LWE sample

$$(A, A\vec s + \vec e)$$

gives you a (pseudorandom) encryption of 0. We can therefore combine two LWE samples to get

$$(A_0, A_1, A_0\vec s_0 + \vec e_0 + A_1\vec s_1 + \vec e_1)$$

as a pseudorandom encryption of 0. To decrypt you will have to remove both $A_0\vec s_0$ and $A_1\vec s_1$, and this can be done in any order. To have it be a useful cryptosystem we will also have to include a message, but this is standard, and I'll do it below.

---

Define the cryptosystem to be the triple of algorithms:

• KeyGen: Samples $\vec s_0, \vec s_1\gets\mathbb{Z}_q^n$ uniformly and independently

• Enc(m):

  1. Sample $A_0, A_1\gets \mathbb{Z}_q^{n\times n}$ uniformly and independently.
  2. Sample $\vec e_0,\vec e_1\gets \chi_\sigma^n$ from a "small" distribution (here, Discrete Gaussian of parameter $\sigma$. You could also do it from $[-n, n]^n\cap\mathbb{Z}^n$ uniformly if you want implementation simplicity).
  3. Return $(A_0, A_1, A_0\vec s_0 + A_1\vec s_1 + \vec e_0 + \vec e_1 + (q/2)\vec m)$, where $2\mid q$ by assumption, and $\vec m\in\{0,1\}^n$

• $\mathsf{Dec}(A_0, A_1, \vec b)$:

  1. Compute $(q/2)\vec m + \vec e_0 + \vec e_1 := \vec b - A_0\vec s_0 - A_1\vec s_1$
  2. Round $(q/2)\vec m + \vec e_0 + \vec e_1\mapsto \left\lfloor \frac{(q/2)\vec m + \vec e_0 + \vec e_1}{q/2}\right\rceil$.

This will be correct provided $\lVert \vec e_0 + \vec e_1\rVert_\infty < \frac{q}{4}$. If we are choosing $\vec e_i\gets [-n,n]^n\cap\mathbb{Z}^n$, this will happen provided $q/4 > 2n$, i.e. $q > 8n$. It is straightforward to prove security of the above under the LWE assumption.

Note that the other answers' point regarding secret-sharing is (mostly) true. You can (essentially) view this as a Threshold Encryption scheme built from the linearly homomorphic encryption underlying LWE using a secret-sharing of $\vec s := \vec s_0 + \vec s_1$. There are additional nuances in this Threshold Encryption scheme that make showing security a little more involved though.

Answer 2

You have described secure secret sharing, which need not resort to homomorphic encryption of the plaintext.

Alice wishes to send Bob a message via courier Carol. Each exchange is non-interactive, via dead drop or throwing over the transom.

In a physical setting, Carol accepts the lock-box, turns one key, and transmits the box to Bob who turns the other key.

In your setting a secret share is arranged among the participants on a per-message basis, and the secret is used as AES key for the message. Additionally Carol has a secure channel for communicating to Bob, perhaps using PKI or a symmetric cipher. Carol accepts the locked message, reveals her share of the secret to Bob via their secure channel, and sends message + share along to Bob who will successfully use AES to decrypt it.