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
- articolo di Trevisan et al.
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)?