1
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – DannyNiu
    Commented Aug 16, 2023 at 11:22
  • 1
    $\begingroup$ 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? $\endgroup$
    – DannyNiu
    Commented Aug 16, 2023 at 11:25
  • $\begingroup$ 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 . $\endgroup$ Commented Aug 16, 2023 at 11:38

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ what is a "transom"? $\endgroup$
    – kodlu
    Commented Aug 16, 2023 at 17:34
  • 1
    $\begingroup$ 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. $\endgroup$
    – J_H
    Commented Aug 16, 2023 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.