Patent Publication Number: US-10333710-B2

Title: Method and system for determining desired size of private randomness using Tsallis entropy

Description:
CROSS REFERENCES TO RELATED APPLICATIONS 
     This application claims the benefit of priority of U.S. Provisional Patent Application No. 62/557,193, filed on Sep. 12, 2017, which is incorporated herein by reference in its entirety. 
    
    
     BACKGROUND 
     Technological Field 
     The disclosed embodiments generally relate to cryptographic methods and systems. More particularly, the disclosed embodiments relate to methods and systems for determining a desired size of private randomness using Tsallis entropy. 
     Background Information 
     Cryptography is becoming increasingly prevalent. The usage of encrypted communication, data encryption, digital signatures, data authentication, decentralized public databases and decentralized public ledgers is increasing. 
     Tsallis entropy is a generalization of the standard Boltzmann Gibbs entropy. Tsallis entropy is used in a number of computer science applications. 
     SUMMARY 
     In some embodiments, methods and systems for generating public randomness are provided. 
     In some embodiments, private randomness may be generated; the private randomness may be encrypted; the private randomness may be deleted so that the private randomness is unrecoverable; and the encrypted private randomness may be published. In some examples, the published encrypted private randomness may be configured to enable a calculation of a public randomness based on the private randomness after the deletion of the private randomness. 
     In some embodiments, public randomness and encrypted private randomness may be obtained; and a new public randomness may be generated based on the public randomness and the encrypted private randomness. In some examples, the encrypted private randomness may be based on a private randomness, and the private randomness may be deleted so that the private randomness is unrecoverable before the generation of the new public randomness. In some examples, the new public randomness may be published. 
     In some embodiments, a measurement of a public randomness and/or a measurement of a plaintext may be obtained; based on the measurement of the public randomness and/or the measurement of the plaintext, a desired size of private randomness may be determined; and private randomness may be generated so that the size of the private randomness is at least the determined desired size. In some examples, the measurement of the public randomness may be based on the length of the public randomness, number of contributors to the public randomness, a measurement of a contribution of a contributor to the public randomness, entropy of the public randomness, Tsallis entropy of the public randomness, and so forth. In some examples, the measurement of the plaintext may be based on the length of the plaintext, entropy of the plaintext, Tsallis entropy of the plaintext, and so forth. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a block diagram illustrating a possible implementation of a communication system. 
         FIG. 2  is a block diagram illustrating a possible implementation of a computerized system. 
         FIG. 3  illustrates an example of a process for generating randomness. 
         FIG. 4  illustrates an example of a process for generating randomness. 
         FIG. 5  illustrates an exemplary embodiment of a memory containing a software module. 
     
    
    
     DESCRIPTION 
     Unless specifically stated otherwise, as apparent from the following discussions, it is appreciated that throughout the specification discussions utilizing terms such as “processing”, “calculating”, “computing”, “determining”, “generating”, “setting”, “configuring”, “selecting”, “defining”, “applying”, “obtaining”, “monitoring”, “providing”, “identifying”, “segmenting”, “classifying”, “analyzing”, “associating”, “extracting”, or the like, include action and/or processes of a computer that manipulate and/or transform data into other data, said data represented as physical quantities, for example such as electronic quantities, and/or said data representing the physical objects. The terms “computer”, “processor”, “controller”, “processing unit”, “computing unit”, and “processing module” should be expansively construed to cover any kind of electronic device, component or unit with data processing capabilities, including, by way of non-limiting example, a personal computer, a wearable computer, a tablet, a smartphone, a server, a computing system, a cloud computing platform, a communication device, a processor (for example, digital signal processor (DSP), an image signal processor (ISR), a microcontroller, a field programmable gate array (FPGA), an application specific integrated circuit (ASIC), a central processing unit (CPA), a graphics processing unit (GPU), a visual processing unit (VPU), and so on), possibly with embedded memory, a core within a processor, any other electronic computing device, or any combination of the above. 
     The operations in accordance with the teachings herein may be performed by a computer specially constructed or programmed to perform the described functions. 
     As used herein, the phrase “for example,” “such as”, “for instance” and variants thereof describe non-limiting embodiments of the presently disclosed subject matter. Reference in the specification to “one case”, “some cases”, “other cases” or variants thereof means that a particular feature, structure or characteristic described in connection with the embodiment(s) may be included in at least one embodiment of the presently disclosed subject matter. Thus the appearance of the phrase “one case”, “some cases”, “other cases” or variants thereof does not necessarily refer to the same embodiment(s). As used herein, the term “and/or” includes any and all combinations of one or more of the associated listed items. 
     As used herein, the terms “encrypt”, “encrypting” or variants thereof does not necessarily convey that the resulting encrypted data can be decrypted, but that deducing the original data from the resulting encrypted data is computationally hard under common hardness assumptions or common cryptographic hardness assumptions. 
     It is appreciated that certain features of the presently disclosed subject matter, which are, for clarity, described in the context of separate embodiments, may also be provided in combination in a single embodiment. Conversely, various features of the presently disclosed subject matter, which are, for brevity, described in the context of a single embodiment, may also be provided separately or in any suitable sub-combination. 
     In embodiments of the presently disclosed subject matter, one or more stages illustrated in the figures may be executed in a different order and/or one or more groups of stages may be executed simultaneously and vice versa. The figures illustrate a general schematic of the system architecture in accordance embodiments of the presently disclosed subject matter. Each module in the figures can be made up of any combination of software, hardware and/or firmware that performs the functions as defined and explained herein. The modules in the figures may be centralized in one location or dispersed over more than one location. 
     It should be noted that some examples of the presently disclosed subject matter are not limited in application to the details of construction and the arrangement of the components set forth in the following description or illustrated in the drawings. The invention can be capable of other embodiments or of being practiced or carried out in various ways. Also, it is to be understood that the phraseology and terminology employed herein is for the purpose of description and should not be regarded as limiting. 
     In this document, an element of a drawing that is not described within the scope of the drawing and is labeled with a numeral that has been described in a previous drawing may have the same use and description as in the previous drawings. 
     The drawings in this document may not be to any scale. Different figures may use different scales and different scales can be used even within the same drawing, for example different scales for different views of the same object or different scales for the two adjacent objects. 
       FIG. 1  is a block diagram illustrating a possible implementation of a communicating system. Two or more entities may communicate with each other. In this example, five entities  121 ,  122 ,  123 ,  124  and  125  may communicate with each other over network  110 . In some embodiments, any entity may communicate with all other entities, while in other embodiments the communication among entities is restricted to specific pairs of entities. In some embodiments, the entities may communicate directly with each other, and/or through a third party system, such as a cloud platform and/or a server connected to network  110 . In some embodiments, network  110  may include any combination of the Internet, phone networks, cellular networks, satellite communication networks, private communication networks, virtual private networks (VPN), a group of point-to-point communication lines that connect pairs of entities, email servers, instant messaging servers, file servers, package delivery service delivering digital and/or non-digital media from one entity to the other, and so forth. In some embodiments, an entity, such as entities  121 ,  122 ,  123 ,  124  and  125 , may include a computerized system  200 , for example as described in  FIG. 2 . In some embodiments, an entity, such as entities  121 ,  122 ,  123 ,  124  and  125 , may include desktop computers, laptop computers, tablets, mobile devices, server computers, applications, cloud computing platforms, virtual machines, and so forth. 
       FIG. 2  is a block diagram illustrating a possible implementation of a computerized system  200 . In this example, computerized system  200  comprises: one or more power sources  210 ; one or more memory units  220 ; one or more processing units  230 ; and one or more communication modules  240 . In some implementations, additional components may be included in computerized system  200 , while some components listed above may be excluded. In some embodiments, power sources  210  and/or communication modules  240  may be excluded from the implementation of computerized system  200 . In some embodiments, computerized system  200  may further comprise one or more of the followings: one or more audio output units; one or more visual outputting units; one or more tactile outputting units; one or more sensors; one or more clocks; one or more user input devices; one or more keyboards; one or more mouses; one or more touch pads; one or more touch screens; one or more antennas; one or more output devices; one or more audio speakers; one or more display screens; one or more augmented reality display systems; one or more LED indicators; and so forth. 
     In some embodiments, power sources  210  may be configured to power computerized system  200 . Some possible implementation examples power sources  210  may comprise: one or more electric batteries; one or more capacitors; one or more connections to external power sources; one or more power convertors; one or more electric power generators; any combination of the above; and so forth. 
     In some embodiments, processing units  230  may be configured to execute software programs, for example software programs stored in memory units  220 , software programs received through communication modules  240 , and so forth. Some possible implementation examples of processing units  230  may comprise: one or more single core processors; one or more multicore processors; one or more controllers; one or more application processors; one or more system on a chip processors; one or more central processing units; one or more graphical processing units; one or more neural processing units; any combination of the above; and so forth. In some examples, the executed software programs may store information in memory units  220 . In some cases, the executed software programs may retrieve information from memory units  220 . 
     In some embodiments, processing units  230  may support a protected execution of software, ensuring that a specific version of software is executed and/or that memory used by the software is not modified by external sources. For example, processing units  230  may allow software to create and/or use private regions of memory, protect selected code and/or data from disclosure and/or modification, detect and/or prevent tampering of code and/or data, securely encrypt selected code and/or data, and so forth. 
     In some embodiments, communication modules  240  may be configured to receive and/or transmit information. Some possible implementation examples of communication modules  240  may comprise: wired communication devices; wireless communication devices; optical communication devices; electrical communication devices; radio communication devices; sonic and/or ultrasonic communication devices; electromagnetic induction communication devices; infrared communication devices; transmitters; receivers; transmitting and receiving devices; modems; network interfaces; wireless USB communication devices, wireless LAN communication devices; Wi-Fi communication devices; LAN communication devices; USB communication devices; firewire communication devices; bluetooth communication devices; cellular communication devices, such as GSM, CDMA, GPRS, W-CDMA, EDGE, CDMA2000, etc.; satellite communication devices; and so forth. 
     In some implementations, control signals and/or synchronization signals may be transmitted and/or received through communication modules  240 . In some implementations, information received though communication modules  240  may be stored in memory units  220 . In some implementations, information retrieved from memory units  220  may be transmitted using communication modules  240 . In some implementations, input and/or user input may be transmitted and/or received using communication modules  240 . In some implementations, output information may be transmitted and/or received through communication modules  240 . 
       FIG. 3  illustrates an example of process  300  for generating randomness. In some examples, process  300 , as well as all individual steps therein, may be performed by various aspects of: processing unit  230 , computerized system  200 , and so forth. For example, process  300  may be performed by processing units  230 , executing software instructions stored within memory units  220 . Process  300  may comprise: generating private randomness (Step  310 ), encrypting the private randomness (Step  320 ), deleting the private randomness (Step  330 ), and publishing the encrypted private randomness (Step  340 ). In some implementations, process  300  may comprise one or more additional steps, while some of the steps listed above may be modified or excluded. In some implementations, one or more steps illustrated in  FIG. 3  may be executed in a different order and/or one or more groups of steps may be executed simultaneously and vice versa. For example, Step  330  may be executed before, after and/or simultaneously with Step  340 , and so forth. Examples of possible execution manners of process  300  may include: continuous execution, returning to the beginning of the process once the process normal execution ends; periodically execution, executing the process at selected times; execution upon the detection of a trigger, where examples of such trigger may include a trigger from a user, a trigger from another process, etc.; any combination of the above; and so forth. 
     In some embodiments, generating private randomness (Step  310 ) may comprise generating one or more random values (such as bits, numbers, etc.). In some examples, generating private randomness (Step  310 ) may comprise using at least one of the followings to generate the private randomness: random number generator, pseudorandom number generator, cryptographically secure pseudorandom number generator, true random number generator (a.k.a. hardware random number generator), and so forth. In some embodiments, the size of the private randomness (for example, the number of bits, numbers, and/or values in the private randomness the entropy of the private randomness, etc.) may be predetermined, selected, calculated, and so forth. For example, a desired size of the private randomness may be determined using Module  510  (described below), and Step  310  may generate a private randomness so that the size of the generated private randomness is at least the determined desired size. For example, a random number generator may be activated repeatedly and the resulting random values may be aggregated until the size of the aggregated random values is sufficient. 
     In some embodiments, encrypting the private randomness (Step  320 ) may comprise encrypting the private randomness generated using Step  310 . In some examples, encrypting the private randomness (Step  320 ) may comprise encrypting the private randomness using a cryptographic encryption algorithm, a cryptographic hash function, an irreversible encoder, and so forth. In some examples, encrypting the private randomness (Step  320 ) may comprise encoding a private randomness τ of a ring F as xyP, where x is a vector of powers of τ, y is a random element of ring F, and P is an elliptic curve group generators, for example as described below. 
     In some embodiments, deleting the private randomness (Step  330 ) may comprise deleting the private randomness generated using Step  310 . In some examples, deleting the private randomness (Step  330 ) may comprise deleting the private randomness so that the private randomness is unrecoverable. In some examples, deleting the private randomness (Step  330 ) may comprise deleting all copies of the private randomness. In some examples, deleting a copy of the private randomness from memory may comprise writing a value over the copy of the private randomness in the memory. In some examples, deleting a copy of the private randomness from memory may comprise repeatedly writing different values over the place in memory where the private randomness was stored. For examples, this may involve one repetition, two repetitions, three repetitions, four repetitions, five or more repetitions, ten or more repetitions, one hundred repetitions or more, one thousand repetitions or more, and so forth. 
     In some embodiments, publishing the encrypted private randomness (Step  340 ) may comprise publishing the encrypted private randomness produced by Step  320 . In some examples, publishing the encrypted private randomness (Step  340 ) may comprise providing the encrypted private randomness to process  400  (described below) and/or to Step  410  (described below) and/or to Step  430  (described below). In some examples, publishing the encrypted private randomness (Step  340 ) may comprise writing the encrypted private randomness to memory, for example to memory units  220 . In some examples, publishing the encrypted private randomness (Step  340 ) may comprise communicating the encrypted private randomness to at least one external entity. In some examples, publishing the encrypted private randomness (Step  340 ) may comprise transmitting the encrypted private randomness to an external entity, for example using communication modules  240 . In some examples, publishing the encrypted private randomness (Step  340 ) may comprise storing the encrypted private randomness in a public repository, such as a public file system, a web server, a blockchain, and so forth. 
     In some embodiments, publishing the encrypted private randomness (Step  340 ) may comprise committing the encrypted private randomness produced by Step  320 . In some examples, a commitment scheme may be used to commit the encrypted private randomness. For example, a hash based commitment scheme (such as BLAKE-2, SHA-256) may be used to commit the encrypted private randomness. For example, algebraic commitment scheme (such as Pedersen commitment scheme) may be used to commit the encrypted private randomness. In some examples, the encrypted private randomness may be committed by adding a commitment record of the encrypted private randomness to a blockchain. In some examples, the encrypted private randomness may be committed by providing the encrypted private randomness and/or a commitment record of the encrypted private randomness to a trusted third party. 
     In some embodiments, an external device may be configured to calculate a public randomness based, at least in part, on the published encrypted private randomness, for example using Step  430  (described below) and/or process  400  (described below), for example after the deletion of the private randomness using Step  330 . In some embodiments, process  300  may further obtain a public randomness, for example using Step  420  (described below), and generate a new public randomness based, at least in part, on the published encrypted private randomness, for example using Step  430  (described below) and/or process  400  (described below), for example after the deletion of the private randomness using Step  330 . In some examples, process  300  may further continue to publish the new public randomness, for example using Step  440  (described below). 
       FIG. 4  illustrates an example of process  400  for generating randomness. In some examples, process  400 , as well as all individual steps therein, may be performed by various aspects of: processing unit  230 , computerized system  200 , and so forth. For example, process  400  may be performed by processing units  230 , executing software instructions stored within memory units  220 . In some examples, process  400 , as well as all individual steps therein, may be performed using a multiparty computation (a.k.a. secure multiparty computation), executed by a plurality of entities. Process  400  may comprise: receiving encrypted private randomness (Step  410 ), obtaining public randomness (Step  420 ), and generating new public randomness (Step  430 ). In some implementations, process  400  may comprise one or more additional steps, while some of the steps listed above may be modified or excluded. For example, Step  410  and/or Step  420  may be excluded from process  400 . For example, process  400  may further comprise publishing the new public randomness (Step  440 ). In some implementations, one or more steps illustrated in  FIG. 4  may be executed in a different order and/or one or more groups of steps may be executed simultaneously and vice versa. For example, Step  410  may be executed before, after and/or simultaneously with Step  420 , and so forth. Examples of possible execution manners of process  400  may include: continuous execution, returning to the beginning of the process once the process normal execution ends; periodically execution, executing the process at selected times; execution upon the detection of a trigger, where examples of such trigger may include a trigger from a user, a trigger from another process, etc.; any combination of the above; and so forth. 
     In some embodiments, receiving encrypted private randomness (Step  410 ) may comprise receiving encrypted private randomness from one or more sources. In some examples, receiving encrypted private randomness (Step  410 ) may comprise obtaining encrypted private randomness produced by one or more instances process  300 , obtaining encrypted private randomness produced by one or more executions of Step  320 , obtaining encrypted private randomness published by one or more instances of process  300 , obtaining encrypted private randomness published by one or more executions of Step  340 , and so forth. In some examples, receiving encrypted private randomness (Step  410 ) may comprise reading the encrypted private randomness from memory, for example from memory units  220 . In some examples, receiving encrypted private randomness (Step  410 ) may comprise communicating with at least one external entity to obtain the encrypted private randomness. In some examples, receiving encrypted private randomness (Step  410 ) may comprise receiving the encrypted private randomness from one or more external entities, for example using communication modules  240 . In some examples, receiving encrypted private randomness (Step  410 ) may comprise accessing encrypted private randomness in a public repository, reading encrypted private randomness from a public file system, accessing encrypted private randomness on a web server, accessing encrypted private randomness encoded in a blockchain, and so forth. 
     In some embodiments, obtaining public randomness (Step  420 ) may comprise receiving public randomness from one or more sources. In some examples, obtaining public randomness (Step  420 ) may comprise obtaining public randomness generated by previous execution of process  400 , by previous execution of Step  430 , and so forth. In some examples, obtaining public randomness (Step  420 ) may comprise reading public randomness from memory, for example from memory units  220 . In some examples, obtaining public randomness (Step  420 ) may comprise communicating with at least one external entity to obtain the public randomness. In some examples, obtaining public randomness (Step  420 ) may comprise receiving the public randomness from one or more external entities, for example using communication modules  240 . In some examples, obtaining public randomness (Step  420 ) may comprise accessing public randomness in a public repository, reading public randomness from a public file system, accessing public randomness on a web server, accessing public randomness encoded in a blockchain, and so forth. 
     In some embodiments, generating new public randomness (Step  430 ) may comprise generating new public randomness based, at least in part, on previous public randomness and/or on encrypted private randomness. In some examples, generating new public randomness (Step  430 ) may comprise generating new public randomness based, at least in part, on encrypted private randomness, for example, based, at least in part, on encrypted private randomness obtained using Step  410 , on encrypted private randomness generated using process  300 , on encrypted private randomness generated using Step  320 , and so forth. In some examples, generating new public randomness (Step  430 ) may comprise generating new public randomness based, at least in part, on previous public randomness obtained using Step  420 , on previous public randomness generated by previous execution of Step  430 , and so forth. Some specific examples of methods for the generation of public randomness based on previous public randomness and/or on encrypted private randomness are detailed below. 
     In some embodiments, publishing the new public randomness (Step  440 ) may comprise publishing public randomness, for example publishing public randomness generated by Step  430  and/or by process  400 . In some examples, publishing the new public randomness (Step  440 ) may comprise providing the public randomness to future instances of process  400  and/or to future instances of Step  420  and/or to future instances of Step  430 . In some examples, publishing the new public randomness (Step  440 ) may comprise writing the public randomness to memory, for example to memory units  220 . In some examples, publishing the new public randomness (Step  440 ) may comprise communicating the public randomness to at least one external entity. In some examples, publishing the new public randomness (Step  440 ) may comprise transmitting the public randomness to an external entity, for example using communication modules  240 . In some examples, publishing the new public randomness (Step  440 ) may comprise storing the public randomness in a public repository, such as a public file system, a web server, a blockchain, and so forth. 
     The Tsallis entropy of n non-negative values that sum to one, denoted p 1 , . . . , p n , is defined as, S q (p 1 , . . . , p n )=(q−1) −1 (1−p 1 − . . . −p n   q ). The parameter q of the Tsallis entropy is called entropic index. In some embodiments, the Tsallis entropy of values in a stream of values may be calculated, for example using one or more entropic indexes. Any valid entropic index may be used, such as: 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, and so forth. 
       FIG. 5  illustrates an exemplary embodiment of a memory containing a software module. Included in memory unit  220  is module  510  for determining desired size of private randomness. Module  510  may contain software instructions for execution by at least one processing device, such as processing unit  230 , by computerized system  200 , and so forth. Module  510  may cooperate with steps of process  300  and/or process  400 . 
     In some embodiments, module  510  for determining desired size of private randomness may comprise determining desired size of private randomness based, at least in part, on a measurement of a public randomness. In some examples, the measurement of the public randomness may be obtained, for example by accessing the public randomness and measuring the public randomness, by accessing records associated with the public randomness, by receiving the measurement of the public randomness from an external source, by reading the measurement of the public randomness from memory, and so forth. For example, the measurement of the public randomness may be the length of the public randomness (for example measured in bits, in bytes, and so forth). For example, the measurement of the public randomness may be the entropy of the public randomness. For example, the measurement of the public randomness may be a Tsallis entropy of the public randomness, a Tsallis entropy of the public randomness with entrophic index smaller than ¼ (one quarter), a Tsallis entropy of the public randomness with entrophic index smaller than ½ (one half), a Tsallis entropy of the public randomness with entrophic index larger than ½ (one half), a Tsallis entropy of the public randomness with entrophic index larger than ¾ (three quarters), and so forth. For example, the measurement of the public randomness may be a function of a plurality of Tsallis entropy values of the public randomness, each of the plurality of Tsallis entropy values may be calculated with a different entrophic index. For example, the measurement of the public randomness may be defined as a function of the number of contributors to the public randomness, the size of contribution of one or more contributors to the public randomness, the length of the public randomness, the entropy of the public randomness, one or more Tsallis entropy values of the public randomness, and so forth. 
     In some embodiments, module  510  for determining desired size of private randomness may comprise determining desired size of private randomness based, at least in part, on a measurement of a plaintext. In some examples, the measurement of the plaintext may be obtained, for example by accessing the plaintext and measuring the plaintext, by receiving the measurement of the plaintext from an external source, by reading the measurement of the plaintext from memory, and so forth. For example, the measurement of the plaintext may be the length of the plaintext (for example measured in bits, in bytes, and so forth). For example, the measurement of the plaintext may be the entropy of the plaintext. For example, the measurement of the plaintext may be a Tsallis entropy of the plaintext, a Tsallis entropy of the plaintext with entrophic index smaller than ¼ (one quarter), a Tsallis entropy of the plaintext with entrophic index smaller than ½ (one half), a Tsallis entropy of the plaintext with entrophic index larger than ½ (one half), a Tsallis entropy of the plaintext with entrophic index larger than ¾ (three quarters), and so forth. For example, the measurement of the plaintext may be a function of a plurality of Tsallis entropy values of the plaintext, each of the plurality of Tsallis entropy values may be calculated with a different entrophic index. 
     In some embodiments, module  510  for determining desired size of private randomness may comprise accessing a table and/or a graph according to the measurement of the public randomness and/or the measurement of the plaintext to determine the desired size of private randomness. In some examples, module  510  for determining desired size of private randomness may comprise evaluating a function using the measurement of the public randomness and/or the measurement of the plaintext as parameters to determine the desired size of private randomness. In some examples, module  510  for determining desired size of private randomness may comprise executing a computer function using the measurement of the public randomness and/or the measurement of the plaintext as parameters to determine the desired size of private randomness. 
     In some examples, process  300  and module  510  may be performed by the same entity. For example, entity  121  may execute module  510  to determine the desired size of private randomness, and continue to execute process  300  to produce the private randomness and/or an encrypted private randomness. In some examples, process  300  and module  510  may be performed by different entities. For example, entity  121  may execute module  510  to determine the desired size of private randomness, provide the determined desired size of private randomness to entity  122 , and entity  122  may execute process  300  to produce the private randomness and/or an encrypted private randomness. 
     In some examples, process  300  and process  400  may be performed by the same entity. For example, entity  121  may execute process  300  to produce an encrypted private randomness. Furthermore, entity  121  may execute process  400  to produce a new public randomness using a previous public randomness and the encrypted private randomness produced by process  300 . Afterwards, entity  121  may publish the new public randomness, for example using Step  440 , which may provide the new public randomness to entity  122 , entity  123 , entity  124 , and/or entity  125 . 
     In some examples, process  300  and process  400  may be performed by different entities. For example, entity  121  may execute process  300  to produce an encrypted private randomness. Entity  122  may execute process  400  to produce a new public randomness using a previous public randomness and the encrypted private randomness produced by entity  121  using process  300 . Afterwards, entity  122  may publish the new public randomness, for example using Step  440 , which may provide the new public randomness back to entity  121  and/or provide the new public randomness to entity  123 , entity  124 , and/or entity  125 . 
     In some examples, process  400  may be performed using a multiparty computation (a.k.a. secure multiparty computation), executed by a plurality of entities. In some examples, the plurality of entities may include an entity performing process  300 , while in other examples the plurality of entities may not include an entity performing process  300 . 
     Following, some more possible implementation details are provided. These implementation details are exemplary and explanatory only and are not restrictive. 
     In some embodiments, randomness may be generated and encoded into some elliptic curve group generators. In some examples, randomness from different sources may be combined, for example using a multiparty computation. Furthermore, the randomness may be destroyed. 
     In some embodiments, a multiparty computation based protocol may output a public randomness, for example in the form of a collection of encoded randomness with a structure, xyP, where x∈F r   d+1  is a d+1 dimensional vector of powers of a random element, τ∈F r , y∈F r  is a random element, and P∈G 1  is an elliptic curve group generators. The i-th player may generates private randomness, random which is shared in the form of an encoding, encode i , for example after committing to it, h i =COMM (encode i ). In some examples, non-interactive zero-knowledge proof may be used to ensure that a player knows the private randomness and/or the random exponents the player committed. In some examples, the protocol may comprise a two-party computation, a first party that may extend a public randomness and/or collection of encoded randomness using a private randomness, and a second party that may provide the collection of encoded randomness and/or may verify that the first party executed the algorithm correctly. In some examples, when no previous public randomness and/or collection of encoded randomness is available, an initial public randomness and/or collection of encoded randomness may be selected randomly, produced based on a private randomness, set to a selected constant value, and so forth. 
     In some embodiments, the system may verify that the exponents of an elliptic curve group elements are the same in each step of a multiparty computation and in each group. In some examples, the system may verify that all the steps were done appropriately by the parties. For example, the system may verify that all players used the same random exponents with each instance of the exponent. For example, using a pairing friendly elliptic curve, E and its twist curve, {tilde over (E)}, specified by a prime r and over a base field F r ; defining three cyclic groups of order r, G 1 , G 2  and G T , and the bilinear pairing f:G 1 ×G 2 →G T , such that G 1  is a subgroup of order r of the group derived from E, G 2  is a subgroup of order r of the group derived from the twist curve, {tilde over (E)} and G T  is the subgroup of r-th roots of unity in some extension field of F r ; fixing two generators, P 1 ∈G 1  and P 2 ∈G 2  the system may verify that two encodings, m∈G 1   2  and w∈G 2   2  use the same random exponent by verifying that f(m 1 ,w 2 )=f(m 2 ,w 1 ). This verification process may be extended to σ-vectors, where V is a σ-vector if for some g∈G, V is of the form V=(g, σg, σ 2 g, . . . , σ d g) for some d∈N. We can rewrite the V to denote the σ-multiples, V′=((g,σg), (σg,σ 2 g), . . . , (σ d−1 g,σ d g)). 
     In some embodiments, given an upper bound on the number of constraints, a sufficient public randomness and/or collection of encoded randomness may be generated. For example, given a maximum number of multiplication gates in the circuit, and given two elliptic curve group generators, P 1 ∈G 1  and P 2 ∈G 2 , the system may generate some random elements random={τ,ρ A ,ρ B ,α A ,α B ,α C ,β,γ} which are combined as exponents, for example using exps P     1   ={ρ A ,α B ,α A ρ A ,α B ρ B ,ρ A ρ B ,α C ρ A ρ B ,βρ A ,βρ B ,βρ A ρ B ,γβ} and exps P     2   ={ρ B ,α C ,γ,α A ,ρ A ρ B ,γβ}, outputting a public randomness and/or collection of encoded randomness (Ξ 1 ,Ξ 2 )∈G 1   (d+1)×9+2 ×G 2   (d+1)×2+4  yielding the following elements for Ξ 1 : 
                 Ξ   1     =         (     1   ,   τ   ,   …   ⁢           ,     τ   d       )     ⁢     P   1       ∈     G   1     d   +   1           ,     
     ⁢       Ξ     1   ,     ρ   A         =         (     1   ,   τ   ,   …   ⁢           ,     τ   d       )     ⁢     ρ   A     ⁢     P   1       ∈     G   1     d   +   1           ,     
     ⁢       Ξ     1   ,       α   A     ⁢     ρ   A           =         (     1   ,   τ   ,   …   ⁢           ,     τ   d       )     ⁢     α   A     ⁢     ρ   A     ⁢     P   1       ∈     G   1     d   +   1           ,     
     ⁢       Ξ     1   ,       α   B     ⁢     ρ   B           =         (     1   ,   τ   ,   …   ⁢           ,     τ   d       )     ⁢     α   B     ⁢     ρ   B     ⁢     P   1       ∈     G   1     d   +   1           ,     
     ⁢       Ξ     1   ,       ρ   A     ⁢     ρ   B           =         (     1   ,   τ   ,   …   ⁢           ,     τ   d       )     ⁢     ρ   A     ⁢     ρ   B     ⁢     P   1       ∈     G   1     d   +   1           ,     
     ⁢       Ξ     1   ,       α   C     ⁢     ρ   A     ⁢     ρ   B           =         (     1   ,   τ   ,   …   ⁢           ,     τ   d       )     ⁢     α   C     ⁢     ρ   A     ⁢     ρ   B     ⁢     P   1       ∈     G   1     d   +   1           ,     
     ⁢       Ξ     1   ,     βρ   A         =         (     1   ,   τ   ,   …   ⁢           ,     τ   d       )     ⁢     βρ   A     ⁢     P   1       ∈     G   1     d   +   1           ,     
     ⁢       Ξ     1   ,     βρ   B         =         (     1   ,   τ   ,   …   ⁢           ,     τ   d       )     ⁢     βρ   B     ⁢     P   1       ∈     G   1     d   +   1           ,     
     ⁢       Ξ     1   ,       βρ   A     ⁢     ρ   B           =         (     1   ,   τ   ,   …   ⁢           ,     τ   d       )     ⁢     βρ   A     ⁢     ρ   B     ⁢     P   1       ∈     G   1     d   +   1           ,     
     ⁢       𝒳     1   ,     α   B         =         α   B     ⁢     P   1       ∈     G   1         ,       𝒳     1   ,   γβ       =       γβ   ⁢           ⁢     P   1       ∈     G   1         ,         
and the following elements for Ξ 2 :
 
                 Ξ     2   ,     ρ   B         =         (     1   ,   τ   ,   …   ⁢           ,     τ   d       )     ⁢     ρ   B     ⁢     P   1       ∈     G   1     d   +   1           ,     
     ⁢       Ξ     2   ,       ρ   A     ⁢     ρ   B           =         (     1   ,   τ   ,   …   ⁢           ,     τ   d       )     ⁢     ρ   A     ⁢     ρ   B     ⁢     P   2       ∈     G   1     d   +   1           ,       𝒳     2   ,   βγ       =       γβ   ⁢           ⁢     P   2       ∈     G   2         ,     
     ⁢       𝒳     2   ,     α   C         =         α   C     ⁢     P   2       ∈     G   2         ,       𝒳     2   ,     α   B         =         α   A     ⁢     P   2       ∈     G   2         ,       𝒳     2   ,   γ       =       γ   ⁢           ⁢     P   2       ∈       G   2     .               
Note that for σ∈exps P     k   , where k∈{1,2}, we write Ξ k,σ =(1, τ, . . . , τ d )σP k  and we write χ k,σ =σP k . The main difference being the vector of powers of τ.
 
     In some embodiments, for an arithmetic circuit, C:F r   n ×F r   h ← r   l , a set of polynomials with degree u and size m representing the gate structure of the circuit may be computed. 
     In some embodiments, quadratic arithmetic program polynomials may be generated from selected constraints, and fast Fourier transform may be performed on randomness and/or on an encoded randomness to generate proving keys and/or verification keys. For example, for some elliptic curve E, with generators, P 1 ∈G 1 , of the elliptic curve group and P 2 ∈G 2  of the group derived from its twisted curve, {tilde over (E)}, for a set of polynomials with degree u and size m representing the gate structure of an arithmetic circuit, C:F r   n ×F r   h ←F r   l , with degree d and size m, and for the random elements R:={τ,α A ,α B ,α C ,ρ A ,ρ B ,β,γ}∈F r , the system may output a proving key pk, where for j=0, . . . , m+3, pk A,j =A j (τ)ρ A P 1 , pk′ A,j =A j (τ)α A ρ A P 1 , pk B,j =B j (τ)ρ B P 2 , pk′ B,j =B j (τ)α B ρ B P 1 , pk C,j =C j (τ)ρ A ρ B P 1 , pk′ C,j =C j (τ)α C ρ A ρ B P 1 , pk K,j =β(A j (τ)ρ A +B j (τ)ρ B +C j (T)ρ A ρ B )P 1 , and for j=0, 1, . . . , d, pk H,j =τ j P 1 , and a verification key vk, where vk A =α A P 2 , vk B =α B P 1 , vk C =α C P 2 , vk γ =γP 2 , vk βγ   1 =γβP 1 , vk βγ   2 =γβP 2  vk Z =Z(τ)ρ A ρ B P 2 , (vk IC,j ) j=0   n =(A j (τ)ρ A P 1 ) j=0   n . In some examples, a fast fourier transform may be used to evaluate the quadratic arithmetic program polynomials at a random point, and to generate a proving key and a verification key. For example, for an element of the collection of encoded randomness and for a polynomial Y(x) the system may calculate (Y(x),Ξ k,σ )=Y(τ)σP k . For example, given a size m of a quadratic arithmetic program polynomial, the system may calculate 
     
       
         
           
             
               ( 
               
                 Ξ 
                 
                   1 
                   , 
                   
                     ρ 
                     A 
                   
                 
               
               ) 
             
             = 
             
               
                 
                   { 
                   
                     p 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       k 
                       
                         A 
                         , 
                         j 
                       
                     
                   
                   } 
                 
                 
                   j 
                   = 
                   0 
                 
                 
                   m 
                   + 
                   3 
                 
               
               . 
             
           
         
       
     
     In some embodiments, a coordinator may interact with one or more players, for example in  FIG. 1  a coordinator  121  may interact with players  122 ,  123 ,  124 , and  125 . In some examples, the interaction may comprise three rounds, where at the end of each round the coordinator (and/or any other player) may verify the computations performed by the players before continuing onto the next computation. Given a fixed integer d, which represents the maximum number of multiplication gates in the circuit to be used in a quadratic arithmetic program, and given two elliptic curve group generators as defined above, P 1 ∈G 1  and P 2 ∈G 2  the first of the three rounds may comprise random shares steps, the second round may comprise checking and combining steps, and a third round may comprise computing the powers of the randomness. 
     In some examples, the first of the three rounds may comprise random shares steps. For example, in the first round a player may generate a private randomness, for example using random i   
               :=       {       τ   i     ,     ρ     A   ,   i       ,     ρ     B   ,   i       ,     α     A   ,   i       ,     α     B   ,   i       ,     α     C   ,   i       ,     β   i     ,     γ   i       }     ⁢     ⟵   R     ⁢     F   r   *         ;         
may compute exps i :={τ,ρ A ,ρ B ,ρ A ρ B ,α A ,α B ,α C ,α A ρ A ,α B ρ B ,α C ρ A ρ B ,β,γ,βγ}, where we have removed the player index i from the elements for clarity and where we have exps i =exps P     1     ,i ∪exps P     2     ,i , without repeated elements; may compute encode i :=(τ,ρ A ,ρ B ,ρ A ρ B ,α A ,α B ,α C ,α A ρ A ,α B ρ B ,α C ρ A ρ B ,β,γ,βγ)·P, which encodes the secret exponents, exps i , in the exponent of the elliptic curve generators, where we write P=(P 1 ,P 2 ); and may commit the to the encodings h i =COMM (encode i ) and publish h i .
 
     In some examples, in the second round a player may publish encode i , and the coordinator (and/or any other player) may verify the commitments made by the players, h i , using the published encode i , for example by checking that the same ρ A  was used in ρ A P 1  and ρ A P 2 , for example as described above, for example by computing a bilinear pairing, f:G 1 ×G 2 →G T , on the elliptic curve points of encode P     1    and encode P     2    that have a random element in the exponent in common. In some examples, for all σ i ∈exps i , the coordinator may verify that e σ     i    is not zero. In case the verification fails, the coordinator may inform the player, inform other players, reject the player, and so forth. In some examples, in the second round a player may prove that the player knows the exponents of the encodings. For example, the player may compute a hash of the public outputs of the first round, h=COMM(h 1 ∘ . . . ∘h n ), and publish it. Furthermore, for each σ i ∈random i , the player may compute h σ     i   =h∘e σ     i     1 , and may compute a proof π σ     i   =NIZK(e σ     i     1 ,h σ     i   ):=(R,u)=(a·P 1 ,a+c·σ i ), where a←F r * and c:=COMM(R∘h σ     i   ) may be interpreted as an element of F r , for example by taking it&#39;s first log r bits. Furthermore, the player may publish (π σ     i   ,e σ     i     1 ,h σ     i   ). At this point, the coordinator (and/or any other player) may verify, for each player and e σ     i   ∈encode i , (π σ     i   ,e σ     i     1 , h σ     i   ), for example using a non-interactive zero-knowledge proof. For example, the coordinator (and/or any other player) may compute c:=COMM(R∘h σ     i   ), and may accept the encoding if u·P 1 =R+c·σ i P 1  for all inputs. By having a different h σ     i    for each non-interactive zero-knowledge proof, a player may verify that a valid string was used with each proof (since they are publicly verifiable) and ensure that each is unique. Finally, a multiparty computation for multiparty multiplication may be performed by the players, as described below. 
     In some examples, a multiparty computation for multiparty multiplication may be performed to compute the multiplication of the player&#39;s private randomness in a distributed and private manner. Given the random shares σ 1 , . . . , σ N ∈F r , corresponding to N players, the multiparty multiplication may compute the elliptic curve group element σQ∈G k , where k∈{1,2}, σ=Π i=1   N σ i  and Q∈G l  is some element of the elliptic curve group. In some examples, a first player may compute ξ σ     1   =σ 1 ·Q and publish ξ σ     1   ; in numerical order 2≤i≤N the i-th player may compute ξ σ     i   =σ i ·ξ σ     i-1    and publish it; and the last player may publish ξ σ     N   =ξ σ =σQ. Next, a coordinator (and/or any other player) may verify the exponents of (Q,ξ σ     1   ) and e σ     1    are the same; may, for i=2, . . . , N, verify that the exponents of (ξ σi-1 ,ξ σ     i   ) and e σ     i    are the same; and may reject the published data if any of the above verifications fails. The above multiparty multiplication may be extended to vectors. 
     In some examples, in the third round the current public randomness and/or encoded randomness may be published, for example {tilde over (Ξ)} 1  and {tilde over (Ξ)} 2  may be published. In some examples, for every element in {tilde over (Ξ)} 1  and {tilde over (Ξ)} 2  the first player may, for I=0; 1; : : : ; d, compute τ 1   l ·τ′ l σP k , yielding Ξ 1,k,σ =(1, t 1 t′, . . . , τ 1   d τ′ d )σσ′P k , and publish Ξ 1,k,σ . In some examples, for every element in {tilde over (Ξ)} 1  and {tilde over (Ξ)} 2  players i=2, . . . , N may compute T i   l  . . . t 1   l ·τ′ l σP k , yielding Ξ i,k,σ =(1, τ i  . . . τ 1 τ′, . . . , τ i   d  . . . τ 1 τ′ d )σσ′P k  and publish Ξ i,k,σ . In some examples, the last player may publish the final public randomness and/or collection of encoded randomness Ξ k,σ =Ξ N,k,σ =(1, ττ′, . . . , τ d τ′ d )σσ′P k =(1, {circumflex over (τ)}, . . . , {circumflex over (τ)} d ){circumflex over (σ)}P k . In some examples, the coordinator (and/or any other player) may verify that the powers of τ were correctly computed, for example by verifying that no player created any inconsistencies in the above steps. For example, the coordinator (and/or any other player) may verify that every player used the correct previous encoded randomness and updated it using the same τ i  in both groups. In some examples, if any of the verification fails, the coordinator may inform the player, inform other players, reject the player, and so forth. In some examples, a player may prove that the player knows the exponents of the encodings. In some examples, one or more of the players may delete their private randomness, for example using Step  330 . 
     In some embodiments, keys may be generated based on the final public randomness and/or collection of encoded randomness. In some examples, quadratic arithmetic program polynomial may be evaluated at a some points, for example at a new random point τ, for example by performing a fast fourier transform on the collection of encoded randomness. The quadratic arithmetic program polynomial may be a representation of some constraints, for example of constraints specified by an arithmetic circuit. This evaluation of the quadratic arithmetic program polynomial may be performed by any entity, including the coordinator and/or players of previous steps. For example, keys may be generated by verifying that a new random point τ is not a zero of Z(x):=X u −1, and evaluating the quadratic arithmetic program polynomial at τ. 
     In some examples, given an arithmetic circuit C:F n ×F h →F l , with a wires and b gates, a quadratic arithmetic program polynomial with degree u and size m may be computed. In case the degree u is greater than the maximal degree assumed in the generation of the public randomness and/or collection of encoded randomness, for example when the maximum number of multiplication gates in the circuit to be used in a quadratic arithmetic program is greater than the maximal number of multiplication gates assumed, a feedback indicating that may be provided, a new process for generating a new public randomness and/or collection of encoded randomness based on an assumption of a larger number of multiplication gates may be launched, the current keys generation process may be abandoned, and so forth. 
     In some examples, given a new random point τ the system may verify that τ is not a zero of Z(x):=X u −1, or in other words, that Z(τ)=τ u −1≠0. For example, by taking the 0 th  and u th  coordinate of Ξ 1  and substracting them, τ u ·P 1 −P 1 =(τ u −1)P 1 . 
     In some examples, given a quadratic arithmetic program polynomial and the public randomness and/or collection of encoded randomness, the quadratic arithmetic program polynomial may be evaluated at a Lagrange basis representation, for example by evaluating elements of the form (1, τ, . . . , τ d )σP for many random σ∈F r . In some examples, this may be performed by a single entity, by a plurality of entities, and so forth. In some examples, the proving and verification keys may be generated by computing KAP(Y(x),Ξ k,σ )=Y(τ)σP k  for a polynomial Y(x) and an element of the public randomness and/or collection of encoded randomness. For example, for j=0, . . . , m+3 the system may compute 
               p   ⁢           ⁢     k     A   ,   j         =       KAP   ⁡     (         A   j     ⁡     (   x   )       ,     Ξ     1   ,     ρ   A           )       =         A   j     ⁡     (   τ   )       ⁢     ρ   A     ⁢     P   1     ⁢           ⁢   and                       p   ⁢           ⁢     k     A   ,   j     ′       =       KAP   ⁡     (         A   j     ⁡     (   x   )       ,     Ξ     1   ,       α   A     ⁢     ρ   A             )       =         A   j     ⁡     (   τ   )       ⁢     α   A     ⁢     ρ   A     ⁢     P   1           ;                 p   ⁢           ⁢     k     B   ,   j         =       KAP   ⁡     (         B   j     ⁡     (   x   )       ,     Ξ     2   ,     ρ   B           )       =         A   j     ⁡     (   τ   )       ⁢     ρ   B     ⁢     P   2     ⁢           ⁢   and                       p   ⁢           ⁢     k     B   ,   j     ′       =       KAP   ⁡     (         B   j     ⁡     (   x   )       ,     Ξ     1   ,       α   B     ⁢     ρ   B             )       =         B   j     ⁡     (   τ   )       ⁢     α   B     ⁢     ρ   B     ⁢     P   1           ;                 p   ⁢           ⁢     k     C   ,   j         =       KAP   ⁡     (         C   j     ⁡     (   x   )       ,     Ξ     1   ,       ρ   A     ⁢     ρ   B             )       =         C   j     ⁡     (   τ   )       ⁢     ρ   A     ⁢     ρ   B     ⁢     P   1     ⁢           ⁢   and                       p   ⁢           ⁢     k     C   ,   j     ′       =       KAP   ⁡     (         C   j     ⁡     (   x   )       ,     Ξ     1   ,       α   C     ⁢     ρ   A     ⁢     ρ   B             )       =         C   j     ⁡     (   τ   )       ⁢     α   C     ⁢     ρ   A     ⁢     ρ   B     ⁢     P   1           ;                   p   ⁢           ⁢     k     K   ,   j         =       KAP   ⁡     (         A   j     ⁡     (   x   )       ,     Ξ     1   ,     βρ   A           )       +     KAP   ⁡     (         B   j     ⁡     (   x   )       ,     
     ⁢     Ξ     1   ,     βρ   B           )       +     KAP   ⁡     (         C   j     ⁡     (   x   )       ,     Ξ     1   ,       βρ   A     ⁢     ρ   B             )           ,         
which yields pk K,j =β(A j (τ)ρ A +B j (τ)ρ B +C j (τ)ρ A ρ B )P 1 . Furthermore, the system may compute vk Z =KAP(Z(x),Ξ 2,ρ     A     ρ     B   )=Z(x)ρ A ρ B P 2 , and derive vk IC,j =A j (τ)ρ A P 1  from pk A,j  for j=0, . . . , n. The system may also use, vk A =χ 2,α     A   =α A P 2 , vk B =χ 1,α     B   =α B P 1 , vk C =χ 2,α     C   =α C P 2  and vk γ =χ 2,γ =γP 2 , vk βγ   1 =χ 1,γβ =γβP 1 , vk βγ   2 =χ 2,βγ =γβP 2 .
 
     It will also be understood that the system according to the invention may be a suitably programmed computer, the computer including at least a processing unit and a memory unit. For example, the computer program can be loaded onto the memory unit and can be executed by the processing unit. Likewise, the invention contemplates a computer program being readable by a computer for executing the method of the invention. The invention further contemplates a machine-readable memory tangibly embodying a program of instructions executable by the machine for executing the method of the invention.