PASS - The Polynomial Authentication and Signature Scheme

This tutorial describes PASS, the Polynomial Authentication and Signature Scheme.

1. PASS Parameters
2. Key Creation
3. The PASS Authentication Sequence
4. Why It Works
5. An Example Using Small Numbers
6. Using PASS as a Digital Signature
7. Further Reading

1. PASS Parameters

The basic collection of objects used by PASS (Polynomial Authentication and Signature Scheme) is the ring R that consists of all truncated polynomials of degree N-1 having coefficients modulo q:

a = a₀ + a₁X + a₂X² + a₃X³ + . . . + a_N-2X^N-2 + a_N-1X^N-1 (modulo q).

Polynomials are added in the usual way. They are also multiplied more-or-less as usual, except that X^N is replaced by 1, X^N+1 is replaced by X, X^N+2 is replaced by X², and so on. For more details about the ring R, see the Section 2 of the Algebra Tutorial.

In addition to the numbers N and q, PASS requires that the user specify a number of other parameters. Here is the complete list of PASS parameters:

N the polynomials in the truncated polynomial ring have degree N-1 q the polynomials have coefficients modulo q (the number q must be prime, and the number N must equal N=q-1) df the private key f=(f1,f2) consists of two polynomials, each of which has df coefficients equal to each of 1 and -1 dg the commitment g=(g1,g2) consists of two polynomials, each of which has dg coefficients equal to each of 1 and -1 dc the challenge c=(c1,c2,c3,c4) consists of four polynomials, each of which has dc coefficients equal to each of 1 and -1 S a set of values {a1,a2,...,aN/2} modulo q, so that if a is in S, then a-1 (mod q) is also in S. Bh a bound for the norm of the polynomial h

The following table gives a set of high security PASS parameters.

N q df dg dc Bh High Security 768 769 256 256 1 2.2

These values are provided to give you some idea of the quantities used in commercial applications. For the examples in this tutorial we will use much smaller parameter values:

N q df dg dc Bh Small Illustration Parameters 16 17 5 5 1 2.2

Also for our examples, we will use the set

S = {3, 5, 6, 7, 8, 10, 12, 15}

Keep in mind that these small parameters are for illustrative purposes only and are much too small to provide security.

back to top

2. Key Creation

Pearl, the "Prover", randomly selects two polynomials f₁,f₂ in the ring of truncated polynomials R according to the following rule:

• f₁ and f₂ have df of their coefficients equal to 1, f₁ and f₂ have d_f of their coefficients equal to -1, and f₁ and f₂ have all of the rest of their coefficients equal to 0.

There are obviously many different possible choices. Pearl must keep the value of the polynomials f₁ and f₂ secret, since anyone who knows their values will be able to pretend that she is Pearl.

Pearl's next step is to evaluate the polynomials f₁ and f₂ at each of the elements of the set S. We will write f(S) for this set, that is,

f(S) = (f₁(S),f₂(S)) = {f₁(a₁), f₁(a₂), ..., f₁(a_N/2),f₂(a₁), f₂(a₂), ..., f₂(a_N/2)} (modulo q).

The set of values f(S) is Pearl's public authentication key, and the small polynomials f₁ and f₂ are her private key.

back to top

3. The PASS Authentication Sequence

Suppose that Pearl wants to use PASS to prove her identity to Vinnie, the "Verifier". A PASS Authentication Sequence consists of four steps: Commitment, Challenge, Response, and Verification. Here is how they work.

Commitment
Pearl randomly selects two polynomial g₁ and g₂ having d_g of their coefficients equal to each of 1 and -1, and all of their other coefficients equal to 0. She also computes the values of g₁ and g₂ at each of the elements of the set S,

g(S) = (g₁(S),g₂(S)) = {g₁(a₁), g₁(a₂), ..., g₁(a_N/2),g₂(a₁), g₂(a₂), ..., g₂(a_N/2)} (modulo q).

Pearl keeps the polynomials g₁ and g₂ secret, and she sends the set of values g(S) to Vinnie. The set g(S) is Pearl's commitment.

Challenge
Vinnie randomly selects four polynomials c₁₁,c₁₂,c₂₁,c₂₂ having d_c of their coefficients equal to each of 1 and -1, and all of its other coefficients equal to 0. Vinnie sends the four polynomials c₁₁,c₁₂,c₂₁,c₂₂ to Pearl. These four polynomials are Vinnie's challenge. (See below for a note about the challenge.)

Response
Pearl computes and sends to Vinnie the polynomial

h = c₁₁*f₁*g₁ + c₁₂*f₁*g₂ + c₂₁*f₂*g₁ + c₂₂*f₂*g₂ (modulo q).

The polynomial h is Pearl's response.

Verification
Vinnie checks that Pearl's response satisfies the following two conditions:
(A) Vinnie writes h as h=h₀+h₁X+h₂X²+...+h_N-1X^N-1 with each h_i between -q/2 and q/2, and then he checks that (recall that B_h is a preset parameter):

h₀² + h₁² + h₂₂ + ... + h_N-1² < (B_h*q)².

(B) For every number a in the set S, Vinnie checks that

h(a) = c₁₁(a)*f₁(a)*g₁(a) + c₁₂(a)*f₁(a)*g₂(a) + c₂₁(a)*f₂(a)*g₁(a) + c₂₂(a)*f₂(a)*g₂(a) (modulo q).

Note that Vinnie can check condition (B) because he knows the sets of values f(S) and g(S), and of course he knows the c polynomials, although he does not know the actual f and g polynomials.

If Pearl's response h passes tests (A) and (B), then Vinnie accepts that Pearl has proven her identity.

NOTE: In order to prevent Vinnie from gaining information about Pearl's key, it is better to create the challenge as follows: Vinnie chooses a random bit string b of a specified length, for example 80 bits. Vinnie sends b to Pearl. Then Vinnie and Pearl feed the bit string b into a hash function to create the four polynomials c₁₁,c₁₂,c₂₁,c₂₂. This prevents Vinnie from chooses challenge polynomials with some special property, since he can have no way of predicting the output of the hash function. Note the similarity to the way in which an authentication scheme such as PASS is turned into a digital signature scheme. To do this, one feeds a message m (and a commitment) into a hash function to produce a challenge, which is then used to create the response.

back to top

4. Why It Works

Pearl's response h will pass test (A) because the polynomials f, g, and c all have very small coefficients. Thus the polynomial h = c₁₁*f₁*g₁+c₁₂*f₁*g₂+c₂₁*f₂*g₁+c₂₂*f₂*g₂ will also have small coefficients, so with an appropriate choice of parameters (such as the norm bound B_h), h will almost certainly pass test (A). On the other hand, since h is actually equal to c₁₁*f₁*g₁+c₁₂*f₁*g₂+c₂₁*f₂*g₁+c₂₂*f₂*g₂ , the equality

h(a) = c₁₁(a)*f₁(a)*g₁(a) + c₁₂(a)*f₁(a)*g₂(a) + c₂₁(a)*f₂(a)*g₁(a) + c₂₂(a)*f₂(a)*g₂(a) (modulo q).

will be true for all values of a modulo q. In particular, it will be true for all a's in S, so Pearl's response will also pass test (B).

back to top

5. An Example Using Small Numbers

We suppose that Pearl and Vinnie (or a standards setting committee) have selected the following PASS parameters:

q=17, N=16, d_f=5, d_g=5, d_c=1.

We further suppose that they have chosen the following set of 8 values modulo 17:

S = {3,5,6,7,8,10,12,15}.

Note that every element of S has a multiplicative inverse in S, since

3*6 = 5*7 = 8*15 = 10*12 = 1 (modulo 17).

Although PASS will work even if S does not have this property, the security of the system may be compromised. We also reiterate that the numbers being used in this example do not lead to a secure system. See Section 1 for a list of secure parameter sets.

Key Creation
Pearl creates her key by randomly choosing two polynomial f₁ and f₂ having 5 coefficients equal to each of 1 and -1, and the other coefficients equal to 0. Say Pearl chooses the polynomials

f₁ = 1-X+X²-X³+X⁶-X⁷+X⁸-X¹²+X¹⁴-X¹⁵
f₂ = -X²-X⁵-X⁶-X⁷+X⁹+X¹⁰+X¹¹+X¹³+X¹⁴-X¹⁵

She computes the value of f₁ and f₂ at each of the elements of S,

f₁(S) = {f₁(3),f₁(5),f₁(6),f₁(7),f₁(8),f₁(10),f₁(12),f₁(15)} = {9,10,5,9,1,12,15,10} (modulo 17),

f₂(S) = {f₂(3),f₂(5),f₂(6),f₂(7),f₂(8),f₂(10),f₂(12),f₂(15)} = {14,9,16,5,14,1,2,8} (modulo 17).

The set f(S)=(f₁(S),f₂(S)) is Pearl's public authentication key.

Commitment
Now suppose that Pearl wants to prove her identity to Vinnie. She randomly selects two polynomials g₁ and g₂ having 5 coefficients equal to each of 1 and -1, and the other coefficients equal to 0. Say Pearl chooses the polynomials

g₁ = X²+X³-X⁴+X⁵-X⁷+X⁸-X⁹-X¹⁰-X¹²+X¹³
g₂ = X+X⁴+X⁵-X⁶+X⁷-X⁸-X⁹-X¹¹-X¹³+X¹⁵

She keeps g₁ and g₂ itself secret, but she evaluates g₁ and g₂ at the elements of S and sends these values to Vinnie:

g₁(S) = {g₁(3),g₁(5),g₁(6),g₁(7),g₁(8),g₁(10),g₁(12),g₁(15)} = {2,16,7,10,0,14,14,10} (modulo 17),

g₂(S) = {g₂(3),g₂(5),g₂(6),g₂(7),g₂(8),g₂(10),g₂(12),g₂(15)} = {8,5,1,1,5,8,2,9} (modulo 17).

Challenge
Vinnie then challenges Pearl by sending her four challenge polynomials c₁₁, c₁₂, c₂₁, c₂₂ randomly selected with 1 coefficient equal to each of 1 and -1, and the other coefficients equal to 0, say

c₁₁=1-X¹³, c₁₂=-X²+X⁴, c₂₁=-X²+X¹⁵, c₂₂=-X⁷+X¹³.

Response
Pearl uses Vinnie's challenge polynomials c_ij and the polynomials f_i and g_j that she alone knows to compute the quantity

h = c₁₁*f₁*g₁ + c₁₂*f₁*g₂ + c₂₁*f₂*g₁ + c₂₂*f₂*g₂
= -2-4X-10X²-9X³-15X⁴-X⁵ -2X⁶-5X⁷+X⁸+X⁹ +9X¹⁰+15X¹¹+2X¹²+16X¹³ +X¹⁴+3X¹⁵ (modulo 17).

Note that in computing this quantity, Pearl always sets X¹⁶=1, X¹⁷=X, and so on.

Verification
Vinnie sums the squares of the coefficients of h and finds that

h₀² + h₁² + h₂² + ... + h_N-1² =1034.

Since this is less than (Bh*q)2=1398.6, Pearl's response passes test (A). Next Vinnie computes the values

h(a) (modulo q)

and

c₁₁(a)*f₁(a)*g₁(a) + c₁₂(a)*f₁(a)*g₂(a) + c₂₁(a)*f₂(a)*g₁(a)+ c₂₂(a)*f₂(a)*g₂(a) (modulo q)

for each number a in S and checks if they are equal. For example, taking a=7 gives

h(7) = 9 (modulo 17)

and

c₁₁(7)*f₁(7)*g₁(7) + c₁₂(7)*f₁(7)*g₂(7) + c₂₁(7)*f₂(7)*g₁(7)+ c₂₂(7)*f₂(7)*g₂(7) = 9 (modulo 17).

Note that in computing this last quantity, it was not necessary to know the f_i and g_j as polynomials; it was only necessary to know their values at a=7.A similar computation for the other a's in S reveals that Pearl's response passes test (B), so Vinnie accepts that Pearl has proven her identity.

back to top

6. Using PASS as a Digital Signature

Any authentication scheme of the commitment, challenge, response type can be transformed, with the addition of a hash function, into a digital signature scheme. A hash function H is a function that takes as input a bit string B of arbitrary length and gives as output a bit string H(B) of some specified length (e.g., 80 bits) in such a way that it is very difficult to predict ahead of time what the output string will be. Another way to say this is that although it is very easy to compute H(B), it is very difficult to find a B such that H(B) has a specified value.

In order to use PASS to create a digital signature, we assume that a hash function H has been specified that takes an arbitrary bit string as input and produces as output an 80 bit string. We also use a formatting function F that takes an 80 bit string and turns it into a valid set of challenge polynomials c=(c₁₁, c₁₂, c₂₁, c₂₂). Further, if B and C are bit strings, we write B | C to denote the concatenation of B and C.

Now suppose that Pearl wants to sign a message M using her authentication key f=(f₁,f₂).

• Pearl picks commitment polynomials g=(g₁,g₂) at random and computes her commitment g(S).
• Pearl constructs the four challenge polynomials c=(c₁₁, c₁₂, c₂₁, c₂₂) by computing c = F(H(g(S) | M)). In other words, Pearl simulates a challenge by hashing together the commitment and the message and using the result to create a challenge polynomial.
• Pearl computes the response h to the commitment g and the challenge c, using her private key f, in the usual way: h = c₁₁*f₁*g₁+c₁₂*f₁*g₂+c₂₁*f₂*g₁+c₂₂*f₂*g₂ .
• Pearl's signed message is then the message M followed by the signature (g(S),h).
• To verify that Pearl signed the message m, Vinnie computes c from g(S) and M by using the publicly available hash function H and formatting function F. He then uses Pearl's public key f(S) to verify that the response h was generated by Pearl, i.e., by someone with knowledge of the private key f. This verifies Pearl's signature on the message M.

back to top

7. Further Reading

A complete description of the PASS authentication scheme with full technical details is given in the paper

Polynomial Rings and Efficient Public Key Authentication, Jeffrey Hoffstein, Daniel Lieman, Joseph H. Silverman, in Proceeding of the International Workshop on Cryptographic Techniques and E-Commerce (CrypTEC '99), M. Blum and C.H. Lee, eds., City University of Hong Kong Press, to appear.

This paper may be downloaded in a variety of formats from the NTRU Technical Center.

The following are some additional sources to learn about algebra, number theory, algorithms, and cryptography.

• A Course in Computational Algebraic Number Theory, H. Cohen, GTM 138, Springer-Verlag, Berlin, 1993.
• A Friendly Introduction to Number Theory, J.H. Silverman, Prentice-Hall, New Jersey, 1997.
• Cryptography: Theory and Practice, D. Stinson, CRC Press, Boca Raton, 1995.
• Handbook of Cryptography, S. Vanstone, P. Van Oorschot, A. Menezes, CRC Press, Boca Raton, 1996.