Orthogonal Lock

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?

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.

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.