## CryptoDB

### Josef Pieprzyk

#### Publications

**Year**

**Venue**

**Title**

2015

EUROCRYPT

2012

JOFC

Graph Coloring Applied to Secure Computation in Non-Abelian Groups
Abstract

We study the natural problem of secure n-party computation (in the computationally unbounded attack model) of circuits over an arbitrary finite non-Abelian group (G,⋅), which we call G-circuits. Besides its intrinsic interest, this problem is also motivating by a completeness result of Barrington, stating that such protocols can be applied for general secure computation of arbitrary functions. For flexibility, we are interested in protocols which only require black-box access to the group G (i.e. the only computations performed by players in the protocol are a group operation, a group inverse, or sampling a uniformly random group element). Our investigations focus on the passive adversarial model, where up to t of the n participating parties are corrupted.Our results are as follows. We initiate a novel approach for the construction of black-box protocols for G-circuits based on k-of-k threshold secret-sharing schemes, which are efficiently implementable over any black-box (non-Abelian) group G. We reduce the problem of constructing such protocols to a combinatorial coloring problem in planar graphs. We then give three constructions for such colorings. Our first approach leads to a protocol with optimal resilience t<n/2, but it requires exponential communication complexity $O({\binom{2 t+1}{t}}^{2} \cdot N_{g})$ group elements and round complexity $O(\binom{2 t + 1}{t} \cdot N_{g})$, for a G-circuit of size Ng. Nonetheless, using this coloring recursively, we obtain another protocol to t-privately compute G-circuits with communication complexity $\mathcal{P}\mathit{oly}(n)\cdot N_{g}$ for any t∈O(n1−ϵ) where ϵ is any positive constant. For our third protocol, there is a probability δ (which can be made arbitrarily small) for the coloring to be flawed in term of security, in contrast to the first two techniques, where the colorings are always secure (we call this protocol probabilistic, and those earlier protocols deterministic). This third protocol achieves optimal resilience t<n/2. It has communication complexity O(n5.056(n+log δ−1)2⋅Ng) and the number of rounds is O(n2.528⋅(n+log δ−1)⋅Ng).

2010

EPRINT

A New Human Identification Protocol and Coppersmith's Baby-Step Giant-Step Algorithm
Abstract

We propose a new protocol providing cryptographically secure authentication to unaided humans against passive adversaries. We also propose a new generic passive attack on human identification protocols. The attack is an application of Coppersmith's baby-step giant-step algorithm on human identification protcols. Under this attack, the achievable security of some of the best candidates for human identification protocols in the literature is further reduced. We show that our protocol preserves similar usability while achieves better security than these protocols. A comprehensive security analysis is provided which suggests parameters guaranteeing desired levels of security.

2007

EPRINT

Multiple Modular Additions and Crossword Puzzle Attack on NLSv2
Abstract

NLS is a stream cipher which was submitted to the eSTREAM project.
A linear distinguishing attack against NLS was presented by Cho and Pieprzyk,
which was called Crossword Puzzle (CP) attack.
NLSv2 is the tweak version of NLS which aims mainly at avoiding the CP attack.
In this paper, a new distinguishing attack against NLSv2 is presented.
The attack exploits high correlation amongst neighboring bits of the cipher.
The paper first shows that the modular addition preserves pairwise correlations
as demonstrated by existence of linear approximations with large biases.
Next it shows how to combine these results with the existence of high correlation
between bits 29 and 30 of the S-box to obtain a distinguisher whose bias is around $2^{-37}$.
Consequently, we claim that NLSv2 is distinguishable from a random process after
observing around $2^{74}$ keystream words.

2007

EPRINT

An Improved Distinguisher for Dragon
Abstract

Dragon stream cipher is one of the focus ciphers which have reached Phase 2 of the eSTREAM project.
In this paper, we present a new method of building a linear distinguisher for Dragon.
The distinguisher is constructed by exploiting
the biases of two S-boxes and the modular addition
which are basic components of the nonlinear function $F$.
The bias of the distinguisher is estimated to be around $2^{-75.32}$ which is
better than the bias of the distinguisher
presented by Englund and Maximov.
We have shown that Dragon is distinguishable from a random cipher
by using around $2^{150.6}$ keystream words and $2^{59}$ memory.
In addition, we present a very efficient algorithm for computing the bias of linear approximation
of modular addition.

2007

EPRINT

An Algebraic Analysis of Trivium Ciphers based on the Boolean Satisfiability Problem
Abstract

Trivium is a stream cipher candidate of the eStream project.
It has successfully moved into phase three of the selection process under
the hardware category. No attacks faster than the exhaustive search have
so far been reported on Trivium.
Bivium-A and Bivium-B are simplified versions of Trivium
that are built on the same design principles but with two registers.
The simplified design is useful in investigating Trivium type ciphers
with a reduced complexity and provides insight into effective
attacks which could be extended to Trivium.
This paper focuses on an algebraic analysis which
uses the boolean satisfiability problem in propositional logic.
For reduced variants of the cipher,
this analysis recovers the internal state with
a minimal amount of keystream observations.

2007

EPRINT

Cryptanalysis of LASH
Abstract

We show that the LASH-$x$ hash function is vulnerable to attacks
that trade time for memory, including collision attacks as
fast as $2^{\frac{4}{11}x}$ and preimage attacks as fast as $2^{\frac47x}$.
Moreover, we describe heuristic lattice based collision attacks that
use small memory but require very long messages.
Based upon experiments, the lattice attacks are expected to find
collisions much faster than $2^{x/2}$.
All of these attacks exploit the designers' choice of an all zero IV.
We then consider whether LASH can be patched simply by changing the IV.
In this case, we show that LASH is vulnerable to a $2^{\frac78x}$
preimage attack. We also show that LASH is trivially not a PRF when any subset of input bytes is used as a secret key.
None of our attacks depend upon the particular contents of the LASH matrix -- we only assume that the distribution of elements is more or less uniform.
Additionally, we show a generalized birthday attack
on the final compression of LASH which requires
$O\left(x2^{\frac{x}{2(1+\frac{107}{105})}}\right) \approx O(x2^{x/4})$ time and memory.
Our method extends the Wagner algorithm to
truncated sums, as is done in the final transform in LASH.

2006

EPRINT

Crossword Puzzle Attack on NLS
Abstract

NLS is one of the stream ciphers submitted to the eSTREAM project.
We present a distinguishing attack on NLS by Crossword Puzzle (CP) attack method
which is newly introduced in this paper.
We build the distinguisher by using linear approximations of
both the non-linear feedback shift register (NFSR) and the nonlinear filter function (NLF).
Since the bias of the distinguisher depends on the $Konst$ value,
which is a key-dependent word,
we present the graph showing how the bias of distinguisher vary with $Konst$.
In result, we estimate the average bias to be around $O(2^{-30})$.
Therefore, we claim that NLS is distinguishable from truly random cipher after observing
$O(2^{60})$ keystream words on the average.
The experiments also show that our distinguishing attack is successful on $90.3\%$ of $Konst$
among $2^{32}$ possible values.

2006

EPRINT

On the Provable Security of an Efficient RSA-Based Pseudorandom Generator
Abstract

Pseudorandom Generators (PRGs) based on the RSA inversion
(one-wayness) problem have been extensively studied in the
literature over the last 25 years. These generators have the
attractive feature of provable pseudorandomness security assuming
the hardness of the RSA inversion problem. However, despite
extensive study, the most efficient provably secure RSA-based
generators output asymptotically only at most $O(\log n)$ bits per
multiply modulo an RSA modulus of bitlength $n$, and hence are too
slow to be used in many practical applications.
To bring theory closer to practice, we present a simple
modification to the proof of security by Fischlin and Schnorr of
an RSA-based PRG, which shows that one can obtain an RSA-based PRG
which outputs $\Omega(n)$ bits per multiply and has provable
pseudorandomness security assuming the hardness of a well-studied
variant of the RSA inversion problem, where a constant fraction of
the plaintext bits are given. Our result gives a positive answer to an open question posed by Gennaro (J. of Cryptology, 2005) regarding finding a PRG beating the rate $O(\log n)$ bits per multiply at the cost of a reasonable assumption on RSA inversion.

2006

EPRINT

Weaknesses of the FORK-256 compression function
Abstract

This report presents analysis of the compression function of a recently proposed hash function, FORK-256. We exhibit some unexpected differentials existing for the step transformation and show their possible uses in collision-finding attacks on different variants of FORK-256. As a simple application of those observations we present a method of finding chosen IV collisions for a variant of FORK-256 reduced to two branches : either 1 and 2 or 3 and 4.
Moreover, we present how those differentials can be used in the full FORK-256 to easily find messages with hashes differing by only a relatively small number of bits.
We argue that this method allows for finding collisions in the full function with complexity not exceeding $2^{126.6}$ hash evaluations, better than birthday attack and additionally requiring only a small amount of memory.

2004

PKC

2004

EPRINT

Finding good differential patterns for attacks on SHA-1
Abstract

In this paper we describe a method of finding differential patterns that may be used to attack reduced versions of SHA-1. We show that the problem of finding optimal differential patterns for SHA-1 is equivalent to the problem of finding minimal weight codeword in a linear code. Finally, we present a number of patterns of different lengths suitable for finding collisions and near-collisions and discuss some bounds on minimal weights of them.

2003

EPRINT

On alternative approach for verifiable secret sharing
Abstract

The proposed approach works for any underlying secret sharing scheme. It is based on the concept of verification sets of participants, related to authorized set of participants.
The participants interact (no third party involved) in order to check validity of their shares before they are pooled for secret recovery. Verification efficiency does not depend on the number of faulty participants.

2003

EPRINT

Universal Designated-Verifier Signatures
Abstract

Motivated by privacy issues associated with dissemination of signed digital certificates, we define a new type of signature scheme called a ?Universal Designated-Verifier Signature? (UDVS). A UDVS scheme can function as a standard publicly-verifiable digital signature but has additional functionality which allows any holder of a signature (not necessarily the signer) to designate the signature to any desired designated-verifier (using the verifier?s public key). Given the designated-signature, the designated-verifier can verify that the message was signed by the signer, but is unable to convince anyone else of this fact.
We propose an efficient deterministic UDVS scheme constructed using any bilinear group-pair. Our UDVS scheme functions as a standard Boneh-Lynn-Shacham (BLS) signature when no verifier-designation is performed, and is therefore compatible with the key-generation, signing and verifying algorithms of the BLS scheme. We prove that our UDVS scheme is secure in the sense of our unforgeability and privacy notions for UDVS schemes, under the Bilinear Diffie-Hellman (BDH) assumption for the underlying group-pair, in the random-oracle model. We also demonstrate a general constructive equivalence between a class of unforgeable and unconditionally-private UDVS schemes having unique signatures (which includes the deterministic UDVS schemes) and a class of ID-Based Encryption (IBE) schemes which contains the Boneh-Franklin IBE scheme but not the Cocks IBE scheme.

2003

EPRINT

Efficient Extension of Standard Schnorr/RSA signatures into Universal Designated-Verifier Signatures
Abstract

Universal Designated-Verifier Signature (UDVS) schemes are digital signature schemes with additional
functionality which allows any holder of a signature to designate the signature to any desired
designated-verifier such that the designated-verifier can verify that the message was signed by the
signer, but is unable to convince anyone else of this fact.
Since UDVS schemes reduce to standard signatures when no verifier designation is performed, it is natural to ask
how to extend the classical Schnorr or RSA signature schemes into UDVS schemes, so that the existing key
generation and signing implementation infrastructure for these schemes can be used without modification. We show
how this can be efficiently achieved, and provide proofs of security for our schemes in the random oracle model.

2002

EPRINT

Cryptanalysis of Block Ciphers with Overdefined Systems of Equations
Abstract

Several recently proposed ciphers are built with layers of small S-boxes, interconnected by linear key-dependent layers. Their security relies on the fact, that the classical methods of cryptanalysis (e.g. linear or differential attacks) are based on probabilistic characteristics, which makes their security grow exponentially with the number of rounds Nr.
In this paper we study the security of such ciphers under an additional hypothesis: the S-box can be described by an overdefined system of algebraic equations (true with probability 1). We show that this hypothesis is true for both Serpent (due to a small size of S-boxes) and Rijndael (due to unexpected algebraic properties).
We study general methods known for solving overdefined systems of equations, such as XL from Eurocrypt'00, and show their inefficiency. Then we introduce a new method called XSL that uses the sparsity of the equations and their specific structure.
The XSL attack is very powerful, but heuristic and it is very difficult to evaluate its complexity. The XSL attack has a parameter P, and in theory we show that P should be a constant. The XSL attack would then be polynomial in Nr, with a huge constant that is double-exponential in the size of the S-box.
We demonstrated by computer simulations that the XSL attack works well enough on a toy cipher. It seems however that P will rather increase very slowly with Nr. More simulations are needed for bigger ciphers.
Our optimistic evaluation shows that the XSL attack might be able to break Rijndael 256 bits and Serpent for key lengths 192 and 256 bits. However if only $P$ is increased by 2 (respectively 4) the XSL attack on Rijndael (respectively Serpent) would become slower than the exhaustive search. At any rate, it seems that the security of these ciphers does NOT grow exponentially with the number of rounds.

1992

EUROCRYPT

1991

ASIACRYPT

1991

ASIACRYPT

#### Program Committees

- Asiacrypt 2020
- Eurocrypt 2016
- Crypto 2015
- Asiacrypt 2015
- FSE 2014
- FSE 2010
- Asiacrypt 2009
- FSE 2008
- Asiacrypt 2008 (Program chair)
- FSE 2007
- PKC 2005
- Eurocrypt 2003
- PKC 2001
- PKC 2000
- Eurocrypt 1997
- Crypto 1995
- Asiacrypt 1994 (Program chair)
- Auscrypt 1992
- Crypto 1991
- Auscrypt 1990 (Program chair)

#### Coauthors

- Hassan Jameel Asghar (2)
- Harry Bartlett (1)
- Olivier Billet (1)
- Alex Biryukov (1)
- Lawrence Brown (2)
- Laurence Bull (2)
- Chris Charnes (4)
- Joo Yeon Cho (4)
- Scott Contini (5)
- Nicolas Courtois (2)
- Ed Dawson (1)
- Yvo Desmedt (3)
- Itai Dinur (2)
- Sareh Emami (2)
- Kris Gaj (2)
- Praveen Gauravaram (1)
- Hossein Ghodosi (1)
- Jian Guo (3)
- Thomas Hardjono (1)
- Ekawat Homsirikamol (2)
- Dmitry Khovratovich (3)
- Zbigniew Kotulski (1)
- Kamil Kulesza (1)
- Matthew Kwan (2)
- San Ling (7)
- Krystian Matusiewicz (8)
- Cameron McDonald (1)
- Dariusz Michatek (1)
- Pawel Morawiecki (6)
- Ivica Nikolić (5)
- Luke O'Connor (1)
- Jaroslaw Pastuszak (1)
- Thomas Peyrin (2)
- Marcin Rogawski (2)
- Babak Sadeghiyan (5)
- Reihaneh Safavi-Naini (2)
- Md. Iftekhar Salam (1)
- Jennifer Seberry (4)
- Leonie Simpson (1)
- Przemyslaw Sokolowski (3)
- Marian Srebrny (6)
- Ron Steinfeld (17)
- Michal Straus (3)
- Xiaoming Sun (1)
- Christophe Tartary (2)
- Huaxiong Wang (20)
- Lei Wei (1)
- Marcin Wójcik (2)
- Kenneth Koon-Ho Wong (1)
- Andrew Chi-Chih Yao (1)
- Xian-Mo Zhang (1)
- Yuliang Zheng (4)