Set membership proofs in data processing systems
AssigneeInternational Business Machines Corporation
InventorsJan Leonhard Camenisch, Rafik Chaabouni, Abhi A. Shelat
Life of this patent
Estimating the term…
Abstract
A method and apparatus for proving and a method and apparatus for verifying that a secret value is a member of a predetermined set of values. The proving mechanism receives a set of signatures which has respective values in the predetermined set signed using a private key. The proving mechanism sends to the verifying mechanism a commitment on the secret value of the proving mechanism. The proving mechanism and verifying mechanism then communicate to implement a proof of knowledge protocol demonstrating knowledge by the proving mechanism of a signature on the secret value committed to in the commitment, thus proving that the secret value is a member of the predetermined set.
Claims25
A method of proving to a verifying mechanism of a data processing system that a value secret to a proving mechanism of the system is a member of a predetermined set of values, the method comprising:
- sending to the verifying mechanism a commitment on the secret value of the proving mechanism;
- receiving at the proving mechanism a set of signatures which has respective values in the predetermined set of values signed using a private key;
- and
- communicating with the verifying mechanism to implement a proof of knowledge protocol demonstrating knowledge by the proving mechanism of a signature on the secret value committed to in the commitment.
A method of verifying at a verifying mechanism of a data processing system that a value secret to a proving mechanism of the system is a member of a predetermined set of values corresponding to a published set of signatures which has respective values in the predetermined set of values signed using a private key, the method comprising the steps of:
- receiving from the proving mechanism a commitment on the secret value;
- and
- communicating with the proving mechanism to implement a proof of knowledge protocol demonstrating knowledge by the proving mechanism of a signature on the secret value committed to in the commitment.
A proving mechanism for a data processing system for proving to a verifying mechanism of the system that a value secret to the proving mechanism is a member of a predetermined set of values, the proving mechanism comprising:
- means for sending to the verifying mechanism a commitment on the secret value;
- means for receiving a set of signatures which has respective values in the predetermined set signed using a private key;
- and
- means for communicating with the verifying mechanism to implement a proof of knowledge protocol demonstrating knowledge by the proving mechanism of a signature on the secret value committed to in the commitment.
A verifying mechanism for a data processing system for verifying that a value secret to a proving mechanism of the system is a member of a predetermined set of values corresponding to a published set of signatures which has respective values in the predetermined set signed using a private key, the verifying mechanism comprising:
- means for receiving from the proving mechanism a commitment on the secret value;
- and
- means for communicating with the proving mechanism to implement a proof of knowledge protocol demonstrating knowledge by the proving mechanism of a signature on the secret value committed to in the commitment.
A data processing system, comprising:
- a proving mechanism having (i) means for sending to a verifying mechanism a commitment on the secret value, (ii) means for receiving a set of signatures which has respective values in the predetermined set signed using a private key, and (iii) means for communicating with the verifying mechanism to implement a proof of knowledge protocol demonstrating knowledge by the proving mechanism of a signature on the secret value committed to in the commitment;
- and
- a communications channel for conveying communications between the proving and verifying mechanisms;
- wherein the verifying mechanism has (i) means for receiving from the proving mechanism a commitment on the secret value and (ii) means for communicating with the proving mechanism to implement a proof of knowledge protocol demonstrating knowledge by the proving mechanism of a signature on the secret value committed to in the commitment.
Dependencies are inferred from the claim text.