1
$\begingroup$

In the book "Introduction to the Theory of Computation", Michael Sipser writes

The field of cryptography, as this area is known, now extends well beyond secret codes for private communication and addresses a broad range of issues concerning the security of information. For example, (1) to allow electronic elections whereby participants can vote over a network and the results can be publicly tallied without revealing any individual’s vote, while preventing multiple voting and other violations; and (2) to construct new kinds of secret codes that do not require the communicators to agree in advance on the encryption and decryption algorithms.

(Chapter: Advance Topics in Complexity Theory, section: Cryptography)

I am assuming that the example (1) refers to Blockchain technology. Are there any other ways of achieving the same?

For the example (2), I am not sure which technology is he trying to refer. Any idea?

$\endgroup$
1
  • 4
    $\begingroup$ "I am assuming that the example (1) refers to Blockchain technology." - given that age of the book (initially published 1997) the answer is likely that it does not refer to Blockchain. $\endgroup$ May 7 at 14:29
2
$\begingroup$

I am assuming that [electronic elections whereby participants can vote over a network and the results can be publicly tallied without revealing any individual’s vote] refers to Blockchain technology. Are there any other ways of achieving the same?

Voting schemes using Blockchain technology mainly aim at avoiding a central authority. I doubt this is what's suggested, given the text, and it's age. I think it refers to voting remotely thru a network. A slightly later classic on this line of thought on electronic voting (among many) is Berry Schoenmakers' A Simple Publicly Verifiable Secret Sharing Scheme and Its Application to Electronic Voting, in proceeding of Crypto 1999.

For [construct new kinds of secret codes that do not require the communicators to agree in advance on the encryption and decryption algorithms], I am not sure which technology is he trying to refer.

The author likely has used algorithm where he meant key. He would then be referring to Diffie-Hellman key exchange. The book has a mere 9 pages on cryptography (including 3 of exercises/problems), and it's section on Public-Key cryptosystems does not cover DH (only RSA). I would not recommend it as an introduction to cryptography.

$\endgroup$
3
  • $\begingroup$ There are voting schemes that use the blockchain, well they are proposed as soon as the blockchain is out. The problem was the anonymity. Also, Schoenmakers's article is still younger for the book. $\endgroup$
    – kelalaka
    May 7 at 15:36
  • 1
    $\begingroup$ Michael Sipser responded to email about the same -- "There are multiple schemes for electronic voting that depend on cryptography, and an extensive literature that you can easily find online. For example: crypto.stanford.edu/pbc/notes/crypto/voting.html For 2 I have in mind public key cryptography where the encryption algorithm can be published in advance, available to any subsequent sender. " $\endgroup$ May 18 at 12:13
  • $\begingroup$ @Mohit Kumar Jangid: For 2, what the author describes in this additional information is consistent with: Alice publicly explains Diffie-Hellman Key Exchange followed by a Key Derivation Function and a symmetric cipher, proposing to do this with certain parameters; then Bob following that guidance. This indeed is secure if done over public channel with integrity. $\endgroup$
    – fgrieu
    May 18 at 12:27
0
$\begingroup$

Blockchain is just a tool to make communication 100% transparent and to avoid a central authority.

Yes there are other ways to allow anonymous voting. I know of two ways.

A simple approach is that everyone signes their vote with a linkable ring signature. That way you can make sure, that the vote came from someone who has the right to vote and that noone votet multiple times but you don't know who's vote it is. This can be done without any central authority as long as everyone agrees in who is allowed to vote an what their public keys are.

Another way is to use RSA blinding. This allows you to get your vote signed by a trusted authority that keeps track of who it signed the votes for to make sure that noone can vote multiple times and that only those who have the right to vote get their vote signed, without revealing it. Later you can send your vote together with a valid signature from the authority, that can't be linked to you.

$\endgroup$
1
  • $\begingroup$ I think an answer to this question requires indicating that the solutions are earlier than 1997. $\endgroup$
    – kelalaka
    May 7 at 18:53

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.