Hey r/compsci, I just finished writing a post about a 1988 paper that completely blew my mind, and I wanted to share the idea and get your take on it.
Most of crypto relies on computational assumptions: things we hope are hard, like “factoring is tough” or “you can’t invert a one-way function.”
But back in 1988, Ben-Or, Goldwasser, Kilian, and Wigderson (BGKW) tossed all that out. They didn’t replace computational hardness with another computational assumption; they replaced it with a physical one: isolation.
Instead of assuming an attacker can’t compute something, you just assume two cooperating provers can’t talk to each other during the proof. They showed that isolation itself can be seen as a cryptographic primitive.
That one shift is huge:
**Unconditional S…
Hey r/compsci, I just finished writing a post about a 1988 paper that completely blew my mind, and I wanted to share the idea and get your take on it.
Most of crypto relies on computational assumptions: things we hope are hard, like “factoring is tough” or “you can’t invert a one-way function.”
But back in 1988, Ben-Or, Goldwasser, Kilian, and Wigderson (BGKW) tossed all that out. They didn’t replace computational hardness with another computational assumption; they replaced it with a physical one: isolation.
Instead of assuming an attacker can’t compute something, you just assume two cooperating provers can’t talk to each other during the proof. They showed that isolation itself can be seen as a cryptographic primitive.
That one shift is huge:
Unconditional Security: You get information-theoretic guarantees with literally no hardness assumptions needed. Security is a fact, not a hope.
Massive Complexity Impact: It introduced Multi-Prover Interactive Proofs (MIP), which led to the landmark results MIP = NEXP and later the crazy MIP* = RE in quantum complexity.
Foundational Shift: It changed how we build primitives like zero-knowledge proofs and bit commitments, making them possible without complexity assumptions.
My question for the community: Do you feel this kind of “physical assumption” (like verifiable isolation or no communication) still has huge, untapped potential in modern crypto? Or has the concept been fully exploited by the multiprover setting and newer models like device-independent crypto ? Do you know any other field in which this idea of physical seperation manage to offer a new lens on problems.
I’m pretty new to posting here, so if this isn’t a great fit for the sub, please let me know, happy to adjust next time! Also, feedback on the post itself is very welcome, I’d love to make future write-ups clearer and more useful.