## CryptoDB

### Boaz Tsaban

#### Publications

**Year**

**Venue**

**Title**

2018

CRYPTO

Cryptanalysis via Algebraic Spans
📺
Abstract

We introduce a method for obtaining provable polynomial time solutions of problems in nonabelian algebraic cryptography. This method is widely applicable, easier to apply, and more efficient than earlier methods. After demonstrating its applicability to the major classic nonabelian protocols, we use this method to cryptanalyze the Triple Decomposition key exchange protocol, the only classic group theory based key exchange protocol that could not be cryptanalyzed by earlier methods.

2015

JOFC

2014

EPRINT

2006

EPRINT

Length-based cryptanalysis: The case of Thompson's Group
Abstract

The length-based approach is a heuristic for solving randomly generated equations in groups which possess a reasonably behaved length function. We describe several improvements of the previously suggested length-based algorithms, that make them applicable to Thompson's group with significant success rates. In particular, this shows that the Shpilrain-Ushakov public key cryptosystem based on Thompson's group is insecure, and suggests that no practical public key cryptosystem based on this group can be secure.

2005

EPRINT

The conjugacy problem and related problems in lattice-ordered groups
Abstract

We study, from a constructive computational point of view, the techniques
used to solve the conjugacy problem in the "generic" lattice-ordered group
Aut(R) of order automorphisms of the real line. We use these techniques in
order to show that for each choice of parameters f,g in Aut(R), the equation
xfx=g is effectively solvable in Aut(R).

2005

EPRINT

Fast generators for the Diffie-Hellman key agreement protocol and malicious standards
Abstract

The Diffie-Hellman key agreement protocol is based on taking
large powers of a generator of a prime-order cyclic group.
Some generators allow faster exponentiation.
We show that to a large extent, using the fast generators is
as secure as using a randomly chosen generator. On the
other hand, we show that if there is some case in which fast generators are
less secure, then this could be used by a malicious
authority to generate a standard for the Diffie-Hellman key agreement protocol
which has a hidden trapdoor.

2005

EPRINT

Theoretical cryptanalysis of the Klimov-Shamir number generator TF-1
Abstract

The internal state of the Klimov-Shamir number generator TF-1 consists of
four words of size w bits each,
whereas its intended strength is 2^{2w}.
We exploit an asymmetry in its output function to show that
the internal state can be recovered after having 2^w outputs,
using 2^{1.5w} operations. For w=32 the attack is practical,
but for their recommended w=64 it is only of theoretical interest.

2005

EPRINT

On an authentication scheme based on the Root Problem in the braid group
Abstract

Lal and Chaturvedi proposed two authentication schemes based
on the difficulty of the Root Problem in the braid group.
We point out that the first scheme is not really as secure as
the Root Problem, and describe an efficient way to crack it.
The attack works for any group.

2003

EPRINT

Guaranteeing the diversity of number generators
Abstract

A major problem in using iterative number generators of the
form $x_i=f(x_{i-1})$ is that they can enter unexpectedly short
cycles. This is hard to analyze when the generator is designed,
hard to detect in real time when the generator is used, and can
have devastating cryptanalytic implications. In this paper we
define a measure of security, called \emph{sequence diversity},
which generalizes the notion of cycle-length for non-iterative
generators. We then introduce the class of counter assisted
generators, and show how to turn any iterative generator (even a
bad one designed or seeded by an adversary) into a counter
assisted generator with a provably high diversity, without
reducing the quality of generators which are already
cryptographically strong.

2003

EPRINT

Efficient linear feedback shift registers with maximal period
Abstract

We introduce and analyze an efficient family of linear
feedback shift registers (LFSR's) with maximal period.
This family is word-oriented and is suitable for implementation
in software, thus provides a solution to a recent challenge \cite{FSE94}.
The classical theory of LFSR's is extended to
provide efficient algorithms for generation of irreducible and primitive
LFSR's of this new type.

2003

EPRINT

Bernoulli numbers and the probability of a birthday surprise
Abstract

A birthday surprise is the event that, given $k$ uniformly random
samples from a sample space of size $n$, at least two of them are identical.
We show that Bernoulli numbers can be used to derive arbitrarily exact
bounds on the
probability of a birthday surprise.
This result can be used in arbitrary precision calculators, and it can
be applied to better understand some questions in
communication security and pseudorandom number
generation.

2003

EPRINT

Permutation graphs, fast forward permutations, and
Abstract

A permutation $P\in S_N$ is a \emph{fast forward permutation} if for each $m$
the computational complexity of evaluating $P^m(x)$ is small
independently of $m$ and $x$.
Naor and Reingold constructed fast
forward pseudorandom cycluses and involutions. By studying the
evolution of permutation graphs, we prove that the number of
queries needed to distinguish a random cyclus from a random
permutation in $S_N$ is $\Theta(N)$ if one does not use queries of
the form $P^m(x)$, but is only $\Theta(1)$ if one is allowed to
make such queries.
We construct fast forward permutations
which are indistinguishable from random
permutations even when queries of the form
$P^m(x)$ are allowed.
This is done by introducing an efficient
method to sample the cycle structure of a
random permutation,
which in turn solves an open problem of Naor and Reingold.

#### Coauthors

- Achiya Bar-On (2)
- Adi Ben-Zvi (2)
- Simon R. Blackburn (1)
- Itai Dinur (2)
- Orr Dunkelman (2)
- W. Charles Holland (1)
- Arkadius Kalka (1)
- Nathan Keller (1)
- Virginie Lallemand (2)
- Noam Lifshitz (1)
- Dima Ruinskiy (2)
- Adi Shamir (3)
- Uzi Vishne (1)