New Digital Signature Scheme - DEFI

[Martin Feussner]

Dear all,

The EHTv3/EHTv4 team (Martin Feussner and Igor Semaev) have come up with a new digital signature scheme which we call DEFI. You can find the paper about it at: https://eprint.iacr.org/2024/679

It is a hash-and-sign digital signature scheme based on isotropic quadratic forms over a commutative ring of characteristic 0. No modular transforms are used in the digital signature algorithm in this work, all calculations are performed in the ring of integers. Therefore, the security of the proposed algorithm does not rely on solving multivariate polynomial equations over finite fields. Also, advances in solving common lattice problems such as SVP and CVP do not seem to undermine the new scheme. The security of the scheme lies in solving a system of quadratic Diophantine equations over rational integers.

The paper provides parameters for DEFI-128 which is of 128-bit security (NIST security category 1). It is very fast (with its reference implementation) and has small key and signature sizes:

• Public Key - 800 bytes
• Private Key - 48 bytes
• Signature - 432 bytes

• Key Generation - 0.431 ms
• Signature Generation - 0.177 ms
• Signature Verification - 0.082 ms

We invite cryptanalysts to have a look at our scheme and we also provide a 64-bit challenge for those of you keen to break it. We will appreciate any comments or discussions on potential vulnerabilities or improvements.

Best regards,
Martin Feussner and Igor Semaev

[Phong Nguyen]

Dear Martin Feussner and Igor Semaev,

> --
> You received this message because you are subscribed to the Google Groups "pqc-forum" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
> To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/b2250ee6-b498-43c4-9902-b64083f74aean%40list.nist.gov.

[Phong Nguyen]

Dear Martin Feussner and Igor Semaev,

Thanks for the interesting scheme.
We believe that DEFI is not secure.
As a proof of concept, we recovered the secret key corresponding to your DEFI-64 challenge,
which can be checked in the sage script at the end of this message.
We will provide details shortly: in this example, the secret key was recovered by a lattice attack using only 4 signatures.

Best regards,
Henry Bambury and Phong Nguyen
----------------------
Z = IntegerRing()
R = PolynomialRing(Z, 'x'); x = R.gen()
S = R.quotient(x^32 + 1, 'a'); a = S.gen()
MM = MatrixSpace(S,4,4,sparse=False)
C=MM([[[10, 0, 9, -6, 3, 0, 8, -8, -12, -8, 6, 8, 0, 22, -8, -24, -3, 4, -16, -6, 18, -20, -8, 24, -8, -2, 10, 0, -8, 0, -25, -24],
[-17, -7, 14, 9, -1, 11, 2, 3, 32, -5, -12, 18, 6, -7, 22, 2, -4, 37, 24, 0, 11, 6, 9, 26, 2, -12, 6, 14, -8, 13, 2, 0],
[36, -31, -1, -31, -10, 27, 30, -24, -2, 19, 1, 24, -10, -22, -2, 48, -28, 6, 10, 19, 29, 30, -37, -20, 8, 1, -10, -3, -39, 17, 29, 1],
[14, -6, 11, -2, 1, 4, 6, 5, -3, 16, -6, 14, 8, 5, 6, 26, 19, 10, 14, 12, 3, 15, -2, 4, 8, 11, -5, 9, -11, -3, 9, 7]],
[[-17, -7, 14, 9, -1, 11, 2, 3, 32, -5, -12, 18, 6, -7, 22, 2, -4, 37, 24, 0, 11, 6, 9, 26, 2, -12, 6, 14, -8, 13, 2, 0],
[-5, -2, -21, 2, -53, -60, 19, -28, -60, -8, -29, -32, 21, -28, -65, -2, 13, -20, -13, -24, -41, 24, 26, -36, 8, 30, 1, 20, 13, -24, 21, 62],
[36, -25, -84, 9, 62, -23, -51, -23, -40, 36, 42, -95, -23, 76, 14, -6, -7, -70, 22, 90, -24, -69, -7, 5, 25, 55, -57, -25, 92, 32, -43, -17],
[-21, -15, -30, -33, -10, -32, -36, -22, -30, -19, 4, -32, -46, -8, -3, -17, 3, -13, -21, 10, -5, -16, 9, 13, 9, 34, -4, -12, 19, 24, 18, 15]],
[[36, -31, -1, -31, -10, 27, 30, -24, -2, 19, 1, 24, -10, -22, -2, 48, -28, 6, 10, 19, 29, 30, -37, -20, 8, 1, -10, -3, -39, 17, 29, 1],
[36, -25, -84, 9, 62, -23, -51, -23, -40, 36, 42, -95, -23, 76, 14, -6, -7, -70, 22, 90, -24, -69, -7, 5, 25, 55, -57, -25, 92, 32, -43, -17],
[-82, 170, 125, -86, -54, -86, 89, 140, -66, -174, 11, 118, 37, 38, -110, -28, 180, 100, -187, -102, -28, 44, 115, -76, -167, 28, 158, 8, -31, -44, -3, 190],
[-42, -7, 19, -23, -20, -27, -21, 17, -5, -35, -5, 51, 10, 35, -17, -44, 2, 33, -7, -22, 12, -7, 11, -7, -45, -11, 46, 22, -1, 12, -34, 34]],
[[14, -6, 11, -2, 1, 4, 6, 5, -3, 16, -6, 14, 8, 5, 6, 26, 19, 10, 14, 12, 3, 15, -2, 4, 8, 11, -5, 9, -11, -3, 9, 7],
[-21, -15, -30, -33, -10, -32, -36, -22, -30, -19, 4, -32, -46, -8, -3, -17, 3, -13, -21, 10, -5, -16, 9, 13, 9, 34, -4, -12, 19, 24, 18, 15],
[-42, -7, 19, -23, -20, -27, -21, 17, -5, -35, -5, 51, 10, 35, -17, -44, 2, 33, -7, -22, 12, -7, 11, -7, -45, -11, 46, 22, -1, 12, -34, 34],
[-25, -28, -19, -30, -43, -30, -42, -4, -9, -16, -16, -16, -20, -18, -2, -2, 1, 12, 5, -14, -6, -2, 5, 16, 2, 2, 14, 16, 5, 30, 10, 22]]])
print("The public key is C = ",C)
J = MM([[1,0,0,0],[0,1,0,0],[0,0,-1,0],[0,0,0,-1]])
print("J = ",J)
B=MM([[[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]],
[[0, 2, 0, 2, 0, 0, 0, 0, -2, 0, 2, 0, -2, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, 1, -2],[0, 1, -1, 1, 2, -1, 0, 1, 0, 1, 0, -1, 1, 3, 0, 1, 1, 0, 2, 1, 0, 1, 1, 0, 0, 0, 0, 1, 3, 0, -1, 1],[-2, 4, -2, -1, 1, 2, 0, 2, -1, -1, 3, -1, -1, -2, 1, 1, 5, 0, -2, 0, 1, -1, 0, -2, -1, 3, 1, -2, 0, 0, 2, 2],[-1, 1, 0, 0, 0, 1, 1, 0, 0, -1, 1, 1, 2, 1, 2, 0, 1, 1, -1, 1, 1, 1, 1, 0, 0, 0, 1, -1, 1, 0, 0, 0]],
[[0, -1, -1, 0, 0, -2, 0, 0, 0, 0, 0, 0, 0, 0, -2, 0, -2, 0, 1, 0, 0, 0, 0, 0, 1, 0, -2, 0, 0, -2, 0, 0],[1, 2, 0, 1, 0, -1, 1, 3, 0, -1, 1, -1, 0, 4, -1, -1, 2, 0, 0, 0, -1, 0, 2, -1, -3, 0, -1, 0, 2, -2, -2, 1],[-2, 3, -4, -2, 5, 2, -2, 0, -1, 2, 5, 1, -4, 1, 3, 0, 1, 0, -4, 1, 1, -5, -1, -1, 2, 2, 0, -6, 1, 3, 2, 0],[0, 1, 0, -1, 0, 1, 0, 1, 0, 0, 1, 2, 0, 1, 2, 0, 0, -1, -1, 0, 1, 0, -1, -2, -1, -2, 1, -2, 0, 1, -1, -1]],
[[-1, 0, -1, -2, 2, 0, 0, -2, 0, 0, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0],[-1, 0, -1, 0, 1, -1, -3, -1, -1, -1, 0, -2, -1, -1, -1, 1, 0, 0, 1, 0, 0, -3, 0, 1, -1, 0, 1, -1, 1, 3, 0, 0],[-3, 0, 1, -1, 1, 1, 3, 0, 0, -6, -1, 1, 2, -1, 1, -1, 3, 2, -1, 0, 1, 0, 1, -3, -3, -3, 4, 0, -1, 1, 2, 1],[0, -1, 1, -1, -1, -2, -1, -2, 0, -1, -1, 1, 0, -1, 0, -1, 1, 0, 0, -1, 0, -1, 0, 1, 0, -1, 1, 0, 1, 0, 2, 2]]])
print("The secret key is B = ",B)
print("We check that C-B^t*J*B = ",C-B.transpose()*J*B)

> Le 6 mai 2024 à 11:11, Martin Feussner <feussne...@gmail.com> a écrit :
>

[Martin Feussner]

Dear Henry Bambury and Phong Nguyen,

We are pleased that you have taken interest in our scheme. The secret key is indeed the same one used in the construction (up to sign +-).  We look forward to the details.

Best regards,

Martin Feussner and Igor Semaev