On the inherent “one-wayness” in asymmetric PoReps

Here we discuss some possible inherent limitations of asymmetric PoReps. We ask whether it is even possible to have asymmetric PoReps where the replica is obtained through the usual XOR-ing trick.

Recall a common approach to obtaining a replica:

Seal(id_D, D): // id_D is some identifier; D is the data

• L = GenLastLayerGraph(id_D)
• R ← D+L // here I assume XOR for simplicity

Assume we have an algorithm Unseal(R)→ D that runs in time faster than sealing described above. (ignore how it works internally)

We ask: is it possible that this construction is actually impossible? In particular, is it possible that the asummptions above lead to an even faster way of computing L? (which would violate the hardness assumptions on the graph)

Some observations on why the above may be true:

• (NB: I am ignoring id_D in the syntax below)
• Observation:
• IF
• there exists an “efficient” algorithm Unseal(R) → D (recall that R = D+L)
• and D is “easy” (e.g., it is highly compressible)
• THEN there exists an “efficient” algorithm Unseal’(L) → D.
• To construct Unseal’ we simply first compute R← L+D internally and then run Unseal(R)
• At this point we have a way to get from L to D. Can we somehow observe that this implies going from D to L easily?
• For example what if Unseal’(L) is somewhat “reversible”?
• Why would this be the case:
• Unseal’ is low depth (maybe this helps)
• Unseal’ may be highly local