US 12,580,751 B2Grant
Fast post-quantum cryptographic sortition
Issue Date:2026-03-17
•20 Claims
•3 Drawing Sheets
Abstract
A method for cryptographic sortition among a group of parties includes committing, by a first party, to a set of n party-specific secret keys k1, kn for a block cipher E and obtaining, by the first and a second party, a common input x and an index r. The method further includes encrypting, by the first party, the input x with the r-th key kr of the committed keys k1, . . . , kn, thereby generating an output y1 of the block-cipher E, and publishing the output y1 with the key kr used for encryption. The method further includes encrypting, by the second party, the common input x with the published key kr, thereby generating an output y1′ of the block-cipher E, and comparing the generated output y1′ with the published output y1. The method can be used to optimize the cryptographic sortition and support secure decision making.
Metadata
Assignee
- NEC CORPORATION
Inventors
- Claudio Soriente
- Dario Fiore
Application Information
Application Number:US 18/291,257
Filing Date:2021-08-20
Priority Date:2021-08-13
Art Unit:2435
Classifications
IPC:
H04L9/08
Field of Search:
H04L 9/0852H04L 9/50H04L 9/3239
Patent Drawings (3 sheets)
Description
Cross Reference to Related Applications
[0001] This application is a U.S. National Phase application under 35 U.S.C. § 371 of International Application No. PCT/EP2021/073178, filed on Aug. 20, 2021, and claims benefit to European Patent Application No. EP 21191370.2, filed on Aug. 13, 2021. The International Application was published in English on Feb. 16, 2023 as WO 2023/016665 A1 under PCT Article 21 (2).
Field
[0002] The present invention relates to the field of cryptology. More specifically, the present invention relates to a computer-implemented method for execution of a cryptographic sortition among a group of parties.
Background
[0003] A Verifiable Random Function (VRF) is essentially a keyed function that, on arbitrary inputs, outputs values that look pseudorandom to third parties that do not have access to the key. Further, each evaluation of the function provides, apart from the output, a verification token that allows third parties to verify that the function was computed correctly.
[0004] Distributed applications, such as blockchains based on proof-of-stake, use VRFs to carry out sortitions (cf. Yossi Gilad et al.: “Algorand: Scaling Byzantine Agreements for Cryptocurrencies”, SOSP '17: Proceedings of the 26th Symposium on Operating Systems Principles, October 2017, p. 51-68, https://doi.org/10.1145/3132747.3132757). For example, in proof-of-stake blockchains, each node defines its own VRF by fixing a secret key. Next, given a common input x, each node broadcasts the output of its VRF evaluated on x along with a proof that evaluation was carried out correctly. Among all nodes that broadcasted a correct output, the leaders are elected according to some pre-defined, public rule. For example, the nodes that broadcasted the largest outputs, among all nodes that broadcasted a correct output, are elected as leaders.
[0005] State-of-the-art VRFs are based on elliptic curves or bilinear maps; thus, they are expensive to compute and do not provide post-quantum security (as described in the above-mentioned reference). Recently proposed VRFs, which are post-quantum secure, are based on lattices. However, they are computationally more expensive than their non post-quantum secure alternatives (cf. Muhammed F. Esgin et al.: “Practical Post-Quantum Few-Time Verifiable Random Function with Applications to Algorand”, Cryptology ePrint Archive, Report 2020/1222, https://eprint.iacr.org/2020/1222).
Summary
[0006] In an embodiment, the present disclosure provides a computer-implemented method for execution of a cryptographic sortition among a group of parties. The computer-implemented method comprises: committing, by a first party of the group, to a set of n party-specific secret keys k1, kn for a block cipher E; obtaining, by the first party and at least a second party of the group, a common input x and an index r; encrypting, by the first party, the input x with the r-th key kr of the committed keys k1, . . . , kn, thereby generating an output y1 of the block-cipher E, and publishing the output y1 together with the key kr used for encryption; and encrypting, by the second party, the common input x with the key kr published by the first party, thereby generating an output y1′ of the block-cipher E, and comparing the generated output y1′ with the output y1 published by the first party. The method can be used to optimize the cryptographic sortition and support secure decision making.
Brief Description of the Drawings
[0007] Subject matter of the present disclosure will be described in even greater detail below based on the exemplary figures. All features described and/or illustrated herein can be used alone or combined in different combinations. The features and advantages of various embodiments will become apparent by reading the following detailed description with reference to the attached drawings, which illustrate the following:
[0008] FIG. 1 is a diagram illustrating a Merkle tree that is manipulated by some functions used in the context of an embodiment of the present invention; and
[0009] FIG. 2 is a diagram illustrating a cryptographic sortition for electing between two parties in accordance with an embodiment of the present invention.
Detailed Description
[0010] In accordance with an embodiment, the present invention improves and further develops a method of the initially described type for execution of a cryptographic sortition among a group of parties in such a way that it provides post-quantum security, while at the same time being computationally less expensive and faster than hitherto existing solutions.
[0011] In accordance with another embodiment, the present invention provides a computer-implemented method for execution of a cryptographic sortition among a group of parties, the method comprising committing, by a first party of the group, to a set of n party-specific secret keys k1, . . . , kn for a block cipher E; obtaining, by the first party and at least a second party of the group, a common input x and an index r; encrypting, by the first party, the input x with the r-th key kr of the committed keys k1, . . . , kn, thereby generating an output y1 of the block-cipher E, and publishing the output y1 together with the key kr used for encryption; and encrypting, by the second party, the common input x with the key kr published by the first party, thereby generating an output y1′ of the block-cipher E, and comparing the generated output y1′ with the output y1 published by the first party.
[0012] Furthermore, in accordance with another embodiment, the present invention provides a corresponding host processing system of a party of a group of parties for execution of a cryptographic sortition among the group of parties and a non-transitory computer readable medium for execution of a cryptographic sortition among a group of parties, respectively, as specified in the independent claims.
[0013] Embodiments of the present invention introduce an n-time-secure VRF that is solely based on symmetric-key primitives. The term “n-time secure” refers to the fact that the VRF can be evaluated on up to n distinct points, where n is a system parameter. As such, the proposed VRF is faster than currently used VRFs and is also post-quantum secure. Compared to state-of-the-art VRF that, once defined, can be evaluated over an arbitrary number of inputs, the proposed VRF is secure only if it is evaluated on a given number of inputs and this parameter, denoted as n, may be set when the function is generated. Nevertheless, according to embodiments of the invention it has been recognized that an n-time-secure VRF is sufficient to build a sortition protocol. According to embodiments of the invention, the sortition protocol uses the output of a block cipher evaluated with a client-specific secret key on a round-specific input as a pseudo-random value to determine the outcome of a sortition.
[0014] According to an embodiment, the present invention provides a method for implementing a cryptographic sortition by using solely symmetric-key cryptographic primitives, wherein the method comprises the steps of
-
- [0015] 1) Committing, by a client, to a set of n secret keys k1, . . . , kn for a block cipher;
- [0016] 2) Obtaining, from a blockchain or a trusted party an input x and an index r;
- [0017] 3) Encrypting, by the client, the input x of step 2) with the r-th key kr committed at step 1);
- [0018] 4) Publishing, by the client, the output of the block-cipher y and the key kr used during step 3); and
- [0019] 5) Comparing, by a second client, the output of the block-cipher when encrypting the input x received at step 2) with the key kr received at step 4) against the value y received at step 4).
[0020] According to an embodiment, the cryptographic sortition may be executed in each election round of a leader election scheme of a proof-of-stake based blockchain. In this context, the index r may determine the value of a counter for the respective election round. By using the cryptographic sortition for a leader election protocol in proof-of-stake based blockchains, the throughput of blockchain applications can be significantly enhanced.
[0021] According to an embodiment, it may be provided that the second party adds the first party to a set of elected leaders in case i) output y1 is determined to conform with a pre-defined, public election rule, and ii) the generated output y1′ is identical with the output y1 published by the first party. For example, the election rule may be modeled with a Boolean function that designates a party as one of the leaders if its VRF output lies in a pre-defined interval or exceeds a predefined threshold.
[0022] According to an embodiment, the input x may be round-specific and the participating parties may commit to the set of party-specific secret keys k1, . . . , kn before any of the round-specific inputs x are available. This is important to the protocol in order to avoid that a party—having already knowledge of the input x—can then simply chose k in such a way that VRF (k,x) outputs a value that guarantees the party's election.
[0023] According to an embodiment, the input x may be round-specific and the participating parties may reveal their party-specific secret key k only after the round-specific input x is available. In this context it is important to note that unless a party publishes y=VRF (k,x) and k, no other party can verify that y was computed correctly.
[0024] According to an embodiment, the common input x and the index r that cycles between 1 and n and keeps track of the next election round may be obtained from a blockchain. For example, both x and r could be derived by applying a deterministic function to the last block of a blockchain. Alternatively, the parameters may be obtained from a trusted party.
[0025] According to an embodiment, commitment to the set of n party-specific secret keys k1, . . . , kn may be realized by the aid of a Merkle Tree. More specifically, the respective party may build a Merkle Tree by using the keys k1, . . . , kn as input binary strings for the leaf nodes of the tree and by using a hash function H. The respective party may then publish the label R of the root of the resulting Merkle Tree as its public key.
[0026] The VRF proposed according to embodiments of the present invention extends the evaluation algorithm Eval( ) with an extra input. In particular, Eval( ) may take as input the secret keys k1, . . . , kn, the common input x and the index r, wherein the index r is used to determine which of the secret keys k1, . . . , kn is used to evaluate the function over the input x, and to produce the output y1 and a proof π1. According to an embodiment, running the function Eval( ) by a participating party may include the following steps:
-
- [0027] calculating the co-path C of node labels from the r-th leaf node of the Merkle Tree to the root, wherein the co-path, given a walk from the i-th leaf to the root, is the set of labels of all siblings of the nodes along the walk;
- [0028] determining the output y1 by encrypting the input x with the key kr using block cipher E; and
- [0029] generating a proof π1 consisting of tuple [kr, C].
[0030] Finally, the respective party may publish the output y1 together with the proof π1.
[0031] The VRF proposed according to embodiments of the present invention includes a verification algorithm Verify( ), which may be implemented in form of a deterministic algorithm that on input a public key pk, binary strings x and y, and a proof π, outputs either 0 (invalid) or 1 (valid). Specifically, according to an embodiment, running the function Verify( ) by a second party—based on the public key pk1 of a first party, the input x, the output y1 and the proof π1 received from the first party and the index r—may include the following steps:
-
- [0032] parsing the public key pk of the first party as the label R of the root of the Merkle Tree;
- [0033] parsing the proof π1 as [kr, C];
- [0034] using co-path C to verify that input x is the input string to the r-th leaf node of the Merkle Tree identified by label R; and
- [0035] if both verifications are successful, outputting 1, otherwise outputting 0.
[0036] As already mentioned above, embodiments of the present invention use only symmetric-key primitives. As such, the sortition protocol according to embodiments of the invention is faster than other sortition protocols and achieves post-quantum security. For instance, an AES, Advanced Encryption Standard, block cipher may be used as the block cipher E. With respect to the hash function H it may be provided that this function is selected from the group of SHA, Secure Hash Algorithm, hash functions.
[0037] There are several ways how to design and further develop the teaching of the present invention in an advantageous way. To this end it is to be referred to the dependent claims on the one hand and to the following explanation of preferred embodiments of the invention by way of example, illustrated by the figure on the other hand. In connection with the explanation of the preferred embodiments of the invention by the aid of the figure, generally preferred embodiments and further developments of the teaching will be explained.
[0038] Distributed applications, such as blockchains based on proof-of-stake, carry out sortitions by using Verifiable Random Functions (VRF). Embodiments of the present invention provide a sortition protocol based on an n-times-secure VRF that is faster than state of the art solutions and that achieves post-quantum security.
[0039] Before describing embodiments of the present invention in detail, the concept of VRFs, as far as required for understanding the present invention, will be explained. Generally, a VRF is a tuple of algorithms ParamGen, KeyGen, Eval, Verify defined as follows:
-
- [0040] ParamGen is a probabilistic algorithm that on input a security parameter λ, outputs some global parameters pp. According to embodiments of the invention, the latter is assumed to be implicit input to all of the following algorithms.
- [0041] KeyGen is a probabilistic algorithm that outputs a secret key sk and a public key pk.
- [0042] Eval is a deterministic algorithm that on input a binary string x and a secret key sk, outputs a binary string y and a proof π.
- [0043] Verify is a deterministic algorithm that on input a public key pk, binary strings x and y, and a proof π, outputs either 0 (invalid) or 1 (valid).
[0044] A VRF is informally correct if, assuming that algorithms ParamGen and KeyGen where honestly executed, then for any binary string x, if Eval(sk, x) outputs [y, π], then Verify(pk, x, y, π) outputs 1.
[0045] Further, a VRF should be pseudo-random. That is, an adversary should not be able to efficiently distinguish the output of the VRF on an input of its choice x, from a random string of the same length of the VRF output. Pseudo-randomness should hold despite the fact that the adversary has access to VRF output values and their proofs, for inputs of its choice but different from x.
[0046] Finally, the VRF should be unique, that is, given a public key pk and an input value x, if Verify(pk, x, y1, π1)=Verify(pk, x, y2, π2)=1, then y1=y2.
[0047] The n-times-secure VRF proposed in accordance with embodiments of the present invention extends the evaluation algorithm Eval with an extra input. In particular, Eval may take as input a secret key sk, an input value x, and—in addition—an index i. The secret key sk is actually a vector of secret keys and index i may be used to determine which of the secret keys of the vector sk is used to evaluate the function over the input value x. Each key can only be used once.
[0048] According to embodiments of the invention, some of the algorithms of the VRF may use a number of particular functions that manipulate a Merkle Tree in a specific way. These particular functions, denoted MTCommit, MTOpen and MTVerify herein, and their usage in connection with a Merkle tree will be described hereinafter in detail with reference to FIG. 1 .
[0049] Given a cryptographic hash function H, a Merkle Tree 100 is a binary tree where each leaf node 110i is labelled with the output of H computed over a binary string 120i, whereas each non-leaf node is labelled with the output of H computed over the labels of its child nodes. Hence, a Merkle Tree T is determined by the n input binary strings 120i used to compute the labels of the leaf nodes 110i as well as by the label of its root 130. Specifically, FIG. 1 shows an example of a Merkle Tree 100 with 8 input strings x1, . . . , x8. A line between two nodes indicates that the label of the parent node is computed by hashing the label(s) of the child node(s).
[0050] Notably, the label of the root 130 can be used as a commitment to the input binary strings 120i. In particular, to commit to a list of n binary strings x1, . . . xn, a party can build a Merkle Tree T using x1, . . . xn as input and publish the root label R of the resulting tree. On the one hand, the root label of the tree fully determines the input strings 120i; on the other hand, the one-wayness property of H, i.e., the fact that given an output of H, it is hard to recover the original input, ensures that the root label does not leak information about the input strings 120i.
[0051] To prove that a binary string x is the i-th committed input, that same party can publish the “co-path” of node labels from the i-th leaf 110i of T to the root 130. Given a walk from the i-th leaf 110i to the root 130, its co-path is the set of labels of all siblings of the nodes along the walk. For example, the co-path of x2 in the tree of FIG. 1 is {l7, l4, l2}. Given a root label R, a co-path C, an input x, and an index i, any party can check whether x was the input to the i-th leaf 110i of the Merkle Tree 100 with root label R. To do so, it is sufficient to use x and C to compute all node labels from the i-th leaf 110i to the root 130 and to compare the resulting root label with R; if the two labels are equal (resp. different), then x is accepted (resp. rejected) as the i-th input to the Merkle Tree 100 with root label R.
[0052] Continuing with the example of FIG. 1 , given the root R label, the co-path {l7, l4, l2} and input x, to verify whether x is input to the second leaf 1102 of the tree determined by R, a party will compute l′8=H(x), l′3=H(l7,l′8), l′1=(l′3,l4), R′=H(l′1,l2) and check whether R′ matches R. It should be noted that the number of elements in the co-path is proportional to n (i.e., the number of input strings 120i).
[0053] In the context of the present disclosure, the following definitions and notations are used:
-
- [0054] T:=MTCommit(H, x1, . . . xn) to denote the algorithm that computes the Merkle Tree from a list of n input strings x1, . . . xn, by using hash function H.
- [0055] [x, C]:=MTOpen (H, T, x, i) to denote the algorithm that outputs the co-path C as a proof that x is the input string to the i-th leaf of T. For notational convenience it is assumed herein that MTOpen also outputs the input string x.
- [0056] MTVerify(H, R, x, i, C) to denote the algorithm that uses co-path C to verify whether x is the input string to the i-th leaf of the tree identified by label R.
[0057] Turning now back to the n-time secure VRF provided in accordance with embodiments of the present invention, the above algorithms for manipulation of a Merkle Tree may be utilized in connection with the VRF algorithms. For instance, let E be a block cipher where E(k,m) denotes the encryption of message m with secret key k. Also let MTCommit(H, x1, . . . xn), MTOpen (H, T, x, i), and MTVerify(H, R, x, i, C) denote the algorithms to manipulate a Merkle Tree as defined above.
[0058] According to an embodiment, the parameters of the VRF may be generated by the VRF's algorithm ParamGen as follows: ParamGen may be designed to output globally valid public parameters pp, including a description of the block cipher E (for example AES-128) and a description of the hash function H (for example SHA-256) to be used by the algorithms that manipulate Merkle Trees. Furthermore, ParamGen may output an upper bound to the number of function evaluation n. The public parameters pp may be assumed to be implicit input for all of the following algorithms.
[0059] According to an embodiment, the key pair used by the VRF, i.e. private key sk and public key pk, may be generated by the VRF's algorithm KeyGen as follows:
-
- [0060] Pick n random keys k1, . . . , kn for the block cipher E;
- [0061] Compute T:=MTCommit(H, k1, . . . , kn); and
- [0062] Set sk:=(k1, . . . kn) and pk:=R, where R is the root label of T.
[0063] According to an embodiment, the evaluation algorithm Eval( ) used by the VRF may take as input a secret key sk, an input value x, and—in addition to current prior art approaches—an index i, i.e. Eval(sk, x, i). As explained above, the secret key sk is a vector of secret keys (namely, sk:=(k1, . . . kn)) and index i is used to determine which of the secret keys of the vector sk is used to evaluate the function over the input value x. Each key can only be used once. The evaluation algorithm may execute the following processing steps:
-
- [0064] Parse sk as k1, . . . , kn;
- [0065] Compute [ki, C]:=MTOpen (H, T, ki, i); and
[0066]
[0067] According to an embodiment, the verification algorithm Verify( ) used by the VRF may take as input a public key pk, an input value x, an output value y, an index i and a proof π, i.e. Verify(pk, x, y, i, π). The verification algorithm may execute the following processing steps:
-
- [0068] Parse pk as R;
- [0069] Parse π as [k, C];
- [0070] If E(k, x) is equal to y and MTVerify(H, R, x, i, C) outputs 1, then outputting 1; otherwise outputting 0.
[0071] According to embodiments of the present invention, the above VRF is used to carry out sortitions among a number of parties, in particular parties participating in a blockchain. In this context it is assumed that the blockchain provides a common input x for the evaluation of the VRF and a round counter r that cycles between 1 and n and keeps track of the next election round. For example, both x and r could be derived by applying a deterministic function to the respective last block of the blockchain.
[0072] Without loss of generality, it is further assumed that each of the participating parties can use a VRF output to tell if the party that provided that output is elected as one of the leaders. For example, the election protocol may designate a party as one of the leaders if its VRF output lies in a pre-defined interval. According to an embodiment of the invention, such leader designations scheme may be modelled with a boolean function Leader( ).
[0073] Let P1, . . . , Pm be the parties participating to the protocol. Before elections can start, all of them agree on the public parameters of the scheme. Alternatively, public parameters may be chosen by a trusted third party. Let x be the common input and r the value of the counter for the next election round. Party Pj does the following:
-
- [0074] If r=1
- [0075] Run [skj, pkj]:=KeyGen( )
- [0076] Broadcast pkj
- [0077] Wait to receive pki for i∈{1, . . . , m} and i≠j
- [0078] Set L:=ø
- [0079] Run [yj, πj]:=Eval(skj, x, r)
- [0080] If Leader (yi)=1
- [0081] L:=L∪{Pj}
- [0082] Broadcast [yj, πj]
- [0083] Upon reception of [yi, πi] from Pi where i∈{1, . . . , m} and i≠j
- [0084] Parse πi as [ki, Ci]
- [0074] If r=1
[0085]
-
-
-
- [0086] L:=L∪{Pi}
-
-
[0087] FIG. 2 shows a simple election scheme 200 between a first party 210 (denoted P1) and a second party 220 (denoted P2) in accordance with an embodiment of the present invention. In the example, the number of participants has been limited to two parties solely for ease of understanding. It will be appreciated by those skilled in the art, however, that in real deployment scenarios, e.g. in connection with the execution of proof-of-stake protocols in blockchains, typically many more participating parties will be involved.
[0088] Initially, as shown in FIG. 2 at S_2.1, a round counter r is set to 1 and an input parameter x is determined.
[0089] Next, as shown at S_2.2, each of the parties 210, 220 creates a keypair ski, pk1 and distributes the public key pki, as shown at S_2.3. According to an embodiment, the keypairs may be generated by running the KeyGen( ) algorithm of a VRF, as described in detail above.
[0090] After the exchange of the public keys pk1, both parties 210, 220 initialize a local set of leaders L for a current election to the empty set (i.e., L:=Ø), as shown at S_2.4.
[0091] Next, both parties 210, 220 run the VRF's Eval( ) function on input x using their secret keys ski to obtain an output value yi and a proof πi, as shown at S_2.5.
[0092] Without loss of generality, the example of FIG. 2 assumes that y1 determines the election of P1, whereas y2 dictates that P2 is not elected. Thus, party 210 adds itself to the set of elected leaders L, i.e. L:=L∪{P1}, as shown at S_2.6, and distributes y1, π1, as shown at S_2.7.
[0093] Upon receiving y1, π1, party P2 carries out the necessary checks and adds P1 to its set of elected leaders, as shown at S_2.8. The checks carried out by party P2 include to first parse the received proof π1 into k1, C1. Next, party P2 runs the verification algorithm Verify( ) on the input of the public key pk1 of party P1, input parameter x, and binary string y1 and proof π1, as received from party P1. If the result is 0 (i.e., invalid), party P2 can abort the process, and the set of elected leaders L remains unaltered.
[0094] On the other hand, if the result is 1 (i.e., valid), party P2 further checks the correctness of parameter y1 received from party P1. To do so, party P2 uses the block cipher E to encrypt input parameter x with the parsed key k1 and to check whether the result corresponds to y1.
[0095] If this is correct, finally, party P2 applies the boolean function Leader( ), which determines whether a party, based on its VRF output, is designated a leader or not, to the VRF output y1 of party P1. If the result is 1, party P2 amends the set of elected leaders L by adding party P1, i.e. L:=L∪{P1}.
[0096] The process described above can securely be repeated A number of n times, i.e. until r=n. After n sortitions, the participating parties P1 and P2 may renew their secret and public keys, i.e. by running the key generation algorithm KeyGen( ).
[0097] Many modifications and other embodiments of the invention set forth herein will come to mind to the one skilled in the art to which the invention pertains having the benefit of the teachings presented in the foregoing description and the associated drawings. Therefore, it is to be understood that the invention is not to be limited to the specific embodiments disclosed and that modifications and other embodiments are intended to be included within the scope of the appended claims. Although specific terms are employed herein, they are used in a generic and descriptive sense only and not for purposes of limitation.
[0098] While subject matter of the present disclosure has been illustrated and described in detail in the drawings and foregoing description, such illustration and description are to be considered illustrative or exemplary and not restrictive. Any statement made herein characterizing the invention is also to be considered illustrative or exemplary and not restrictive as the invention is defined by the claims. It will be understood that changes and modifications may be made, by those of ordinary skill in the art, within the scope of the following claims, which may include any combination of features from different embodiments described above.
[0099] The terms used in the claims should be construed to have the broadest reasonable interpretation consistent with the foregoing description. For example, the use of the article “a” or “the” in introducing an element should not be interpreted as being exclusive of a plurality of elements. Likewise, the recitation of “or” should be interpreted as being inclusive, such that the recitation of “A or B” is not exclusive of “A and B,” unless it is clear from the context or the foregoing description that only one of A and B is intended. Further, the recitation of “at least one of A, B and C” should be interpreted as one or more of a group of elements consisting of A, B and C, and should not be interpreted as requiring at least one of each of the listed elements A, B and C, regardless of whether A, B and C are related as categories or otherwise. Moreover, the recitation of “A, B and/or C” or “at least one of A, B or C” should be interpreted as including any singular entity from the listed elements, e.g., A, any subset from the listed elements, e.g., A and B, or the entire list of elements A, B and C.
Claims
The invention claimed is:
1. A computer-implemented method for execution of a cryptographic sortition among a group of parties, the computer-implemented method comprising:
committing, by a first party of the group, to a set of n party-specific secret keys k1, . . . , kn for a block cipher E;
obtaining, by the first party and at least a second party of the group, a common input x and an index r;
encrypting, by the first party, the input x with the r-th key kr of the committed keys k1, . . . , kn, thereby generating an output y1 of the block cipher E, and publishing the output y1 together with the key kr used for encryption;
encrypting, by the second party, the common input x with the key kr published by the first party, thereby generating an output y1′ of the block cipher E, and comparing the generated output y1′ with the output y1 published by the first party; and
running, by the first party of the group, a deterministic function Eval( ) comprising:
calculating a co-path C of node labels from an r-th leaf node of a Merkle Tree, which was built using the set of n party-specific secret keys k1, . . . , kn, to a root of the Merkle Tree,
determining the output y1 by encrypting the input x with the key kr using the block cipher E,
generating a proof π1 consisting of a tuple [kr, C], and
publishing, by the first party of the group, the output y1 together with the proof π1.
2. The method according to claim 1, wherein the cryptographic sortition is executed in each election round of a leader election scheme of a proof-of-stake based blockchain, wherein the index r determines the value of a counter for a respective election round.
3. The method according to claim 1, further comprising:
adding, by the second party, the first party to a set of elected leaders based on determining that:
the output y1 is determined to conform with a pre-defined public election rule, and
the comparison of the output y1′ with the output y1 published by the first party shows that both outputs y1′ and y1 match.
4. The method according to claim 1, wherein the input x is round-specific and wherein the parties of the group commit to the set of party-specific secret keys k1, . . . , kn before any of the round-specific inputs x are available.
5. The method according to claim 1, wherein the input x is round-specific and wherein the parties of the group reveal a respective party-specific secret key k after the round-specific input x is available.
6. The method according to claim 1, wherein the common input x and the index r are obtained from a blockchain or a trusted party.
7. The method according to claim 1, wherein the common input x and the index r are derived by applying a deterministic function to the last block of a blockchain.
8. The method according to claim 1, wherein committing, by the first party of the group, to the set of n party-specific secret keys k1, . . . , kn comprises:
building the Merkle Tree by using the set of n party-specific secret keys k1, . . . , kn as input binary strings for leaf nodes and a hash function H; and
publishing a label R of the root of the resulting Merkle Tree as a public key of the first party.
9. The method according to claim 8, wherein the deterministic function Eval( ) is of a verifiable random function (VRF) that is configured to take as input the set of n party-specific secret keys k1, . . . , kn, the common input x and the index r, wherein the index r is used to determine which of the set of n party-specific secret keys k1, . . . , kn is used to evaluate the function over the input x, and produce the output y1 and the proof π1.
10. The method according to claim 9, further comprising:
running, by the second party of the group, a function Verify( ) of the VRF on a public key pk1 of the first party, the input x, the output y1 and the proof π1 received from the first party and the index r, the function Verify( ) comprises the steps of:
parsing the public key pk1 of the first party as the label R of the root of the Merkle Tree;
parsing the proof π1 as [kr, C];
using the co-path C to verify that input x is the input string to the r-th leaf node of the Merkle Tree identified by label R; and
based on determining that both verifications are successful, outputting 1, otherwise outputting 0.
11. The method according to claim 1, wherein the block cipher E is an Advanced Encryption Standard (AES) block cipher.
12. The method according to claim 8, wherein the hash function H is selected from the group of Secure Hash Algorithm (SHA) hash functions.
13. A host processing system of a party of a group of parties for execution of a cryptographic sortition among the group of parties, the host processing system comprising a processor and a memory, the memory comprising processor executable instructions that, when executed by the processor, cause the processor to perform the following operations:
obtaining a common input x and an index r;
receiving, from another party of the group of parties, an output y1 together with a key kr, wherein the output y1 was generated by the other party by encrypting the input x with the r-th key kr of a set of n party-specific secret keys k1, . . . , kn for a block cipher E the other party has committed to;
encrypting the common input x with the key kr received from the other party, thereby generating an output y1′ of the block cipher E, and comparing the generated output y1′ with the output y1 received from the other party; and
running a function Verify( ) of a Verifiable Random Function (VRF) on a public key pk1 of the other party, the input x, the output y1 and a proof π1 received from the other party and the index r, the function Verify( ) comprising the steps of:
parsing the public key pk1 of the other party as a label R of a root of a Merkle Tree, which was built using the set of n party-specific secret keys k1 . . . , kn,
parsing the proof π1 as [kr, C];
using a co-path C to verify that input x is the input string to an r-th leaf node of the Merkle Tree identified by label R; and
based on determining that both verifications are successful, outputting 1, otherwise outputting 0.
14. A non-transitory computer readable medium for execution of a cryptographic sortition among a group of parties, the computer readable medium storing program code for, when executed by a processor, configuring a host processing system of a party of the group of parties to:
obtain a common input x and an index r;
receive, from another party of the group of parties, an output y1 together with a key kr, wherein the output y1 was generated by the other party by encrypting the input x with the r-th key kr of a set of n party-specific secret keys k1, . . . , kn for a block cipher E the other party has committed to;
encrypt the common input x with the key kr received from the other party, thereby generating an output y1′ of the block cipher E, and compare the generated output y1′ with the output y1 received from the other party; and
running a function Verify( ) of a Verifiable Random Function (VRF) on a public key pk1 of the other party, the input x, the output y1 and a proof π1 received from the other party and the index r, the function Verify( ) comprising the steps of:
parsing the public key pk1 of the other party as a label R of a root of a Merkle Tree, which was built using the set of n party-specific secret keys k1, . . . , kn,
parsing the proof π1 as [kr, C];
using a co-path C to verify that input x is the input string to an r-th leaf node of the Merkle Tree identified by label R; and
based on determining that both verifications are successful, outputting 1, otherwise outputting 0.
15. The method according to claim 1, wherein the first party is elected as a leader based on the output y1 being in a pre-defined interval or exceeding a predefined threshold.
16. The method according to claim 1, wherein a number of sortition rounds is bounded by n.
17. The method according to claim 9, wherein the VRF is based solely on symmetric-key primitives.
18. The host processing system according to claim 13, wherein the block cipher E is an Advanced Encryption Standard (AES) block cipher.
19. The host processing system according to claim 13, wherein the VRF is based solely on symmetric-key primitives.
20. The non-transitory computer readable medium according to claim 14, wherein the VRF is based solely on symmetric-key primitives.
Patent Citations (1)
| Patent | Date | Inventor | Cited By |
|---|---|---|---|
| US2020/0396059(A1) | 2020-12-01 | Micali | Examiner |
Non-Patent Literature (4)
- Boneh, Dan et al.; “Algebraic Pseudorandom Functions with Improved Efficiency from the Augmented Cascade”; Proceedings of the 17th ACM Conference on Computer and Communications Security; Aug. 13, 2010; pp. 131-140; vol. 20100817:100737; XP061004204; International Association for Cryptologic Research; Santa Barbara, CA, USA.Applicant
- Buser, Maxime et al.; “Post-Quantum Verifiable Random Function from Symmetric Primitives in PoS Blockchain”; 2022 European Symposium on Research in Computer Security, Mar. 8, 2021; pp. 25-45; vol. 20210309: 134732; XP061052394; International Association for Cryptologic Research; Santa Barbara, CA, USA.Applicant
- Esgin, Muhammed F. et al.; “Practical Post-Quantum Few-Time Verifiable Random Function with Applications to Algorand”; 25th International Conference on Financial Cryptography and Data Security-Revised Selected Papers, Part II; Mar. 1, 2021; pp. 560-578; ACM Publications; New York, NY, USA.Applicant
- Gilad, Yossi et al.; “Argorand: Scaling Byzantine Agreements for Cryptocurrencies”; SOSP '17: Proceedings of the 26th Symposium on Operating Systems Principles; Oct. 14, 2017; pp. 51-68; XP055573405; ACM Publications; New York, NY, USA.Applicant