Advisors

Collaborators

Level

L0

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

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