Cryptographic security is usually proven against P/Poly adversaries as this encapsulates the possibility for someone to do heavy precomputation to be used later, eg. rainbow tables.

However actually finding this advice string is assumed very impractical for large instances, rendering the process generally infeasible.

Several questions on this site already ask about the power of P/Poly, but do we know anything more about feasibility if we restrict the non-uniform TM to only using logarithmic read-write space? I'm only concerned with a definition of L/Poly that includes well-formed languages, specifically not undecidable.

I'm also interested in results about randomization, or even potentially derandomization. A logspace variant of Adleman's theorem shows that BPL is contained in L/Poly, so probabilistic algorithms for a large subset of L/Poly could potentially be derandomized to fall in SC. However I'm unsure of the general case in between BPL and L/Poly (assuming a gap), and especially whether L/Poly is in any way relatable to P.

  • $\begingroup$ I'm not sure I understand your question. You are asking about schemes that are secure against L/poly adversaries? That doesn't seem very interesting: L/poly is too constrained to capture many attacks that will be feasible in practice. What exactly do you want to know about it? Generally in cryptography, cryptographers tend to be glad to give adversaries every reasonable advantage (non-uniform model, randomness, etc.) and seek schemes that are secure even against those adversaries. Since we can build schemes that do seem to meet this stricter criterion, why bother with weaker criteria? $\endgroup$ – D.W. May 22 '17 at 21:38
  • $\begingroup$ cstheory.stackexchange.com/q/5160/5038 $\endgroup$ – D.W. May 22 '17 at 21:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy