The present work investigates the possibility of designing zero-knowledge identification schemes based on hard-on-average problems. It includes a new two-party identification protocol whose security relies on a problem classified as DistNP-Complete under the average-case analysis, the so-called Distributional Matrix Representability Problem. One of the most critical questions in cryptography is referred to the misunderstanding equivalence between using a difficult problem as basis of a cryptographic application and its security. Problems belonging to NP according to the worst-case analysis are frequently used in cryptography, but when random generated instances are used, in most cases there exist efficient algorithms to solve them that make useless their worst-case difficulty. So, by using the search version of the mentioned distributional problem, the security of the proposed scheme is actually guaranteed. Also, with the proposal of a new zero-knowledge proof based on a problem not used before for this purpose, the set of tools for designing cryptographic protocols is enlarged.
