Logo

    Trade-off Cryptography WG

    Advisors
    Collaborators
    Level
    L0
    Research Problems

    Motivation

    Why Trade-off Cryptography?

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

    Background

    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

    Examples:

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

    Refs:

    • (complexity paper) relating time/space to circuit efficiency
      • http://www.cs.toronto.edu/~bor/Papers/relating-time-space-size-depth.pdf
    • articolo di Trevisan et al.
      • https://www.semanticscholar.org/paper/Time-Space-Tradeoffs-for-Attacks-against-One-Way-De-Trevisan/06293dcf1ddc9815c8468312bb152845fcc59818

    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)?

    CryptoNet is a Protocol Labs initiative.