Publications related to Generic Round-Function-Recovery Attacks for Feistel Networks over Small Domains

Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm

We address the weighted max-cut problem, or equivalently the problem of maximizing a quadratic form in n binary variables. If the underlying (symmetric) matrix is positive semidefinite of fixed rank d, then the problem can be reduced to searching the extre ...

2004

On the complexity of fixed parameter clique and dominating set

Friedrich Eisenbrand

We provide simple, faster algorithms for the detection of cliques and dominating sets of fixed order. Our algorithms are based on reductions to rectangular matrix multiplication. We also describe an improved algorithm for diamonds detection. © 2004 Elsevie ...

2004

How fast can a distributed atomic read be?

Rachid Guerraoui, Ron Levy, Partha Dutta, Arindam Chakraborty

This paper addresses the problem of designing an efficient implementation of a basic atomic read-write data structure over an asynchronous message-passing system. In particular, we consider time-efficient implementations of this abstraction in the case of ...

2004

Fast Non-Blocking Atomic Commit: An Inherent Trade-off

Rachid Guerraoui, Bastian Pochon, Partha Dutta

This paper investigates the time-complexity of the non-blocking atomic commit (NBAC) problem in a synchronous distributed model where t out of n processes may fail by crashing. We exhibit for t > 3 an inherent trade-off between the fast abort property of N ...

2004

Undeniable Signatures Based on Characters: How to Sign with One Bit

Serge Vaudenay, Jean Monnerat

We present a new undeniable signature scheme which is based on the computation of characters. Our signature scheme offers the advantage of having an arbitrarily short signature. Its asymptotic complexity is attractive: the asymptotic complexity of all algo ...

2004

Early Local Decisions in Distributed Agreement

Rachid Guerraoui, Bastian Pochon, Partha Dutta

When devising a distributed agreement algorithm, it is common to minimize the time complexity of global decisions, which is typically measured as the number of communication rounds needed for all correct processes to decide. In practice, what we might want ...

2003

A sampling theorem for the radon transform of finite complexity objects

Martin Vetterli, Irena Maravic

See full text ...

2002

On the Complexity of Matsui's Attack

Pascal Junod

Linear cryptanalysis remains the most powerful attack against DES at this time. Given

2^{43}

known plaintext-ciphertext pairs, Matsui expected a complexity of less than

2^{43}

DES evaluations in 85% of the cases for recovering the key. In this paper, w ...

2001

Reconfiguration strategies for hybrid systems

Giancarlo Ferrari Trecate

In this work we propose several algorithms to solve the reconfiguration problem for linear and hybrid systems. In particular, we consider the decision about the usage of redundant hardware in order to compensate for faults. While this problem can be transl ...

2001

Reduced complexity likelihood approximation for chaotic trajectory segments

Thomas Schimming

Recently, statistically optimal detection methods for communication schemes based on chaos have been developed. The decision criterion is based on the well-known maximum likelihood criterion. Unfortunately, the calculation of the likelihoods is of exponent ...

2000

Generic Round-Function-Recovery Attacks for Feistel Networks over Small Domains

Graph Chatbot

Chat with Graph Search

Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm

On the complexity of fixed parameter clique and dominating set

How fast can a distributed atomic read be?

Fast Non-Blocking Atomic Commit: An Inherent Trade-off

Undeniable Signatures Based on Characters: How to Sign with One Bit

Early Local Decisions in Distributed Agreement

A sampling theorem for the radon transform of finite complexity objects

On the Complexity of Matsui's Attack

Reconfiguration strategies for hybrid systems

Reduced complexity likelihood approximation for chaotic trajectory segments

How fast can a distributed atomic read be?

Reconfiguration strategies for hybrid systems

Undeniable Signatures Based on Characters: How to Sign with One Bit

A sampling theorem for the radon transform of finite complexity objects

On the Complexity of Matsui's Attack

Reduced complexity likelihood approximation for chaotic trajectory segments

Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm

On the complexity of fixed parameter clique and dominating set

Fast Non-Blocking Atomic Commit: An Inherent Trade-off

Early Local Decisions in Distributed Agreement