Video summary
The presentation introduces morphic accumulators as an innovative cryptographic primitive designed to address a fundamental tension in accumulator security: the need for division-intractability versus the preservation of algebraic structure. Traditional accumulators compress sets into short digests using group elements, but standard encoding methods that ensure security by hashing objects into unrelated integers inevitably destroy any underlying mathematical relationships between those objects. This work proposes a novel approach where group exponentiation serves as the hash function instead of generic randomization. By leveraging this specific encoding within the Group Model, the authors demonstrate that it is possible to maintain division-intractability for security while retaining homomorphic properties. Consequently, an accumulator can now verify membership without erasing the algebraic relations between elements, allowing provers to reason about complex structures like subset products directly on the accumulated data.
Building upon this core capability, the talk details three primary applications that leverage preserved algebra to achieve optimal efficiency in proof systems. The first application is a highly efficient range proof for proving that an integer lies within $n$ bits by decomposing it into powers of a generator and accumulating these as group elements; preserving their multiplicative structure allows for constant-size proofs with linear prover time, eliminating the need for expensive zero-knowledge setups previously required. Second, this optimized range proof is integrated into polynomial commitment schemes to remove existing bottlenecks, resulting in commitments that are essentially linear-time to generate while maintaining constant verification costs and flexible evaluation fields crucial for recursive SNARKs. The third application is a linkable ring signature scheme where the deterministic nature of the preserved algebra enables the creation of unique tags based on binary decompositions; this allows signatures from different users or even multiple messages by the same user to be linked if they share specific properties, all while keeping online signing and verification costs constant regardless of the ring size.
The theoretical foundation supporting these applications relies on a new security notion called Group Element Division-Intractability (GEDI), which strengthens standard assumptions to prevent fake subset relations from emerging due to modular arithmetic collisions. The authors prove that under a variant of the modular subset product assumption, their construction ensures that if an integer derived from a group element divides an accumulated product modulo $M$, it must correspond to a genuine subset product in reality rather than being a spurious result of reduction operations. This rigorous security guarantee is essential for soundness when proving statements about original group elements using only the compressed accumulator representations. Ultimately, morphic accumulators provide a unified framework that combines succinct membership proofs with rich algebraic reasoning, opening new avenues for efficient cryptographic protocols where both compact proof sizes and complex structural verifications are required simultaneously without compromising on security or performance.
Read the full video transcript
Hello everyone. I'm Jiajun Xin. Today
I'm going to present our work Morphic
Accumulators and Applications, Opt in
More Range Proofs, Polynomial
Commitment, and Ring Signatures.
This is joint work with Demetris and
Xiao.
Let me start with cryptographic
accumulators. An accumulator compress a
set into a short, possibly constant-size
digest.
To prove X is accumulated in the in the
accumulator, a prover generates a proof
which should be short and easy to
verify, and the verifier is convinced
that X is indeed in the set with
constant verification time.
There are many different kinds of
accumulators, and we are interested in
accumulators built from groups of
unknown order. You can think of Adlers
accumulators as a canonical example,
although the same paradigm also applies
to other unknown order groups.
We're working on group of unknown order,
and let D be a public base element in
the group. Suppose we want to accumulate
a set of integers S1 to Sn, and the
accumulator
is simply the D to the power of the
product of all the elements.
Now I want to prove that
uh Si is a member of the set. I remove
Si from the product and compute the Pi i
equals to D to the product of all the
elements except for Si.
Then the verifier only needs to check
that the Pi i to the power of Si is is
the same as the accumulator.
So, even though the entire set has been
a compressed into one group element, we
can still efficiently prove membership
proofs. And this is one of the region
reasons that group accumulators are so
attractive. This for very succinct
constant-size batch membership proofs
with efficient proving time and
verification.
But there is one important security
requirement hiding in this simple
construction. We cannot accumulate the
arbitrary integers. If some values
outside the set can divide the product
of all the accumulated values, then it
can also produce a valid membership
witness.
So, what we really need from the
this accumulated integers is division
intractability.
It should be hard to find a new value
and divide the product of the
existing ones.
And this is why in practice we don't
directly accumulate the original objects
like set. And traditionally we first
pass each object through a division
intractable encoding. And earlier in
constructions use hash of prime and also
use a
long random oracle outputs. And only
then do we accumulate the resulting
integers.
This solves the security problem. But it
also creates another problem. This
encoding is essentially generic hash.
So, if the original objects had useful
algebraic structures, and the structure
will disappear after the encoding.
For example, if the original
objects are group elements and satisfy
some multiplication relations, after the
DI hashing they just become unrelated
integers. So, the accumulator can still
tell us which elements are in the set,
but it can no longer help us reason
about how these elements are
algebraically related. And this leads to
a question behind this work.
Security requires division
intractability, but standard DI encoding
destroys the algebra.
How can we have have both?
Let me first put this in the broader
context of proof systems.
Many modern succinct arguments follow a
compressing proof paradigm.
The prover starts with a large witness
or structured data set and compress it
into a short binding representations.
The ultimate goal is to keep the prover
roughly linear in the input size while
making the proof and the verification
succinct.
Well, accumulators are particularly
attractive in this paradigm.
They offer O(1) proven proven proving
time, O(1) proof size, and O(1)
verification for membership and subset
statement.
However, standard division intractable
encoding erase algebra,
and uh so, this efficiency is largely
confined to set membership proofs.
Our goal is to preserve the algebra and
extend the same compression proof
efficiency to richer statements. And the
first application I will show is range
proofs.
Suppose I want to prove that X is an
n-bit integer.
We prove through binary decompositions.
Well, accumulate the set as powers of G,
then proving X in the is in the range is
the same as proving G to X is a product
of some subset of these elements.
For example, if X equals to 21, then G
to 21 is the same as G to 1 * G to 4 * G
to 16. And now, we benefit of preserving
preserving algebra becomes clear.
If these powers of G can be accumulated
accumulated while keeping their
multiplication structure, then we can
have we can have the accumulator to
prove the subset product relation very
succinctly.
In fact, this eventually give us an
optimal range proof with O(1) prover,
O(1) proof size, and O(1) verification
with a transparent setup. So, preserving
the
algebra
can buy us something quite powerful.
So, the range proof example suggests
exactly what kind of encoding we would
like. Instead of hashing an element to
an unrelated random integer, we use a
very simple encoding. Group
exponentiation as a DI hash.
We then take the
canonical integer representation of this
group element and put that into the
accumulator. These encodings have a lot
a lot of algebraic structure, so why
should they still be division tractable?
And one of our main technical result is
that integer in our group model this
digital log encodings are indeed
division tractable. But unlike a
standard DI hash, this encoding
preserves the homomorphic properties.
So, now the accumulator give us both the
things at the same time.
Division tractable for security and the
homomorphism for the computations. This
is what we call morphic accumulator.
And from this one idea, we got three
main applications.
First, an optimal ring proof we just
discussed. Linear prover time, constant
proof size, and constant verification
with a transparent setup.
Second, plugging this ring proof into
existing group of on and other
polynomial commitment, remove their main
bottleneck, reducing the prover to
linear time while retaining constant
size proofs and constant group
verification. This also preserves the
flexible evaluation field that is useful
for recursive native SNARKs.
And
And third, a linkable ring signature
scheme with a linear offline work,
constant online signing, constant online
verification, and constant signature
size with a transparent setup.
These look like three rather different
applications, but they are all coming
from the same capacity. We can
accumulate group elements without losing
their algebra.
Now, we can directly accumulate group
elements without destroying their
algebra. So, next question is what can
we actually prove about this accumulated
elements? And the basic capacity we want
is the following.
Suppose we have group elements as one
equals to G2X1,
S2 equals to G2X2, and SN equals to G2XN
in our value group
that have been homomorphically
accumulated.
Given some subset of these elements, we
want to prove that our target group
element Z is is exactly their product.
And importantly, we want the proof size
and verification verification cost to be
constant in the in independent of how
many elements are in the set.
The key point is that there are actually
two different kinds of multiplication
involved.
The accumulator does not operate on the
group multiplication directly. It sees
each group group element through its
canonical integer representations.
And the accumulator accumulate
accumulate integers.
Using the accumulator, the prover can
then give a batch membership proof
showing these factors really come from
the accumulated set.
But what we want to prove is a a
statement in the original group over
group operations.
To bridge these two worlds together, the
prover proves the subset product over
integers using the batch subset proof
showing the product of the subset as
prime.
So, if the S that is a claimed group
product product, it is enough to prove
the product is equivalent to the Z
modulo M. And this is exactly what the
PoK mod N protocol give us.
We also prove that the Z is a valid
element
of the value group by proving knowledge
of exponent.
So, the overall picture is accumulator
subset proof plus modular reductions
proof plus proof of knowledge of
exponent implies a group subset product
proof.
And because the underlying accumulator
proof and the modular proof are constant
size, this gives us a constant size
proof of group operations with an
arbitrary number of accumulated
elements.
There is one subtle soundness challenge.
The product plus KM divides the product
of SI does not guarantee that product is
a subset product of S.
This means the standard division
intractability is not enough for us.
Standard DSS that a fresh encoding Z
should not divide accumulated products.
But our modular proof only gives the
product equal to Z plus KM.
So we need a stronger property that also
considers all the different integer
representations of the same group
element modulo M.
And we call this group element division
intractability or GEDI.
Informally, GEDI says that if Z plus KM
divides accumulated products, then A
should be actually correspond to a
genuine genuine subset product. In other
words, reducing modulo M should not
create a fake subset relations.
Why should this hold?
Given a large modulo M, it should be
computed computationally hard to take a
fresh group group element, add some
multiple of M, and suddenly land on a
divisor of an accumulated product.
We prove the GEDI under a variant of
modular subset product assumption. And
And with GEDI in place, our sub sub
subset product argument is sound.
Range proofs are the core and bottleneck
in many growth based polynomial
commitments.
So replacing the range proofs is ours in
the existing polynomial frameworks
directly leads to a new and efficient
polynomial commitment.
Once our range proofs become optimal,
the growth polynomial commitment become
essentially linear time while keeping
constant proofs, constant group
verification, and flexible evaluation
field.
Finally, let me show a rather different
application in boring signatures.
Suppose we have a ring of Schnorr public
keys
where pub uh pki equals to g2xi.
In addition to these public keys, we
accumulate powers of another generator
h.
For sender i, we define the linkable tag
as t equals to gh to the power of xi.
To produce a signature, the signer first
proves that t corresponds to a valid
subset product of the accumulated
elements.
Intuitively, this combines a sender's
public key g2xi with appropriate powers
of h corresponds to the same binary
decomposition of xi.
Then the signer simply produces a
standard Schnorr signature and the other
public key uh t using gh as a base.
And the verification therefore consists
of constant size subset product proofs
and one Schnorr verification. And the
linkable linkability is in immediate.
Two signatures are linked when their
tags are equal.
Here's a comparison table of our boring
signatures.
Let me first clarify the distinction
between offline and online cost.
Offline work depends only on the ring
and can be performed once when the ring
is fixed, whereas online work is message
dependent and must be repeated for every
signature.
Our construction is the first to achieve
constant size signatures, linkabilities,
and transparent setup. It requires O O
and O offline work to process the ring,
which is
asymptotically optimal because O and
public keys be read.
Once a ring and accumulator are
prepared, online online signing, online
verification, and signature size are all
O of 1.
This is another benefit of preserving
algebra. The accumulator provides
succinct membership. Well, the retained
group structure give us a deterministic
linkable tag.
To conclude, the main contribution of
this work is not only one specific range
proofs or one specific signature
schemes. The main main point is a
primitive, morphic accumulators.
They let us accumulate group elements
while preserving their algebraic
structure. So, we will get division
tractability for accumulator security,
but we also retain enough homomorphism
to prove algebraic relations such as
subset products.
From this single capacity, we obtain
optimal range proofs, efficient
polynomial commitments, and linkable
ring signatures.
I think the broader message is that
morphic accumulators give us a new way
to combine accumulators with algebraic
proof systems, and there may be many
more applications beyond the ones we
show here.
Thanks for listening.