1 of 14

TRIFORS: LINKable Trilinear Forms Ring Signature

G. D'Alconzo - A. Gangemi

CrypTO Conference 2023�26 Maggio 2023

giuseppe.dalconzo@polito.it

2 of 14

https://it.cleanpng.com/png-uxw1c1/

https://www.vhv.rs/viewpic/hooobbw_the-legend-of-zelda-triforce-zelda-png-transparent/

OR Sigma Protocol

(Ring signatures)

Post-Quantum Assumptions

(Trilinear forms)

(Linkable) Trilinear Forms Ring Signature Scheme

TRIFORS and Link-TRIFORS!

Roadmap

3 of 14

Ring Signatures

R. Rivest, A. Shamir, and Y. Tauman, “How to leak a secret,” Asiacrypt 2001.

Introduced in 2001 by Rivest, Shamir and Tauman.

Linkability:

two signatures generated by the same user can be linked (keeping anonymity).

Applications:

  • anonymous signatures;
  • e-voting;
  • transactions (Monero).

4 of 14

The Quantum Menace

  • Old cryptographic assumptions: factorization and dlog.
  • New assumptions: lattices, linear codes, isogenies, etc!

Cryptographic group actions

  • Flexible framework.
  • Easy instantiation.
  • Post-Quantum assumptions!

Group action of G on the set X:

for every g in G, there is a permutation       of X.

​

The elements of G "mix" X.

x

1

x

2

x

3

x

4

x

5

x

6

x

0

x

7

Action of 4 on x

5 of 14

Trilinear Forms

G. Tang, D. H. Duong, A. Joux, T. Plantard, Y. Qiao, and W. Susilo, “Practical post-quantum signature schemes from isomorphism problems of trilinear forms,” Eurocrypt 2022.

Trilinear Forms Equivalence (TFE)

Given two trilinear forms

                                    and

find the matrix A. 

Alternating Tril. Forms Eq. (ATFE)

Given two alternating trilinear forms

                                 and

find the matrix A. 

The group of invertible matrices acts on the set of trilinear forms:

Group action

The set of trilinear forms is a vector space.

�              coefficients needed.

​

IDEA. Alternating forms: zero whenever two inputs are equal. Small vector space:

​

                                              coefficients.

​

6 of 14

(OR) Sigma Protocols

An user holding the key pair              can authenticate itself with a server using a sigma protocol (or identification protocol).

​

Sigma protocol

(interactive)

OR Sigma protocol

Given a set of public keys

                          , an user holding the secret key          can authenticate itself with a server hiding his identity!

Digital Signature

(non interactive)

Fiat-Shamir

Fiat-Shamir

Ring Signature

(non interactive)

7 of 14

OR Sigma Protocol da ATFE 

W. Beullens, S. Katsumata, and F. Pintore, “Calamari and falafl: Logarithmic (linkable) ring signatures from isogenies and lattices,” Asiacrypt 2020.

L'utente I  vuole firmare:

Parametro pubblico        ,

 tale che

2) Challenge e 3) Response

Ogni utente ha le chiavi pubbliche dell'anello e la sua chiave segreta.

Il server ha l'insieme delle chiavi pubbliche.

Response:

​

Response:

​

Commitment: root

  1. Fase di commitment: index-hiding Merkle Tree

root

8 of 14

OR Sigma Protocol from ATFE 

W. Beullens, S. Katsumata, and F. Pintore, “Calamari and falafl: Logarithmic (linkable) ring signatures from isogenies and lattices,” Asiacrypt 2020.

User I  wants to sign:

Public parameter        , keys

 such that

Each user has the public keys of the ring and his secret key.

The server knows the public keys of the ring.

Response:

​

Response:

​

Commitment: root

9 of 14

OR Sigma Protocol from ATFE 

W. Beullens, S. Katsumata, and F. Pintore, “Calamari and falafl: Logarithmic (linkable) ring signatures from isogenies and lattices,” Asiacrypt 2020.

User I  wants to sign:

Public parameter        , keys

 such that

Each user has the public keys of the ring and his secret key.

The server knows the public keys of the ring.

Response:

​

Response:

​

Commitment: root

10 of 14

  • If the challenge is 1, the user does not use the secret key.
  • A malicious user can cheat half of the times.
  • Only 1 bit of security!

!

11 of 14

Optimizations

Using Fiat-Shamir, we get a signature of                                                                                                           bits.

Opt 2

If ch = 0, the response is very long.

​

​

Then, we want that

Using the combinatorial number system, the challenge becames about 128 bit, for every L.

We can fix the number of 1s (K) and 0s (L-K).

Opt 1

If ch=1, we send a seed for these values: 128 bits.

random

Opt 3

Through the repetitions, we generate L seeds and we send K of them in the response.

Seed tree: structure to send less seeds.

The length becomes about

​

​

​

12 of 14

Optimizations

Opt 1

If ch=1, we send a seed for these values: 128 bits.

Opt 3

If ch = 0, the response is very long.

Then, we want that                             .

Combinatorial number system: bijection between the strings of L bits with K ones and the set of integers enumerating them.

​

As a result, for every L the challenge has about 128 bits.

We can fix the number of 1s (K) and 0s (L-K).

Using Fiat-Shamir, we get a signature of                                                                                                           bits.

Opt 2

Seed tree: structure to send less seeds.

The length becomes about

​

​

​

13 of 14

Ok, but concretely?

In November 2022, Beullens attacked the ATFE assumption.

​

New parameters to resist this attack.

W. Beullens, “Graph-theoretic algorithms for the alternating trilinear form equivalence problem,” Cryptology ePrint Archive, 2022.

q

n

L

K

R

2

8

64

4096

2^21

4194301

10

512

23

9.1

10.6

12.8

17.2

23.8

4194301

12

512

23

11.9

13.4

15.6

20.0

26.6

Signature length in KB. R is the size of the ring.

In general, for the first parameters set, we have

8.4 + 0.7Log(R) KB.

14 of 14

More concretely?

Recap

​

  • (Linkable) ring signature competitive with the post-quantum state-of-the-art.

​

  • Analysis of new parameters for ATFE.

​

  • Challenge compression through the combinatorial number system.

​

Thank you!

Questions?