CassandrichHmm, prediction markets are evil in general and I'm pretty much entirely opposed to their existence.
But it would be kinda hilarious to bet huge amounts of money that a 2048-bit RSA key won't be cracked by 2050.
Fortunately I don't think there's any way to set up such a bet. Someone would have to know the factors to generate the key, and they could use/leak that knowledge to cheat.
You can't just say "any key" because then you get what the QC scammers do now: picking a 'key' they already know the factors for.
None of this is non-obvious. It was the standard for classical cracking challenges dating back to the late 90s or so. But with QC it's "you get to pick the number you claim you can factor!" 🤡
Of course the more practical problem: whether these criminal markets will be solvent long enough to collect your winnings. 🤡
Wanja@dalias It might be doable with some secure multiparty computation shenanigans. You can still break the crypto used for *that* instead of RSA2048 but if set up correctly that's probably harder.
@dalias e.g. some N distrustful parties each select two "random" numbers pi, qi. They do some SMC bullshit to securely compute p = p1 ^ ... ^ pN and q = q1 ^ ... ^ qN and check whether they're prime. If they're not, start over. If they are, securely compute and publish n = p*q.
Or something. I dunno crypto.
Hovav Shacham@muvlon @dalias Indeed! I think the current state-of-the-art is represented by https://eprint.iacr.org/2020/370, https://eprint.iacr.org/2020/374, and https://eprint.iacr.org/2023/644
Multiparty Generation of an RSA Modulus
We present a new multiparty protocol for the distributed generation of biprime RSA moduli, with security against any subset of maliciously colluding parties assuming oblivious transfer and the hardness of factoring. Our protocol is highly modular, and its uppermost layer can be viewed as a template that generalizes the structure of prior works and leads to a simpler security proof. We introduce a combined sampling-and-sieving technique that eliminates both the inherent leakage in the approach of Frederiksen et al. (Crypto'18), and the dependence upon additively homomorphic encryption in the approach of Hazay et al. (JCrypt'19). We combine this technique with an efficient, privacy-free check to detect malicious behavior retroactively when a sampled candidate is not a biprime, and thereby overcome covert rejection-sampling attacks and achieve both asymptotic and concrete efficiency improvements over the previous state of the art.
Demi Marie Obenour@dalias Is there a method (indistinguishability obfuscation?) to generate the key without knowing the factors?
@alwayscurious No, at least not known. For EC that works because the entire range (essentially) is valid public keys so you can just pick a random public key. But with RSA the valid public keys (semiprimes) are extremely sparse.
@dalias When it comes to quantum computing, I don’t recommend betting against Scott Aaronson. When it comes to cryptographic algorithm selection, I don’t recommend betting against Filippo Valsorda.
@alwayscurious I might be more inclined to agree if there were any examples of him being right about something in this domain.
@alwayscurious @filippo It's a very reasonable hedge from a cryptographic strategy perspective. I don't see disagreement as "betting against him". The nature of a hedge is that he's right either way. I just don't see the hedge as necessary, and that's from a physics perspective not a crypto perspective.