20

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?

v s
  • 2,208
  • 13
  • 21
  • 9
    You, of course, know that no lower bound better than 5n for circuit complexity is known, for any 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 Igor Sparlinski. – Stasys Jul 15 '11 at 15:58
  • @Stasys, do you have a reference for this interesting fact? – Simd Jul 15 '11 at 17:05
  • 8
    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 http://www.thi.informatik.uni-frankfurt.de/~jukna/BFC-book/. User: friend Password: catchthecat – Stasys Jul 15 '11 at 17:24
  • @Stasys Great book. I am going to munch through it.

    Also I am new to circuit complexity. So I did not know the $5n$ result. Is there a specific name for it? I am interested in the proof.

    Also what kind of results are known for restricted circuits for these problems? Thankyou.

     – v s Jul 15 '11 at 20:47
  • 1
    @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. – Kaveh Jul 16 '11 at 22:42
  • 12
    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: http://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!).

     – Stasys Jul 17 '11 at 15:01
  • 5
    @StasysJukna: a combination of your comments is appropriate as an answer. – Suresh Venkat Aug 29 '11 at 06:43
  • I agree with suresh. But for discrete log anything helpful? – v s Aug 29 '11 at 07:35
  • 1
    @Kaveh, search engines do get comments: https://encrypted.google.com/search?q=%22I+think+results+for+polytime+transfer+upwards+using+padding%2C+don%27t+they%3F%22 – didest Aug 29 '11 at 18:08

1 Answers1

27

@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.

Stasys
  • 6,765
  • 29
  • 54
  • Is this Hastad's 1998 paper? http://www.nada.kth.se/~johanh/monotoneconnect.pdf

    I do not think the bound involves 'not'. Plus the exponent is quadratic.

     – Turbo Jul 02 '13 at 16:35
  • @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. – Stasys May 21 '14 at 15:27
  • 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. – Manu Nov 08 '16 at 15:58