Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

    Presentations 2023
Presentation

MinRank-based zero-knowledge proofs and signatures

August 9, 2023

Presenters

Javier Verbel - Technology Innovation Institute (UAE)

Description

Abstract. The MinRank problem involves finding a non-trivial low-rank matrix in a given linear code of matrices over a finite field. It is NP-complete and considered hard for quantum adversaries. The MinRank problem first appeared in cryptography in 1999 in the cryptanalysis of the Hidden Field Equations (HFE) cryptosystem. Since then, it has been instrumental in the cryptanalysis of many schemes, including the NIST standardization candidates ROLLO, GeMSS, and Rainbow. In addition, zero-knowledge proofs, signatures, and ring-signatures schemes based on the MinRank problem have been known since early 2000. Currently, two signature schemes (MiRitH and MIRA) are candidates in NIST's new post-quantum standardization process. In this talk, we introduce the MinRank problem and the main algorithms to solve it. Then, we will go over the techniques used to construct zero-knowledge proofs for MiRitH, MIRA, and previous MinRank-based schemes.

Presented at

Crypto Reading Club talk on 2023-Aug-09

Parent Project

See: Crypto Reading Club

Related Topics

Security and Privacy: cryptography

Created July 25, 2023, Updated August 18, 2023