There are certain unsolvable problems (I am not referring to NP), that seem solvable, and an apparent solution can be made and deployed. These systems can be used, but do not fulfil there requirements (security, privacy, …).
This differs from the case where the software lacks these features, because of poor workmanship (also an ethical issue), in this case it can not be done. I turn down the work, because it is impossible. The client thinks they need to find someone that is more clever, that can do it. Eventually they find someone that has no idea of the problems, that agrees to do the project. If the new supplier realises that it can not be done, and tells the client, then the process repeats, else a faulty product is delivered.
An example is electronic voting.
It is impossible to create an electronic voting system that meets all of the requirements. If we just have 2 of the requirements for a voting system.
Then we can not produce an electronic system, that can meet just these requirements. There are also other requirements, thus it is even harder (in the higher than infinity sort of way (∞+1 = ∞), therefore we don't need to look at the other requirements, to see how hard it is).
How would you audit this system? You could check its source code, to see that it does the right thing (if you can read it, so every one involved would have to have a good enough level of CS, and know the language). Oh but how do we know that the system is running this code.
Every single solution to this problem, has a counter measure ( a dis-proof ).
This has not stopped these things from being deployed many times, and in countries that are considered to have a well run voting system.
What is needed
A box, that you put all of your votes into, and out comes a count for each candidate.
Possible solutions
How do you know that the output is correct. Ah that is easy, you produce an audit trail. But now we have no anonymity. So we add encryption. But for it to be audit-able, anonymity can still be broken. (If you can check your own vote, then I can check your vote (if I torture you long enough, then you will give up your key).
A solution that works, but does not use a computer.
The many boxes
- you walk into a room (box1), and show your ID, your name is removed from the list, and you are given a voting sheet.
- you walk into a subroom (box2), and make your mark on the sheet.
- you then fold(box3) the sheet.
- you leave box2 and walk to a locked box (box4), and place your sheet into it.
- at all times observers (from all interested parties) are walking around box1, to check that the rules are being followed.
- at the end box 4 is sealed.
- latter box 4 is opened and the sheets counted. With lots of people watching. A set of totals is produced and announced. The sheets are put back in box 4, sealed and locked.
I have probably missed some detail, but this solution cannot be implemented electrically, because there is no way of putting people into the electronic boxes to observe.
Some videos on this
The problem
Some solutions I found a problem with all of these solution, as I was watching it (Did not have to sit and think for days).
Other stuff