Method for proving the authenticity or integrity of a message by means of a public exponent equal to the power of two

A computer implemented process comprising:

• obtaining a set of one or more private values Q1, Q2, . . . , Qm and respective public values G1, G2, . . . , Gm, each pair of values Qi, Gi verifying either the quation Gi·Qiv≡1 mod n or the equation Gi≡Qiv mod n, wherein m is an integer greater than or equal to 1, i is an integer between 1 and m, and wherein n is a public integer equal to the product of f private prime factors designated by p1, . . . , pf, at least two of these prime factors being different from each other, wherein f is an integer greater than 1, wherein v is a public exponent such that v=2k, and wherein k is a security parameter having an integer value greater than 1, and wherein each public value Gi for i=1, . . . , m is such that Gi≡gi2 mod n, wherein gi for i=1, . . . , m is a base number having an integer value greater than 1 and smaller than each of the prime factors p1, . . . , pf, and gi is a non-quadratic residue of the ring of integers modulo n;
• receiving a commitment R from a demonstrator, the commitment R having a value computed using the Chinese remainder method from a series of commitment components Rj, the commitment components Rj having a value such that:
• Rj=rjv mod pj for j=1, . . . , f, wherein r1, . . . , rf is a series of integers randomly chosen by the demonstrator;
• choosing m challenges d1, d2, . . . , dm randomly;
• sending the challenges d1, d2, . . . , dm to the demonstrator;
• receiving a response D from the demonstrator, the response D being computed from a series of response components Dj using the Chinese remainder method, the response components Dj having a value such that:
• Dj=rj●Q1,jd1●Q2,jd2● . . . ●Qm,jdm mod pj for j=1, . . . , f, wherein Qi, j=Qi mod pj for i=1, . . . , m and j=1, . . . , f;
• and
• determining that the demonstrator is authentic if the response D has a value such that:
• Dv●G168 1d1●G2ε2d2● . . . ●Gmεmdm mod n is equal to the commitment R, wherein, for i=1, . . . , m, εi=+1 in the case Gi●Qiv=1 mod n and εi=−1 in the case Gi=Qiv mod n.

A computer implemented process comprising:

• obtaining a set of one or more private values Q1, Q2, . . . , Qm and respective public values G1, G2, . . . , Gm, each pair of values Qi, Gi verifying either the equation Gi·Qiv≡1 mod n or the equation Gi≡Qiv mod n, wherein m is an integer greater than or equal to 1, i is an integer between 1 and m, and wherein n is a public integer equal to the product of f private prime factors designated by p1, . . . , pf, at least two of these prime factors being different from each other, wherein f is an integer greater than 1, and wherein v is a public exponent such that v=2k, and wherein k is a security parameter having an integer value greater than 1, and wherein each public value Gi for i=1, . . . , m is such that Gi≡gi2 mod n, wherein gi for i =1, . . . , m is a base number having an integer value greater than 1 and smaller than each of the prime factors p1, . . . , pf, and gi is a non-quadratic residue of the ring of integers modulo n;
• receiving a token T from a demonstrator, the token T having a value such that T=h(M, R), wherein h is a hash function, M is a message received from the demonstrator, and R is a commitment having a value computed such that:
• R=rv mod n, wherein r is an integer randomly chosen by the demonstrator;
• choosing m challenges d1, d2, . . . , dm randomly;
• sending the challenges d1, d2, . . . , dm to the demonstrator;
• receiving a response D from the demonstrator, the response D having a value such that:
• D=r●Q1hu d1●Q2d2● . . . ●Qmdm mod n;
• and
• determining that the message M is authentic if the response D has a value such that:
• h(M, Dv●G1ε1d1●G2ε2d2● . . . ●Gmεmdm mod n) is equal to the token T, wherein, for i=1, . . . , m, εi=+1 in the case Gi●Qiv=1 mod n and εi=−1 in the case Gi=Qiv mod n.

A computer implemented process comprising:

• obtaining a set of one or more private values Q1, Q2, . . . , Qm and respective public values G1, G2, . . . , Gm, each pair of values Qi, Gi verifying either the equation Gi·Qiv≡1 mod n or the equation Gi≡Qiv mod n, wherein m is an integer greater than or equal to 1, i is an integer between 1 and m, and wherein n is a public integer equal to the product of f private prime factors designated by p1, . . . , pf, at least two of these prime factors being different from each other, wherein f is an integer greater than 1, and wherein v is a public exponent such that v=2k, and wherein k is a security parameter having an integer value greater than 1, and wherein each public value Gi for i=1, . . . , m is such that Gi≡gi2 mod n, wherein gi for i=1, . . . , m is a base number having an integer value greater than 1 and smaller than each of the prime factors p1, . . . , pf, and gi is a non-quadratic residue of the ring of integers modulo n;
• receiving a token T from a demonstrator, the token T having a value such that T=h(M, R), wherein h is a hash function, Mis a message received from the demonstrator, and R is a commitment having a value computed out of commitment components Rj by using the Chinese remainder method, the commitment components Rj having a value such that:
• Rj=rjv mod pj for j=1, . . . , f, wherein r1, . . . rf is a series of integers randomly chosen by the demonstrator;
• choosing m challenges d1, d2, . . . , dm randomly;
• sending the challenges d1, d2, . . . , dm to the demonstrator;
• receiving a response D from the demonstrator, the response D being computed from a series of response components Dj using the Chinese remainder method, the response components Dj having a value such that:
• Dj=rj●Q1,jd1●Q2,jd2● . . . ●Qm,jdm mod pj for j=1, . . . , F, wherein Qi,j=Qi mod pj for i=1, . . . , m and j=1, . . . , f;
• and
• determining that the message M is authentic if the response D has a value such that:
• h(M, Dv●G1ε1d2● . . . ●Gmεmdm mod n) is equal to the token T, wherein, for i=1, . . . , m, εi=+1 in the case Gi●Qiv=1 mod n and εi=−1 in the case Gi=Qiv mod n.

A computer implemented process comprising:

• obtaining a set of on eor more private values Q1, Q2, . . . , Qm and respective public values G1, G2, . . . , Gm, each pair of values Qi, Gi verifying either the equation Gi·Qiv≡1 mod n or the equation Gi≡Qiv mod n, wherein m is an integer greater than or equal to 1, i is an integer between 1 and m, and wherein n is a public integer equal to the product of f private prime factors designated by p1, . . . , pf, at least two of these prime factors being different from each other, wherein f is an integer greater than 1, and wherein v is a public exponent such that v=2k, and wherein k is a security parameter having an integer value greater than 1, and wherein each public value Gi for i=1, . . . , m is such that Gi≡gi2 mod n, wherein gi for i=1, . . . , m is a base number having an integer value greater than 1 and smaller than each of the prime factors p1, . . . , pf, and gi is a non-quadratic residue of the ring of integers modulo n;
• recording a message M to be signed;
• choosing m integers ri randomly, wherein i is an integer between 1 and m;
• computing commitments Ri having a value such that:
• Ri=riv mod n for i=1, . . . , m;
• computing a token T having a value such that T=h(M, R1, R2, . . . , Rm), wherein h is a hash function producing a binary train consisting m bits;
• identifying the bits d1, d2, . . . , dm of the token T;
• computing responses Di=ri·Qidi mod n for i=1, . . . , m;
• and
• performing at least one of transmitting the token T and the response Di to at least one verifying entity, or storing the token T and the response Di on a database accessible to the public or to at least one verifying entity.

A memory storing instructions which when executed cause a processor to execute the following method:

• obtaining a set of one or more private values Q1, Q2, . . . , Qm and respective public values G1, G2, . . . , Gm, each pair of values Qi, Gi verifying either the equation Gi·Qiv≡1 mod n or the equation Gi≡Qiv mod n, wherein m is an integer greater than or equal to 1, i is an integer between 1 and m, and wherein n is a public integer equal to the product of f private prime factors designated by p1, . . . , pf, at least two of these prime factors being different from each other, wherein f is an integer greater than 1, and wherein v is a public exponent such that v=2k, and wherein k is a security parameter having an integer value greater than 1, and wherein each public value Gi for i=1, . . . , m is such that Gi≡gi2 mod n, wherein gi for i=1, . . . , m is a base number having an integer value greater than 1 and smaller than each of the prime factors p1, . . . , pf, and gi is a non-quadratic residue of the ring of integers modulo n;
• receiving a commitment R from a demonstrator, the commitment R having a value computed such that:
• R=rv mod n, wherein r is an integer randomly chosen by the demonstrator;
• choosing m challenges d1, d2, . . . , dm randomly;
• sending the challenges d1, d2, . . . , dm to the demonstrator;
• receiving a response D from the demonstrator, the response D having a value computed such that:
• D=r·Q1di·Q2d2· . . . ·Qmdm mod n;
• and
• determining that the demonstrator is authentic if the response D has a value such that:
• Dv·G1ε1d1·G2ε2d2· . . . ·Gmεmdm mod n is equal to the commitment R, wherein, for i=1, . . . , m, εi=+1 in the case Gi·Qiv=1 mod n and εi=−1 in the case Gi=Qiv mod n.

A memory storing instructions which when executed cause a processor to execute the following method:

• obtaining a set of one or more private values Q1, Q2, . . . , Qm and respective public values G1, G2, . . . , Gm, each pair of values Qi, Gi verifying either the equation Gi·Qiv≡1 mod n or the equation Gi≡Qiv mod n, wherein m is an integer greater than or equal to 1, i is an integer between 1 and m, and wherein n is a public integer equal to the product of f private prime factors designated by p1, . . . , pf, at least two of these prime factors being different from each other, wherein f is an integer greater than 1, and wherein v is a public exponent such that v=2k, and wherein k is a security parameter having an integer value greater than 1, and wherein each public value Gi for i=1, . . . , m is such that Gi≡gi2 mod n, wherein gi for i=1, . . . , m is a base number having an integer value greater than 1 and smaller than each of the prime factors p1, . . . , pj, and gi is a non-quadratic residue of the ring of integers modulo n;
• receiving a commitment R from a demonstrator, the commitment R having a value computed using the Chinese remainder method from a series of commitment components Rj, the commitment components Rj having a value such that:
• Rj=rjv mod pj for j=1, . . . , f, wherein r1, . . . , rf is a series of integers randomly chosen by the demonstrator;
• choosing m challenges d1, d2, . . . , dm randomly;
• sending the challenges d1, d2, . . . , dm to the demonstrator;
• receiving a response D from the demonstrator, the response D being computed from a series of response components Dj using the Chinese remainder method, the response components Dj having a value such that:
• Dj=rj·Q1,jd1·Q2,jd2· . . . ·Qm,jdm mod pj for j=1, . . . , f, wherein Qi,j=Qi mod pj for i=1, . . . , m and j=1, . . . , f;
• and
• determining that the demonstrator is authentic if the response D has a value such that:
• Dv·G1ε1d1·G2ε2d2· . . . ·Gmεmdm mod n is equal to the commitment R, wherein, for i=1, . . . , m, εi=+1 in the case Gi·Qiv=1 mod n and εi=−1 in the case Gi=Qiv mod n.

A memory storing instructions which when executed cause a processor to execute the following method:

• obtaining a set of one or more private values Q1, Q2, . . . , Qm and respective public values G1, G2, . . . , Gm, each pair of values Qi, Gi verifying either the equation Gi·Qiv≡1 mod n or the equation Gi≡Qiv mod n, wherein m is an integer greater than or equal to 1, i is an integer between 1 and m, and wherein n is a public integer equal to the product of f private prime factors designated by p1, . . . , pf, at least two of these prime factors being different from each other, wherein f is an integer greater than 1, and wherein v is a public exponent such that v=2k, and wherein k is a security parameter having an integer value greater than 1, and wherein each public value Gi for i=1, . . . , m is such that Gi≡gi2 mod n, wherein gi for i=1, . . . , m is a base number having an integer value greater than 1 and smaller than each of the prime factors p1, . . . , pf, and gi is a non-quadratic residue of the ring of integers modulo n;
• receiving a token T from a demonstrator, the token T having a value such that T=h(M, R), wherein h is a hash function, M is a message received from the demonstrator, and R is a commitment having a value computed such that:
• R=rv mod n, wherein r is an integer randomly chosen by the demonstrator;
• choosing m challenges d1, d2, . . . , dm randomly;
• sending the challenges d1, d2, . . . , dm to the demonstrator;
• receiving a response D from the demonstrator, the response D having a value such that:
• D=r·Q1d1Q2d2· . . . ·Qmdm mod n;
• and
• determining that the message M is authentic if the response D has a value such that:
• h(M, Dv·G1ε1d1·G2ε2d2· . . . ·Gmεmdm mod n) is equal to the token T, wherein, for i=1, . . . , m, εi=+1 in the case Gi·Qiv=1 mod n and εi=−1 in the case Gi=Qiv mod n.

A memory storing instructions which when executed cause a processor to execute the following method:

• obtaining a set of one or more private values Q1, Q2, . . . , Qm and respective public values G1, G2, . . . , Gm, each pair of values Qi, Gi verifying either the equation Gi·Qiv≡1 mod n or the equation Gi≡Qiv mod n, wherein m is an integer greater than or equal to 1, i is an integer between 1 and m, and wherein n is a public integer equal to the product of f private prime factors designated by p1, . . . , pf, at least two of these prime factors being different from each other, wherein f is an integer greater than 1, and wherein v is a public exponent such that v=2k, and wherein k is a security parameter having an integer value greater than 1, and wherein each public value Gi for i=1, . . . , m is such that Gi≡gi2 mod n, wherein gi for i=1, . . . , m is a base number having an integer value greater than 1 and smaller than each of the prime factors p1, . . . , pf, and gi is a non-quadratic residue of the ring of integers modulo n;
• receiving a token T from a demonstrator, the token T having a value such that T=h(M, R), wherein h is a hash function, M is a message received from the demonstrator, and R is a commitment having a value computed out of commitment components Rj by using the Chinese remainder method, the commitment components Rj having a value such that:
• Rj=rjv mod pj for j=1, . . . , F, wherein r1, . . . , rf is a series of integers randomly chosen by the demonstrator;
• choosing m challenges d1, d2, . . . , dm randomly;
• sending the challenges d1, d2, . . . , dm to the demonstrator;
• receiving a response D from the demonstrator, the response D being computed from a series of response components Dj using the Chinese remainder method, the response components Dj having a value such that:
• Dj=rj·Q1,jd1·Q2,jd2· . . . ·Qm,jdm mod pj for j=1, . . . , F, wherein Qi,j=Qi mod pj for i=1, . . . , m and j=1, . . . , f;
• and
• determining that the message M is authentic if the response D has a value such that:
• h(M, Dv·G1ε1d1·G2ε2d2· . . . ·Gmεmdm mod n) is equal to the token T, wherein, for i=1, . . . , m, εi=+1 in the case Gi·Qiv=1 mod n and εi=−1 in the case Gi=Qiv mod n.

A memory storing instructions which when executed cause a processor to execute the following method:

• obtaining a set of one or more private values Q1, Q2, . . . , Qm and respective public values G1, G2, . . . , Gm, each pair of values Qi, Gi verifying either the equation Gi·Qiv≡1 mod n or the equation Gi≡Qiv mod n, wherein m is an integer greater than or equal to 1, i is an integer between 1 and m, and wherein n is a public integer equal to the product of f private prime factors designated by p1, . . . , pf, at least two of these prime factors being different from each other, wherein f is an integer greater than 1, and wherein v is a public exponent such that v=2k, and wherein k is a security parameter having an integer value greater than 1, and wherein each public value Gi for i=1, . . . , m is such that Gi≡gi2 mod n, wherein gi for i=1, . . . , m is a base number having an integr value greater than 1 and smaller than eachof the prime factors pi, . . . , pf, and gi is a non-quadratic residue of the ring of integers modulo n;
• recording a message M to be signed;
• choosing m integers ri randomly, wherein i is an integer between 1 and m;
• computing commitments Ri having a value such that:
• Ri=riv mod n for i=1, . . . , m;
• computing a token T having a value such that T=h(M, R1, R2, . . . , Rm), wherein h is a hash function producing a binary train consisting of m bits;
• identifying the bits d1, d2, . . . , dm of the token T;
• computing responses Di=ri·Qidi mod n for i=1, . . . , m;
• and
• performing at least one of transmitting the token T and the response Di to at least one verifying entity, or storing the token T and the response Di on a database accessible to the public or to at least one verifying entity.