COMPUTER IMPLEMENTED VOTING PROCESS AND SYSTEM

Abstract

A computer implemented voting process (2) for executing a blockchain transaction, such as a transaction on the Bitcoin blockchain, is disclosed. The process comprises distributing shares (6) of a first common secret among a plurality of participants (4), wherein the first common secret implements an automated voting process (14) by the participants and is accessible to a first threshold number of shares and is inaccessible to less than the first threshold number of shares. The process further comprises determining (10, 12), based on different numbers of said shares of the first common secret held by a plurality of the participants, at least one combination of shares held by a plurality of the participants, to provide the first threshold number of shares.

Claims

1. A computer-implemented voting process comprising: distributing a plurality of shares of a first common secret among a plurality of participants, wherein said first common secret implements an automated voting process by the participants and is accessible to a first threshold number of said shares and is inaccessible to less than said first threshold number of shares; and determining, based on different numbers of said shares of said first common secret held by a plurality of said participants, at least one combination of said shares held by a plurality of said participants, to provide said first threshold number of shares.

2. The computer-implemented voting process according to claim 1, wherein the step of determining at least one said combination comprises applying a knapsack algorithm to data including information representing respective numbers of shares held by a plurality of said participants.

3. The computer-implemented voting process according to claim 2, where the data further includes information representing estimated voting behaviour of a plurality of said participants.

4. The computer-implemented voting process according to claim 3, wherein the information representing estimated voting behaviour includes a coefficient by which the information representing respective numbers of shares held by a plurality of said participants is multiplied.

5. The computer-implemented voting process according to claim 2, wherein the knapsack algorithm determines at least one first said combination for shares held by a first plurality of said participants on the basis of at least one second said combination for shares held by a second plurality of said participants, wherein said second plurality is different from said first plurality.

6. The computer-implemented voting process according to claim 2, wherein numbers of shares held by the plurality of participants are estimated by comparing said data to a plurality of predetermined values.

7. The computer-implemented voting process according to claim 6, wherein the predetermined values are based on at least one Stern series.

8. The computer-implemented voting process according to claim 6, wherein a plurality of said predetermined values are determined on the basis of other said predetermined values.

9. The computer-implemented voting process according to claim 1, wherein the first common secret is a digital signature.

10. A process according to claim 9, wherein each said share is a partial signature, signed by a respective share of a private key and a respective share of an ephemeral key, and the computer-implemented voting process further comprises distributing a plurality of shares of said private key among said plurality of participants, wherein said first private key is accessible to a second threshold number of shares and is inaccessible to less than said second threshold number of shares, and distributing a plurality of shares of said ephemeral key among said plurality of participants, wherein said ephemeral key is accessible to a third threshold number of shares and is inaccessible to less than said third threshold number of shares.

11. The computer-implemented voting process according to claim 9, wherein the digital signature is applied to a blockchain transaction.

12. A system, comprising: a processor; and memory including executable instructions that, as a result of execution by the processor, causes the system to perform any embodiment of the computer-implemented voting process as defined in claim 1.

13. A non-transitory computer-readable storage medium having stored thereon executable instructions that, as a result of being executed by a processor of a computer system, cause the computer system to at least perform an embodiment of the computer-implemented process as defined in claim 1.

14. A system, comprising: a processor; and memory including executable instructions that, as a result of execution by the processor, causes the system to perform any embodiment of the computer-implemented process as defined in claim 2.

15. A system, comprising: a processor; and memory including executable instructions that, as a result of execution by the processor, causes the system to perform any embodiment of the computer-implemented process as defined in claim 3.

16. A system, comprising: a processor; and memory including executable instructions that, as a result of execution by the processor, causes the system to perform any embodiment of the computer-implemented process as defined in claim 5.

17. A system, comprising: a processor; and memory including executable instructions that, as a result of execution by the processor, causes the system to perform any embodiment of the computer-implemented process as defined in claim 6.

18. A non-transitory computer-readable storage medium having stored thereon executable instructions that, as a result of being executed by a processor of a computer system, cause the computer system to at least perform an embodiment of the computer-implemented process as defined in any one of claim 2.

19. A non-transitory computer-readable storage medium having stored thereon executable instructions that, as a result of being executed by a processor of a computer system, cause the computer system to at least perform an embodiment of the computer-implemented process as defined in any one of claim 3.

20. A non-transitory computer-readable storage medium having stored thereon executable instructions that, as a result of being executed by a processor of a computer system, cause the computer system to at least perform an embodiment of the computer-implemented process as defined in any one of claim 6.

Description

[0035] These and other aspects of the present invention will be apparent from and elucidated with reference to, the embodiment described herein. An embodiment of the present invention will now be described, by way of example only, and with reference to the accompany drawings, in which:

[0036] FIG. 1 shows a schematic representation of an automated voting process embodying the present invention; and

[0037] FIG. 2 is a schematic diagram illustrates a computing environment in which various embodiments can be implemented.

[0038] A mechanism for generating shares of a signed blockchain transaction will first be described.

[0039] Initially, secure communication channels are established between participants in a manner described in detail in International Patent Application WO 2017/145016, so that data can be exchanged between participants without being made available to other participants.

[0040] When secure communication channels have been established between the participants, shares d.sub.A(i) of a first private key d.sub.A are distributed between a group of first participants by means of a method as described below.

[0041] Algorithm 1Key Generation

[0042] Domain Parameters (CURVE, Cardinality n, Generator G)

[0043] Input: N/A

[0044] Output: Key Shares d.sub.A1, d.sub.A2 . . . d.sub.AN

[0045] The method for algorithm 1 follows: [0046] 1) Each participant p.sub.(i) of (N) where 1iN exchanges an ECC public key (or in this implementation, a Bitcoin address) with all other participants. This address is the Group identity address and does not need to be used for any other purpose.

[0047] It should be noted that this is a derived address, for example as disclosed in International patent application WO2017/145016, and key based on a shared value between each of the participants from the process disclosed therein. [0048] 2) Each participant p.sub.(i) selects a polynomial .sub.i(x) of degree (k1) with random coefficients in a manner that is secret from all other parties.

[0049] This function is subject to the participant's secret a.sub.0.sup.(i) that is selected as the polynomial free term. This value is not shared. This value is calculated using a derived private key. .sub.i(h) is defined to be the result of the function, .sub.(x) that was selected by participant p.sub.(i) for the value at point (x=h), and the base equation for participant p.sub.(i) is defined as the function: .sub.(x)=.sub.p=0.sup.(k-1) a.sub.px.sup.p mod n

[0050] In this equation, a.sub.0 is the secret for each participant p.sub.(i) and is not shared.

[0051] Hence, each participant p.sub.(i) has a secretly kept function .sub.i(x) that is expressed as the degree (k1) polynomial with a free term a.sub.0.sup.(i) being defined as that participant's secret such that:

.sub.i(x)=.sub.=0.sup.(k-1)a.sub.x.sup.mod n [0052] 3) Each participant p.sub.(i) encrypts .sub.i(h) to participant P.sub.(h)h={1, . . . (i1),(i+1), . . . , N} using P.sub.(h)'s public key as noted above and exchanges the value for P.sub.(h) to decrypt.

[0053] Given that Z.sub.n is a field and it is possible to validly do Lagrange interpolation modulo n over the values selected as ECC private keys, a condition exists which leads to the conclusion that Shamir's Secret Sharing Scheme SSSS [5] can be implemented over Z.sub.n. [0054] 4) Each participant P.sub.(i) broadcasts the values below to all participants.

a.sub..sup.(i)G={0, . . . ,(k1)}a)

.sub.i(h)Gh={1, . . . ,N}b)

[0055] The value associated with the variable h in the equation above can either be the position of the participant P.sub.(h) such that if participant P.sub.(h) represents the third participant in a scheme, then h=3 or equally may represent the value of the ECC public key used by the participant as an integer. Use cases and scenarios exist for either implementation. In the latter implementation, the value h={1, . . . , N} would be replaced by an array of values mapped to the individual participant's utilised public key. [0056] 5) Each participant P.sub.(hi) verifies the consistency of the received shares with those received from each other participant. That is:

.sub.=0.sup.(k-1)h.sup.a.sub..sup.(i)G=f.sub.i(h)G

[0057] And that .sub.i(h)G is consistent with the participant's share. [0058] 6) Each participant P.sub.(hi) validates that the share owned by that participant (P.sub.(hi)) and which was received is consistent with the other received shares:

[00001]$a_0^{\left(i\right)}.Math.G={}_{hB}.Math.{}_j.Math.f_i\left(h\right).Math.G.Math..Math.P_{\left(hi\right)}$

[0059] In effect, this means that the participant carries out a process which would recover the shared secret from the received shares, but instead recovers the shared secret multiplied by the generator point G, from the shares multiplied by G. If this is not consistent, the participant rejects the protocol and starts again. [0060] 7) Participant p.sub.(i) now either calculates their share d.sub.A(i) as:

SHARE(p.sub.(i))=d.sub.A(i)=.sub.h=1.sup.j.sub.h(i)mod n [0061] Where: SHARE(p.sub.(i))Z.sub.n [0062] and [0063] Where: Q.sub.A=ExpInterpolate(.sub.1, . . . , .sub.N) [=Gd.sub.A]

[0064] Where the operation ExpInterpolate(.sub.1, . . . , .sub.N) means carrying out an operation to recover the shared secret value Gd.sub.A, from the shares f.sub.1 G, . . . f.sub.NG, in the manner usually used to recover a shared secret d.sub.A, from the shares f.sub.1, . . . f.sub.N, for example by means of interpolation using Lagrange coefficients in the case of a Shamir secret sharing scheme. [0065] Return (d.sub.A(i),Q.sub.A)

[0066] Participant p.sub.(i) now uses the share in calculating signatures. This role can be conducted by any participant or by a party p.sub.(c) that acts as a coordinator in the process of collecting a signature. The participant p.sub.(c) can vary and does not need to be the same party on each attempt to collect enough shares to sign a transaction.

[0067] Hence private key shares d.sub.A(i)Z.sub.n* have been created without knowledge of the other participant's shares.

[0068] Algorithm 2Updating the Private Key

[0069] Input: Participant P.sub.i's share of private key d.sub.A denoted as d.sub.A(i)

[0070] Output: Participant P.sub.i's new private key share d.sub.A(i).

[0071] Algorithm 2 can be used to both update the private key as well as to add randomness into the protocol. [0072] 1) Each participant selects a random polynomial of degree (k1) subject to zero as its free term. This is analogous to Algorithm 1 but that the participants must validate that the selected secret of all other participants is zero.

[0073] It should be noted that: G=nG=0 where 0 is a point at infinity on the elliptic curve.

[0074] Using this equality, all active participants validate the function:

a.sub.0.sup.(i)G= i={1, . . . ,N} [0075] Generate the zero share: z.sub.iZ.sub.n* [0076] 2) d.sub.A(i)=d.sub.A(i)+z.sub.i [0077] 3) Return: d.sub.A(i)

[0078] A collection of participants construct private key shares d.sub.A.sub.1,d.sub.A.sub.2, . . . , d.sub.A.sub.N in accordance with algorithm 1. New key shares Dk.sub.1, Dk.sub.2, . . . , Dk.sub.N are introduced to each participant in the collection. These shares may be constructed using algorithm 1 above in which a threshold share of participants may be able to construct a shared secret Dk that is not previously known. Alternatively, Dk may be known in advance (eg a deterministic key) and shares may be constructed in a manner similar to algorithm but such that a pre-known Dk is chosen to be the free term in the polynomial. In either case, Dk.Math.G is known to all but only a slice Dk.sub.1, Dk.sub.2, . . . , Dk.sub.N is known by each of the participant in the collection.

[0079] As all participants know 1.sup.st public key

P.sub.1S=d.sub.A.Math.G

they can calculate

P.sub.2S=P.sub.1S+Dk.Math.G

[0080] without broadcasting their slice of the d.sub.A or Dk, because the first V.sub.1S and second V.sub.2S private keys are related by V.sub.2S=V.sub.1S+Dk. The individual shares [0081] d.sub.A.sub.1, . . . , d.sub.A.sub.N and Dk.sub.1, . . . , Dk.sub.N

[0082] remain known only to each individual participant.

[0083] A new address P.sub.2S can be created and a transaction tx signed to this, that changes who controls the main funds. That is, a payment from P.sub.1S to P.sub.2S can be signed by members of address P.sub.1S.

[0084] The Dk collection can be set as either a group from P.sub.1S collection (either a threshold number or all members) or may be a new group. Each threshold slice of Dk is able to be assigned separately, but it should be remembered that if P.sub.1S and Dk are controlled separately then this creates a dual signing structure where both P.sub.1S and Dk are required at the respective threshold rates to sign a transaction tx. It should also be noted that P.sub.1S and Dk do not require the same members nor the same proportions.

[0085] Algorithm 3Signature Generation [0086] Input: [0087] Message to be signed

e=H(m).

[0088] Private key share [0089] d.sub.A.sub.1, . . . , d.sub.A.sub.N, where d.sub.A.sub.iZ.sub.n*.

[0090] Deterministic key share [0091] Dk.sub.1, . . . , Dk.sub.N where Dk.sub.iZ.sub.n*.

[0092] The private key shares d.sub.A.sub.1, d.sub.A.sub.2, . . . , d.sub.A.sub.N are generated by means of algorithm 1. The deterministic key shares Dk.sub.1, Dk.sub.2, . . . , Dk.sub.N, are generated by means of algorithm 1 using a random constant as the free term in the polynomial or using a pre-known deterministic key Dk as the free term. [0093] Output: [0094] Signature [0095] (r,s) where r,sZ.sub.n*.

[0096] The signatures are generated using a method which incorporates both the shares of the private key d.sub.A and shares of the deterministic key Dk into the signature. This is described in detail as follows.

[0097] Firstly, each participant generates emphemeral key shares using algorithm 1

k.sub.iZ.sub.n*.

[0098] Next mask shares are generated using algorithm 1 above

.sub.iZ.sub.n*

[0099] and zero mask shares are generated using algorithm 2 above

.sub.iZ.sub.n c.sub.iZ.sub.n.

[0100] Each participant knows k.sub.i,.sub.i,.sub.i,c.sub.i and they are not known to anyone else.

[0101] 1)

e=H(m)

[0102] Distribute the message (transaction to be signed). Broadcast

.sub.i=k.sub.i.sub.i+.sub.i mod n

and

.sub.i=G.Math..sub.i

[0103] 2) Calculate :=Interpolate(.sub.1, . . . , .sub.N) mod n

[=k mod n]

[0104] where is the private key corresponding to the mask shares .sub.i, and the operation Interpolate (.sub.1, . . . .sub.N) means obtain the shared secret from the shares .sub.1, . . . .sub.N, for example by using Lagrange interpolation coefficients.

[0105] 3) Calculate :=ExpInterpolate(.sub.1, . . . , .sub.N) mod n

[=G.Math.].

[0106] 4) Calculate (R.sub.x,R.sub.y) where

R.sub.xy:=(R.sub.x,R.sub.y)=.Math..sup.1.

[=G.Math.k.sup.1].

[0107] 5) Define

r:=r.sub.x=R.sub.x mod n.

[0108] If r=0 start over.

[0109] 6) [0110] Broadcast

S.sub.i:=k.sub.i(e+[d.sub.A.sub.i+Dk.sub.i]r)+c.sub.i mod n.

[0111] Note that if d.sub.A.sub.i and Dk.sub.i represent different collections of participants then two participants from each collection must communicate to broadcast each individual S.sub.i.

[0112] 7)

s:=Interpolate(S.sub.1, . . . ,S.sub.M)mod n

[=k(e+[d.sub.A+Dk]r)mod n].

[0113] If S=0 start over.

[0114] 8) Return (r,s).

[0115] 9) Construct a transaction that comes from P.sub.2S=(d.sub.A+Dk).Math.G. This is a standard Bitcoin transaction with an (r,s) signature. At no point have d.sub.A or Dk been reconstructed (unless Dk has been split from an existing known value).

Mechanism for Optimisation of VotingEmbodiment of Solution

[0116] Referring to FIG. 1, a computer-implemented voting process 2 embodying the present invention for a plurality of participants 4 is disclosed. Each participant 4 holds a number of shares 6 of votes in the form of shares of a signed blockchain transaction, so that a threshold number of shares 6 is required in order to sign, and therefore execute 14, the blockchain transaction. The participants 4 can hold varying numbers of shares 6, and therefore the participants 4 can each hold a varying proportion of the total number of shares 6. A probability of reliability 8 can be assigned to each participant 4, wherein the probability of reliability 8 specifies the estimated probability that that participant 4 will vote as expected (or as required) on a given voting decision. The reliability value for the voter can be used as a measure of a cost of an item in a knapsack algorithm 10, described in greater detail below, for example so that cost=1reliability.

[0117] A threshold number of shares needs to be achieved in order to have a transaction signed. The proportions of shares can be assembled in ascending order. A safety margin for the number of required votes in the threshold can be included, i.e. combinations are calculated which provide higher than the threshold number of shares, in case the probability of reliability 8 is estimated too low. A collection of computational bins is then constructed, sized corresponding to rational numbers ordered according to the Stern-Brocot tree, described in greater detail below. The Stern-Brocot tree can be constructed by dividing neighbouring terms of the Stern series to generate rational numbers. Alternatively the Stern-Brocot tree can be computed by following a matrix multiplication procedure detailed below. The tree to infinite depth lists a complete set of the rational numbers, as in this construction each rational number occurs only once. Clearly this set is an infinite set. In implementation the depth of the Stern-Brocot tree can be calibrated to tune the granularity of the computational bins. As the number of bins required grows, the computational expense of the sorting procedure increases.

[0118] Only the rational numbers whose value is between zero and one are considered, and these values are ordered by value 12 as the upper and lower bound values for the computational bins. These bins will hold the proportion of total votes that a voter has cast in favour of a motion in question, for example a proposal to execute a blockchain transaction.

[0119] The share proportions multiplied by their reliability (as defined above) are compared to the ordering of the rational numbers less than unity in value and the share proportions placed in the rational number bin that is closest (but larger) in value. This provides an ordering, or a sorting, of the proportions of the shares 6. There will inevitably be a residual, as the share proportions will not exactly match the rational numbers in value, they will however, fall into the computational bins with upper and lower bounds defined as above.

[0120] To illustrate this an example is shown in the table below:

TABLE-US-00001 Total Share proportion Reliability Contribution 20% 80% 16% 15% 100% 15% 30% 40% 12%

[0121] The contribution is the product of the total share proportion that a voter has and the reliability of those votes. The contribution can be viewed as the expected number of votes a voter will contribute.

[0122] The optimum collection of voters can then be computed using a solution to a Knapsack problem (for example dynamic programming, or genetic algorithms), as described in greater detail in Different Approaches to Solve the 0/1 Knapsack Problem, Maya Hristakeva Computer Science Department, Simpson College, Indianola, Iowa 50125.

[0123] A further advantage is that if the voting profile of the voters changes, or the reliability profile of the voters changes, the ordering and optimisation can be recomputed by re-running the same computation. This enables use of this technique in highly dynamically changing circumstances. This also enables the technique to scale to scenarios where there are large numbers of voters.

[0124] Algorithmic Approach to Voting Scheme at Scale

[0125] Algorithm 1

[0126] Step 1: Collect information on voters and the number shares that they have.

[0127] Step 2: Calculate the proportion of total shares each voter has. Assess the degree of reliability that the voter has in voting habits. Assign a cost to the voter for the issue being voted on, as described above. Create a series of computational bins sized according to the rational numbers of value less than unity, as described by the Stern-Brocot tree.

[0128] Step 3: Compare proportions of shares with the values of the rationals less than unity as enumerated by the Stern-Brocot tree. This is an efficient way of sorting values in order of size based on rational fractions of value less than one. This procedure defines both the upper and lower bounds for computational bins. Place the expected proportions of the shares in the associated bin. Keep a track of each entry in each bin. Keep a track of how many entries there are in each bin. This prepares the information about the proportion of shares for the knapsack optimisation process.

[0129] Step 4: Run standard solutions to Knapsack algorithm, for example as described in Different Approaches to Solve the 0/1 Knapsack Problem, Maya Hristakeva Computer Science Department, Simpson College, Indianola, Iowa 50125, with threshold values as constraints. An example of a dynamic programming approach to Knapsack is detailed below.

[0130] Step 5: Confirm voting scheme

[0131] Detailed Definition of Knapsack Algorithm

[0132] An analogy can be drawn between filing a knapsack with valuable items and achieving a threshold vote with expected contributions from a number of voters, as described above. Solutions to the Knapsack problem are described in the Hristakeva reference cited above. One example is described in detail below.

[0133] The Knapsack problem specification is as follows:

[0134] Let Xi denote how many copies of item i are to be placed into the knapsack. The objective function to maximise:

[0135] Maximize

[00002]$\underset{i-1}{\overset{N}{.Math.}}.Math.B_i.Math.X_i$

[0136] Where Xi is the quantity of item type X, and i is the index of the item packed into the knapsack, B is the benefit (so B=1 indicates good, B=0 indicates bad), B.sub.i is the expected benefit of voter i, as defined above, X.sub.i is the proportion of the total shares that voter i has, subject to the constraints

[00003]$\underset{i=1}{\overset{N}{.Math.}}.Math.V_i.Math.X_{i}V$

where V, is the volume of the object index i, and V is the total number of votes, and

[0137] 0X.sub.iQ.sub.i where Q is the maximum number of items of type i

[0138] If one or more of the Qi is infinite, the KP is unbounded; otherwise, the KP is bounded, as described in more detail in Chen T. S. Huang G. S. Liu T. P. and Chung Y. F (2002), Digital Signature Scheme Resulted from Identification Protocol for Elliptic Curve Cryptosystem, Proceedings of IEEE TENCON'02. pp. 192-195.

[0139] Implementation of a Solution to the Knapsack Problem

[0140] A dynamic programming approach solution is described below.

[0141] Dynamic Programming solves problems whose solutions satisfy recurrence relations with overlapping sub-problems.

[0142] Dynamic Programming solves each of the smaller sub-problems only once and records the results in a table. This increases the computational efficiency of the overall solution.

[0143] The table is then used to obtain a solution to the original problem. The dynamic programming approach works bottom-up, for example as described in Hsu C. L and Wu T. C. (1998), Authenticated Encryption Scheme with (t, n) Shared Verification, IEEE ProceedingsComputers and Digital Techniques, Vol. 145, no. 2, pp. 117-120, but the technique can also be applied top-down.

[0144] To design a dynamic programming algorithm for the 0/1 Knapsack problem, it is first necessary to derive a recurrence relation that expresses a solution to an instance of the knapsack problem in terms of solutions to its smaller instances.

[0145] Consider an instance of the problem defined by the first i items, 1iN, with:

weights w1, . . . ,wN,

values v1, . . . ,vN,

and knapsack capacity j, 1jV.

[0146] Let Table[i,j] be the optimal solution of this instance (that is, the value of the most valuable subsets of the first i items that fit into the knapsack capacity of j).

[0147] All the subsets of the first i items that fit the knapsack of capacity j can be divided into two subsets that do not include the i th item and subsets that include the i th item.

[0148] This generates the recurrence relation:

TABLE-US-00002 If j < w.sub.i then Table[i, j] Table[i 1, j] Cannot fit the i.sup.th item Else Table[i, j] maximum { Table[i 1, j] Do not use the i.sup.th item AND vi + Table[i 1, j vi, ] Use the i.sup.th item

[0149] In this context the symbol denotes assignment of a value to a data structure.

[0150] The aim is to find Table [N, Capacity] the maximal value of a subset of the knapsack.

[0151] The two boundary conditions for the knapsack problem are: [0152] The knapsack has no value when there no items included in it (that is, i=0).

Table [0,j]=0 for j0 [0153] The knapsack has no value when its capacity is zero (that is, j=0), because no items can be included in it.

Table [i, 0]=0 for i0

TABLE-US-00003 ALGORITHM Dynamic Programming (Weights [1 . . . N], Values[1 . . . N], table [0 . . . N, 0 . . . Capacity]) Input: Array Weights contains the weights of all items. Array Values contains the values of all items. Array Table is initialized with 0 s; it is used to store the results from the dynamic programming algorithm. Output: The last value of array Table (Table [N, Capacity]) contains the optimal solution of the problem for the given Capacity for i = 0 to N do for j = 0 to Capacity if < Weights[i] then Table[i, j] Table[i 1, j] else Table[i, j] maximum { table[i 1, j] AND Values[i] + table[i 1, j Weights[i[ ] return Table[N, Capacity]

[0154] In this algorithm instance we use two separate arrays are used for the weights and the values of the items, and one further array Items of type item, where item is a structure with two fields: weight and value.

[0155] To find which items are included in the optimal solution, the following algorithm is used:

TABLE-US-00004 n N c Capacity Start at position Table[n, c] While the remaining capacity is greater than 0 do If Table[n, c] = Table[n 1, c] then Item n has not been included in the optimal solution Else Item n has been included in the optimal solution Process Item n Move one row up to n1 Move to column c weight(n) Definition of Stern-Brocot tree 1/1 2/1 3/2 3/1

[0156] It can be seen from the above schematic, which is derived from a Stern series, that the rational numbers can be arranged in the form of a tree. The relationship between the leaves in the tree is that they are all derived from the top element, namely (1/1).

[0157] By considering this value as a vector and multiplying this by either a left matrix L or a right matrix R, successive leaves on the tree can be generated. The matrices L and Rare defined as follows:

[00004]$I=\begin{array}{cc}1& 0\\ 0& 1\end{array}$$L=\begin{array}{cc}1& 0\\ 1& 1\end{array}$$R=\begin{array}{cc}1& 1\\ 0& 1\end{array}$

[0158] And the structure that emerges is as follows:

TABLE-US-00005 I IL IR ILL ILR IRL IRR

[0159] By recursively applying the matrices R and L, it can be seen that further branches of the tree can be generated. The terms at any given level of the tree can then be read from left to right, and an ordering of the rational numbers can be generated. Those numbers to the left of the centre line (aligned with the matrix I) have a value between zero and unity. Those to the right of the centre line have a value greater than unity.

[0160] Turning now to FIG. 2, there is provided an illustrative, simplified block diagram of a computing device 2600 that may be used to practice at least one embodiment of the present disclosure. In various embodiments, the computing device 2600 may be used to implement any of the systems illustrated and described above. For example, the computing device 2600 may be configured for use as a data server, a web server, a portable computing device, a personal computer, or any electronic computing device. As shown in FIG. 2, the computing device 2600 may include one or more processors with one or more levels of cache memory and a memory controller (collectively labelled 2602) that can be configured to communicate with a storage subsystem 2606 that includes main memory 2608 and persistent storage 2610. The main memory 2608 can include dynamic random-access memory (DRAM) 2618 and read-only memory (ROM) 2620 as shown. The storage subsystem 2606 and the cache memory 2602 and may be used for storage of information, such as details associated with transactions and blocks as described in the present disclosure. The processor(s) 2602 may be utilized to provide the steps or functionality of any embodiment as described in the present disclosure.

[0161] The processor(s) 2602 can also communicate with one or more user interface input devices 2612, one or more user interface output devices 2614, and a network interface subsystem 2616.

[0162] A bus subsystem 2604 may provide a mechanism for enabling the various components and subsystems of computing device 2600 to communicate with each other as intended. Although the bus subsystem 2604 is shown schematically as a single bus, alternative embodiments of the bus subsystem may utilize multiple busses.

[0163] The network interface subsystem 2616 may provide an interface to other computing devices and networks. The network interface subsystem 2616 may serve as an interface for receiving data from, and transmitting data to, other systems from the computing device 2600. For example, the network interface subsystem 2616 may enable a data technician to connect the device to a network such that the data technician may be able to transmit data to the device and receive data from the device while in a remote location, such as a data centre.

[0164] The user interface input devices 2612 may include one or more user input devices such as a keyboard; pointing devices such as an integrated mouse, trackball, touchpad, or graphics tablet; a scanner; a barcode scanner; a touch screen incorporated into the display; audio input devices such as voice recognition systems, microphones; and other types of input devices. In general, use of the term input device is intended to include all possible types of devices and mechanisms for inputting information to the computing device 2600.

[0165] The one or more user interface output devices 2614 may include a display subsystem, a printer, or non-visual displays such as audio output devices, etc. The display subsystem may be a cathode ray tube (CRT), a flat-panel device such as a liquid crystal display (LCD), light emitting diode (LED) display, or a projection or other display device. In general, use of the term output device is intended to include all possible types of devices and mechanisms for outputting information from the computing device 2600. The one or more user interface output devices 2614 may be used, for example, to present user interfaces to facilitate user interaction with applications performing processes described and variations therein, when such interaction may be appropriate.

[0166] The storage subsystem 2606 may provide a computer-readable storage medium for storing the basic programming and data constructs that may provide the functionality of at least one embodiment of the present disclosure. The applications (programs, code modules, instructions), when executed by one or more processors, may provide the functionality of one or more embodiments of the present disclosure, and may be stored in the storage subsystem 2606. These application modules or instructions may be executed by the one or more processors 2602. The storage subsystem 2606 may additionally provide a repository for storing data used in accordance with the present disclosure. For example, the main memory 2608 and cache memory 2602 can provide volatile storage for program and data. The persistent storage 2610 can provide persistent (non-volatile) storage for program and data and may include flash memory, one or more solid state drives, one or more magnetic hard disk drives, one or more floppy disk drives with associated removable media, one or more optical drives (e.g. CD-ROM or DVD or Blue-Ray) drive with associated removable media, and other like storage media. Such program and data can include programs for carrying out the steps of one or more embodiments as described in the present disclosure as well as data associated with transactions and blocks as described in the present disclosure.

[0167] The computing device 2600 may be of various types, including a portable computer device, tablet computer, a workstation, or any other device described below. Additionally, the computing device 2600 may include another device that may be connected to the computing device 2600 through one or more ports (e.g., USB, a headphone jack, Lightning connector, etc.). The device that may be connected to the computing device 2600 may include a plurality of ports configured to accept fibre-optic connectors. Accordingly, this device may be configured to convert optical signals to electrical signals that may be transmitted through the port connecting the device to the computing device 2600 for processing. Due to the ever-changing nature of computers and networks, the description of the computing device 2600 depicted in FIG. 2 is intended only as a specific example for purposes of illustrating the preferred embodiment of the device. Many other configurations having more or fewer components than the system depicted in FIG. 2 are possible.

[0168] It should be noted that the above-mentioned embodiments illustrate rather than limit the invention, and that those skilled in the art will be capable of designing many alternative embodiments without departing from the scope of the invention as defined by the appended claims. In the claims, any reference signs placed in parentheses shall not be construed as limiting the claims. The word comprising and comprises, and the like, does not exclude the presence of elements or steps other than those listed in any claim or the specification as a whole. In the present specification, comprises means includes or consists of and comprising means including or consisting of. The singular reference of an element does not exclude the plural reference of such elements and vice-versa. The invention may be implemented by means of hardware comprising several distinct elements, and by means of a suitably programmed computer. In a device claim enumerating several means, several of these means may be embodied by one and the same item of hardware. The mere fact that certain measures are recited in mutually different dependent claims does not indicate that a combination of these measures cannot be used to advantage.

REFERENCES

[0169] 1. Chen T. S. Huang G. S. Liu T. P. and Chung Y. F (2002), Digital Signature Scheme Resulted from Identification Protocol for Elliptic Curve Cryptosystem, Proceedings of IEEE TENCON'02. pp. 192-195 [0170] 2. Hsu C. L and Wu T. C. (1998), Authenticated Encryption Scheme with (t, n) Shared Verification, IEEE ProceedingsComputers and Digital Techniques, Vol. 145, no. 2, pp. 117-120. [0171] 3. Graham, R. L.; Knuth, D. E.; and Patashnik, O. Concrete Mathematics: A Foundation for Computer Science, 2nd ed. Reading, Mass.: Addison-Wesley, pp. 116-117, 1994. [0172] 4. Koblitz N. (1987), Elliptic Curve Cryptosystems, Mathematics of Computation, pp 203-209. [0173] 4a. Padma Bh et. al./(IJCSE) International Journal on Computer Science and Engineering Vol. 02, No. 05, 2010, 1904-1907 Encoding And Decoding of a Message in the Implementation of Elliptic Curve Cryptography using Koblitz's Method [0174] 5. Nyberg K. and Rueppel R. A. (1993), A New Signature Scheme Based on DSA giving message Recovery, ACM Computer and Communications Security, Vol. 1, pp 0.58-61. [0175] 6. Rajaram Ramasamy R, Prabakar M. A, Devi M. I, and Suguna M(2009), Knapsack Based ECC Encryption and Decryption, International Journal of Network Security, Vol. 9, no. 3, pp. 218-226. [0176] 7. Rajaram Ramasamy R. and Amutha Prabakar M. (2011), Digital Signature Scheme with message Recovery Using Knapsack-based ECC, International Journal of Network Security, Vol. 12, no. 1, pp. 15, 20. [0177] 8. Reznick (2008), Regularity Properties of the Stern Enumeration of the Rationals, Journal of Integer Sequence. [0178] 9. Stern, M. A. ber eine zahlentheoretische Funktion. J. reine angew. Math. 55, 193-220, 1858. [0179] 10. Different Approaches to Solve the 0/1 Knapsack Problem Maya Hristakeva Computer Science Department Simpson College Indianola, Iowa 50125 hristake@simpson.edu