This is a really cool result, and I'm looking forward to reading Part 3.
My view on the ROM is that cryptographic proofs (the ones we are able to actually do) always rule out only some attacks but not out others. A standard model (non-ROM) proof will still be under some assumption about lattices or elliptic curves or AES or whatever, will be valid only under a certain model of the attacker's capabilities and goals, and will often have tightness issues (where the parameters or probability of success on the "proved" system will be worse than with the assumption). Even a tight unconditional proof (such as for the one-time pad) assumes a certain model of the attacker's goals and capabilities.
The ROM is another axis of this: a ROM proof rules out attacks that treat the hash function as a random oracle. Since hash functions are designed to have as few non-ROM properties as possible, and since most real attacks on cryptosystems either break the hash or treat it as a random oracle, ruling out those attacks can usually give you some confidence. But if your cryptosystem is itself making use of non-ROM properties of the hash, then it gives you a lot less confidence, and that's the situation of this new KRS result.
elchananHaas 20 days ago [-]
I'm also looking forward to part 3.
A good counterpoint to some of the concerns in the series is https://cacr.uwaterloo.ca/techreports/2015/cacr2015-01.pdf. This article shows "several examples of attempts to avoid random oracles that have
led to protocols that have security weaknesses".
Of course, that article is only focused on more classical constructions and not on the newer SNARKS/SNARG/STARK and other constructions in the zero knowledge zoo. So there isn't really a disagreement, but we probably shouldn't ditch random oracle based constructs in use today.
That explains why part three with the punchline wasn't published yet...
GrantMoyer 20 days ago [-]
In addition to being very technically interesting, I think this is among the best executions of a "humorously flippant" tone I've read. I particularly enjoyed:
> They’ll simply describe an interactive protocol with the right structure, then they say something like “of course this can be flattened using Fiat-Shamir, if we assume a random oracle or something” and everyone nods and deposits a billion dollars onto it.
This is a blog post about a recent paper covering the Fiat-Shamir transform. It involves zero-knowledge proofs and verifiable computation, not simple logic.
fuzztester 19 days ago [-]
>zero-knowledge
>not simple logic
bro ... you impractical academic ... i'm calling you out as an impractical academic, based on your fancy, high-falutin, chi-chi words above ... because logic is all there is.
there is nothing in life, the universe, and everything, except (simple) logic.
My view on the ROM is that cryptographic proofs (the ones we are able to actually do) always rule out only some attacks but not out others. A standard model (non-ROM) proof will still be under some assumption about lattices or elliptic curves or AES or whatever, will be valid only under a certain model of the attacker's capabilities and goals, and will often have tightness issues (where the parameters or probability of success on the "proved" system will be worse than with the assumption). Even a tight unconditional proof (such as for the one-time pad) assumes a certain model of the attacker's goals and capabilities.
The ROM is another axis of this: a ROM proof rules out attacks that treat the hash function as a random oracle. Since hash functions are designed to have as few non-ROM properties as possible, and since most real attacks on cryptosystems either break the hash or treat it as a random oracle, ruling out those attacks can usually give you some confidence. But if your cryptosystem is itself making use of non-ROM properties of the hash, then it gives you a lot less confidence, and that's the situation of this new KRS result.
A good counterpoint to some of the concerns in the series is https://cacr.uwaterloo.ca/techreports/2015/cacr2015-01.pdf. This article shows "several examples of attempts to avoid random oracles that have led to protocols that have security weaknesses".
Of course, that article is only focused on more classical constructions and not on the newer SNARKS/SNARG/STARK and other constructions in the zero knowledge zoo. So there isn't really a disagreement, but we probably shouldn't ditch random oracle based constructs in use today.
> They’ll simply describe an interactive protocol with the right structure, then they say something like “of course this can be flattened using Fiat-Shamir, if we assume a random oracle or something” and everyone nods and deposits a billion dollars onto it.
This statement is false.
https://en.m.wikipedia.org/wiki/Liar_paradox
>not simple logic
bro ... you impractical academic ... i'm calling you out as an impractical academic, based on your fancy, high-falutin, chi-chi words above ... because logic is all there is.
there is nothing in life, the universe, and everything, except (simple) logic.
https://en.m.wikipedia.org/wiki/Life,_the_Universe_and_Every...
;)
logic does not need to be complicated. confusion worse confounded. :)
just that some of it may not be evident to you or us at any given time.
like, you know, at first people thought, euclidean geometry was the only kind of geometry.
https://en.m.wikipedia.org/wiki/Euclidean_geometry
later, non-euclidean geometry was discovered or invented.
https://en.m.wikipedia.org/wiki/Non-Euclidean_geometry
go figure. pun intended.
galileo is another example. don't tell me you didn't hear about him. a lot of people learned about him in elementary school.
https://en.m.wikipedia.org/wiki/Galileo_Galilei
And yet it moves:
https://en.m.wikipedia.org/wiki/And_yet_it_moves