Logic in Computer Science (LICS 1999)

Paper: Weak Bounded Arithmetic, the Diffie-Hellman Problem and Constable's Class K (at LICS 1999)

Authors: Jan Johannsen

Abstract

The bounded arithmetic theory \mathof Johannsen and Pollett (LICS'98), which is closely related to the complexity class DLogTime- uniform \math, is extended by a function symbol and axioms for integer division, which is not known to be in DLogTime-uniform \math. About this extended theory \math, two main results are proved:1. The \math-definable functions of \math[div]$ are exactly Constable's class K, a function algebra whose precise complexity- theoretic nature is yet to be determined. This also yields the new upper bound \mathuniform \math.2. The \math-theorems of \math[div]$ do not have Craig-interpolants of polynomial circuit size, unless the Diffie-Hellman key exchange protocol is insecure.

BibTeX

  @InProceedings{Johannsen-WeakBoundedArithmet,
    author = 	 {Jan Johannsen},
    title = 	 {Weak Bounded Arithmetic, the Diffie-Hellman Problem and Constable's Class K},
    booktitle =  {Proceedings of the Fourteenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1999},
    year =	 1999,
    editor =	 {Giuseppe Longo},
    month =	 {July}, 
    pages =      {268--274},
    location =   {Trento, Italy}, 
    publisher =	 {IEEE Computer Society Press}
  }