Re: [TLS] Before we PQC... Re: PQC key exchange sizes

[Sofía Celi <[e-mail]>]

Dear, all,

On 06/08/2022 07:15, Benjamin Kaduk wrote:
> On Fri, Aug 05, 2022 at 07:16:06PM -0700, Rob Sayre wrote:
>> On Fri, Aug 5, 2022 at 5:16 PM Sofía Celi <[e-mail]> wrote:
>>
>>> There is a notion of being 'quantum annoyant' to a quantum computer:
>>>
>>
>> I've encountered the term "quantum annoyant" a few times. Is there a
>> precise definition that could be referenced? Maybe [0]?
>>
>> I don't find the references I know of very satisfying, and I would
>> translate "annoyant" to "doesn't actually work".
>>
>> thanks,
>> Rob
>>
>> [0] https://urldefense.com/v3/__https://eprint.iacr.org/2021/696.pdf__;!!GjvTz_vk!S_lXpy5HvfAfDJmtXdME2kuOOLXGTGz07_pqClIgY8ppVcZYu7Cf2WQ0K7YjyyOypKFppMI6NE_C$
> 
> I think [0] is the reference (or at least very similar content) I've seen in previous discussions of this topic.
> 
> It's annoying to the attacker when they have to use their expensive and finicky
> hardware once (or multiple times) for each individual message/exchange they
> want to break, rather than being able to amortize the cost of running the
> quantum computer across many protocol runs that are broken by that computer.
> They'd have to be selective about what to decrypt (quickly), rather than just
> getting "everything" -- while a QC does provide massive speedups, it does still
> take some actual amount of time to run, and we can build protocols so that
> the runtime of the QC is a practical constraint on the attacker's ability, even
> if it is not necessarily a theoretical constraint on them.

Correct. Note that it doesn't mean that a QC will not break it at the 
end, but just that is is 'annoying' to perform such operations over and 
over. Edward Eaton and Douglas Stebila properly defined the "property" 
over here: https://eprint.iacr.org/2021/696.pdf It was first mentioned 
during the PAKE selection process at CFRG by Thomas: 
https://mailarchive.ietf.org/arch/msg/cfrg/dtf91cmavpzT47U3AVxrVGNB5UM/

Thanks,
-- 
Sofía Celi
@claucece
Cryptographic research and implementation at many places, specially Brave.
Chair of hprc at IRTF and anti-fraud at W3C.
Reach me out at: [e-mail]
Website: https://sofiaceli.com/
3D0B D6E9 4D51 FBC2 CEF7  F004 C835 5EB9 42BF A1D6