# 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?

• If you look at public-key encryption and key-derivation functions, and consider how to combine them, I think there will be a solution. But before anything concrete can be devised, there just need a little bit more detail. Aug 16 at 11:22
• For example, is 'Lock A' at a higher/lower level than 'Lock B'? Or are they parallel? Does unlocking either one implicitly also unlock the other? Or one of them can override the other? Aug 16 at 11:25
• they can and should be parallel, like a XOR function. The only issue with XOR is that when we use 2 XORS we are getting a 3rd key that can open both. So I'm looking for a solution like in a real life when we have a box with 2 locks , each can be opened with a different key . Aug 16 at 11:38

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.

• what is a "transom"? Aug 16 at 17:34
• It's like "throw it over the wall" to another person. A transom is at the base of a ventilation window above a door. The idea being: you've delivered your package, though the office door remains shut.
– J_H
Aug 16 at 17:36