19
$\begingroup$

Are there any references that provide details about circuit lower bounds for specific hard problems arising in cryptography such as integer factoring, prime/composite discrete logarithm problem and its variant over group of points of elliptic curves (and their higher dimensional abelian varieties) and the general hidden subgroup problem?

Specifically do any of these problems have more than a linear complexity lower bound?

$\endgroup$
  • 9
    $\begingroup$ You, of course, know that no lower bound better than 5n for circuit complexity is known, for <i>any</i> explicit function, not just for ones you mentioned. So, you should specify the question. Better bounds are only known for restricted circuits. You could, perhaps, find some partial answers on the home page of <a href="web.science.mq.edu.au/~igor" rel="nofollow"> Igor Sparlinski.</a> $\endgroup$ – Stasys Jul 15 '11 at 15:58
  • 8
    $\begingroup$ Well, I am not quite sure what do you mean under "this interesting fact". Anyway, the current state of art in circuit complexity is given in my upcoming book thi.informatik.uni-frankfurt.de/~jukna/BFC-book. User: friend Password: catchthecat $\endgroup$ – Stasys Jul 15 '11 at 17:24
  • 1
    $\begingroup$ @Stasys, I remember a student from Russia talked about their lowerbound of the form 7n+O(1) based on gate elimination in the Prague Fall School two years ago, but I cannot remember any more details. $\endgroup$ – Kaveh Jul 16 '11 at 22:42
  • 12
    $\begingroup$ Kaveh, this a (7/3)n-c lower bound, not 7n. It was proved by Arist Kojevnikov and Sasha Kulikov from Petersburg. The advantage of their proof is its simplicity, not numerical. Later they gave a simple proof of 3n-o(1) lower bound for general circuits (all fanin-2 gates are allowed). Albeit for very complicated functions - affine dispersers. Papers are online at: logic.pdmi.ras.ru/~kulikov/papers. Actually, tight bound 7n-7 were shown by Redkin (1973) for the parity function, but only if only NOT and AND gates are allowed. If also OR is allowed, then his bound is 4n-4 (also tight!). $\endgroup$ – Stasys Jul 17 '11 at 15:01
  • 5
    $\begingroup$ @StasysJukna: a combination of your comments is appropriate as an answer. $\endgroup$ – Suresh Venkat Aug 29 '11 at 6:43
25
+50
$\begingroup$

@Suresh: following your advice, here is my "answer". The status of circuit lower bounds is quite depressing. Here are the "current records":

  • $4n-4$ for circuits over $\{\land,\lor,\neg\}$, and $7n-7$ for circuits over $\{\land,\neg\}$ and $\{\lor,\neg\}$ computing $\oplus_n(x)=x_1\oplus x_2\oplus\cdots\oplus x_n$; Redkin (1973). These bounds are tight.
  • $5n-o(n)$ for circuits over the basis with all fanin-2 gates, except the parity and its negation; Iwama and Morizumi (2002).
  • $3n-o(n)$ for general circuits over the basis with all fanin-2 gates; Blum (1984). Arist Kojevnikov and Sasha Kulikov from Petersburg have found a simpler proof of a $(7/3)n-o(1)$ lower bound. The advantage of their proof is its simplicity, not numerical. Later they gave a simple proof of $3n-o(1)$ lower bound for general circuits (all fanin-2 gates are allowed). Albeit for very complicated functions - affine dispersers. Papers are online here.
  • $n^{3-o(1)}$ for formulas over $\{\land,\lor,\neg\}$; Hastad (1998).
  • $\Omega(n^2/\log n)$ for general fanin-$2$ formulas, $\Omega(n^2/\log^2 n)$ for deterministic branching programs, and $\Omega(n^{3/2}/\log n)$ for nondeterministic branching programs; Nechiporuk~(1966).

So, your question "Specifically do any of these problems have more than a linear complexity lower bound?" remains widely open (in the case of circuits). My appeal to all young researchers: go forward, these "barriers" are not unbreakable! But try to think in a "non-natural way", in the sense of Razborov and Rudich.

$\endgroup$
  • $\begingroup$ Is this Hastad's 1998 paper? nada.kth.se/~johanh/monotoneconnect.pdf I do not think the bound involves 'not'. Plus the exponent is quadratic. $\endgroup$ – Turbo Jul 2 '13 at 16:35
  • $\begingroup$ @J.A.: No, this is in another his paper of the same year J. Håstad, The Shrinkage Exponent is 2, SIAM Journal on Computing, 1998, Vol 27, pp 48-64. $\endgroup$ – Stasys May 21 '14 at 15:27
  • $\begingroup$ It seems noone has updated this answer with the new results, so I'll do it here. The 2015 paper by Magnus Find, Alexander Golovnev, Edward A. Hirsch, and Alexander S. Kulikov "A Better-than-3n Lower Bound for the Circuit Complexity of an Explicit Function." gives a $(3+\Omega(1))n$ lower bound. Maybe this makes things a little less depressing. $\endgroup$ – Manu Nov 8 '16 at 15:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.