Secure Evaluation of a Program

摘要

A method for enabling a client in a user device to securely evaluate a linear branching program. The program may include decision nodes and end-labels. A decision node is associated with a comparison computation for comparing a first value with a second value and a decision rule that links the outcome of the comparison computation to a further decision node or end-label. The method includes transforming the comparison computation into encrypted evaluation sequences on the basis of an additive homomorphic cryptosystem. An evaluation sequence of a decision node includes a sequence of numbers in which the outcome of a comparison computation at a node is embedded; and, evaluating evaluation sequences, evaluating including detecting presence of a predetermine value in an evaluation sequence of a node and determining an evaluation sequence of a further node or an end-label on the basis of the detection of the predetermined value.

主权项

1. Computer-implemented method for securely evaluating at least part of a linear branching program, said program having a binary decision tree structure comprising one or more decision nodes and two or more end-label nodes, wherein a decision node is associated with a comparison operation between a user attribute and a threshold value, said method comprising:
a processor in a secure server executing computer readable program code for transforming at least part of the comparison operations associated with said one or more decision node into one or more encrypted evaluation sequences on the basis of a first additive homomorphic cryptosystem, wherein an evaluation sequence of a decision node comprises a sequence of numbers in which an outcome of the comparison operation of a decision node is embedded; and a processor in a user device executing computer readable program code for 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 of the detection of said predetermined number.