I know it might seem a bit too much theoretical, but I was wondering if there was some list of known open problems in security?

In a similar way that there are open problems in Theoretical Computer Science, it would be interesting to get a similar list in security, especially for research purposes.

Note that I am particularly interested in theoretical/research problems, rather than concrete usage or implementation problems, as those given in this list: What are the biggest unsolved problems in IT Security?.

Any idea/suggestion/comment is welcome, this is just question that came up to my mind after a panel discussion at a security conference.

I'm more interested here on non-crypto problems, such as those involving policies, enforcement mechanisms, etc.

  • If you want the theoretical problems, you should try on the crypto site. Commented Feb 8, 2012 at 21:27
  • Well, actually, I'm more interested in non-crypto problems, as they already have quite well defined problems. Thanks for pointing this out, I will update my question!
    – Charles
    Commented Feb 8, 2012 at 21:30
  • @RoryAlsop Yes, I actually cite this question already in my question, and I'm rather interested in theoretical/research problems, while it seems (but I might be wrong) that this question focuses more on concrete implementation problems. It also seems that the answers given for this question show unsolvable problems rather than open ones.
    – Charles
    Commented Feb 8, 2012 at 21:38
  • Ah - gotcha. Interesting topic - hope you get some good answers.
    – Rory Alsop
    Commented Feb 8, 2012 at 21:43
  • 1
    I think you'll find several questions have already looked at some of the open problems such as this one. Commented Feb 8, 2012 at 22:07

1 Answer 1


Covert channels and side channels are hard to eliminate.

Additionally, many of the open problems in computer science have implications for security.

There is a need for formal ways to specify software, and there is a need for formal ways to specify security requirements.

The difficulty we have proving program correctness for critical programs the size of operating systems, means that it is difficult to prove that widely used security critical code (IP stacks, OpenSSL) is correct.

The inability to efficiently check for ambiguity in a grammar, means it is hard to prove that an authority carrying message will exercise only the authority intended.

The inability to prove halting for a broad and interesting subset of programs makes it hard to reason about denial of service and resource hogging.

The inability to tightly bound aliasing statically means it's hard to statically prove that data does not leak from one part of a program to another.

  • Thanks, you make a very good point by relating security problems to more "traditional" software problem. However, correct me if I'm wrong, but it seems that most problems you mention are not really open, but just hard. For instance, the halting problem is not open: we know that it's undecidable to know whether a program (including security programs) stops or not. Similarly, we know that in general, because of aliasing, an assignment may have a different effect according to the context. Unless you were thinking about something more specific, which would be very interesting to discuss!
    – Charles
    Commented Feb 9, 2012 at 3:47
  • @CharlesMorisset, Sorry. I chose poor examples and I interpreted "open" not as "there exists no proof that answers the question Q" to "there is no solution or good heuristics for problem P, therefore C.S. practitioners lack good tools/methodologies for producing code with property R." Commented Feb 9, 2012 at 4:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .