Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Cryptanalysis:
TR01-078 | 6th November 2001
Matthias Krause

BDD-based Cryptanalysis of Keystream Generators

Many of the keystream generators which are used in practice are LFSR-based in the sense
that they produce the keystream according to a rule $y=C(L(x))$,
where $L(x)$ denotes an internal linear bitstream, produced by a small number of parallel
linear feedback shift registers (LFSRs),
and $C$ denotes ... more >>>

TR11-076 | 7th May 2011
Eric Miles, Emanuele Viola

The Advanced Encryption Standard, Candidate Pseudorandom Functions, and Natural Proofs

Revisions: 1

We put forth several simple candidate pseudorandom functions f_k : {0,1}^n -> {0,1} with security (a.k.a. hardness) 2^n that are inspired by the AES block-cipher by Daemen and Rijmen (2000). The functions are computable more efficiently, and use a shorter key (a.k.a. seed) than previous
constructions. In particular, we ... more >>>

TR18-182 | 31st October 2018
Henry Corrigan-Gibbs, Dmitry Kogan

The Function-Inversion Problem: Barriers and Opportunities

Revisions: 1

We study preprocessing algorithms for the function-inversion problem. In this problem, an algorithm gets oracle access to a function $f\colon[N] \to [N]$ and takes as input $S$ bits of auxiliary information about $f$, along with a point $y \in [N]$. After running for time $T$, the algorithm must output an ... more >>>

TR24-054 | 13th March 2024
Karthik Gajulapalli, Alexander Golovnev, Samuel King

On the Power of Adaptivity for Function Inversion

We study the problem of function inversion with preprocessing where, given a function $f : [N] \to [N]$ and a point $y$ in its image, the goal is to find an $x$ such that $f(x) = y$ using at most $T$ oracle queries to $f$ and $S$ bits of preprocessed ... more >>>

ISSN 1433-8092 | Imprint