Video summary
The video presents a cryptographic breakthrough regarding three-move blind signature schemes within pairing-free groups, addressing a long-standing open problem in the field. The presenter explains that while classical constructions like those by Chaum and Pedersen offered limited concurrency or relied on insecure assumptions such as the Ross problem, recent advancements have been restricted to models requiring algebraic group properties (AGM). This work successfully constructs a scheme that achieves full security under unbounded concurrency without relying on AGM, instead basing its proof solely on standard hardness assumptions like the Decisional Diffie-Hellman (DDH) problem within the random oracle model. Although this approach results in signatures consisting of over fifty elements—making it less efficient than concurrent works achieving thirty-three elements—it represents a significant theoretical milestone by solving an issue that remained unresolved for more than two decades using only black-box access to groups and oracles.
To achieve these security guarantees, the presentation details a novel architectural design inspired by the online-offline paradigm but adapted specifically for blind signatures. The core innovation involves deferring the use of the actual message until later in the protocol by having the signer generate one-time keys upfront. During the interactive phase between the user and signer, they do not operate directly on the original message or key; instead, they execute a formal scheme based on an encryption of the blinded one-time key. This structure ensures that any forgery attempt either breaks the underlying one-time signature security or forces the adversary to generate more valid signatures than allowed by the number of protocol executions, thereby satisfying the property known as one-more unforgeability while maintaining blindness against malicious signers who cannot link new signatures to previous interactions.
The technical implementation relies heavily on generalized versions of blind Schnorr protocols that allow for linear shifts in both statements and proof components. By translating algebraic statements about messages into operations involving encryptions, the scheme leverages these extended tools to create unlinkable proofs without exposing sensitive data prematurely. The presenter clarifies a subtle distinction regarding security reductions, noting that while one-time signatures are often cited as sufficient, the specific reduction technique employed here necessitates two-time signature security to handle rewinding attacks effectively; however, this requirement is easily met by standard Okamoto-Schnorr constructions extended for multiple uses. Furthermore, the talk acknowledges concurrent research from other groups that achieved similar goals with better efficiency through different instantiations of algebraic statements and optimized one-time signatures, yet emphasizes that their techniques can be integrated into the presented framework to further enhance performance while maintaining rigorous security proofs under standard assumptions.
Read the full video transcript
Hello everyone.
I'm Yanbo Chen from the University of
Ottawa.
I'm going to present my work about
three-move blind signatures in
pairing-free groups.
A blind signature scheme involves a
signer and a user.
The signer holds a secret signing key,
while the user holds the message.
They run an interactive protocol
such that the user can obtain a
signature on the message.
A blind signature scheme should satisfy
two security notions.
The first one is called blindness.
Here we consider a malicious signer.
Roughly,
blindness says that
running the protocol should not leak
information about the message.
More formally, it says that
after running the protocol,
when the adversary sees the message
together with the signature generated by
the protocol,
they should not be able to link this
tuple with the previous protocol run
that generated the signature.
The second notion is called one-more
unforgeability.
Now we consider malicious users.
It says that after running the protocol
for K times
with an honest signer,
the adversary should not be able to
output more than K valid tuples of
message and signatures.
Blind signatures have found application
in, for example,
privacy pass protocol and e-cash system.
In this work, we focus on blind
signatures in pairing-free groups.
Now, let me review some important
related work.
Dating back to 1992,
Chaum and Pedersen and Okamoto proposed
three new blind signature schemes for
Schnorr and Okamoto Schnorr schemes.
However, the security analysis of this
scheme
has a long history.
The blind Okamoto Schnorr scheme was
first proven secure under polylog many
concurrent sessions.
This means that to guarantee security,
we require the signer to open a limited
number of sessions at the same time.
Here, polylog is an asymptotic term.
If we look at the concrete number, it's
very bad.
For example,
for a standard 256-bit group,
it only allows two or three concurrent
sessions.
Later, the blind Schnorr schemes was
proven concurrent secure
uh in GGM or DAGM.
Additionally, assuming the hardness of
the Ross problem,
the Ross problem
is not related to group,
and unfortunately,
it turns out that the Ross problem is
actually easy.
This means that
the bounded concurrency
is not just a limitation of the proofs,
but is inherent for these schemes.
The blind Schnorr and Okamoto Schnorr
schemes are indeed insecure
when we have more concurrent sessions.
>> There are also other constructions of
three move schemes.
Our paper proposed the first three move
scheme proven secure with unbounded
concurrency.
The original proof only assumes the
random oracle model.
However, it was pointed out that the
original proof is flawed.
And the
uh and the proof was only fixed in the
GGM.
Recently,
it was also fixed in the AGM.
There are also some recent proposals of
three move schemes
that achieve full security
and better efficiency than our best
scheme,
but they are also in the GGM or AGM.
Finally, a recent line of work
constructs blind signature schemes
proven full security
only assuming the random oracle model.
This line of work has achieved
short signatures in communication,
for example, consisting of six elements.
And the scheme can be proven secure
under standard assumptions like DDH,
CDH, or even Dlog.
However,
all of them have at least four moves.
Now, a quick summary of the existing
schemes.
We have some classical three move
constructions,
but they are only secure under limited
concurrency.
We have three move schemes that is
secure with unbounded concurrency, but
only in the AGM.
Recently, we have four move fully secure
scheme without the AGM.
So, there is an obvious gap.
Can we construct a three move scheme
that can be proven secure under
unbounded concurrency without the AGM?
Here, I have to narrow down the
question.
We require only black box use of the
underlying groups and random oracle.
For non-black box construction, we have
two move schemes from generic
transformation.
But, the instantiation in pairing-free
group is often inefficient.
A recent and concurrent work shows that
for black box pairing-free construction,
three move is the best we can hope for.
The question of constructing a three
move scheme is not new at all.
This goal is very natural
because many pairing-free signature
schemes are based on classical three
move signature protocols.
And from this signature protocols, you
also have some very natural blind
signature construction
that is
the blind Schnorr and Okamoto-Schnorr
scheme.
Although, unfortunately, they are not
fully secure.
I just mentioned that
there have been at least two attempts on
this question in the related work.
However, they were pointed out to fail
later.
So, after these failed attempts, this
question remains open for more than 20
years.
In this work, we solve this old problem.
We construct a three-move scheme.
We prove its full security in the random
oracle model based on standard DDH.
The signature and communication consists
of constant number of elements.
Although the concrete number are more
than 50, so the scheme is much less
efficient than the construction in the
AGM.
In a concurrent work, also in Crypto,
Champ, Wrestler, and Tessaro solved the
same problem.
At high level,
our techniques are very similar.
But somehow they achieve better
efficiency
with signature and communication of more
than
30 elements.
And they also achieve more extensions
like strong unforgeability and partial
blindness.
Now, let's get into the technical part.
Before going to the construction, I want
to recall some useful tools which can be
considered as originally coming from the
Schnorr protocol.
In the Schnorr scheme,
the signer and the user run the
classical
sigma protocol for the log.
At the same time, the user apply a
linear shift on each component of the
sigma protocol.
So, the final signature is unlinkable to
the previous interaction.
The first useful thing is that this
protocol can be generalized to something
called blind signature protocol for
linear statements?
For a large family of statements in
group,
we have a three-move protocol for the
user to obtain an unlinkable proof of
the statement.
The second thing is that a user can not
only shift the component of the proof,
but can also apply a linear shift to the
statement itself.
So, we have an extended version of the
protocol
for the user to obtain a proof for an
unlinkable shifted statement.
This generalized and extended protocol
is very useful in basically all
pairing-free blind signature
constructions.
Now, let me start from a very high-level
description of the recent four-move
schemes.
The first part of the protocol is that
the signer and the user blindly set up a
statement about the message M using two
moves.
The second step is that starting from
the second move, they run the three-move
protocol to blindly issue a proof for
the statement.
Meanwhile, the user shifts a statement
to make it unlinkable to the previous
interaction.
The final signature consists of the
statement and a proof.
Now, I want to further simplify this
four-move scheme.
In the first part,
the signer and the user set up the
statement without blindness.
So, I can let the user send a message M
in plain text.
In the second part, we still use the
blind protocol.
Here, note that the message is used at
the very beginning of the protocol to
set up the statement.
However, if we want to have a three-move
scheme,
uh in a three-move scheme, the signer
initiates the protocol,
and the user start participating
in the scheme only from the second move.
So, the message can be used only from
the second move.
So, to get a three-move scheme, we must
answer a question.
How can we defer the use of M?
Our idea is to apply the online-offline
paradigm
to the formal scheme.
Between the signer and the user, they
run the formal scheme
not on the original message M,
but on a verification key of a one-time
signature scheme.
The one-time key is chosen by the
signer, not the user.
So, in the protocol,
the signer runs the first move on its
own,
and there only remains three moves
between the signer and the user.
At the same time,
the signer issues the one-time signature
on the message M.
The final signature consists of the
one-time key,
the signature on the one-time key
generated by the formal protocol,
and the one-time signature on the
message.
The reasoning for one more
unforgeability is that
if a forgery contains a one-time key
that has been used by the signer,
then the adversary has broken the
one-time security.
If the forgery contains a one-time key
that has not appeared before,
then the adversary has
generated one more forgery
for the formal protocol.
Remember that previously we forget about
blindness.
Now we want to recover it.
First,
we actually required
a blind protocol for issuing a one-time
signature.
So,
the user doesn't need to send a message
in plain text.
Also,
we want the user
to blind the one-time key
because the signer know the one-time
key.
So, if the one-time key is in a final
signature,
it is linkable to the previous
interaction.
Next,
we require a different functionality on
the formal scheme.
We want the protocol to generate a
signature not on the original one-time
key,
but something that verify
an encryption of the one-time key.
The encryption acts like an extractable
commitment, so in the protocol no one
can decrypt it.
It's secretly generated by the user
during the protocol,
so it's unlinkable to the previous
interaction.
Now, the final signature contains
an encryption of the one-time key,
a signature on the encryption generated
by the formal protocol,
a blinded one-time key,
and a blinded one-time signature.
Finally, the user also generates a
non-interactive proof for the relation
between the encrypted one-time key and
the blinded one-time key.
It's the user who encrypts and blinds
the key, so
it can generate this proof fully
locally.
Here we have the full high-level
structure.
Now, let's look at the instantiation.
First, for the formal scheme,
we note that
in a recent blind signature proposed by
Brandt, Hofheinz, Kiltz, and Rassler,
in the first step,
the signer and the user set up an
algebraic statement about the message.
The statement looks like
a C commits to X + W * M,
where X and W are committed in the
public key,
or something.
So, the whole statement is a composition
of many things like these.
Um
but the point is that
this statement
directly talk about the message M as a
group element.
The scheme doesn't hash the message
like many other scheme.
So, it's easy to translate this
statement
to talk about only the encryption of the
message.
In particular,
this translation is linear.
So, we can happily use the extended
version of the blind Schnorr protocol.
For blind signature, we use the one-time
version of Okamoto-Schnorr.
We have R becomes part of the public
key, not part of the signature.
To get a blind signature scheme, we
modify the blind Okamoto-Schnorr
signature scheme.
Here, let me talk about one detail that
I ignored before.
We actually require a two-time signature
scheme, not one-time.
The reason is that in the security
reduction,
we need to reduce to the one-time
security.
So, the reduction need to rewind the
adversary to extract the witness of the
proof and use the witness to recover the
original one-time signature.
This means that
to get one forgery,
the reduction need to issue two
signature during rewinding.
So, we actually realize on
two-time security, not just one-time.
But, this is no problem because
Okamoto-Schnorr is easy
to extend to two-time security.
Finally, let me talk about the
concurrent work by Chaum, Wrestler, and
Tseng-Yuh.
Our techniques are similar in the sense
that
although they have a different
demonstration,
I can also put this scheme in my
framework.
In my framework,
they achieve better efficiency
by finding better instantiations for
both parts.
For the formal scheme,
they give better instantiations from
algebraic max.
For the one-time signature part,
they shows that using the original blind
Okamoto-Schnorr protocol is enough.
The way they use Okamoto-Schnorr is very
similar to a one-time signature scheme.
So, here for me, the most interesting
part is that
they go into the black box
and shows that for Okamoto-Schnorr, it's
actually not needed
to extend to two-time security.
And this is my talk. Thanks.