Trade-off Cryptography WG

Research Problems
Related to Research Projects (1) (WG)
Related to Research Projects (1) (WG) 1
Related to Research Projects (Related to Research Areas (Projects) 1)
Related to Research Projects (Related to Research Areas (Projects) 1) 1
Related to Research Projects (Related to Research Areas (Projects) 1) 2


Why Trade-off Cryptography?

  • This could lead to more efficient cryptography
  • This could lead to post-quantum constructions


Fine-Grained crypto and motivation

  • FG = resource-bounded "crypto" on very weak assumptions (weaker than OWF-based maybe)
  • FG crypto could be motivated by two reasons:
    • possible better efficiency than "standard" crypto.
    • (important) post-quantum resistance
      • still moderately secure
      • Next action: understanding plausibility of this. E.G. Does Orthogonal Vector stay n^2 hard for quantum computers?

Trade-off characteristics

  • Resources:
    • Bandwith
    • SpaceTime
    • Memory
    • Computation
    • Parallel Computation (latency)
  • Types of algorithms
    • Work (includes functions)
    • Functions
      • see also "types of input" below
  • Types of verifiability
    • Non-verifiable
    • Verifiable
  • Types of input (for the function case)
    • arbitrary (may be used to define "useful" case)
    • uniform (or somewhat random)

Practical trade-off crypto

  • There are some resources for which worst adversary costs lead to very inefficient construction (see PoRep using mem bandwidth) and we may have to come up with heuristics/practical assumptions


  • Verifiable Work with Parallel Computation is VDF
  • Work with Parallel Computation is PoSW


Paper would like to see

  • Bounds on mem/bandwidth/space - time tradeoff
  • Trade-off based crypto primitives or techniques (scoring, fine grained crypto, what are the crypto techniques)
  • Examples of weakened constructions that can lead to better properties (aggregatable hashes)
  • New ways to combine information-theoretic tools/rational tools/resource bounded tools to obtain, e.g., proof systems
    • Trade-off SNARKs: Background: e.g. we can obtain SNARKs from an ITObj + CryptoPrimitive, i.e. an information-theoretic obj (e.g. PCP) + a cryptographic
    • Rational Proof of Space
    • Rational Commitments
    • What if either of these two pieces were: resource-bounded, rational-based, with small sec param, etc...? Is the output of it useful?

Next steps

Paper survey: Define a theoretical framework for trade-off cryptography
Write down application settings (and define which are useful for PL) for tradeoff crypto
Agree on what are the assumptions that we are happy to make
  • Are we open to rational assumptions (long term)?