1
$\begingroup$

I'm curious if there's a cryptographic (or mathematical) technique for key stretching that

  1. allows someone with a secret to quickly derive the final key,
  2. requires a deterministic number of rounds for stretching (ie is not probabilistic) for someone that does not have the secret.

Does such a thing exist?

For context, I think this would be useful for a regular pseudo-atomic information exchange. Two parties would encrypt the information they want to exchange each with a key they derive using a seed and an additional secret, exchange the encrypted info, exchange the seeds, then exchange the additional secret. That way, one party can't simply wait until they've received the other key to send their key - even if they delay the last step, the counter-party can still derive the key (tho it will take more time). And if they delay the second-to-last step, the counter-party will know they're not cooperating.

$\endgroup$
  • 2
    $\begingroup$ Well, there's $2^{2^t} \bmod pq$ or any of various other ‘verifiable delay functions’. But, how do you ensure that both parties exchange the last step? What prevents one party from walking off after the other party shares the secret? $\endgroup$ – Squeamish Ossifrage Oct 23 at 17:52
  • $\begingroup$ (You also need some way to make sure that a malicious party isn't just giving encrypted garbage to a chump.) $\endgroup$ – Squeamish Ossifrage Oct 23 at 17:58
  • $\begingroup$ You might want to have a look at Makwa (which does the exponential squarings mentioned by Squeamish Ossifrage). $\endgroup$ – SEJPM Oct 23 at 22:14
  • $\begingroup$ So for the application I'm thinking of, the only thing necessary is that both parties usually share the secret within an allotted amount of time. The situation is where two parties share their last known state on connection, assuming that most times both parties still have the state. The issue is when one party loses state (dead backup), the counter party shouldn't know anything has gone awry and should honestly share the latest state as normal. In this case, if one party consistently fails to do the last step in the allotted time, that party can be permanently disconnected from. $\endgroup$ – B T Oct 24 at 0:30
  • $\begingroup$ I understand the verifiable delay functions, that seems simple enough. What is missing is a way to shortcut those functions if a secret is known. $\endgroup$ – B T Oct 24 at 0:32
1
$\begingroup$

Let $p$ and $q$ be secret uniform random primes, and define $n = pq$. Consider $s = 2^{2^t} \bmod n$.

  • Without knowledge of $p$ or $q$, the best way we know to find $s$ is to start with $2$ and square it $t$ times successively. We can tune $t$ to force the other party to take arbitrarily many steps.

  • With knowledge of $p$ and $q$, we can use the shortcut $2^e \equiv 2^{e \bmod \lambda(n)} \pmod n$ by Carmichael's theorem, since $\lambda(n) = \operatorname{lcm}(p - 1, q - 1)$; then it only takes one division of $t$ by $\lambda(n)$ and about $\log_2 n$ squarings and multiplications modulo $n$ to compute the answer, no matter what $t$ is.

But suppose you use this protocol. What happens when one of the parties skips town just before the protocol is done?

BOB: Hey, Alice, the combination to the box the magic words are in is $2^{2^{t_b}} \bmod n_b$ where $t_b = 1\,000\,000\,000\,000$ and $n_b = \dotsb$.

ALICE: Great! The secret to the meaning of life, the universe, and everything is encrypted with the key $2^{2^{t_a}} \bmod n_a$ where $t_a = 3\,141\,159\,265\,359$ and $n_a = \dotsb$.

BOB: Awesome, thanks! By the way, $n_b = p_b q_b$ where $p_b = \dotsb$ and $q_b = \dotsb$.

ALICE: Ha-ha, sucker! Have fun chasing meaning while I go open your box of magic words!

BOB: Blast! It will take my ASIC three hundred years to compute this.

Another approach you could try—which doesn't involve shortcuts—is to have each party reveal the secret bit by bit (or letter by letter) in lock-step:

ALICE: The first letter of my secret is C.

BOB: The first letter of my secret is V.

ALICE: The second letter of my secret is H.

BOB: The second letter of my secret is L.

ALICE: The third letter of my secret is U.

BOB: The third letter of my secret is F.

ALICE: The fourth letter of my secret is M.

BOB: The fourth letter of my secret is E.

ALICE: The fifth letter of my secret is P, spelling out CHUMP, because you've given me enough to guess the rest of your secret by brute force and I ain't given you diddly squat!

The trouble is twofold:

  1. Bob shouldn't have proceeded to divulge any of the secret without a verifiable proof that what Alice gave is actually part of her secret.

  2. The protocol favors whichever party has more computational power—that party can abort the protocol at any time and leave the other one in the dust.

$\endgroup$
  • $\begingroup$ Thanks! That's exactly the kind of thing I'm looking for. To answer your question about what happens if Alice skips town, the idea is that in 99.9% of the cases, the information each party is revealing is the same information. The purpose of the exchange is so that if one party somehow loses the info, they can get it back. Since the other party knows there is a very high chance their counterparty already has the data (and thus keeping it secret is not worth anything), their motivation is to be honest and release the data. If they don't, the counterparty can end contact with them. $\endgroup$ – B T Oct 30 at 20:13
  • $\begingroup$ @BT It sounds like you're really talking about a zero-knowledge proof of equality, as in the socialist millionaires problem, for which you want a symmetric password-authenticated key agreement? $\endgroup$ – Squeamish Ossifrage Oct 30 at 20:19
  • $\begingroup$ No, the goal is not finding identical information without disclosing the information. The goal is to disclose the information symmetrically in a way where not disclosing the information is detectable. $\endgroup$ – B T Oct 31 at 3:04
  • $\begingroup$ @BT If the parties are honest, why don't they just share all the data up front without games? If they're not honest, how do you prevent Alice from ripping Bob off like a CHUMP? $\endgroup$ – Squeamish Ossifrage Oct 31 at 5:16
  • $\begingroup$ The problem scenario is that most actors are usually honest, but you can't trust them to always be honest. If the actor is not honest, you prevent Alice from ripping off Bob by detecting Alice's dishonesty when Bob doesn't require honesty, and preventing Alice from knowing when Bob does require honesty. $\endgroup$ – B T Oct 31 at 23:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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