A new procedure for authentication of at least one prover by a verifier, the authentication being based on public and secret key cryptographic techniques and making use of a zero-knowledge protocol. In addition, this protocol is established using the problem of constrained linear equations and finds applications in cryptography. This procedure uses a published matrix M of dimension m.times.n where coefficients are chosen at random from the integers from 0 to d-1, where d is generally a prime number close the square of a number c. The "prover" authenticates itself to a "verifier" by performing hashing functions based on a randomly chosen vector U of dimension m and a randomly chosen vector V of dimension n, the results of which are called commitments and are sent to the prover. The prover then chooses one of several predefined functions and requests that the verifier perform this one predefined function. When the verifier receives a result of the predefined function, it compares the result with the commitments to determine if the prover has provided a correct set of responses. The procedure also can be repeated for other random vectors U and V for increased security.