Lattice-Based Accumulator and Application to Anonymous Credential Revocation

Motivation: Revoking Anonymous Credentials

In a typical anonymous credential system, a user, Bob, receives a credential from an organization. He can then prove to a vendor that he satisfies a certain predicate (e.g., “is over 21”) without revealing his identity. A critical challenge is credential revocation. If Bob’s driving license is revoked, the system must prevent him from continuing to use it. Simple solutions like expiration dates are insufficient for immediate, fine-grained revocation.

A powerful cryptographic primitive for this task is a positive dynamic accumulator. This system allows for the compact representation of a set of elements, enabling efficient proof of membership.

Applying Accumulators to Revocation

The proposed solution integrates an accumulator into the credential system:

1. Issuance: When Bob receives his credential, he is also given a unique random element x and a corresponding membership witness w_x for an accumulator. The credential itself is tied to x.
2. Verification: To redeem his credential, Bob must now prove two things in zero-knowledge:
   • His credential satisfies the required predicate P.
   • He possesses an element x and a valid witness w_x showing that x is in the current public accumulator A.
3. Revocation: To revoke Bob’s credential, the organization simply deletes the element x from the accumulator. This invalidates the second part of Bob’s proof, effectively making his credential unusable.

A key desired property is communication efficiency, where the public accumulator value A and existing user witnesses do not need to be updated when new elements are added. Updates should only be necessary for deletions. While classical constructions based on strong-RSA achieve this, prior post-quantum accumulators required updates for both additions and deletions. This work introduces a post-quantum construction that is communication-efficient.

Core Construction: An Updatable Digital Signature Scheme

The core idea is to build the accumulator from a special type of digital signature scheme that supports public key updates.

• Accumulator Value (A): The public key of the signature scheme.
• Membership Witness (w_x): A signature on the element x.
• Add(x): The organization signs the element x. Since only a new signature is created, the public key (the accumulator value A) remains unchanged.
• Delete(y): The organization uses a special update_pk algorithm to change the public key A to a new value A'. This process generates an update message. The new public key A' is constructed such that it invalidates the signature for y.
• Update Witness: Other users can use an update_sig algorithm with the public update message to update their existing witnesses (signatures) to be valid for the new accumulator value A'.

This design inherently achieves communication efficiency because update messages are only generated during deletions.

A Lattice-Based Instantiation

The talk presents a concrete construction based on the Module Short Integer Solution (Module-SIS) assumption, which is believed to be post-quantum secure.

Key Building Blocks:

• Lattice Trapdoors: A secret key (trapdoor) allows for efficiently solving certain problems, which in this context enables the signing operation. The signature scheme is inspired by the Agrawal-Boneh IBE scheme.
• Homomorphic Operations on Matrices: The construction leverages a scheme that allows for homomorphic evaluation of functions on encrypted matrices. Specifically, it uses indicator functions (f(x) = 1 if x=y, 0 otherwise) to target a specific element for deletion.

Operations:

• Add(x): Signing x involves using the trapdoor to find a short matrix W_x (the witness) such that a public equation holds.
• Delete(y): The accumulator value A is updated by adding a matrix generated by the homomorphic evaluation of an indicator function for y. A_new = A_old + B_indicator(y).
• Update Witness for x: A user updates their witness W_x by adding another matrix H derived from the homomorphic scheme. The properties of the scheme ensure that the updated witness W_x' will be valid with respect to the new accumulator A_new.

A notable property of this lattice-based approach is that the norm of the witness grows slightly with each update. This means the system can only support a polynomially bounded number of deletions before the witness norm becomes too large, a trade-off compared to unbounded deletions in some classical schemes.

Security and Practical Considerations

The base construction has two main caveats:

1. Replacement-Free: Once an element x is added and then deleted, it cannot be added again. Re-adding would allow for the creation of a forged witness.
2. Selective Security: The security proof requires the adversary to declare which element it will forge a witness for before the system parameters are generated.

However, these limitations can be overcome. A known compiler technique can transform this selectively secure, replacement-free accumulator into a fully adaptively secure one by combining it with any standard, adaptively secure digital signature. For the anonymous credential use case, the base construction is often sufficient, as the elements x are chosen randomly, making re-addition highly improbable.

The construction is also compatible with lattice-based zero-knowledge proofs, allowing a user to prove knowledge of a private element x and its witness W_x without revealing them. While performance analysis shows that witness sizes are still large (e.g., ~14 MB), making storage a concern, the corresponding zero-knowledge proofs can be much more compact (~125 KB).

• Tags:
• Cryptography
• Zero-Knowledge Proofs
• Anonymous Credentials
• Post-Quantum Cryptography
• Lattice-Based Cryptography
• Accumulators
• Revocation