Cryptocounters for Our PETs
Over the next months, I will be releasing under open-source licenses a number of projects I have been lately working on, in the areas of security software, software security, and privacy-enhancing technologies (PETs).
Today, I am announcing Encounter, a software library aimed at providing a production-grade implementation of cryptographic counters and fostering further research on their constructions and applications.
A cryptographic counter is a public string representing an encryption of a quantity, satisfying the following properties:
- Subjects with access to the public-key can update the encrypted counter by an arbitrary amount, by means of increment or decrement operations and without first decrypting the encryption of the counter value (i.e., the increment/decrement operations are performed over encrypted data);
- The plaintext value is hidden from all participants except the entity holding some secret key;
- The adversary can only learn if the cryptographic counter was updated (i.e., information about whether the counter was incremented, decremented, or re-encrypted is kept hidden to all participants except the secret-key holder and the updating entity -- honest-but-curious threat model).
This cryptographic primitive has number of possible applications ranging from privacy-preserving statistics gathering in a honest-but-curious threat-model, to secure electronic voting, to digital rights management, and cryptovirology.
For instance, an electronic voting system could allow voters to cast their votes by incrementing a cryptographic counter by encrypted addend chosen between the randomized encryption of 0 or 1, according to their preference. An authority would later compute the final tally by decrypting the cryptocounter and retrieving the plaintext value. The cryptocounter properties would give to other participants no information about the modification introduced by each voter.
In the upcoming posts, I will discuss the applications of cryptocounters in greater detail.
The Encounter APIs
Encounter provides a number of APIs for working with cryptocounters, as well as APIs for creating, persisting, and disposing key-pairs and their key stores.
While looking at the operations that can be performed on counters, it is convenient to distinguish among those based on public-keys (i.e., operations that can be performed by entities different from the authority holding the secret key) and those on private-keys.
Users with access to the public-key only can: increment or decrement the cryptocounter, add or subtract two cryptocounters, multiply a cryptocounter for a given quantity, create duplicates or copies, or probabilistically re-encrypt a counter (i.e., touch it), hence diminishing the possibility of correlations by an adversary observing the update operations.
Users with access to the private key can gain access to the plaintext counter by decrypting the cryptographic object and, with the upcoming Encounter release, they can compare two cryptocounters using a variety of techniques I will describe in the next blog post.
The Paillier PKCS
Encounter is designed to support a number of cryptographic backends, keystore mechanisms and cryptocounters constructions with different security/performance trade-offs. To date, the only construction implemented is based on the Paillier public-key cryptographic scheme (PKCS).
The Paillier PKCS is additive homomorphic cryptosystem providing semantic security against chosen-plaintext attacks (IND-CPA) under the decision composite residuosity (DCR) problem. For the sake of this post, it will suffice to say that the homomorphic properties of this cryptographic scheme provides one of the most elegant cryptocounters constructions. In particular:
- the product of two ciphertexts will decrypt to the sum of the their corresponding plaintexts;
- the product of a ciphertext with a public quantity (the generator) raised to the plaintext will decrypt to the sum of the correspnding plaintexts
- a ciphertext raised to the power of another plaintext will decrypt to the product of the to plaintexts.
As always, feedback are welcome and invite you to play with it and share your experiences.
On the upcoming releases, you will find:
- a mechanism to probabilistically re-encrypt the cryptocounters on a periodic basis (an API already exist for probabilistically re-encrypt your counters, please see encounter_touch());
- protocols for the private comparison of counters;
- more keystore mechanisms;
- more cryptocounters constructions;
- bindings to other programming languages;
- applications using Encounter.
Interested? Please be in touch.