Quantum-safe cryptographic methods and systems

Abstract

Cryptographic methods and systems for key exchange, digital signature and zero-knowledge proof. In the digital signature scenario, there is provided a method of signing a digital document, comprising: obtaining a private cryptographic key associated with the signer; obtaining a digital asset from the digital document; selecting a base data element; computing a plurality of signature data elements from (i) the digital asset, (ii) the base data element and (iii) the private cryptographic key; and transmitting the digital document and the plurality of signature data elements to a recipient over a data network. Provenance of the digital document is confirmable by the recipient carrying out a predefined computation involving the digital document, the signature data elements, a plurality of noise variables and a public cryptographic key corresponding to the private cryptographic key associated with the signer. In the zero-knowledge proof scenario, the digital asset plays the role of a challenge data element.

What is claimed is: 
     
         1 . A method of operating a computing apparatus to sign a digital document, comprising:
 obtaining a private cryptographic key associated with the computing apparatus;   obtaining a digital asset from the digital document;   selecting a base data element;   computing a plurality of signature data elements from (i) the digital asset, (ii) the base data element and (iii) the private cryptographic key; and   transmitting the digital document and the plurality of signature data elements to a recipient over a data network;   wherein provenance of the digital document is confirmable by the recipient carrying out a predefined computation involving the digital document, the signature data elements, a plurality of noise variables and a public cryptographic key corresponding to the private cryptographic key associated with the computing apparatus.   
     
     
         2 . The method defined in  claim 1 , wherein obtaining the digital asset from the digital document comprises executing a hash function on the digital document, the hash function being known to the recipient. 
     
     
         3 . The method defined in  claim 1 , further comprising transmitting an identity of the computing apparatus to the recipient over the data network. 
     
     
         4 . The method defined in  claim 1 , wherein the base data element represents an integer, wherein the plurality of signature data elements includes a first signature data element, wherein the method further comprises computing the first signature data element by (i) computing a first quantity from the digital asset and the private cryptographic key; and (ii) setting the first signature data element to equal the base data element to the power of said first quantity. 
     
     
         5 . The method defined in  claim 4 , wherein the plurality of signature data elements includes a second signature data element, wherein the method further comprises computing the second signature data element by (i) computing a second quantity from the digital asset and the private cryptographic key; and (ii) setting the second signature data element to equal the base data element to the power of said second quantity. 
     
     
         6 . The method defined in  claim 5 , wherein the plurality of signature data elements includes a third signature data element, wherein the method further comprises computing the third signature data element by (i) computing a third quantity from the digital asset and the private cryptographic key; and (ii) setting the third signature data element to equal the base data element to the power of said third quantity. 
     
     
         7 . The method defined in  claim 6 , wherein the plurality of signature data elements includes a fourth signature data element, wherein the method further comprises computing the fourth signature data element by (i) computing a fourth quantity from the digital asset and the private cryptographic key; and (ii) setting the fourth signature data element to equal the base data element to the power of said fourth quantity. 
     
     
         8 . The method defined in  claim 7 , wherein the plurality of signature data elements includes a fifth signature data element, wherein the method further comprises computing the fifth signature data element by (i) computing a fifth quantity from the digital asset and the private cryptographic key; and (ii) setting the fifth signature data element to equal the base data element to the power of said fifth quantity. 
     
     
         9 . The method defined in  claim 1 , wherein the base data element is selected to be an integer greater than 2 but less than modulo p, where p is selected to be a prime number greater than 2. 
     
     
         10 . The method defined in  claim 9 , wherein the digital asset is constrained to have a value between 0 and p. 
     
     
         11 . The method defined in  claim 10 , wherein p is at least as great as 2 6 , 2 8 , 2 10 , 2 12 , 2 14 , 2 16 , 2 18 , 2 20 , 2 22  or 2 24 . 
     
     
         12 . The method defined in  claim 1 , further comprising encrypting the digital asset with a public key of the recipient before the transmitting. 
     
     
         13 . A non-transitory computer-readable storage medium comprising computer-readable instructions which, when executed by a processing entity of a computing apparatus, cause the computing apparatus to carry out operations to sign a digital document, the operations including:
 obtaining a private cryptographic key associated with the computing apparatus;   obtaining a digital asset from the digital document;   selecting a base data element;   computing a plurality of signature data elements from (i) the digital asset, (ii) the base data element and (iii) the private cryptographic key; and   transmitting the digital document and the plurality of signature data elements to a recipient over a data network;   wherein provenance of the digital document is confirmable by the recipient carrying out a predefined computation involving the digital document, the signature data elements, a plurality of noise variables and a public cryptographic key corresponding to the private cryptographic key associated with the computing apparatus.   
     
     
         14 . A method of operating a computing apparatus to sign a digital asset, comprising:
 obtaining a private cryptographic key associated with the computing apparatus;   selecting a base data element;   computing a plurality of signature data elements from (i) the digital asset, (ii) the base data element and (iii) the private cryptographic key; and   transmitting the digital asset and the plurality of signature data elements to a recipient over a data network;   wherein provenance of the digital asset is confirmable by the recipient carrying out a predefined computation involving the digital asset, the signature data elements, a plurality of noise variables and a public cryptographic key corresponding to the private cryptographic key associated with the computing apparatus.   
     
     
         15 . A non-transitory computer-readable storage medium comprising computer-readable instructions which, when executed by a processing entity of a computing apparatus, cause the computing apparatus to carry out operations to sign a digital asset, the operations including:
 obtaining a private cryptographic key associated with the computing apparatus;   selecting a base data element;   computing a plurality of signature data elements from (i) the digital asset, (ii) the base data element and (iii) the private cryptographic key; and   transmitting the digital asset and the plurality of signature data elements to a recipient over a data network;   wherein provenance of the digital asset is confirmable by the recipient carrying out a predefined computation involving the digital asset, the signature data elements, a plurality of noise variables and a public cryptographic key corresponding to the private cryptographic key associated with the computing apparatus.   
     
     
         16 . A computing apparatus comprising:
 a processor; and   a non-transitory memory storing computer-readable instructions;   the processor being configured for reading and executing the computer-readable instructions in the memory, thereby to cause the computing apparatus to carry out a method according to  claim 1 .   
     
     
         17 . The method defined in  claim 16 , wherein obtaining the digital asset from the digital document comprises executing a hash function on the digital document, the hash function being known to the recipient. 
     
     
         18 . The method defined in  claim 16 , further comprising transmitting an identity of the computing apparatus to the recipient over the data network. 
     
     
         19 . The method defined in  claim 16 , wherein the base data element represents an integer, wherein the plurality of signature data elements includes a first signature data element, wherein the method further comprises computing the first signature data element by (i) computing a first quantity from the digital asset and the private cryptographic key; and (ii) setting the first signature data element to equal the base data element to the power of said first quantity. 
     
     
         20 . The method defined in  claim 19 , wherein the plurality of signature data elements includes a second signature data element, wherein the method further comprises computing the second signature data element by (i) computing a second quantity from the digital asset and the private cryptographic key; and (ii) setting the second signature data element to equal the base data element to the power of said second quantity.