Essentially Optimal Interactive Certificates

in Linear Algebra

Erich L. Kaltofen
North Carolina State University
google->kaltofen

Joint with Jean-Guillaume Dumas

University of Grenoble, France
 2

Sparse Matrix GL7d19

From K-Theory Conjectures [Elbaz-Vincent, Gangle, Soulé ’05]

1911130 × 1955309 matrix of rank 1033568

Computed by J.-G. Dumas with LinBox in 1050 CPU days

With Monte-Carlo randomized algorithm ...

Do you believe the rank?

 2

Sparse Matrix GL7d19

From K-Theory Conjectures [Elbaz-Vincent, Gangle, Soulé ’05]

1911130 × 1955309 matrix of rank 1033568

Computed by J.-G. Dumas with LinBox in 1050 CPU days

With Monte-Carlo randomized algorithm ...

Do you believe the rank?

We construct an easily checkable certificate

 3

Kaltofen, Li, Yang, Zhi 2009

“A certificate for a problem that is given by

input/output specifications is an input-dependent data
structure and an algorithm that computes from that
input and its certificate the specified output, and that
has lower computational complexity than any known
algorithm that does the same when only receiving the
input. Correctness of the data structure is not
assumed but valdidated by the algorithm
(adversary-verifier model).”
 3

Kaltofen, Li, Yang, Zhi 2009

“A certificate for a problem that is given by

input/output specifications is an input-dependent data
structure and an algorithm that computes from that
input and its certificate the specified output, and that
has lower computational complexity than any known
algorithm that does the same when only receiving the
input. Correctness of the data structure is not
assumed but valdidated by the algorithm
(adversary-verifier model).”

Fancy setting: Certificates are produced by the

“prover (Peggy)” in the Cloud,
which the “verifier (Victor)” client user checks
 3

Kaltofen, Li, Yang, Zhi 2009

“A certificate for a problem that is given by

input/output specifications is an input-dependent data
structure and an algorithm that computes from that
input and its certificate the specified output, and that
has lower computational complexity than any known
algorithm that does the same when only receiving the
input. Correctness of the data structure is not
assumed but valdidated by the algorithm
(adversary-verifier model).”
What it is NOT: programs that check their results [Blum et al.]

What it is: limiting prover power in delegated computation

[Goldwasser et. al. 2008]: more on this later
 4

Warm-up: Rusin Freivalds’s 1979 Certificates

Let A, B,C ∈ Zn×n
Certify C = A · B via a random vector y ∈ Sn , S ⊆ Z
and check Cy = A(By) : Monte Carlo of n2+o(1) bit complexity
 4

Warm-up: Rusin Freivalds’s 1979 Certificates

Let A, B,C ∈ Zn×n
Certify C = A · B via a random vector y ∈ Sn , S ⊆ Z
and check Cy = A(By) : Monte Carlo of n2+o(1) bit complexity

Kimbrel and Sinha 1993: O(log n) random bits

Choose y = [1, r, r2 , . . . , rn−1 ]T , r ∈ S
If |S| ≥ 2n, then ≥ n of the r certify C 6= A · B
Otherwise (C − A · B) · (non-sing. Vandermonde matrix) = 0.
 4

Warm-up: Rusin Freivalds’s 1979 Certificates

Let A, B,C ∈ Zn×n
Certify C = A · B via a random vector y ∈ Sn , S ⊆ Z
and check Cy = A(By) : Monte Carlo of n2+o(1) bit complexity

Kimbrel and Sinha 1993: O(log n) random bits

Choose y = [1, r, r2 , . . . , rn−1 ]T , r ∈ S
If |S| ≥ 2n, then ≥ n of the r certify C 6= A · B
Otherwise (C − A · B) · (non-sing. Vandermonde matrix) = 0.

Non-singularity certificate
Smallish prime p, L,U ∈ Zn×n
p , P permut. matrix
Verify (A mod p) ≡ LUP (mod p) as above
 5

Warm-up continued: Singularity, Rank

Singularity certificate
y ∈ Zn with log kyk = n1+o(1) such that Ay = 0
Verify for smallish random prime p : (A mod p)(y mod p) ≡ 0
Note: y mod p also takes n2+o(1) bit operations
 5

Warm-up continued: Singularity, Rank

Singularity certificate
y ∈ Zn with log kyk = n1+o(1) such that Ay = 0
Verify for smallish random prime p : (A mod p)(y mod p) ≡ 0
Note: y mod p also takes n2+o(1) bit operations

Rank certificate [Kaltofen, Nehring, Saunders 2011]

List of 2 n1+o(1) smallish primes pi , L[i] ,U [i] , P[i] with

rank(A) = rank(U [i] ) and L[i] AP[i] ≡ U [i] (mod pi )

Verify for random j rank of U [ j] and modular row echelon form

Note: only n1+o(1) bad pi that can lie about the rank undetectably
But: certificate occupies n3+o(1) bit space
 6

Bit complexity of the Determinant/Rank

ω : matrix-multiplication exponent: best ω = 2.372864
log kAk : bit-size of entries in A ∈ Zn×n

Det with Chinese remaindering: (n · log kAk)1+o(1) × nω

Monte-Carlo Rank = Rank modulo a random smallish prime

(n2 log kAk + nω loglog kAk)1+o(1)

Monte-Carlo Rank r = n2/ω +o(1) : (n2 log kAk)1+o(1)

[Essentially optimal!]

Las-Vegas Det + Rank: (nω log kAk)1+o(1)

[Storjohann 2002, 2009]
 7
Certificates for Det/Rank of n2+o(1)
Bit Complexity
[Kaltofen, Nehring, Saunders 2011]
Step 1: Run Storjohann’s Las Vegas algorithms

Step 2: Record all random choices and intermediate results

except in matrix multiplications

Step 3: For the matrix multiplications, record inputs and outputs

 7
Certificates for Det/Rank of n2+o(1)
Bit Complexity
[Kaltofen, Nehring, Saunders 2011]
Step 1: Run Storjohann’s Las Vegas algorithms

Step 2: Record all random choices and intermediate results

except in matrix multiplications

Step 3: For the matrix multiplications, record inputs and outputs

Verfication: rerun Storjohann’s algorithms, making the same

random choices and instead of the matrix multiplications,
verify the AB = C by Freivalds’s algorithm
It’s like running the det/rank algorithms with a quadratic matrix
multiplication procedure
 8
Baby steps/giant steps bit complexity exponent η
via block Wiedemann [Kaltofen&Villard 2001, 2004]
ω ζ η σ τ
1−ζ ω −(1+ζ ) ω −2
1 ω ζ ω + ω 2 −(2+ ζ )ω +2
1 − ω 2 −(2+ζ )ω +2 ω 2 −(2+ζ )ω +2

2 2.372864 0.3029805 2.694691∗ 0.506016 0.172158

1 ω −1 ω −2
3 ω 0 ω + (ω −1)2 +1 1 − (ω −1)2 +1 (ω −1)2 +1

4 3 0 3 + 51 3
5
1
5

5 log2 (7) 0 3.041738 0.576388 0.189230

6 2.372864 0 2.719514 0.524070 0.129253

7 2 0 2 + 21 1
2 0
∗ Bestknown for M IN P OLY, C HAR P OLY, F ROBENIUS , S MITH
—all Monte-Carlo
[Also best known for algebraic division-free Determinant]
 9
Monte-Carlo Yields Cryptographically Strong
Certificates [Kaltofen 2012]
Prevent cheating with “unlucky” random choices by fixing a
pseudo-random bits generator and always seed it the same,
dependent on input matrix: s = ∑ |ai, j | mod 264
At ISSAC 2014, we used a cryptographic hash value (random
oracle function) hash(A)

But:
With Kaltofen-Villard algorithms—rerun with Freivalds’s matrix
multiplication check—we get C HAR P OLY /M IN P OLY certificates
of verification complexity (n2.5 log kAk)1+o(1) :
[Superlinear in input size!]
 9
Monte-Carlo Yields Cryptographically Strong
Certificates [Kaltofen 2012]
Prevent cheating with “unlucky” random choices by fixing a
pseudo-random bits generator and always seed it the same,
dependent on input matrix: s = ∑ |ai, j | mod 264
At ISSAC 2014, we used a cryptographic hash value (random
oracle function) hash(A)

But:
With Kaltofen-Villard algorithms—rerun with Freivalds’s matrix
multiplication check—we get C HAR P OLY /M IN P OLY certificates
of verification complexity (n2.5 log kAk)1+o(1) :
[Superlinear in input size!]

Our original motivation for certificates:

Certify a symmetric matrix positive semidefinite
[Kaltofen, Li, Yang, Zhi 2009]
 10

Our motivation: sum-of-squares proofs in global optim.

For a real polynomial f ∈ R[X1 , . . . , Xn ] :
f  0 ( f is positive semidefinite)
⇐⇒ ∀ξ1 , . . . , ξn ∈ R : f (ξ1 , . . . , ξi ) ≥ 0,
f ≻ 0 ( f is positive definite)
⇐⇒ ∀ξ1 , . . . , ξn ∈ R : f (ξ1 , . . . , ξi ) > 0.
Note: µ = infξ ∈R f (ξ ) =⇒ f − µ  0
 10

Our motivation: sum-of-squares proofs in global optim.

For a real polynomial f ∈ R[X1 , . . . , Xn ] :
f  0 ( f is positive semidefinite)
⇐⇒ ∀ξ1 , . . . , ξn ∈ R : f (ξ1 , . . . , ξi ) ≥ 0,
f ≻ 0 ( f is positive definite)
⇐⇒ ∀ξ1 , . . . , ξn ∈ R : f (ξ1 , . . . , ξi ) > 0.
Note: µ = infξ ∈R f (ξ ) =⇒ f − µ  0
For a real symmetric matrix W ∈ RN×N , all of whose
eigenvalues are necessarily ∈ R :
W  0 if W is positive semidefinite, i.e.,
all eigenvalues of W are ≥ 0;
W ≻ 0 if W is positive definite, i.e.,
all eigenvalues of W are > 0 (=⇒ W is nonsingular).
 10

Our motivation: sum-of-squares proofs in global optim.

For a real polynomial f ∈ R[X1 , . . . , Xn ] :
f  0 ( f is positive semidefinite)
⇐⇒ ∀ξ1 , . . . , ξn ∈ R : f (ξ1 , . . . , ξi ) ≥ 0,
f ≻ 0 ( f is positive definite)
⇐⇒ ∀ξ1 , . . . , ξn ∈ R : f (ξ1 , . . . , ξi ) > 0.
Note: µ = infξ ∈R f (ξ ) =⇒ f − µ  0
For a real symmetric matrix W ∈ RN×N , all of whose
eigenvalues are necessarily ∈ R :
W  0 if W is positive semidefinite, i.e.,
all eigenvalues of W are ≥ 0;
Note: W  0 ⇐⇒ ± f W(−x) = ∏α (x + α ) has coeff’s ≥ 0
where f W is C HARPOLY /M IN P OLY(W )
 11

Certification of Lower Bounds

Emil Artin’s 1927 Theorem (Hilbert’s 17th Problem)

f ∈ Q[X1 , . . . , Xn ] : f 0
m
∑m u
i=1 i
2
∃ui , v j ∈ Q[X1 , . . . , Xn ] : f (X1 , . . . , Xn ) = m
∑ j=1 v2j
m
mT W [1] m
d
∃rational W [1]  0,W [2]  0 : f = dT [2]
me W me

with md (X1 , . . . , Xn ), me (X1 , . . . , Xn ) vectors of terms

W  0 (positive semidefinite)
⇐⇒ W = PL D LT PT , D diagonal, Di,i ≥ 0 (Cholesky)
 12

Theodore Motzkin’s 1967 Polynomial

(3 arithm. mean − 3 geom. mean)(x4 y2 , x2 y4 , z6 )

= x4 y2 + x2 y4 + z6 − 3x2 y2 z2

is positive semidefinite (AGM inequality) but not a sum-of-squares.

However,

(x4 y2 + x2 y4 + z6 − 3x2 y2 z2 )(x2 + y2 + z2 ) =

 3 3 2  3 3 2
4 2 2 2

2 xy x y xy x y
z − x y + 3 xyz − − + −
2 2 2 2
2 2
3

3 2

2
+ xz − xy z + yz − x yz
 12

Theodore Motzkin’s 1967 Polynomial

(3 arithm. mean − 3 geom. mean)(x4 y2 , x2 y4 , z6 )

= x4 y2 + x2 y4 + z6 − 3x2 y2 z2

is positive semidefinite (AGM inequality) but not a sum-of-squares.

However,

(x4 y2 + x2 y4 + z6 − 3x2 y2 z2 )(x2 + z2 ) =

4 2 2 2 2 3 2 3 2 2




z − x y + xyz − x y + xz − xy z
 13
Proof of Knowledge 2 Rounds Protocol
[Chaum, Evertse, van de Graaf, Peralta 1986]
Public p, g where g is primitive root modulo prime p
Given x, computing v = (gx mod p) is easy,
but given v, x cannot be computed fast [Discrete Log Problem]
 13
Proof of Knowledge 2 Rounds Protocol
[Chaum, Evertse, van de Graaf, Peralta 1986]
Public p, g where g is primitive root modulo prime p
Prover “Peggy” must convince Verifier “Victor”
that she has ID x without revealing x

Prover Commun. Verifier

Chooses r ∈ Z p−1 randomly
v = (gx mod p),
v, h
h = (gr mod p) −−−−−−→
“commits”

←−−c−−−− Chooses c ∈ Z p−1 randomly

s = (r + cx) mod (p − 1) s−−→ Checks gs ≡ hvc (mod p)

−−−−
 14
Non-Interactive Proof of Knowledge Protocol
[Fiat, Shamir 1986]
Public p, g where g is primitive root modulo prime p
Prover “Peggy” must convince Verifier “Victor”
that she has ID x without revealing x

Prover Commun. Verifier

Chooses r ∈ Z p−1 randomly
v = (gx mod p),
v, h
h = (gr mod p) −−−−−−→
c = hash(p, g, v, h) −−−−c−−→
s = (r + cx) mod (p − 1) −−−− s−−→Checks c = hash(p, g, v, h)
Checks gs ≡ hvc (mod p)
 15

Matrix Rank Certificate As Interactive Protocol

Prover “Peggy” must convince Verifier “Victor”
that r = rank(A), A ∈ Zn×n

Prover Commun. Verifier

p
←−−−−−−−−Chooses smallish p randomly

Computes LUP factor-

L[p] ,U [p] , P
ization of A modulo p −−−−−−−−→Checks L[p] AP ≡ U [p] (mod p)
via Freivalds algorithm
Then r = rank(U [p] ) w.h.p
 16
Kaltofen’s 2012 Matrix Rank Certificate
As Fiat-Shamir Non-Interactive Protocol
Prover “Peggy” must convince Verifier “Victor”
that r = rank(A), A ∈ Zn×n

Prover Commun. Verifier

p
p = hash(A) −−−−−−−−→
Computes LUP factor-
L[p] ,U [p] , P
ization of A modulo p −−−−−−−−→Checks p = hash(A)
Checks L[p] AP ≡ U [p] (mod p)
via Freivalds’s algorithm
Then r = rank(U [p] ) w.h.p
 17
Dumas’s & Kaltofen’s 2014 CharPoly Certificate
As 2 Round Interactive Protocol
Prover “Peggy” must convince Verifier “Victor”
that cA (λ ) = det(λ I − A), A ∈ Zn×n
Prover Commun. Verifier
cA (λ )
cA (λ ) = det(λ I − A) −−−−−−−−→
“commits”
p a smallish random prime
p, r
←−−−−−−−−r a smallish random integer

Computes LUP factor.

L[p] ,U [p] , P
of rI − A modulo p −−−−−−−−→Checks L[p] (rI − A)P
“Certificate for det(rI − A)” ≡ U [p] (mod p) by Freivalds’s alg.
Checks det(U [p] ) ≡ cA (r) (mod p)
 18
At Last: Dumas’s & Kaltofen’s 2014 CharPoly Certi-
ficate As Non-Interactive Protocol With Optimal Verifier
Prover “Peggy” must convince Verifier “Victor”
that cA (λ ) = det(λ I − A), A ∈ Zn×n
Prover Commun. Verifier
c A (λ )
cA (λ ) = det(λ I − A) −−−−−−−−→
A p, r
p, r = hash(A, c ) −−−−−−−−→
Computes LUP factor.
L[p] ,U [p] , P
of rI − A modulo p −−−−−−−−→Checks p, r = hash(A, cA )
Checks L[p] (rI − A)P
≡ U [p] (mod p) by Freivalds’s alg.
Checks det(U [p] ) ≡ cA (r) (mod p)
 18
At Last: Dumas’s & Kaltofen’s 2014 CharPoly Certi-
ficate As Non-Interactive Protocol With Optimal Verifier
Prover “Peggy” must convince Verifier “Victor”
that cA (λ ) = det(λ I − A), A ∈ Zn×n
Prover Commun. Verifier
c A (λ )
cA (λ ) = det(λ I − A) −−−−−−−−→
A p, r
p, r = hash(A, c ) −−−−−−−−→
Computes LUP factor.
L[p] ,U [p] , P
of rI − A modulo p −−−−−−−−→Checks p, r = hash(A, cA )
Checks L[p] (rI − A)P
≡ U [p] (mod p) by Freivalds’s alg.
Checks det(U [p] ) ≡ cA (r) (mod p)
Verification complexity: (n2 log kAk)1+o(1)
 19
Dumas’s & Kaltofen’s 2014 Sparse Matrix Rank
Certificate As Interactive Protocol
Prover “Peggy” must convince Verifier “Victor”
that r = rank(A), A ∈ Zn×n , A has n1+o(1) non-zero entries
Prover Commun. Verifier
p a smallish random prime
a random b ∈ Znp
p, b, T [1] , T [2] [1] [2]
←−−−−−−−−−−T , T ∈ Z p 2 random Toeplitz matrices

x ∈ Zrp s.t. (T [1] AT [2] )1...r,1...r x ≡ b1...r

Computes x −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−→
“Certificate for non-singularity”
0 6= w ∈ Zr+1
p s.t. (T [1] AT [2] )1...r+1,1...r+1 w ≡ 0
Computes w−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−→
“Certificate for singularity”
 19
Dumas’s & Kaltofen’s 2014 Sparse Matrix Rank
Certificate As Interactive Protocol
Prover “Peggy” must convince Verifier “Victor”
that r = rank(A), A ∈ Zn×n , A has n1+o(1) non-zero entries
Prover Commun. Verifier
p a smallish random prime
a random b ∈ Znp
p, b, T [1] , T [2] [1] [2]
←−−−−−−−−−−T , T ∈ Z p 2 random Toeplitz matrices

x ∈ Zrp s.t. (T [1] AT [2] )1...r,1...r x ≡ b1...r

Computes x −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−→
“Certificate for non-singularity”
0 6= w ∈ Zr+1
p s.t. (T [1] AT [2] )1...r+1,1...r+1 w ≡ 0
Computes w−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−→
“Certificate for singularity”
Verification complexity: (n log kAk)1+o(1)
Commun. complexity: (n loglog kAk)1+o(1)
 20
Goldwasser, Kalai, Rothblum 2008: Delegating
Computation: Interactive Proofs for “Muggles”
Theorem: Let CN be a family of log-space uniform Boolean
circuit with N inputs. Then any computation has a randomized
interactive proof protocol with
Verifier complexity: (N + depth(CN )) × (log N)O(1)
Prover complexity: size(CN )O(1)
 20
Goldwasser, Kalai, Rothblum 2008: Delegating
Computation: Interactive Proofs for “Muggles”
Theorem: Let CN be a family of log-space uniform Boolean
circuit with N inputs. Then any computation has a randomized
interactive proof protocol with
Verifier complexity: (N + depth(CN )) × (log N)O(1)
Prover complexity: size(CN )O(1)

Construction based on Probabil. Checkable Proofs (PCP):

Prover compresses levels of the evaluated circuit by a linear form,
the verifier performs a single Boolean operation on the levels
 20
Goldwasser, Kalai, Rothblum 2008: Delegating
Computation: Interactive Proofs for “Muggles”
Theorem: Let CN be a family of log-space uniform Boolean
circuit with N inputs. Then any computation has a randomized
interactive proof protocol with
Verifier complexity: (N + depth(CN )) × (log N)O(1)
Prover complexity: size(CN )O(1)

Construction based on Probabil. Checkable Proofs (PCP):

Prover compresses levels of the evaluated circuit by a linear form,
the verifier performs a single Boolean operation on the levels

Thaler 2012: Better prover complexity: O(size(CN ))

Our customized certificates are:

– Independent of the circuits that compute them: expose bugs in CN
– Optimal prover complexity: size(CN ) + o(size(CN ))
 21

Open Problems

Certificates for Smith Normal Form of Dense Integer Matrices

Certificates for Determinant of a Sparse Matrix

And, of course,
Remove the cryptographic assumptions for C HAR P OLY
 21

Open Problems

Certificates for Smith Normal Form of Dense Integer Matrices

Certificates for Determinant of a Sparse Matrix

And, of course,
Remove the cryptographic assumptions for C HAR P OLY

Right now, applies crypto to symbolic computation, not the other

way around, unlike Groebner breaking encryption schemes
 22

Thank you!
 23

"End Key" wrong!