Secure Evaluation of a Program

A user device for enabling secure evaluation of a linear branching program, said program having a binary decision tree structure comprising one or more decision nodes and two or more end-labels, wherein a decision node is associated with a comparison operation between a user attribute and a threshold value, said user device comprising:

• a computer readable storage medium having at least part of a transformed linear branching program embodied therewith, wherein at least part of the comparison operations associated with said one or more decision nodes of said stored linear branching program are transformed into one or more encrypted evaluation sequences on the basis of an additive homomorphic cryptosystem, wherein an evaluation sequence of a decision node comprises a sequence of numbers in which the outcome of the comparison operation of a node is embedded;
• and,
• a computer readable storage medium having computer readable program code embodied therewith, and a processor, preferably a microprocessor, coupled to the computer readable storage medium, wherein responsive to executing the computer readable program code, the processor is configured to perform executable operations comprising:
• evaluating said one or more evaluation sequences, said evaluating including detecting the presence of a predetermined number, preferably a zero, in a first evaluation sequence of a first node and determining a second decision node for evaluation or an index of an end-label on the basis the detection of said predetermined number.

A device comprising a computer readable storage medium having computer readable program code embodied therewith, and a processor, preferably a microprocessor, coupled to the computer readable storage medium, wherein responsive to executing the computer readable program code, the processor is configured to perform executable operations comprising:

• providing via a transmitter at said device one or more encrypted user attributes [vj] to a secure server, said user attributes being encrypted by said device on the basis of an additive homomorphic cryptosystem;
• said one or more encrypted user attributes [vj] being linked by said secure server to a node index αj in order to form an indexed encrypted user attribute;
• and said indexed encrypted user attribute [vαj] being combined with an associated encrypted threshold value [tj] and a random blinding value [bj] into an encrypted blinded node value [vαj−tj+bj] on the basis of one or more homomorphic computations on the basis of said homomorphic cryptosystem;
• receiving from said secure server via a receiver at said device said encrypted blinded node value [vαj−tj+bj],
• decrypting said encrypted blinded node value [vαj−tj+bj] into a blinded node value.

A computer program product for enabling secure evaluation of a linear branching program, said program having a binary decision tree structure comprising one or more decision nodes and two or more end-labels, wherein a decision node is associated with a comparison operation between a user attribute and a threshold value, the computer program product comprising:

• a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising:
• transforming at least part of the comparison operations associated with said one or more decision nodes into one or more encrypted evaluation sequences on the basis of an additive homomorphic cryptosystem, wherein an evaluation sequence of a decision node comprises a sequence of numbers in which the outcome of the comparison operation of a node is embedded;
• and/or,
• evaluating said one or more evaluation sequences, said evaluating including detecting the presence of a predetermine number, preferably a zero, in a first evaluation sequence of a first node and determining a second decision node for evaluation or an index of an end-label on the basis the detection of said predetermined number.