4
$\begingroup$

My question is a follow-up to a recent question regarding quantum-secure time-lock puzzles (TLPs). TLPs can be built (in principle) from indistinguishability obfuscation (iO) [BGJ+,BGL+] as noted in this thread. As a corollary, quantum-secure iO would lead to quantum-secure TLPs (provided that there are inherently-sequential languages in the quantum world, which seems plausible).

So it boils down to whether any of the candidate constructions of iO are quantum-secure. It seems that some of the candidates are broken given a quantum computer [PM]. The question is whether any remaining candidate construction of iO is believed/conjectured to be quantum-secure?

[BGJ+]: Bitansky et al., Time-Lock Puzzles from Randomized Encodings, ITCS'16

[BGL+]: Bitansky et al., Succinct Randomized Encodings and their Applications, STOC'15

[PM]: Pellet-Mary, Quantum Attacks against Indistinguishablility Obfuscators Proved Secure in the Weak Multilinear Map Model, Crypto'18

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

Turns out that this was an open question. Brakerski et al. [BDGM] posted a paper today on the ePrint claiming the first (provable) post-quantum construction of iO. Their underlying security assumption is the "circular security" of an encryption scheme based on LWE.

[BDGM], Brakerski, Döttling, Garg and Malavolta, Factoring and Pairings are not Necessary for iO: Circular-Secure LWE Suffices, ePrint Archive

Improve this answer
$\endgroup$

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.