The purpose of this paper is the research of the matrix-based knapsack cipher in the context of additively homomorphic encryption and its application in secret electronic voting. Group-based knapsack ciphers represent a novel approach for building knapsack-like encryption schemes, which is based on the properties of generating sets of finite groups and isomorphic transformations. The matrix-based knapsack cipher is a cryptosystem of the given class, which is constructed using the direct product of diagonal subgroups of a general linear group over a finite field. In the given paper two new results are proposed. The first one is represented by the proof that the considered encryption scheme is additively homomorphic. This property allows the investigated cipher to be used in several application fields besides key agreement in hybrid cryptosystems. The second result is a brief description of a new secret electronic voting protocol, which is built on the basis of the matrix-based knapsack cipher.
Asymmetric ciphers, also known as public-key encryption schemes, are of great importance for ensuring the confidentiality of data exchange as they allow users of insecure communication channels to establish a common secret key for a symmetric cryptosystem [1]. For this reason the given ciphers are used in such widespread network protocols like TLS, SSH and IKEv2 [2].
The knapsack-like ciphers constitute the class of asymmetric encryption schemes, which has been among the earliest representatives of public-key cryptosystems. The Merkle-Hellman knapsack cipher is the historically first encryption scheme of the given class. Although this cryptosystem, as well as many other ciphers of the aforementioned class, has been broken, knapsack-based cryptography continues to attract attention of researchers [1]. Attempts to develop new or improve the existing cryptosystems of this class are undertaken as the general knapsack problem has been proven to be NP-complete [3].
Group-based knapsack ciphers represent a novel approach for building knapsacklike encryption schemes, which is based on the properties of generating sets of finite groups and isomorphic transformations. The matrix-based knapsack cipher is a cryptosystem of the given class, which is constructed using the direct product of diagonal subgroups of a general linear group over a finite field [4, 5]. This encryption scheme, as well as its class, has been proposed in [4].
The purpose of the present work is to continue and deepen the matrix-based knapsack cipher research, which has been started in [5]. In the given paper two new results are proposed. The first one is represented by the proof that the considered encryption scheme is additively homomorphic. This property can be useful, since homomorphic ciphers are used in several fields of application such as electronic voting, secure multi-party computation and private information retrieval [6]. The second result is a brief description of a new secret electronic voting protocol, which is built on the basis of the matrix-based knapsack cipher. 2
Let n and q be parameters of this cryptosystem. Consider a group G, which is the
diagonal subgroup of general linear group GL(n, GF(q)). As the multiplication of
diagonal matrices is commutative, G is an abelian group. Choose a generating set of
G and represented it by a tuple (g1, g2, ..., gn). A value of gi is chosen as a diagonal
matrix, where the i-th entry of the main diagonal is some primitive element zі of
GF(q) and other elements equal the corresponding entries of n-dimensional identity
matrix. Thus, the generating set of G can be completely described by (z1, z2, ..., zn).
The multiplicative order for gi equals q - 1, so for each d ∈ G there is a single integer
tuple (x1, x2, ..., xn) such that
d = g1x1 g2x2 ...gnxn ,
(
For purpose of brevity, define entі(x) to be the i-th element of the main diagonal of
x ∈ GL(n, GF(q)). If b ∈ G, then enti(b·gi) = zi·enti(b) and entj(b·gi) = entj(b) for j ≠ і.
Therefore, entі(d) equals zi to the power of xi. Hence,
xі = logzі (entі d),
(
Select a secret value s ∈ GL(n, GF(q)) to define an isomorphism f: G → H and its inverse f-1: H → G, where H is some subgroup of GL(n, GF(q)), as follows: f: x → s-1·x·s, f-1: y → s·y·s-1.
Owing to (
The key generation procedure for the matrix-based knapsack cipher consists of choosing a private key s ∈ GL(n, GF(q)) and computation of a tuple (e1, e2, ..., en), which is a public key [5].
The encryption lies in using (
The decryption is performed as follows [5]:
1. A value of d is calculated using the formula d = f-1(c). A tuple (z1, z2, ..., zn), which
is required for the next stage of decryption, is either stored along with a private key
or computed by the formula zi = enti(f-1(ei)).
2. A plaintext tuple is obtained in accordance with (
In absence of a correct private key the recovery of a plaintext from a ciphertext and a
public key requires to solve (
A toy example of the matrix-based knapsack cipher, where q = 11 and n = 4, is presented below. In this case, G is a diagonal subgroup of GL(4, GF(11)), so a tuple (g1, g2, g3, g4) can be chosen in the following way:
2 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0
g1 = 0 1 0 0 , g2 = 0 6 0 0 , g3 = 0 1 0 0 , g4 = 0 1 0 0 .
0 0 1 0 0 0 1 0 0 0 7 0 0 0 1 0
0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 8
Hence, (z1, z2, z3, z4) equals (
A private key s and its inverse s-1 are selected as follows:
3 8 5 2 2 2 0 9 s = 1 3 4 5 , s-1 = 8 8 10 10 1 10 8 5 8 5 2 10 9 0 9 7 6 2 10 4 .
The corresponding public key (e1, e2, e3, e4) is described in the following way:
A plaintext to be encrypted is (
A cipher is additively homomorphic if for all parameters and keys it possesses all of the following features [7, 8]: 1. A set of plaintexts with and a ciphertexts set with are additive and multiplicative abelian groups, respectively. The symbols and designate some binary operations. 2. If an encryption procedure converts m1 to c1 and m2 to c2, then the decryption of c1 c2 yields m1 m2.
For the matrix-based knapsack cipher define operations and as follows: u1, ..., un v1, ..., vn = u1+ v1 mod q - 1, ..., un + vn mod q - 1 It is easy to show that the set of plaintexts and constitute an additive abelian group. The ciphertexts set and form the group H, which is isomorphic to the multiplicative abelian group G. Thus, the investigated cipher fulfills the first of the aforesaid necessary conditions of additive homomorphism.
Consider this cipher in the context of the second feature from the list above. Let the
plaintexts be m1 = (u1, u2, ..., un) and m2 = (v1, v2, ..., vn). The ciphertexts c1 and c2 are
obtained by encryption of m1 and m2, respectively. As the group H is abelian, it
follows from (
c1 c2 = e1u1+ v1 e2u2+ v2 ... enun + vn .
Since ei is defined by (
c1 c2 = e1u1+ v1 modq -1 e2u2 + v2 modq -1 ... enun + vn modq -1
In (
Thus, the matrix-based knapsack cipher is additively homomorphic, as it has all the features from the list above. 4
Secret electronic voting systems can be built on the basis of additively homomorphic encryption schemes. However, such systems require using additional cryptographic tools, among which there are secret-sharing schemes and zero-knowledge proof protocols [9].
As the matrix-based knapsack cipher is additively homomorphic, it can be used to construct the secret e-voting protocol, which is proposed below. Secret sharing and zero-knowledge proof schemes are not considered in the current paper, since choosing them can be the subject of a separate research. The focus of this section is on the role, which the investigated cryptosystem plays in the described e-voting protocol. Using this cipher allows voters to keep their votes secret during the tallying process.
The proposed secret e-voting protocol consist of the preparatory, voting and
tallying stages. The first stage comprises registering voters and candidates, choosing
pa(
The preparatory stage includes the following steps: 1. Voters and candidates are registered in the e-voting system. Let nv and nc be quantities of voters and candidates, respectively. 2. The tallying committee chooses positive integer number tv, which determines the range of marks used by a voter, and publishes it. Accordingly, a vote is a tuple of marks given to candidates, where each element belongs to {0, 1, 2, ..., tv}. The value of tv should be small to provide computational efficiency, since the use of a large tv leads to calculation of discrete logarithms in a large finite field during the tallying stage. 3. The parameters of the matrix-based knapsack cipher are chosen. The value of q must be no less than tv · nv + 2 to ensure that any total mark given to a candidate is less than q - 1. The parameter n is chosen to equal nc + np, where np is the length of a random padding tuple used to provide a probabilistic encryption of a vote. Consequently, an encrypted vote is a ciphertext corresponding to the plaintext obtained by concatenating a vote tuple with a random padding. The value of q to the power of np must be sufficiently large to provide semantic security against chosenplaintext attack. Choosing the value of np can be considered in further research. 4. The public and private keys for the matrix-based knapsack cipher are generated. A secret sharing scheme is used to split the private key into nt unique secret shares, where nt is the number of members of tallying committee. Each member receives only one of these shares. No member must obtain the private key or a share given to another member. All nt shares are required to recover the decryption key. After the secret shares are generated, the public key is published, whereas the private one is deleted as no one must know it.
The voting stage can be described as follows: 1. The voting server and a voter perform mutual authentication. 2. A voter gives to each candidate some nonnegative integer mark, which does not exceed tv, and performs probabilistic encryption of his vote by means of the considered cipher using the public key of the voting system. Let wi,j denote the mark given by the i-th voter to the j-th candidate. The k-th element of the random padding tuple generated by the i-th voter is designated as pi,k. The i-th encrypted vote сі is obtained as the result of encryption of the plaintext
wi,1, wi,2 , ..., wi,nc , pi,1, pi,2 , ..., pi,np ,
where wi,j ∈ {0, 1, 2, ..., tv} for all j ≤ nc, pi,k ∈ [0, q - 2] for all k ≤ np. Thus, it follows
from (
ci = e1wi,1 e2wi,2 ... enwci,nc enpic,11 enpic,22 ... en 3. The value of сі and proof of its correctness are sent to the voting server. This proof, which is generated by means of a non-interactive zero-knowledge range proof protocol, allows voting server to make sure that for сі every wi,j is not greater than tv. The tallying stage consists of the following steps:
1. The voting server calculates h, which is defined as the product of all correct
encrypted votes received on the previous stage, and sends its value to the tallying
committee. Let nr denote the number of such votes. It follows from (
2. The members of the tallying committee give their secret shares, as well as the
ciphertext h, to the voting system, which restores the private key, decrypts h and
truncates the obtained plaintext tuple, leaving only the first nc elements. The resulting
tuple, which describes an outcome of the voting, is sent to the tallying committee. In
accordance with (
b1 mod (q -1), ..., bnc mod (q -1), m1 mod (q -1), ..., mnp mod (q -1), where bj < q - 1 for all j ≤ nc, which follows from the way of choosing q on the third step of the preparatory stage. Thus, the resulting tuple received by the tallying committee is equal to
b1, b2 , ..., bnc -1, bnc .
The restored private key, as well as the received shares, are kept secret by the voting system. These data must be deleted after h is decrypted.
3. The tallying committee announces the result of the voting.
Consider a toy example of execution of this secret e-voting protocol, where 3 candidates are assessed by 7 voters, which give to each candidate some mark from the set {0, 1, 2, 3, 4, 5}. In this case, nv = 7, nc = 3 and tv = 5.
The parameters for the underlying cipher are chosen as follows. The smallest
possible value of q is nv · tv + 2 = 37, since this number is prime. Therefore, let q be 37 as
this choice is suitable for a toy example. The value of np is chosen to equal 2, so
n = nc + np = 5. Accordingly, for the given parameters of the matrix-based knapsack
cipher the group G is a diagonal subgroup of GL(5, GF(37)). The elements of the
tuple (g1, g2, g3, g4, g5) can be selected as follows:
Thus, (z1, z2, z3, z4, z5) is equal to (
A private key s and its inverse s-1 are chosen in the following way: Hence, the public key (e1, e2, e3, e4, e5) is described as follows: The value of s is split into unique secret shares, which are distributed among of the members of tallying committee. The values of s and s-1 are deleted as soon as all secret shares are generated.
The first voter gives marks 2, 4 and 5 to the first, second and third candidates,
respectively. The random values used to encrypt the vote are 27 and 34. Accordingly,
w1 = (
1
The decryption ends with obtaining the plaintext tuple (x1, x2, x3, x4, x5) as follows:
x1 = logz1 (ent1 d) log2 (30) 14, x2 = logz2 (ent2 d) log5(12) 20,
x3 = logz3 (ent3 d) log13(10) 12, x4 = logz4 (ent4 d) log15(
x5 = logz5 (ent5 d) log17 (11) 30.
The plaintext truncated to the first 3 elements, which represents the outcome of the voting, is sent to the tallying committee. Its members receive the tuple (14, 20, 12) and publish it as the voting results. Since w1 + ... + w7 = (14, 20, 12), the published total marks are correct. 5
The property of additive homomorphism, which is proven for the matrix-based knapsack cipher in the current work, allows this encryption scheme to be used in several fields of application, which include but are not limited to key agreement in hybrid cryptosystems. In particular, a new secret electronic voting protocol constructed on the basis of the given cipher is proposed in the given paper in the form of a brief description. This protocol allows a voter to assess each candidate by means of using nonnegative integer marks.
Future research can be focused on choosing the parameters for the considered cryptosystem, which would provide 128-bit and 256-bit security levels. Another possible research direction encompasses the probabilistic encryption by means of the given cipher in the context of the proposed secret e-voting protocol.