## CryptoDB

### Guang Gong

#### Affiliation: University of Waterloo

#### Publications

**Year**

**Venue**

**Title**

2020

PKC

PAKEs: New Framework, New Techniques and More Efficient Lattice-Based Constructions in the Standard Model
Abstract

Password-based authenticated key exchange (PAKE) allows two parties with a shared password to agree on a session key. In the last decade, the design of PAKE protocols from lattice assumptions has attracted lots of attention. However, existing solutions in the standard model do not have appealing efficiency. In this work, we first introduce a new PAKE framework. We then provide two realizations in the standard model, under the Learning With Errors (LWE) and Ring-LWE assumptions, respectively. Our protocols are much more efficient than previous proposals, thanks to three novel technical ingredients that may be of independent interests. The first ingredient consists of two approximate smooth projective hash (ASPH) functions from LWE, as well as two ASPHs from Ring-LWE. The latter are the first ring-based constructions in the literature, one of which only has a quasi-linear runtime while its function value contains $$varTheta (n)$$ field elements (where n is the degree of the polynomial defining the ring). The second ingredient is a new key conciliation scheme that is approximately rate-optimal and that leads to a very efficient key derivation for PAKE protocols. The third one is a new authentication code that allows to verify a MAC with a noisy key.

2007

EPRINT

Time-Memory-Data Trade-off Attack on Stream Ciphers based on Maiorana-McFarland Functions
Abstract

In this paper, we present the time-memory-data (TMD) trade-off attack on stream ciphers filtered by Maiorana-McFarland functions. This can be considered as a generalization of the time-memory-data trade-off attack of Mihaljevic and Imai on Toyocrypt. First, we substitute the filter function in Toyocrypt (which has the same size as the LFSR) with a general Maiorana-McFarland function. This allows us to apply the attack to a wider class of stream ciphers. Second, we highlight how the choice of different Maiorana-McFarland functions can affect the effectiveness of our attack. Third, we show that the attack can be modified to apply on filter functions which are smaller than the LFSR and on filter-combiner stream ciphers. This allows us to cryptanalyze other configurations commonly found in practice. Finally, filter functions with vector output are sometimes used in stream ciphers to improve the throughput. Therefore the case when the Maiorana-McFarland functions have vector output is investigated. We found that the extra speed comes at the price of additional weaknesses which make the attacks easier.

2006

EPRINT

Algebraic Immunity of S-boxes Based on Power Mappings: Analysis and Construction
Abstract

The algebraic immunity of an S-box depends on the number and type
of linearly independent multivariate equations it satisfies. In
this paper techniques are developed to find the number of linearly
independent, multivariate, bi-affine and quadratic equations for
S-boxes based on power mappings. These techniques can be used to
prove the exact number of equations for any class of power
mappings. Two algorithms to calculate the number of bi-affine and
quadratic equations for any $(n,n)$ S-box based on power mapping
are also presented. The time complexity of both algorithms is only
$O(n^2)$. To design algebraically immune S-boxes four new classes
of S-boxes that guarantee zero bi-affine equations and one class
of S-boxes that guarantees zero quadratic equations are presented.
The algebraic immunity of power mappings based on Kasami, Niho,
Dobbertin, Gold, Welch and Inverse exponents are discussed along
with other cryptographic properties and several cryptographically
strong S-boxes are identified. It is conjectured that a known
Kasami like APN power mapping is maximally nonlinear and a known
Kasami like maximally nonlinear power mapping is differentially
4-uniform. Finally an open problem to find an $(n,n)$ bijective
nonlinear S-box with more than $5n$ quadratic equations is solved
and it is conjectured that the upper bound on this number is
$\frac{n(n-1)}{2}$.

2005

EPRINT

A 32-bit RC4-like Keystream Generator
Abstract

In this paper we propose a new 32-bit RC4 like keystream
generator. The proposed generator produces 32 bits in each
iteration and can be implemented in software with reasonable
memory requirements. Our experiments show that this generator is
3.2 times faster than original 8-bit RC4. It has a huge internal
state and offers higher resistance against state recovery attacks
than the original 8-bit RC4. We analyze the randomness properties
of the generator using a probabilistic approach. The generator is
suitable for high speed software encryption.

2004

EPRINT

Password Based Key Exchange with Mutual Authentication
Abstract

A reasonably efficient password based key exchange (KE) protocol with
provable
security without random oracle was recently proposed
by Katz, {\em et al.} \cite{KOY01} and later by Gennaro and Lindell \cite{GL03}.
However, these protocols do not support mutual authentication
(MA). The authors explained that this could be achieved by adding
an additional flow. But then this protocol turns out to be
4-round. As it is known that a high entropy secret based key
exchange protocol with MA\footnote{we do not consider a protocol
with a time stamp or a stateful protocol (e.g., a counter based
protocol). In other words, we only consider protocols in which a
session execution within an entity is independent of its history,
and in which the network is asynchronous.} is optimally 3-round
(otherwise, at least one entity is not authenticated since a
replay attack is applicable), it is quite interesting to ask
whether such a protocol in the password setting (without random
oracle) is achievable or not. In this paper, we
provide an affirmative answer with an efficient construction in
the common reference string (CRS) model.
Our protocol is even simpler than that of Katz, {\em et al.}
Furthermore, we show that our protocol is secure under the DDH
assumption ({\em without} random oracle).

2003

EPRINT

Hybrid Broadcast Encryption and Security Analysis
Abstract

A broadcast encryption scheme for stateless receivers
is a data distribution method which
never updates users' secret information while in order to maintain the
security the system
efficiency decreases with the number of revoked users.
Another method, a rekeying scheme is a data distribution approach
where it revokes
illegal users in an {\em explicit} and {\em immediate} way whereas it
may cause inconvenience for users.
A hybrid approach that appropriately combines these two types of
mechanisms
seems resulting in a good scheme.
In this paper, we suggest such a
hybrid framework by proposing a rekeying algorithm for subset cover
broadcast encryption
framework (for stateless receivers) due to Naor et al. Our rekeying
algorithm
can simultaneously revoke a number of users.
A hybrid approach that appropriately combines these two types of
mechanisms
seems resulting in a good scheme.
In this paper, we suggest such a
hybrid framework by proposing a rekeying algorithm for subset cover
broadcast encryption
framework (for stateless receivers) due to Naor et al. Our rekeying
algorithm
can simultaneously revoke a number of users.
As an important contribution, we formally prove that this hybrid
framework has a pre-CCA like security, where in addition to pre-CCA
power, the adversary is allowed to {\em adaptively}
corrupt and revoke users.
Finally, we realize the hybrid framework by
two secure concrete schemes that are
based on complete subtree method and Asano
method, respectively.

#### Program Committees

- Asiacrypt 2013
- FSE 2012
- Asiacrypt 2006

#### Coauthors

- Mark D. Aagaard (3)
- Xingong Chang (1)
- Guanhan Chew (1)
- Zong-Duo Dai (1)
- Kishan Chand Gupta (3)
- Jingnan He (1)
- Shaoquan Jiang (3)
- Khoongming Khoo (1)
- Hian-Kiat Lee (1)
- Kalikinkar Mandal (1)
- Yassir Nawaz (3)
- Khoa Nguyen (1)
- Valentin Suder (2)
- Yin Tan (1)
- Huaxiong Wang (1)
- Teng Wu (1)
- Gangqiang Yang (3)
- Amr M. Youssef (2)
- Bo Zhu (2)