Re: [Cfrg] Big-key cryptography

[Dan Brown <[e-mail]>]

it looks interesting, but am so far having trouble with the threat model and actual proposal, though maybe others understood better than I did:

how realistic is this exfiltration adversary that the scheme aims to protect against? eg why not exfiltrate an inbox instead? if R is published, why not exfiltrate the p bits needed?

is there a bigkey per each pair of users, and how is it established? with small-key public keys?


  Original Message
From: Aaron Zauner
Sent: Sunday, December 6, 2015 7:28 PM
To: '[e-mail]'
Subject: [Cfrg] Big-key cryptography


Hi,

People that have read Rogaway's recent IACR Distinguished Lecture [0]
might have noticed (besides an amazing essay on crypto, ethics and
politics of course) that there's new work mentioned on something they
call 'Big-key cryptography'. Let me quote Verbatim:

```
Suppose you have a bigkey K. You want to use it for some protocol P that
has been designed to use a conventional-length key K. So choose a random
value R (maybe 256 bits) and hash it to get some number p of probes into
the bigkey:

i_1 = H(R, 1) i_2 = H(R, 2) ... i_p = H(R, p) .

Each probe i_j points into K: it’s a number between 1 and |K|. So you
grab the p bits at those locations and hash them, along with R, to get a
derived key K:

K = H'(R, K[i_1], . . . , K[i_p]) = XKEY(K, R) .

Where you would otherwise have used the protocol P with a shared key K,
you will now use P with a shared bigkey K, a freshly chosen R, this
determining the conventional key K = XKEY(K, R).

We show that derived-key K is indistinguishable from a uniformly random
key K0 even if the adversary gets R and can learn lots of information
about the bigkey K. The result is quantitative, measuring how good the
derived key is as a function of the length of the bigkey, the number of
bits leaked from it, the number of probes p, the length of R, and the
number of random-oracle calls.

[...]

I think that the subkey prediction problem, and the key-encapsulation
algorithm based on it, will give rise to nice means for
exfiltration-resistant authenticated-encryption and pseudorandom
generators. In general, I see bigkey cryptography as one tool that
cryptographers can contribute to make mass surveillance harder.
```

This seems to be a yet unpublished manuscript but I can think of quite a
few instances where this approach might come in handy for keys used in
various high-confidentiality protocols. What does CFRG think?

Thanks,
Aaron

[0] - http://web.cs.ucdavis.edu/~rogaway/papers/moral-fn.pdf p. 31-32