A toy model of information-theoretic security

In a previous post we discussed the foundations of cryptography in terms of different types of uncertainty stemming from limited information or computation. We saw an example using the caesar cipher that demonstrated how an adversary may have all the information necessary to reveal a secret if the relationship between the message space, key space and length of the ciphertext satisfies certain conditions:

Note how we were able to pick out the correct message because none of the other attempts gave meaningful results. This happens because the space of possible keys is so small that only one of them decrypts to a possible message. In technical terms, the key space and message space[2] are small enough compared to the length of the message that only one key will decrypt.

The situation can be coarsely be classified into three cases:

  1. H(K | C) = H(K) – Perfect secrecy
  2. H(K | C) < H(K) – Information-theoretic security
  3. H(K | C) = 0 – Computational security

Information-theoretic security refers to the epistemic uncertainty of the previous entry. We can use a simple model to illustrate how the conditions governing information-theoretic privacy work and when these conditions fail reducing to computational security.

Elements of our model

The XOR function

Our toy model needs to specify how messages are encrypted from some plaintext language to ciphertexts, using a key that determines the exact transformation and can be used by the intended recipient to recover the secret. We can use the simplest language possible, a two character alphabet whose messages are equivalent to binary sequences. Our encryption function will be the XOR function, which takes two binary sequences and produces a third one as its output. This choice fixes our key space to also be binary sequences. Here’s an example encryption:

1010011000 XOR 1100111010 = 110100010

The XOR function takes as input a message (1010011000), a key (1100111010) and produces a ciphertext 110100010. Of course, the message in this case means nothing to us, but there is no difference as to the process, we can simply imagine that the 1010011000 above is some meaningful content like “WELL DONE YOU HAVE FOUND THE SECRET”. The important thing to note is that, just like in english, there is a subset of the combinations in the plaintext space (binary sequences) that make meaningful messages whereas the rest do not. This brings us to the notion of language entropy, which precisely quantifies how big the meaningful subset of messages is relative to the entire plaintext space.

Untitled5

The higher the language entropy, the bigger the blue region will be compared to the entire plaintext space. In the case of a binary language the entropy ranges from 0 to 1, since this quantity is measured in bits per character. So far our toy model has these elements:

  • Plaintext space: ∈ {0, 1}n
  • Message space: M ⊂ P
  • Key space: K ⊂ {0, 1}n
  • Ciphertext space: C ∈ {0, 1}n
  • Encryption function: XOR: P x K → C
  • Language entropy: HL ∈ {0.0-1.0}

The security properties of our system depends on three parameters related to the above:

  • n: the number of characters in the plaintext
  • |K|: the size of the key space
  • HL: the language entropy
  • RL = 1 – HL: the language redundancy

The last parameter, redundancy, is just a rewriting of the language entropy. The equation that describes the security in terms of these parameters is:

spurious

This equation gives a lower bound for the expected number of spurious keys, represented by the term sn. A spurious key, for a given ciphertext, is a key that decrypts said ciphertext into a message that does not correspond to the message which was encrypted with the real key. In the example encryption at the beginning of the post we saw that when trying all the keys to decrypt the ciphertext only one of them yielded a meaningful plaintext: the ciphertext had no spurious keys. If, on the other hand, one of the keys, s, had decrypted the ciphertext into something like

THE MESSAGE COULD BE THIS

then that key s would be a spurious key. An attacker trying all keys would get two possible messages when trying all possible keys backwards and would not know which of them was the real one. The secret would remain somewhat protected. The existence and number of  expected spurious keys determines which of the three coarse categories above a cryptosystem belongs to. Looking at the spurious key equation we can see the following trends

  • sn increases with the size of the key space, |K|
  • sn decreases with the size of the plaintext, n
  • sn decreases with language redundancy, RL

A visual representation

Untitled7

Encryption representation with n = 2, H = 0.8, M = 3, K = 1

The left part of the image is visual representation of our toy model for parameter values, the left axis is the plaintext space, the right axis is the ciphertext space. A point on the plot represents an encryption, in other words, a mapping from the plaintext space to the ciphertext space. We have used n = 2, giving a plaintext space of size 4. Of these four, three are meaningful messages (for a language entropy of 0.8). The 3 red dots on the plot therefore correspond to the three encryptions of these 3 meaningful messages. Because K=1, there is only one ciphertext per plaintext, or visually, only one point on any given horizontal line. Compare with:

g8

n = 2, H = 0.8, M = 3, K = 3

Here we can see 9 points, corresponding to 3 messages x 3 keys. A horizontal line thus represents all the encryptions for a given message under different keys. What about the color difference? Here’s another set of parameters:

g9

n = 6, H = 0.8, M = 28, K = 3

With a higher plaintext length the number of meaningful messages rises to 28, resulting in a total of 28 x 3 = 84 encryptions, which show up as red and blue points in this case. Can you spot the pattern that explains this?

It’s not easy to see, but the answer lies in understanding what vertical lines mean in the representation. Points lying on the same horizontal line are different encryptions for the same message. Points lying on the same vertical line are different messages for the same encryption. As we saw before, this is exactly the situation where it is not possible for an adversary to determine the secret by trying all keys in reverse, as there is no way to tell which of the resulting messages is the original.

Blue points are ciphertexts for which there is more than one key that decrypts to a meaningful message, or equivalently, blue points are ciphertexts with one or more spurious keys.

sn > 0 ⇒ blue point

sn = 0 ⇒ red point

Now we can go see the visual equivalent the properties of information-theoretic security we mentioned before.

  • sn increases with the size of the key space, |K|
g1

Fixed n, H, increasing values of K

Visually: the proportion of blue dots increases.

  • sn decreases with the size of the plaintext, n
g2

Fixed K, H, increasing values of n

Visually: the proportion of red dots increases.

  • sn decreases with language redundancy, RL
g3

Fixed n, K, decreasing values of H (increasing values of R)

Visually: the proportion of red dots increases.

Visualizing the categories

Besides these trends, we also spoke about three broad categories into which cryptosystems fit:

  • H(K | C) = H(K) – Perfect secrecy
perfect

n = 8, H = 0.55, K = 256

Visually: the number of blue dots per column is equal to the number of horizontal lines. This means that the adversary gains no information from the ciphertext. Note also that 2^8 = 256, which is the value of K.

  • H(K | C) < H(K) – Information-theoretic security
partial

n = 9, H = 0.55, K = 106

Visually: there are only blue dots. Every ciphertext is partially protected in the sense that the adversary does not have enough information to reveal the secret unequivocally.

  • H(K | C) = 0 – Computational security
g12

n = 13, H = 0.53, K = 29

Visually: there are red dots, these ciphertexts have no information-theoretic protection and depend on computational security for their confidentiality.

Try it yourself

In this post we have described some of the key ideas presented in Claude Shannon’s seminal Communication Theory of Secrecy Systems published in 1949. We have also constructed a toy model that allowed us to visualize the security properties of cryptosystems and how they vary with its main parameters. You can try playing around with the model here. If you are a teacher and find it helpful please let us know!

Privacy-preserving e-participation with nMix

In this post we describe a concrete design enabling privacy for e-participation platforms falling under the category of social information filtering systems. This is an extension of work presented in the User Anonymization for Decidim Barcelona report. Although this report was written in the context of the Decidim e-participation tool, the techniques generalize to any platform with similar characteristics and intent. Continue reading here.

AI Progress: Ladders and Rockets

I once heard a metaphor about progress that I now use when talking about AI. Don’t know where I heard it first, so can’t give credit.

Imagine you want to get to the moon, but you don’t know how. Someone suggests using a ladder propped up against a tree. So a ladder is built, put in place, and the climb begins. To be scientific about it, distance to the moon is measured during the ascent. Sure enough, the distance decreases, all the way to the top of the ladder. To get closer, bigger and bigger ladders are constructed, propped up against taller and taller trees. The enterprise is making progress, as the distance to the moon diminishes with each attempt. If we continue on this way, we will surely make it to the moon.

Or you could try building a rocket. However, building the rocket does not result in any progress of the same kind being reported. You can build all the rocket parts correctly, but building any one of those wont result in any direct progress, as defined by distance to the moon. By that metric, there is no progress at all.

The metaphor illustrates that progress towards an objective does not imply that the employed solution will scale all the way towards reaching its goal. Conversely, it also illustrates that a solution that will scale may not reveal any progress during its development. These two situations are the core of what makes progress towards AI difficult to assess. If we factor in the hype, things are even more confusing because there is a propensity to report progress on advances that may be of the ladder type rather than the rocket type.

Because we have not solved AI, there is no way to know to which type a certain advance belongs. We can have intuitions. For example, an advance that involves generality and can solve many different problems is more likely to be a rocket type component. But not necessarily so. Most techniques in AI developed all the way from the 1960’s until the present day will never scale to full AI, and surely many of them were thought to. And today, what can we say of the latest techniques in deep learning? Perhaps they are a rocket component that solves a small piece of the puzzle, such as low level perception. Or maybe in 20 years time they will be remembered a promising direction that ultimately failed to overcome its data efficiency issues.

But there is one general and large scale trend that we can be confident is bringing us closer to AI, if only in the vague chronological sense. This trend is the continued alignment of the economy with AI research. We can take a previous and related example to illustrate the phenomenon: the semiconductor industry. Before the information age, the allocation of resources to the development of microprocessors and related technologies was orders of magnitude smaller than today. When society entered the information age, the explosion in demand for devices resulted in a shift in resources that gave rise to the exponential advances known as Moore’s law.

Of course, a resource shift is in itself not sufficient to guarantee explosive advances; rather it is a culmination of previous enabling scientific advances that typically occur at a slower pace. However, the limiting factor in scientific progress is typically aggregate cognitive power, which is itself one of the resources being allocated. Whether we are talking about a slow accretion of knowledge, or a fast explosion of applications, the two can only occur when the right people are working on the right task. Which brings us back to the surrounding conditions these individuals are in when making decisions.

Today, we have entered another phase of the information age. A phase in which society is demanding services that project great value onto technologies that can deliver analysis, prediction and automation in data intensive domains. This has shifted huge resources towards AI research. Whether or not specific AI advances are real progress towards AI, the large scale activity resulting from a stronger economic alignment is very likely producing overall progress. And this would be true even if we restricted ourselves to enabling conditions such as increasing computational power or accumulation of training data.

We may not know which are the ladders and which are the rocket components. But we do know that as the resources in play rise the chances that somewhere some group is building rocket components become increasingly significant.

Secure online voting

What do we mean by secure voting?

This is the subject of a new post on the nvotes blog, found here. Here’s the summary:

  • The term “secure voting” is generally thought to refer to cybersecurity and resistance to cyberattacks.
  • However, cybersecurity is a general property of hardware/software that does not reflect the specific requirements of voting as a political process. The secret ballot is an established and indispensable requirement for voting.
  • Secure voting systems must support privacy as well as integrity; these two requirements stand in opposition.
  • In a system supporting privacy, no one, not even system administrators or other privileged observers can violate the secret ballot.
  • In a system supporting end-to-end verifiability, voters can ensure that their vote was cast, recorded, and counted correctly.
  • Cryptographically secure voting systems employ cryptographic technology to satisfy these two properties simultaneously. The gold standard are end-to-end verifiable voting systems.
  • A secure voting system is an end-to-end verifiable voting system that also employs general computer security principles.

A mixnet-based secure voting protocol

This post will describe the main steps and operations that compose the cryptographic protocol of a re-encryption mixnet based voting system we are currently prototyping. This prototype is based around work[1][2] by the E-Voting Group at the Bern University of Applied Sciences, and uses their unicrypt library.  The main elements of the cryptographic scheme are

  • Public, tamper resistant, access controlled bulletin board
  • ElGamal cryptosystem[6]
  • Distributed public key generation
  • Election public key vote encryption with proof of plaintext knowledge
  • Authenticated vote casting (optionally with ciphertext signing) with cast as intended verifiability (Benaloh cast-or-cancel)
  • Re-encryption mixnet using Terelius-Wikstrom[4][5] proof of shuffle
  • Joint decryption via partial decryption of ciphertexts
  • Individual verifiability via hash checking on bulletin board (recorded as cast)
  • Universal verifiability via execution of verifier against bulletin board (counted as recorded)

These have been listed to roughly correspond chronologically with the protocol phases. Here they are at a glance.

protocol

This example shows two authorities both for key generation/joint decryption and mixing, but the protocol generalizes to any number of authorities. Also note that although above the key generation/decryption authorities are the same as the mixing authorities, this need not be the case. One could have four authorities such that two of them were key custodians and two of them were mixers. It is standard practice, however, that the number of authorities of each type is the same. There would be no privacy gain having more of one type as the limiting factor would the smaller number.

Key generation

In the first step the key generation/decryption authorities jointly create the election public key. This is the key with which voters will encrypt their votes before casting them. As can be seen in the diagram, this process occurs in parallel at each authority. Furthermore the simple distributed key generation scheme does not require communication between the authorities (as would be the case for example with a threshold scheme such as joint-feldman/pedersen). Each authority creates its share of the key and posts the public fragment, along with proofs of correctness, at the bulletin board. The bulletin board then checks the proofs and combines the shares, resulting in the public key which is also posted. The purpose of a distributed key generation scheme is to distribute trust such that the privacy of the vote is safe as long as just one of the authorities is not corrupted. Note that the corresponding private key only exists conceptually as the combination of private information at each authority, it is never recreated.

Voting

Once the public key is generated and publicly available at the bulletin board the election can begin. When casting votes, user’s voting clients, in this case the voting booth hosted by the browser, download the public key from the bulletin board. Once they have made their selection, the voting client encrypts the ballot and produces a hash. Before casting, users are presented with the option to audit their ballots according to Benaloh’s cast-or-cancel procedure. This provides cast-as-intended verifiability. Finally, the ballot is cast and sent to the bulletin board. The bulletin board verifies the user’s eligibility in the election as well as the proofs of plaintext knowledge, and then posts the vote. The user records the hash corresponding to their vote to allow verifying that their ballot was actually stored and counted correctly.

Mixing

When the election period is over and all the votes have been recorded the mixing phase begins. The purpose of this phase is to anonymize the votes such that it is impossible to trace what ciphertext belongs to what voter. This is necessary to protect privacy, as the joint decryption phase will reveal vote contents to allow tallying. Just like in the key generation phase is trust distributed across several authorities, so too is the mixing. Each mixing authority permutes and re-encrypts the votes handling them as input to the next authority. Only if all of the mixing authorities are corrupt is it possible to establish the correspondence between the cast votes on the bulletin board and the output of the mixing phase, which will be decrypted. The prototype uses the Terelius-Wikstrom proof of shuffle, which is composed of an offline and online phase. Although the offline phase (permutation) can be precomputed prior the election start our prototype does not exploit this feature, opting for simplicity. However, what is exploited is the parallelism made possible by the fact that the offline only depends on the vote count. This allows all authorities to this phase simultaneously once the election period ends. This is in contrast to the online shuffle phase, where each authority must wait for the mixing results of the previous authority. The diagram above reflects this; we can see the computation bars overlap in time for the permutation but not the shuffle. Each authority submits the vote mixing results along with the proofs to the bulletin board. The bulletin board verifies the shuffle and posts the mixed votes for the next authority to mix. Once all the authorities have completed the mix and the bulletin board has verified all the proofs the mixing phase is over.

Decrypting

Having completed the mixing phase the bulleting board contains the set of anonymized votes for the election. Because they are anonymized these votes can now be decrypted without compromising privacy. Just as the key generation phase was distributed across several authorities, these same authorities must intervene to decrypt the votes. Since the scheme is distributed but not a threshold system, all the authorities must participate in joint decryption. Similarly, as long as one authority remains honest it is not possible to decrypt non-anonymized votes. To carry out the joint decryption each authority downloads the mixed votes from the bulletin board and calculates their partial decryptions using its private share of the key, along with corresponding proofs of correctness. As can be seen above this process is parallel and occurs simultaneously at all authorities once the mixing phase is finished. The partial decryptions and proofs are then posted to the bulletin board, which verifies the proofs. Once all partial decryptions are available the bulletin board combines them and subsequently obtains the plaintexts. As noted previously, the private key is never reconstructed, the combination occurs only for partial decryptions.

Tally and verification

The plaintexts are posted on the bulletin board. This completes the public data for the election, which we summarize below:

  • Election public key shares and proofs of correctness (for each key authority)
  • Election public key
  • Cast votes, proofs of knowledge of plaintext, and signatures
  • Votes mixes and proofs of shuffle (for each mix authority)
  • Mixed votes partial decryptions and proofs (for each key authority)
  • Combined partial decryption and plaintexts

With this information:

  • The election result can be obtained by tallying plaintext votes
  • Each voter can verify that their vote was recorded correctly
  • Anyone can verify that the set of mixed votes corresponds to the recorded (cast) votes
  • Anyone can verify that the plaintexts correspond to correct decryption of the mixed votes
  • Anyone can verify that the election results corresponds to a correct tally of the plaintexts

The above properties, together with the ballot auditing procedure, make the prototype a secure[3] end-to-end verifiable voting system.


References

[1] https://github.com/bfh-evg/univote2/raw/development/doc/report/report.pdf

[2] http://subs.emis.de/LNI/Proceedings/Proceedings232/article100.html

[3] By secure we mean specifically that it employs cryptography to support privacy. No voting system is 100% secure in the general sense.

[4] B. Terelius and D. Wikstrom. Proofs of Restricted Shuffles. In D. J. Bernstein and ¨ T. Lange, editors, AFRICACRYPT’10, 3rd International Conference on Cryptology in Africa, LNCS 6055, pages 100–113, Stellenbosch, South Africa, 2010.

[5] D. Wikstrom. A Commitment-Consistent Proof of a Shuffle. In C. Boyd and J. Gonz ¨ alez ´ Nieto, editors, ACISP’09, 14th Australasian Conference on Information Security and Privacy, LNCS 5594, pages 407–421, Brisbane, Australia, 2009.

[6] http://caislab.kaist.ac.kr/lecture/2010/spring/cs548/basic/B02.pdf