PPT Slide

Phase II:

H={ (i1 , Xi ) , …. , (in-1 , Xi ) }

• DR checks if exists EH

H ? EH ? {(1,X1), … , (4n,X4n)}

such that:

1. | EH | = 3n
2. All 3n points of EH are on the curve of some polynomial f(t) of degree n-1

• If yes, DR outputs constant term M of f(t) .

• Otherwise, DR outputs “Failed proof”.

n-1

1