Trade-off Cryptography WG

Why Trade-off Cryptography?

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

Background

• 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

• (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