321:. Commitments are used in zero-knowledge proofs for two main purposes: first, to allow the prover to participate in "cut and choose" proofs where the verifier will be presented with a choice of what to learn, and the prover will reveal only what corresponds to the verifier's choice. Commitment schemes allow the prover to specify all the information in advance, and only reveal what should be revealed later in the proof. Second, commitments are also used in zero-knowledge proofs by the verifier, who will often specify their choices ahead of time in a commitment. This allows zero-knowledge proofs to be composed in parallel without revealing additional information to the prover.
379:: in order to securely compute a function of some shared input, the secret shares are manipulated instead. However, if shares are to be generated by malicious parties, it may be important that those shares can be checked for correctness. In a verifiable secret sharing scheme, the distribution of a secret is accompanied by commitments to the individual shares. The commitments reveal nothing that can help a dishonest cabal, but the shares allow each individual party to check to see if their shares are correct.
36:
3838:
450:
we formalise different versions of the binding and hiding properties of commitments. The two most important combinations of these properties are perfectly binding and computationally hiding commitment schemes and computationally binding and perfectly hiding commitment schemes. Note that no commitment
10348:
One subtle assumption of the proof is that the commit phase must be finished at some point in time. This leaves room for protocols that require a continuing information flow until the bit is unveiled or the protocol is cancelled, in which case it is not binding anymore. More generally, Mayers' proof
387:
Formal definitions of commitment schemes vary strongly in notation and in flavour. The first such flavour is whether the commitment scheme provides perfect or computational security with respect to the hiding or binding properties. Another such flavour is whether the commitment is interactive, i.e.
140:
that allows one to commit to a chosen value (or chosen statement) while keeping it hidden to others, with the ability to reveal the committed value later. Commitment schemes are designed so that a party cannot change the value or statement after they have committed to it: that is, commitment schemes
1538:
A commitment scheme can either be perfectly binding (it is impossible for Alice to alter her commitment after she has made it, even if she has unbounded computational resources); or perfectly concealing (it is impossible for Bob to find out the commitment without Alice revealing it, even if he has
279:
If Alice and Bob are not in the same place a problem arises. Once Alice has "called" the coin flip, Bob can stipulate the flip "results" to be whatever is most desirable for him. Similarly, if Alice doesn't announce her "call" to Bob, after Bob flips the coin and announces the result, Alice can
3187:
374:
scheme, each of several parties receive "shares" of a value that is meant to be hidden from everyone. If enough parties get together, their shares can be used to reconstruct the secret, but even a malicious cabal of insufficient size should learn nothing. Secret sharing is at the root of many
2227:
These constructions are tightly related to and based on the algebraic properties of the underlying groups, and the notion originally seemed to be very much related to the algebra. However, it was shown that basing statistically binding commitment schemes on general unstructured assumption is
10372:(PUFs) rely on the use of a physical key with internal randomness, which is hard to clone or to emulate. Electronic, optical and other types of PUFs have been discussed extensively in the literature, in connection with their potential cryptographic applications including commitment schemes.
10340:
However, this is impossible, as
Dominic Mayers showed in 1996 (see for the original proof). Any such protocol can be reduced to a protocol where the system is in one of two pure states after the commitment phase, depending on the bit Alice wants to commit. If the protocol is unconditionally
308:
A real-life application of this problem exists, when people (often in media) commit to a decision or give an answer in a "sealed envelope", which is then opened later. "Let's find out if that's what the candidate answered", for example on a game show, can serve as a model of this system.
160:
A way to visualize a commitment scheme is to think of a sender as putting a message in a locked box, and giving the box to a receiver. The message in the box is hidden from the receiver, who cannot open the lock themselves. Since the receiver has the box, the message inside cannot be
304:
For Bob to be able to skew the results to his favor, he must be able to understand the call hidden in Alice's commitment. If the commitment scheme is a good one, Bob cannot skew the results. Similarly, Alice cannot affect the result if she cannot change the value she commits to.
5262:
hash values from the tree, one from each level, must be revealed as the proof. The verifier is able to follow the path from the claimed leaf node all the way up to the root, hashing in the sibling nodes at each level, and eventually arriving at a root node value that must equal
183:
In the above metaphor, the commit phase is the sender putting the message in the box, and locking it. The reveal phase is the sender giving the key to the receiver, who uses it to open the box and verify its contents. The locked box is the commitment, and the key is the proof.
10328:
bit commitment protocols exist on the quantum level, that is, protocols which are (at least asymptotically) binding and concealing even if there are no restrictions on the computational resources. One could hope that there might be a way to exploit the intrinsic properties of
1619:
Bob will need to make 2 (for an incorrect guess) or 2 (on average, for a correct guess) queries to the random oracle. We note that earlier schemes based on hash functions, essentially can be thought of schemes based on idealization of these hash functions as random oracle.
1539:
unbounded computational resources); or formulated as an instance-dependent commitment scheme, which is either hiding or binding depending on the solution to another problem. A commitment scheme cannot be both perfectly hiding and perfectly binding at the same time.
345:
of the data packets, and then selectively revealing partial secret data packets in a manner that conforms specifically to the data to be signed. In this way, the prior public commitment to the secret values becomes a critical part of the functioning of the system.
8771:. This demonstrates the polynomials are identical, because, if the parameters were validly constructed, the trapdoor value is known to no one, meaning that engineering a polynomial to have a specific value at the trapdoor is impossible (according to the
3544:
2173:. An example of an information-theoretically hiding commitment scheme is the Pedersen commitment scheme, which is computationally binding under the discrete logarithm assumption. Additionally to the scheme above, it uses another generator
10763:
Toshiya Itoh, Yiji Ohta, Hiroki
Shizuya (1997). A language dependent cryptographic primitive, In J. Cryptol., 10(1):37-49, cited in Shien Hin Ong and Salil Vadhan (2008). An Equivalence between Zero Knowledge and Commitments, Theory of
199:, from the sender to the receiver, followed by a check performed by the receiver. The value chosen during the commit phase must be the only one that the sender can compute and that validates during the reveal phase (this is called the
6041:
349:
Because the
Lamport signature system cannot be used more than once, a system to combine many Lamport key-sets under a single public value that can be tied to a person and verified by others was developed. This system uses trees of
5511:
776:
3539:
10753:
Shien Hin Ong and Salil Vadhan (1990). Perfect zero knowledge in constant round, In Proc. STOC, p. 482–493, cited in Shien Hin Ong and Salil Vadhan (2008). An
Equivalence between Zero Knowledge and Commitments, Theory of
7760:
2910:
2903:
1020:
8232:
1289:
4793:
1823:
Note that since we do not know how to construct a one-way permutation from any one-way function, this section reduces the strength of the cryptographic assumption necessary to construct a bit-commitment protocol.
7481:. Due to the construction of the trapdoor, it is not possible to evaluate a rational function at the trapdoor value, only to evaluate a polynomial using linear combinations of the precomputed known constants of
1212:
8349:
4510:
8115:
9993:
8462:
2150:. In fact, this scheme isn't hiding at all with respect to the standard hiding game, where an adversary should be unable to guess which of two messages he chose were committed to - similar to the
9881:
8743:
8549:
7325:
5417:
6372:
1971:
This scheme is statistically binding, meaning that even if Alice is computationally unbounded she cannot cheat with probability greater than 2. For Alice to cheat, she would need to find a
6296:
4614:
9588:
6972:
6126:
4083:
901:
9661:
2591:
2510:
2053:
The concealing property follows from a standard reduction, if Bob can tell whether Alice committed to a zero or one, he can also distinguish the output of the pseudo-random generator
6197:
10061:
5546:
2442:
1726:
4374:
8026:
541:
9357:
9690:
9482:
9228:
9151:
9122:
8838:
8617:
7928:
7887:
7452:
6612:
6468:
5722:
5693:
5624:
5595:
5446:
3975:
3881:
3833:{\displaystyle C(m_{1},r_{1})\cdot C(m_{2},r_{2})=m_{1}^{e}g_{m}^{r_{1}}\cdot m_{2}^{e}g_{m}^{r_{2}}=(m_{1}\cdot m_{2})^{e}g_{m}^{r_{1}+r_{2}}=C(m_{1}\cdot m_{2},r_{1}+r_{2})}
2639:
222:, based on various types of commitment schemes. But the concept was used prior to that without being treated formally. The notion of commitments appeared earliest in works by
9776:
5178:
639:
2652:
The
Pedersen commitment scheme introduces an interesting homomorphic property that allows performing addition between two commitments. More specifically, given two messages
7969:
2228:
possible, via the notion of interactive hashing for commitments from general complexity assumptions (specifically and originally, based on any one way permutation) as in.
1137:
932:
831:
674:
9520:
9301:
7512:
6412:
5788:
5755:
5260:
2222:
9453:
9263:
7363:
6523:
3229:
10905:
Moni Naor, Rafail
Ostrovsky, Ramarathnam Venkatesan, Moti Yung: Perfect Zero-Knowledge Arguments for NP Using Any One-Way Permutation. J. Cryptology 11(2): 87–108 (1998)
10310:
5878:
2379:
2286:
10125:
1040:
590:
8966:
7835:
7809:
7152:
6700:
2009:
1963:
1749:
9729:
8893:
7626:
7187:
7065:
7010:
6822:
9165:, and this assumption is also what guards the trapdoor value from being computed, making it also a foundation of KZG commitments. In that case, we want to check if
8925:
7539:
6727:
6647:
6439:
5905:
5225:
4877:
4850:
4823:
4304:
4277:
3935:
3908:
3394:
3367:
3340:
3313:
3283:
3256:
2758:
2731:
2704:
2677:
2469:
1102:
1075:
508:
10228:
10199:
9398:
9067:
7571:
7250:
5322:
5134:
5073:
5044:
5015:
4946:
10274:
9093:
8769:
7652:
7091:
10248:
10170:
10150:
10081:
9418:
9030:
9010:
8990:
8858:
8657:
8637:
7855:
7783:
7591:
7475:
7423:
7403:
7383:
7230:
7207:
7111:
7030:
6902:
6882:
6862:
6842:
6787:
6767:
6747:
6667:
6583:
6563:
6543:
6488:
6217:
5917:
5828:
5808:
5664:
5644:
5566:
5362:
5342:
5281:
5198:
5105:
4986:
4966:
4917:
4897:
4637:
4250:
4230:
4210:
4190:
4166:
4146:
4126:
4106:
4003:
2550:
2530:
2346:
2326:
2306:
2254:
1828:
1369:
is now controlled by the environment, which attempts to distinguish protocol execution from the ideal process. Consider an environment that chooses a message
280:
report that she called whatever result is most desirable for her. Alice and Bob can use commitments in a procedure that will allow both to trust the outcome:
11177:
Rührmair, Ulrich; van Dijk, Marten (2013-04-01). "On the practical use of physical unclonable functions in oblivious transfer and bit commitment protocols".
5451:
354:
to compress many published
Lamport-key-commitment sets into a single hash value that can be associated with the prospective author of later-verified data.
11006:
3399:
3182:{\displaystyle C(m_{1},r_{1})\cdot C(m_{2},r_{2})=g^{m_{1}}h^{r_{1}}\cdot g^{m_{2}}h^{r_{2}}=g^{m_{1}+m_{2}}h^{r_{1}+r_{2}}=C(m_{1}+m_{2},r_{1}+r_{2})}
10727:
Gennaro; Rosario; Rabin, Michael O.; Rabin, Tal. "Simplified VSS and fast-track multiparty computations with applications to threshold cryptography".
7660:
2763:
8121:
3288:
Similarly, the RSA-based commitment mentioned above has a homomorphic property with respect to the multiplication operation. Given two messages
4645:
679:
10578:
1217:
1396:
The protocol is only secure if this scenario is indistinguishable from the ideal case, where the functionality interacts with a simulator
1145:
9360:
10601:
937:
191:. It is essential that the specific value chosen cannot be extracted from the message by the receiver at that time (this is called the
8238:
4379:
10431:
17:
451:
scheme can be at the same time perfectly binding and perfectly hiding – a computationally unbounded adversary can simply generate
2644:
The security of the above commitment relies on the hardness of the RSA problem and has perfect hiding and computational binding.
1389:, the receiver must, after receiving a commitment, output a message "receipt". After the environment sees this message, it tells
3985:
Some commitment schemes permit a proof to be given of only a portion of the committed value. In these schemes, the secret value
100:
8034:
5838:
A KZG commitment reformulates the vector of values to be committed as a polynomial. First, we calculate a polynomial such that
9886:
8355:
72:
10975:
10838:
10661:
2169:, public-key encryption scheme with perfect completeness, and the decommitment is the string of random bits used to encrypt
6585:
is essentially the polynomial evaluated at a number known to no one, with the outcome obfuscated into an opaque element of
187:
In simple protocols, the commit phase consists of a single message from the sender to the receiver. This message is called
9781:
8662:
8468:
10250:, we subtract a polynomial that causes multiple roots, at all the locations we want to prove, and instead of dividing by
79:
234:
et al. The terminology seems to have been originated by Blum, although commitment schemes can be interchangeably called
7257:
5378:
53:
11230:
Nikolopoulos, Georgios M. (2019-09-30). "Optical scheme for cryptographic commitments with physical unclonable keys".
10825:. Lecture Notes in Computer Science. Vol. 576. Berlin, Heidelberg: Springer Berlin Heidelberg. pp. 129–140.
11342:
11332:
10440:
10409:— used by 17th-century natural philosophers to establish priority of a discovery without revealing it to others
1296:
119:
10357:. Kent has shown that there exist unconditionally secure protocols for bit commitment that exploit the principle of
7457:
This computation is only possible if the above polynomials were evenly divisible, because in that case the quotient
6304:
11327:
9162:
4518:
86:
10870:
6222:
9525:
5364:, increases, the commitments and proofs do not get larger, and the proofs do not take any more effort to verify.
6910:
11312:
6049:
4011:
57:
11013:
9597:
2555:
2474:
1459:
However a protocol that is extractable in this sense cannot be statistically hiding. Suppose such a simulator
68:
10854:
Metere, Roberto; Dong, Changyu (2017). "Automated cryptographic analysis of the pedersen commitment scheme".
10821:
Pedersen, Torben Pryds (1992). "Non-Interactive and
Information-Theoretic Secure Verifiable Secret Sharing".
6131:
367:
9998:
1526:. But this is impossible, because at this point the commitment has not been opened yet, so the only message
10369:
5516:
2384:
2161:
A better example of a perfectly binding commitment scheme is one where the commitment is the encryption of
1669:
4317:
10856:
International
Conference on Mathematical Methods, Models, and Architectures for Computer Network Security
9364:
9158:
7974:
1552:
517:
351:
342:
11302:
10341:
concealing, then Alice can unitarily transform these states into each other using the properties of the
9306:
4279:
to be revealed, and it is impossible to create valid proofs that reveal different values for any of the
11307:
10386:
5292:
2147:
2146:
This scheme isn't perfectly concealing as someone could find the commitment if he manages to solve the
2109:
10687:
Proofs that yield nothing but their validity, or all languages in NP have zero-knowledge proof systems
9666:
9458:
9168:
9127:
9098:
8778:
8557:
7892:
7863:
7428:
6588:
6444:
5698:
5669:
5600:
5571:
5422:
3940:
3846:
2596:
10714:
9734:
8772:
5139:
840:
363:
10486:
9693:
10334:
7933:
804:
11136:
McGrath, Thomas; Bagci, Ibrahim E.; Wang, Zhiming M.; Roedig, Utz; Young, Robert J. (2019-02-12).
9487:
9268:
7484:
6384:
5760:
5727:
5230:
4314:
Vector hashing is a naive vector commitment partial reveal scheme based on bit-commitment. Values
2184:
11337:
11038:
10962:. Lecture Notes in Computer Science. Vol. 7778. Springer Berlin Heidelberg. pp. 55–72.
9423:
9233:
7333:
6493:
3937:
has to be added. This newly generated commitment is distributed similarly to a new commitment to
3194:
1637:
1308:
555:
137:
46:
10955:
5841:
2351:
2259:
1108:. A commitment scheme is respectively perfect, statistical, or computational hiding, if for all
595:
242:. Earlier to that, commitment via one-way hash functions was considered, e.g., as part of, say,
10481:
10279:
10086:
8028:
be a helper function for lifting into the pairing group, the proof verification is more clear.
5908:
1025:
389:
146:
93:
10775:
9778:, preventing any contradiction with discrete logarithm earlier. This value can be compared to
8930:
7814:
7788:
7116:
1111:
906:
648:
11046:
International
Conference on the Theory and Application of Cryptology and Information Security
10984:
10652:
10342:
6672:
2158:
is small, then an attacker could simply try them all and the commitment would not be hiding.
1994:
1948:
1906:
1767:) and comparing to the committed value. This scheme is concealing because for Bob to recover
1734:
1530:
can have received in the ideal process is a "receipt" message. We thus have a contradiction.
443:
179:
during which the value is revealed by the sender, then the receiver verifies its authenticity
161:
changed—merely revealed if the sender chooses to give them the key at some later time.
10906:
9699:
8863:
7596:
7157:
7035:
6980:
6792:
11249:
11149:
11102:
10592:
10406:
10321:
8898:
7517:
6705:
6625:
6417:
5883:
5203:
4855:
4828:
4801:
4282:
4255:
3913:
3886:
3372:
3345:
3318:
3291:
3261:
3234:
2736:
2709:
2682:
2655:
2447:
1140:
1080:
1053:
486:
318:
150:
10729:
Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing
10709:
10204:
10175:
9374:
9043:
7556:
7235:
6036:{\displaystyle p(x)=\sum _{i=0}^{n-1}x_{i}\prod _{0\leq j<n,j\neq i}{\frac {x-j}{i-j}}}
5298:
5110:
5049:
5020:
4991:
4922:
2064:
564:
8:
10518:
Russell Impagliazzo, Moti Yung: Direct Minimum-Knowledge Computations. CRYPTO 1987: 40-51
10454:
10253:
9072:
8748:
7631:
7070:
2166:
1641:
1292:
790:
779:
11253:
11153:
11106:
11281:
11239:
11212:
11118:
11092:
10934:"Masquerade: Verifiable Multi-Party Aggregation with Secure Multiplicative Commitments"
10691:
10551:
10501:
10381:
10358:
10354:
10233:
10155:
10135:
10066:
9403:
9015:
8995:
8975:
8843:
8642:
8622:
7840:
7768:
7576:
7460:
7408:
7388:
7368:
7215:
7192:
7096:
7015:
6887:
6867:
6847:
6827:
6772:
6752:
6732:
6652:
6568:
6548:
6528:
6473:
6202:
5813:
5793:
5649:
5629:
5551:
5347:
5327:
5266:
5183:
5090:
4971:
4951:
4902:
4882:
4622:
4235:
4215:
4195:
4175:
4151:
4131:
4111:
4091:
3988:
2535:
2515:
2331:
2311:
2291:
2239:
2070:
1633:
548:
447:
376:
154:
10871:"Pedersen: Non-interactive and information-theoretic secure verifiable secret sharing"
10686:
1436:. Hence, when the commitment is opened during protocol execution, it is unlikely that
388:
whether both the commit phase and the reveal phase can be seen as being executed by a
11285:
11273:
11265:
11204:
10971:
10834:
10657:
10573:
10436:
10391:
10330:
7478:
5506:{\displaystyle e:\mathbb {G} _{1}\times \mathbb {G} _{2}\rightarrow \mathbb {G} _{T}}
1636:. The scheme relies on the fact that every one-way function can be modified (via the
794:
334:
330:
243:
11216:
10555:
10132:
Additionally, a KZG commitment can be extended to prove the values of any arbitrary
2647:
215:
11257:
11194:
11186:
11157:
11122:
11110:
10963:
10826:
10647:
10541:
10505:
10491:
5448:
is the multiplicative group of the pairing. In other words, the pairing is the map
5046:
in size and verification time. Either way, the commitment or the proof scales with
4128:
in the commit phase. Normally, in the reveal phase, the prover would reveal all of
1629:
11308:
Kate-Zaverucha-Goldberg (KZG) Constant-Sized Polynomial Commitments - Alin Tomescu
3534:{\displaystyle C(m_{1},r_{1})\cdot C(m_{2},r_{2})=C(m_{1}\cdot m_{2},r_{1}+r_{2})}
1522:
with high probability. Now in the ideal process the simulator has to come up with
10350:
558:
219:
207:
11114:
10967:
10800:"Citations: Bit Commitment using Pseudorandom Generators - Naor (ResearchIndex)"
6729:
was reformulated into a polynomial, we really need to prove that the polynomial
10673:
10426:
9154:
8969:
5324:
commitment sizes, proof sizes, and proof verification time. In other words, as
371:
338:
11190:
10799:
8554:
Assuming that the bilinear map is validly constructed, this demonstrates that
7755:{\displaystyle e(\pi ,H\cdot t-H\cdot i)\ {\stackrel {?}{=}}\ e(C-G\cdot y,H)}
6622:
A KZG proof must demonstrate that the revealed data is the authentic value of
2014:. If she could find such a value, she could decommit by sending the truth and
11321:
11269:
11208:
10704:
10681:
10677:
9230:. This cannot be done without a pairing, because with values on the curve of
2898:{\displaystyle C(m_{1},r_{1})\cdot C(m_{2},r_{2})=C(m_{1}+m_{2},r_{1}+r_{2})}
1548:
1302:
261:
10830:
5790:
are known and shared values for arbitrarily many positive integer values of
11277:
11072:
Secure classical Bit Commitment using Fixed Capacity Communication Channels
10639:
10635:
10618:
10396:
9591:
7514:. This is why it is impossible to create a proof for an incorrect value of
7232:
through the above polynomial division, then calculates the KZG proof value
5372:
5180:
in size and verification time. The root hash of the tree is the commitment
10600:
1981, pp. 11–15, 1981, reprinted in SIGACT News vol. 15, pp. 23–27, 1983,
10496:
10469:
9040:
The utility of the bilinear map pairing is to allow the multiplication of
8227:{\displaystyle e(G\cdot q(t),H\cdot t-H\cdot i)=e(G\cdot p(t)-G\cdot y,H)}
265:. If they are physically in the same place, a typical procedure might be:
11261:
11199:
11097:
11071:
11059:
8745:, then the polynomials evaluate to the same output at the trapdoor value
6378:
5084:
4788:{\displaystyle (i,y_{1},y_{2},...,y_{i-1},x_{i},m_{i},y_{i+1},...,y_{n})}
2154:
game. One consequence of this is that if the space of possible values of
771:{\displaystyle {\text{Commit}}_{k}(x,open)={\text{Commit}}_{k}(x',open')}
227:
223:
211:
10933:
5367:
A KZG commitment requires a predetermined set of parameters to create a
238:—sometimes reserved for the special case where the committed value is a
10881:
10546:
10529:
9455:, but the other side of the multiplication is done in the paired group
2760:, respectively, it is possible to generate a new commitment such that:
2065:
A perfectly binding scheme based on the discrete log problem and beyond
300:
If Alice's revelation matches the coin result Bob reported, Alice wins.
231:
11162:
11137:
10869:
Tang, Chunming; Pei, Dingyi; Liu, Zhuojun; He, Yong (16 August 2004).
10625:(proceedings of CRYPTO '82), pp. 148–153, Santa Barbara, CA, US, 1982.
10458:, Journal of Computer and System Sciences, vol. 37, pp. 156–189, 1988.
1827:
In 1991 Moni Naor showed how to create a bit-commitment scheme from a
317:
One particular motivating example is the use of commitment schemes in
10364:
9124:, where division is assumed to be computationally hard. For example,
9012:, since that is the output of evaluating the committed polynomial at
6046:
Under this formulation, the polynomial now encodes the vector, where
1284:{\displaystyle \{{\text{Commit}}_{k}(x',U_{k})\}_{k\in \mathbb {N} }}
2231:
1207:{\displaystyle \{{\text{Commit}}_{k}(x,U_{k})\}_{k\in \mathbb {N} }}
195:
property). A simple reveal phase would consist of a single message,
35:
11244:
10917:
Menezes, Alfred J; Van Oorschot, Paul C; Vanstone, Scott A (2018).
10742:
10401:
6545:
can be distributed out of the evaluation. Since the trapdoor value
4376:
are chosen randomly. Individual commitments are created by hashing
4172:). Instead, the prover is able to reveal any single value from the
2038:) are only able to produce 2 possible values each (that's 2) while
10932:
Mouris, Dimitris; Tsoutsos, Nektarios Georgios (26 January 2022).
2328:
are large secret prime numbers. Additionally, she selects a prime
2057:
from true-random, which contradicts the cryptographic security of
547:
determines the security of the commitment scheme it is called the
392:
or whether they are non-interactive, consisting of two algorithms
206:
The concept of commitment schemes was perhaps first formalized by
11039:"Constant-size commitments to polynomials and their applications"
9368:
7550:
5368:
2648:
Additive and multiplicative homomorphic properties of commitments
2151:
1799:) with probability greater than one-half is as hard as inverting
1045:
1015:{\displaystyle {\text{Commit}}(x,open)={\text{Commit}}(x',open')}
11007:"Merkle Signature Schemes, Merkle Trees and Their Cryptanalysis"
8344:{\displaystyle e(G\cdot q(t),H\cdot (t-i))=e(G\cdot (p(t)-y),H)}
1818:
1463:
exists. Now consider an environment that, instead of corrupting
145:. Commitment schemes have important applications in a number of
10597:
10230:. The proof is the same, but instead of subtracting a constant
4505:{\displaystyle y_{1}=H(x_{1}||m_{1}),y_{2}=H(x_{2}||m_{2}),...}
4192:
vector, and create an efficient proof that it is the authentic
1365:
is corrupted. In the UC framework, that essentially means that
7365:, as above. In other words, the proof value is the polynomial
4212:
th element of the original vector that created the commitment
4169:
1623:
164:
Interactions in a commitment scheme take place in two phases:
11060:
A brief review on the impossibility of quantum bit commitment
10880:. Advances in Cryptology CRYPTO 1991 Springer. Archived from
5724:
respectively. As part of the parameter setup, we assume that
1755:, bitwise addition modulo 2. To decommit, Alice simply sends
1361:
that realizes this functionality. Suppose that the committer
467:, and in a perfectly binding scheme this uniquely identifies
431:
being the randomness used for computing the commitment, then
27:
Cryptographic scheme that allows commitment to a chosen value
5087:, in which a binary hash tree is created of the elements of
1542:
10916:
6470:
is an additive group with associativity and commutativity,
5083:
A common example of a practical partial reveal scheme is a
1311:(UC) framework. The reason is that UC commitment has to be
11083:
Kent, A. (1999). "Unconditionally Secure Bit Commitment".
10361:
stating that information cannot travel faster than light.
1452:
from the messages it received from the environment before
1303:
Impossibility of universally composable commitment schemes
793:. It is also possible to state the same requirement using
8110:{\displaystyle e(\pi ,H\cdot t-H\cdot i)=e(C-G\cdot y,H)}
1929:
to Bob, who can then check whether he initially received
275:
If Alice's call is correct, she wins, otherwise Bob wins.
239:
218:
in 1988, as part of various zero-knowledge protocols for
11037:
Kate, Aniket; Zaverucha, Gregory; Goldberg, Ian (2010).
10468:
Goldreich, Oded; Micali, Silvio; Wigderson, Avi (1991).
10467:
9988:{\displaystyle e(G,H)^{q(t)\cdot (t-i)}=e(G,H)^{p(t)-y}}
8457:{\displaystyle e(G,H)^{q(t)\cdot (t-i)}=e(G,H)^{p(t)-y}}
6702:, the revealed value we must prove. Since the vector of
1315:, as shown by Canetti and Fischlin and explained below.
3191:
To open the above Pedersen commitment to a new message
1547:
Bit-commitment schemes are trivial to construct in the
543:
be the corresponding commitment scheme. As the size of
259:
Suppose Alice and Bob want to resolve some dispute via
11135:
10282:
7593:
that demonstrates the desired property, which is that
6225:
2050:
satisfying the equation required to cheat will exist.
1829:
cryptographically secure pseudorandom number generator
1307:
It is impossible to realize commitment schemes in the
297:
Bob verifies that Alice's call matches her commitment,
11036:
11012:. Ruhr-Universität Bochum. p. 16. Archived from
10435:: Volume 1, Basic Tools. Cambridge University Press.
10256:
10236:
10207:
10178:
10158:
10138:
10089:
10069:
10001:
9889:
9784:
9737:
9702:
9669:
9600:
9528:
9490:
9461:
9426:
9406:
9377:
9309:
9271:
9236:
9171:
9130:
9101:
9075:
9046:
9018:
8998:
8978:
8933:
8901:
8866:
8846:
8781:
8751:
8665:
8659:
are. The validator can be assured of this because if
8645:
8625:
8560:
8471:
8358:
8241:
8124:
8037:
7977:
7936:
7895:
7866:
7843:
7817:
7791:
7771:
7663:
7634:
7599:
7579:
7559:
7520:
7487:
7463:
7431:
7411:
7391:
7371:
7336:
7260:
7238:
7218:
7195:
7160:
7119:
7099:
7073:
7038:
7018:
6983:
6913:
6890:
6870:
6850:
6830:
6795:
6775:
6755:
6735:
6708:
6675:
6655:
6628:
6591:
6571:
6551:
6531:
6496:
6476:
6447:
6420:
6387:
6307:
6205:
6134:
6052:
5920:
5886:
5844:
5816:
5796:
5763:
5730:
5701:
5672:
5652:
5632:
5603:
5574:
5554:
5519:
5454:
5425:
5381:
5350:
5330:
5301:
5269:
5233:
5206:
5186:
5142:
5113:
5093:
5052:
5023:
4994:
4974:
4954:
4925:
4905:
4885:
4858:
4831:
4804:
4648:
4625:
4521:
4382:
4320:
4285:
4258:
4238:
4218:
4198:
4178:
4154:
4134:
4114:
4094:
4014:
3991:
3943:
3916:
3889:
3849:
3547:
3402:
3375:
3348:
3321:
3294:
3264:
3237:
3197:
2913:
2766:
2739:
2712:
2685:
2658:
2599:
2558:
2538:
2518:
2477:
2450:
2387:
2354:
2334:
2314:
2294:
2262:
2242:
2187:
1997:
1951:
1783:
is a computationally hard-core predicate, recovering
1737:
1672:
1220:
1148:
1114:
1083:
1056:
1028:
940:
909:
843:
807:
682:
651:
598:
567:
520:
489:
337:
system that relies on maintaining two sets of secret
10814:
10726:
10664:), pp. 37–43. Wadsworth, Belmont, California, 1981.
10172:(not just one value), with the proof size remaining
9876:{\displaystyle e(G\cdot (p(t)-y),H)=e(G,H)^{p(t)-y}}
8738:{\displaystyle \tau (q(t)\cdot (t-i))=\tau (p(t)-y)}
8544:{\displaystyle \tau (q(t)\cdot (t-i))=\tau (p(t)-y)}
6824:. We will do this by demonstrating that subtracting
1318:
The ideal commitment functionality, denoted here by
10910:
10847:
8992:th value of the committed vector must have equaled
7654:. The verification computation checks the equality
6525:, since all the additions and multiplications with
4005:is a vector of many individually separable values.
1416:has to do likewise. The only way to do that is for
362:Another important application of commitments is in
60:. Unsourced material may be challenged and removed.
10992:International Association for Cryptologic Research
10798:
10710:On the Composition of Zero-Knowledge Proof Systems
10452:Gilles Brassard, David Chaum, and Claude Crépeau,
10365:Commitments based on physical unclonable functions
10304:
10268:
10242:
10222:
10193:
10164:
10144:
10119:
10075:
10055:
9987:
9875:
9770:
9723:
9684:
9655:
9582:
9514:
9476:
9447:
9412:
9392:
9351:
9295:
9257:
9222:
9145:
9116:
9087:
9061:
9024:
9004:
8984:
8960:
8919:
8887:
8852:
8832:
8763:
8737:
8651:
8631:
8611:
8543:
8456:
8343:
8226:
8109:
8020:
7963:
7922:
7881:
7860:By rewriting the computation in the pairing group
7849:
7829:
7803:
7777:
7754:
7646:
7620:
7585:
7565:
7533:
7506:
7469:
7446:
7417:
7397:
7377:
7357:
7319:
7244:
7224:
7201:
7181:
7146:
7105:
7085:
7059:
7024:
7004:
6966:
6896:
6876:
6856:
6836:
6816:
6781:
6761:
6741:
6721:
6694:
6661:
6641:
6606:
6577:
6557:
6537:
6517:
6482:
6462:
6433:
6406:
6366:
6290:
6211:
6191:
6120:
6035:
5899:
5872:
5822:
5802:
5782:
5749:
5716:
5687:
5658:
5638:
5618:
5589:
5560:
5540:
5505:
5440:
5411:
5356:
5336:
5316:
5275:
5254:
5219:
5192:
5172:
5128:
5099:
5067:
5038:
5009:
4980:
4960:
4940:
4911:
4891:
4879:, and then is able to verify that the hash of all
4871:
4844:
4817:
4787:
4631:
4608:
4504:
4368:
4298:
4271:
4244:
4224:
4204:
4184:
4160:
4140:
4120:
4100:
4077:
3997:
3969:
3929:
3902:
3875:
3832:
3533:
3388:
3361:
3334:
3307:
3277:
3250:
3223:
3181:
2897:
2752:
2725:
2698:
2671:
2633:
2585:
2544:
2524:
2504:
2463:
2436:
2373:
2340:
2320:
2300:
2280:
2248:
2216:
2003:
1957:
1743:
1720:
1334:, which stores it and sends "receipt" to receiver
1283:
1206:
1131:
1096:
1069:
1034:
1014:
926:
895:
825:
770:
668:
633:
584:
535:
502:
246:, the original one-time one-bit signature scheme.
7320:{\displaystyle \pi =\sum _{i=0}^{n-1}q_{i}Gt^{i}}
5412:{\displaystyle \mathbb {G} _{1},\mathbb {G} _{2}}
5371:, and a trusted trapdoor element. For example, a
2232:A perfectly hiding commitment scheme based on RSA
2096: − 1 to commit to and calculates
284:Alice "calls" the coin flip but only tells Bob a
11319:
11176:
10063:, without ever knowing what the actual value of
1628:One can create a bit-commitment scheme from any
4948:in size and verification time. Alternately, if
2120:, so under this assumption, Bob cannot compute
1655:a hard-core predicate. Then to commit to a bit
1615:) is ≈ 2, but to test any guess at the message
833:secure, if for all algorithms that run in time
404:can often be seen as a derandomised version of
172:during which a value is chosen and committed to
10931:
10925:
10470:"Proofs that yield nothing but their validity"
10345:, effectively defeating the binding property.
10201:, but the proof verification time scales with
9161:. Then, the division assumption is called the
9095:to happen securely. These values truly lie in
6367:{\displaystyle C=\sum _{i=0}^{n-1}p_{i}Gt^{i}}
3843:To open the above commitment to a new message
2116:, it is computationally infeasible to compute
1046:Perfect, statistical, and computational hiding
10982:
10953:
7549:To verify the proof, the bilinear map of the
6291:{\textstyle p(x)=\sum _{i=0}^{n-1}p_{i}x^{i}}
4609:{\displaystyle C=H(y_{1}||y_{2}||...||y_{n})}
2042:is picked out of 2 values. She does not pick
1847:bits, then if Alice wants to commit to a bit
1819:Bit-commitment from a pseudo-random generator
1803:. Perfect binding follows from the fact that
442:Using this notation and some knowledge about
11229:
10868:
10579:McGill University School of Computer Science
10577:, Cryptography and Quantum Information Lab,
4619:In order to prove one element of the vector
2512:group. Finally, Alice commits to her secret
2124:. On the other hand, Alice cannot compute a
1264:
1221:
1187:
1149:
357:
10985:"Vector Commitments and Their Applications"
10956:"Vector Commitments and Their Applications"
9583:{\displaystyle e(G\cdot q(t),H\cdot (t-i))}
5107:. This scheme creates commitments that are
4232:. The proof does not require any values of
2046:, so there is a 2/2 = 2 probability that a
1624:Bit-commitment from any one-way permutation
10853:
10602:Carnegie Mellon School of Computer Science
6967:{\displaystyle q(x)={\frac {p(x)-y}{x-i}}}
5291:A Kate-Zaverucha-Goldberg commitment uses
1905:) to Bob, otherwise she sends the bitwise
1644:(while retaining the injective property).
291:Bob flips the coin and reports the result,
11243:
11198:
11161:
11096:
10567:
10565:
10545:
10495:
10485:
10315:
9672:
9464:
9163:elliptic curve discrete logarithm problem
9133:
9104:
7869:
7434:
6977:This polynomial is itself the proof that
6594:
6450:
6121:{\displaystyle p(0)=x_{0},p(1)=x_{1},...}
5830:itself is discarded and known to no one.
5704:
5675:
5606:
5577:
5528:
5493:
5478:
5463:
5428:
5399:
5384:
4078:{\displaystyle X=(x_{1},x_{2},...,x_{n})}
2561:
2480:
1543:Bit-commitment in the random oracle model
1275:
1198:
435:reduces to simply verifying the equation
120:Learn how and when to remove this message
10820:
10420:
9696:, so even though we know that value and
9656:{\displaystyle e(G,H)^{q(t)\cdot (t-i)}}
4512:. The overall commitment is computed as
4148:and some additional proof data (such as
2586:{\displaystyle \mathbb {Z} _{N^{2}}^{*}}
2505:{\displaystyle \mathbb {Z} _{N^{2}}^{*}}
1471:instead. Additionally it runs a copy of
559:probabilistic polynomial time algorithms
474:
382:
312:
10530:"Bit commitment using pseudorandomness"
10349:applies only to protocols that exploit
10335:unconditionally secure key distribution
9361:computational Diffie–Hellman assumption
7785:is the bilinear map function as above.
7189:). The KZG proof will demonstrate that
6192:{\displaystyle p_{0},p_{1},...,p_{n-1}}
2177:of the prime group and a random number
1835:is a pseudo-random generator such that
1651:be an injective one-way function, with
14:
11320:
11004:
10983:Catalano, Dario; Fiore, Dario (2013).
10954:Catalano, Dario; Fiore, Dario (2013).
10773:
10562:
10455:Minimum Disclosure Proofs of Knowledge
10056:{\displaystyle q(t)\cdot (t-i)=p(t)-y}
7385:again evaluated at the trapdoor value
5295:to build a partial reveal scheme with
2471:as an element of maximum order in the
2444:. Alice then computes a public number
1322:, works roughly as follows. Committer
1104:opening values for security parameter
412:constituting the opening information.
9157:over a finite field, as is common in
8619:, without the validator knowing what
7553:is used to show that the proof value
6789:. Simply, we just need to prove that
5911:allows us to compute that polynomial
5541:{\displaystyle t\in \mathbb {F} _{p}}
2437:{\displaystyle gcd(e,\phi (N^{2}))=1}
1831:. The construction is as follows. If
1721:{\displaystyle (h,f(x),b\oplus h(x))}
1385:. Note here that in order to realize
1077:be the uniform distribution over the
11179:Journal of Cryptographic Engineering
11082:
11058:Brassard, Crépeau, Mayers, Salvail:
10628:
10527:
9036:Why the bilinear map pairing is used
4369:{\displaystyle m_{1},m_{2},...m_{n}}
2532:by first generating a random number
2084:Alice randomly picks a secret value
1502:. At some point in the interaction,
1428:. However, note that by this point,
324:
294:Alice reveals what she committed to,
58:adding citations to reliable sources
29:
11303:Quantum bit commitment on arxiv.org
10823:Advances in Cryptology – CRYPTO '91
10743:Universally Composable Commitments.
10667:
10607:
10584:
10521:
8021:{\displaystyle \tau (x)=e(G,H)^{x}}
5227:is part of the original tree, only
536:{\displaystyle {\text{Commit}}_{k}}
510:, i.e., it can be represented as a
24:
10960:Public-Key Cryptography – PKC 2013
10697:
10446:
9352:{\displaystyle G\cdot (q(x)(x-i))}
6298:. The commitment is calculated as
2018:, or send the opposite answer and
1759:to Bob. Bob verifies by computing
1518:. Note that by assumption we have
463:until finding a pair that outputs
25:
11354:
11296:
10320:It is an interesting question in
9731:, we cannot extract the exponent
8840:is now verified to be true, then
6381:between the predetermined values
5286:
4309:
3980:
3396:, respectively, one can compute:
1297:computationally indistinguishable
10919:Handbook of applied cryptography
9685:{\displaystyle \mathbb {G} _{T}}
9477:{\displaystyle \mathbb {G} _{2}}
9223:{\displaystyle q(x)(x-i)=p(x)-y}
9146:{\displaystyle \mathbb {G} _{1}}
9117:{\displaystyle \mathbb {G} _{1}}
8895:must be polynomial-divisible by
8860:is verified to exist, therefore
8833:{\displaystyle q(x)(x-i)=p(x)-y}
8612:{\displaystyle q(x)(x-i)=p(x)-y}
7923:{\displaystyle \pi =q(t)\cdot G}
7882:{\displaystyle \mathbb {G} _{T}}
7447:{\displaystyle \mathbb {G} _{1}}
6607:{\displaystyle \mathbb {G} _{1}}
6463:{\displaystyle \mathbb {G} _{1}}
6414:and the polynomial coefficients
5717:{\displaystyle \mathbb {G} _{2}}
5688:{\displaystyle \mathbb {G} _{1}}
5619:{\displaystyle \mathbb {G} _{2}}
5590:{\displaystyle \mathbb {G} _{1}}
5441:{\displaystyle \mathbb {G} _{T}}
4798:The verifier is able to compute
4639:, the prover reveals the values
3970:{\displaystyle m_{1}\cdot m_{2}}
3876:{\displaystyle m_{1}\cdot m_{2}}
2634:{\displaystyle c=m^{e}g_{m}^{r}}
2077:, with multiplicative generator
1494:The environment initially tells
254:
149:including secure coin flipping,
34:
11223:
11170:
11129:
11076:
11064:
11052:
11030:
10998:
10947:
10899:
10862:
10791:
10767:
10757:
10747:
10735:
10720:
10615:Protocol for signing contracts.
9771:{\displaystyle q(t)\cdot (t-i)}
9363:, a foundational assumption in
5173:{\displaystyle O(\log _{2}{n})}
4988:values, then the commitment is
1640:) to possess a computationally
1533:
1357:Now, assume we have a protocol
896:{\displaystyle x,x',open,open'}
366:, a critical building block of
249:
45:needs additional citations for
10512:
10461:
10217:
10211:
10188:
10182:
10114:
10102:
10099:
10093:
10044:
10038:
10029:
10017:
10011:
10005:
9974:
9968:
9961:
9948:
9937:
9925:
9919:
9913:
9906:
9893:
9862:
9856:
9849:
9836:
9827:
9818:
9809:
9803:
9797:
9788:
9765:
9753:
9747:
9741:
9718:
9706:
9648:
9636:
9630:
9624:
9617:
9604:
9577:
9574:
9562:
9550:
9544:
9532:
9509:
9497:
9442:
9436:
9387:
9381:
9346:
9343:
9331:
9328:
9322:
9316:
9290:
9278:
9252:
9246:
9211:
9205:
9196:
9184:
9181:
9175:
9056:
9050:
8943:
8937:
8914:
8902:
8876:
8870:
8821:
8815:
8806:
8794:
8791:
8785:
8732:
8723:
8717:
8711:
8702:
8699:
8687:
8681:
8675:
8669:
8600:
8594:
8585:
8573:
8570:
8564:
8538:
8529:
8523:
8517:
8508:
8505:
8493:
8487:
8481:
8475:
8443:
8437:
8430:
8417:
8406:
8394:
8388:
8382:
8375:
8362:
8338:
8329:
8320:
8314:
8308:
8299:
8290:
8287:
8275:
8263:
8257:
8245:
8221:
8200:
8194:
8182:
8173:
8146:
8140:
8128:
8104:
8080:
8071:
8041:
8009:
7996:
7987:
7981:
7952:
7946:
7911:
7905:
7749:
7725:
7697:
7667:
7609:
7603:
7352:
7346:
7209:exists and has this property.
7170:
7164:
7129:
7123:
7048:
7042:
6993:
6987:
6941:
6935:
6923:
6917:
6805:
6799:
6512:
6506:
6235:
6229:
6090:
6084:
6062:
6056:
5930:
5924:
5854:
5848:
5488:
5311:
5305:
5167:
5146:
5123:
5117:
5078:
5062:
5056:
5033:
5027:
5004:
4998:
4935:
4929:
4919:. Unfortunately the proof is
4782:
4649:
4603:
4589:
4584:
4570:
4565:
4550:
4545:
4531:
4487:
4473:
4468:
4454:
4432:
4418:
4413:
4399:
4072:
4021:
3827:
3775:
3725:
3698:
3612:
3586:
3577:
3551:
3528:
3476:
3467:
3441:
3432:
3406:
3176:
3124:
2978:
2952:
2943:
2917:
2892:
2840:
2831:
2805:
2796:
2770:
2425:
2422:
2409:
2397:
1715:
1712:
1706:
1691:
1685:
1673:
1260:
1236:
1183:
1164:
1009:
978:
967:
946:
820:
808:
765:
734:
716:
695:
408:, with the randomness used by
13:
1:
10858:. Springer. pp. 275–287.
10413:
10370:Physical unclonable functions
9995:we are able to conclude that
7964:{\displaystyle C=p(t)\cdot G}
7573:summarizes a real polynomial
6377:This is computed simply as a
5419:are the additive groups, and
5136:in size, and proofs that are
826:{\displaystyle (t,\epsilon )}
483:be chosen from a set of size
368:secure multiparty computation
11005:Becker, Georg (2008-07-18).
10741:R. Canetti and M. Fischlin.
9515:{\displaystyle H\cdot (t-i)}
9296:{\displaystyle G\cdot (x-i)}
7507:{\displaystyle G\cdot t^{i}}
6407:{\displaystyle G\cdot t^{i}}
5783:{\displaystyle H\cdot t^{i}}
5750:{\displaystyle G\cdot t^{i}}
5548:be the trapdoor element (if
5255:{\displaystyle \log _{2}{n}}
2217:{\displaystyle c=g^{x}h^{r}}
2143:, so the scheme is binding.
1815:) has exactly one preimage.
1583:). The probability that any
1510:. This message is handed to
1381:, as if it has committed to
269:Alice "calls" the coin flip,
7:
11313:Kate polynomial commitments
11115:10.1103/PhysRevLett.83.1447
10968:10.1007/978-3-642-36362-7_5
10432:Foundations of Cryptography
10375:
9448:{\displaystyle G\cdot q(x)}
9365:elliptic-curve cryptography
9258:{\displaystyle G\cdot q(x)}
9159:elliptic-curve cryptography
7811:is a precomputed constant,
7358:{\displaystyle G\cdot q(t)}
7093:, meaning it has a root at
6565:is unknown, the commitment
6518:{\displaystyle G\cdot p(t)}
5810:, while the trapdoor value
5200:. To prove that a revealed
3224:{\displaystyle m_{1}+m_{2}}
1659:Alice picks a random input
1567:, Alice generates a random
10:
11359:
10717:, 25: 1, pp. 169–192, 1996
10694:, 38: 3, pp. 690–728, 1991
10593:Coin Flipping by Telephone
10387:Accumulator (cryptography)
10333:, as in the protocols for
10312:for those same locations.
10305:{\textstyle \prod _{i}x-i}
9694:discrete logarithm problem
9371:to sidestep this problem.
7405:, hidden in the generator
5873:{\displaystyle p(i)=x_{i}}
5344:, the number of values in
5293:pairing-based cryptography
5017:in size, and the proof is
2374:{\displaystyle e>N^{2}}
2281:{\displaystyle N=p\cdot q}
2148:discrete logarithm problem
2110:discrete logarithm problem
1559:bit output, to commit the
1408:. In particular, whenever
634:{\displaystyle open,open'}
11191:10.1007/s13389-013-0052-8
10941:Cryptology ePrint Archive
10878:Cryptology ePrint Archive
10715:SIAM Journal on Computing
10581:, accessed April 11, 2008
10120:{\displaystyle q(t)(t-i)}
9359:. That would violate the
7544:
6617:
5833:
5375:can be used. Assume that
4899:values is the commitment
1475:. Messages received from
1035:{\displaystyle \epsilon }
364:verifiable secret sharing
358:Verifiable secret sharing
11343:Cryptographic primitives
11333:Zero-knowledge protocols
10653:The Mathematical Gardner
10623:Advances in Cryptography
9594:of the map, is equal to
8961:{\displaystyle p(i)-y=0}
7830:{\displaystyle H\cdot i}
7804:{\displaystyle H\cdot t}
7147:{\displaystyle p(i)-y=0}
6884:. Define the polynomial
2181:. The commitment is set
1925:To decommit Alice sends
1393:to open the commitment.
1377:to act as prescribed by
1132:{\displaystyle x\neq x'}
927:{\displaystyle x\neq x'}
669:{\displaystyle x\neq x'}
18:Cryptographic commitment
11328:Public-key cryptography
11142:Applied Physics Reviews
10831:10.1007/3-540-46766-1_9
9663:. In this output group
9400:is still multiplied by
8972:. This proves that the
7477:is a polynomial, not a
6695:{\displaystyle y=x_{i}}
6199:be the coefficients of
2004:{\displaystyle \oplus }
1958:{\displaystyle \oplus }
1870:Alice selects a random
1744:{\displaystyle \oplus }
1638:Goldreich-Levin theorem
1506:will commit to a value
1498:to commit to a message
1309:universal composability
645:, the probability that
147:cryptographic protocols
138:cryptographic primitive
10803:. Citeseer.ist.psu.edu
10774:Wagner, David (2006),
10326:unconditionally secure
10316:Quantum bit commitment
10306:
10270:
10244:
10224:
10195:
10166:
10146:
10121:
10077:
10057:
9989:
9877:
9772:
9725:
9724:{\displaystyle e(G,H)}
9686:
9657:
9584:
9516:
9478:
9449:
9414:
9394:
9353:
9297:
9259:
9224:
9147:
9118:
9089:
9063:
9026:
9006:
8986:
8962:
8921:
8889:
8888:{\displaystyle p(x)-y}
8854:
8834:
8765:
8739:
8653:
8633:
8613:
8545:
8458:
8345:
8228:
8111:
8022:
7965:
7924:
7883:
7851:
7831:
7805:
7779:
7756:
7648:
7628:was evenly divided by
7622:
7621:{\displaystyle p(x)-y}
7587:
7567:
7535:
7508:
7471:
7448:
7419:
7399:
7379:
7359:
7321:
7293:
7246:
7226:
7203:
7183:
7182:{\displaystyle p(i)=y}
7148:
7107:
7087:
7061:
7060:{\displaystyle p(x)-y}
7026:
7006:
7005:{\displaystyle p(i)=y}
6968:
6898:
6878:
6858:
6838:
6818:
6817:{\displaystyle p(i)=y}
6783:
6763:
6743:
6723:
6696:
6663:
6643:
6608:
6579:
6559:
6539:
6519:
6484:
6464:
6435:
6408:
6368:
6340:
6292:
6267:
6213:
6193:
6122:
6037:
5962:
5909:Lagrange interpolation
5901:
5874:
5824:
5804:
5784:
5751:
5718:
5689:
5660:
5640:
5620:
5591:
5568:is the prime order of
5562:
5542:
5507:
5442:
5413:
5358:
5338:
5318:
5277:
5256:
5221:
5194:
5174:
5130:
5101:
5075:which is not optimal.
5069:
5040:
5011:
4982:
4962:
4942:
4913:
4893:
4873:
4846:
4819:
4789:
4633:
4610:
4506:
4370:
4300:
4273:
4246:
4226:
4206:
4186:
4162:
4142:
4122:
4102:
4079:
3999:
3971:
3931:
3904:
3877:
3834:
3535:
3390:
3363:
3336:
3309:
3279:
3252:
3225:
3183:
2899:
2754:
2727:
2700:
2673:
2635:
2593:and then by computing
2587:
2546:
2526:
2506:
2465:
2438:
2375:
2342:
2322:
2302:
2282:
2250:
2218:
2005:
1959:
1855:Bob selects a random 3
1807:is injective and thus
1745:
1722:
1285:
1208:
1133:
1098:
1071:
1036:
1016:
928:
897:
827:
797:: A commitment scheme
772:
670:
635:
586:
537:
504:
444:mathematical functions
433:CheckReveal (C,x,open)
390:cryptographic protocol
236:bit commitment schemes
10534:Journal of Cryptology
10497:10.1145/116825.116852
10343:Schmidt decomposition
10307:
10271:
10245:
10225:
10196:
10167:
10147:
10122:
10078:
10058:
9990:
9878:
9773:
9726:
9687:
9658:
9585:
9517:
9479:
9450:
9415:
9395:
9354:
9298:
9260:
9225:
9148:
9119:
9090:
9064:
9027:
9007:
8987:
8963:
8922:
8920:{\displaystyle (x-i)}
8890:
8855:
8835:
8773:Schwartz–Zippel lemma
8766:
8740:
8654:
8634:
8614:
8546:
8459:
8346:
8229:
8112:
8023:
7966:
7925:
7884:
7852:
7837:is computed based on
7832:
7806:
7780:
7757:
7649:
7623:
7588:
7568:
7536:
7534:{\displaystyle x_{i}}
7509:
7472:
7449:
7420:
7400:
7380:
7360:
7322:
7267:
7247:
7227:
7204:
7184:
7154:(or, in other words,
7149:
7108:
7088:
7062:
7027:
7007:
6969:
6899:
6879:
6859:
6839:
6819:
6784:
6769:, takes on the value
6764:
6744:
6724:
6722:{\displaystyle x_{i}}
6697:
6664:
6644:
6642:{\displaystyle x_{i}}
6609:
6580:
6560:
6540:
6520:
6485:
6465:
6436:
6434:{\displaystyle p_{i}}
6409:
6369:
6314:
6293:
6241:
6214:
6194:
6123:
6038:
5936:
5902:
5900:{\displaystyle x_{i}}
5875:
5825:
5805:
5785:
5752:
5719:
5690:
5666:be the generators of
5661:
5641:
5621:
5592:
5563:
5543:
5508:
5443:
5414:
5359:
5339:
5319:
5278:
5257:
5222:
5220:{\displaystyle x_{i}}
5195:
5175:
5131:
5102:
5070:
5041:
5012:
4983:
4963:
4943:
4914:
4894:
4874:
4872:{\displaystyle m_{i}}
4847:
4845:{\displaystyle x_{i}}
4820:
4818:{\displaystyle y_{i}}
4790:
4634:
4611:
4507:
4371:
4301:
4299:{\displaystyle x_{i}}
4274:
4272:{\displaystyle x_{i}}
4247:
4227:
4207:
4187:
4170:simple bit-commitment
4163:
4143:
4123:
4103:
4080:
4000:
3972:
3932:
3930:{\displaystyle r_{2}}
3905:
3903:{\displaystyle r_{1}}
3878:
3835:
3536:
3391:
3389:{\displaystyle r_{2}}
3364:
3362:{\displaystyle r_{1}}
3337:
3335:{\displaystyle m_{2}}
3310:
3308:{\displaystyle m_{1}}
3280:
3278:{\displaystyle r_{2}}
3253:
3251:{\displaystyle r_{1}}
3226:
3184:
2900:
2755:
2753:{\displaystyle r_{2}}
2728:
2726:{\displaystyle r_{1}}
2701:
2699:{\displaystyle m_{2}}
2674:
2672:{\displaystyle m_{1}}
2636:
2588:
2547:
2527:
2507:
2466:
2464:{\displaystyle g_{m}}
2439:
2376:
2343:
2323:
2303:
2283:
2251:
2219:
2006:
1960:
1746:
1723:
1663:and sends the triple
1456:outputs the receipt.
1286:
1209:
1141:probability ensembles
1134:
1099:
1097:{\displaystyle 2^{k}}
1072:
1070:{\displaystyle U_{k}}
1037:
1017:
929:
903:the probability that
898:
828:
773:
671:
641:of increasing length
636:
587:
538:
514:bit string, and let
505:
503:{\displaystyle 2^{k}}
475:Computational binding
400:. In the latter case
383:Defining the security
319:zero-knowledge proofs
313:Zero-knowledge proofs
151:zero-knowledge proofs
11262:10.1364/OE.27.029367
10322:quantum cryptography
10280:
10254:
10234:
10223:{\displaystyle O(k)}
10205:
10194:{\displaystyle O(1)}
10176:
10156:
10136:
10087:
10067:
9999:
9887:
9782:
9735:
9700:
9667:
9598:
9590:, which, due to the
9526:
9488:
9459:
9424:
9404:
9393:{\displaystyle q(x)}
9375:
9307:
9303:, we cannot compute
9269:
9234:
9169:
9128:
9099:
9073:
9062:{\displaystyle q(x)}
9044:
9016:
8996:
8976:
8931:
8899:
8864:
8844:
8779:
8749:
8663:
8643:
8623:
8558:
8469:
8356:
8239:
8122:
8035:
7975:
7934:
7893:
7864:
7841:
7815:
7789:
7769:
7661:
7632:
7597:
7577:
7566:{\displaystyle \pi }
7557:
7518:
7485:
7461:
7429:
7409:
7389:
7369:
7334:
7258:
7245:{\displaystyle \pi }
7236:
7216:
7212:The prover computes
7193:
7158:
7117:
7097:
7071:
7036:
7016:
6981:
6911:
6888:
6868:
6848:
6828:
6793:
6773:
6753:
6749:, when evaluated at
6733:
6706:
6673:
6653:
6626:
6589:
6569:
6549:
6529:
6494:
6474:
6445:
6418:
6385:
6305:
6223:
6203:
6132:
6050:
5918:
5884:
5842:
5814:
5794:
5761:
5728:
5699:
5670:
5650:
5630:
5601:
5572:
5552:
5517:
5452:
5423:
5379:
5348:
5328:
5317:{\displaystyle O(1)}
5299:
5267:
5231:
5204:
5184:
5140:
5129:{\displaystyle O(1)}
5111:
5091:
5068:{\displaystyle O(n)}
5050:
5039:{\displaystyle O(1)}
5021:
5010:{\displaystyle O(n)}
4992:
4972:
4952:
4941:{\displaystyle O(n)}
4923:
4903:
4883:
4856:
4829:
4802:
4646:
4623:
4519:
4380:
4318:
4283:
4256:
4236:
4216:
4196:
4176:
4152:
4132:
4112:
4092:
4012:
3989:
3941:
3914:
3887:
3847:
3545:
3400:
3373:
3346:
3319:
3292:
3262:
3235:
3195:
2911:
2764:
2737:
2710:
2683:
2656:
2597:
2556:
2536:
2516:
2475:
2448:
2385:
2352:
2332:
2312:
2292:
2260:
2240:
2185:
1995:
1949:
1735:
1670:
1218:
1146:
1112:
1081:
1054:
1026:
938:
907:
841:
805:
680:
649:
596:
585:{\displaystyle x,x'}
565:
518:
487:
54:improve this article
11254:2019OExpr..2729367N
11238:(20): 29367–29379.
11154:2019ApPRv...6a1303M
11107:1999PhRvL..83.1447K
10703:Oded Goldreich and
10638:, and L. Adleman, "
10528:Naor, Moni (1991).
10269:{\displaystyle x-i}
9367:. We instead use a
9088:{\displaystyle x-i}
8764:{\displaystyle x=t}
7647:{\displaystyle x-i}
7086:{\displaystyle x-i}
6490:is equal to simply
4306:than the true one.
3768:
3694:
3672:
3654:
3632:
2630:
2582:
2501:
2167:semantically secure
2112:dictates that from
1642:hard-core predicate
1483:, and replies from
1424:to send a value to
1412:outputs "receipt",
1293:statistically close
791:asymptotic analysis
780:negligible function
455:for every value of
272:Bob flips the coin,
69:"Commitment scheme"
10692:Journal of the ACM
10547:10.1007/BF00196774
10474:Journal of the ACM
10382:Oblivious transfer
10359:special relativity
10355:special relativity
10302:
10292:
10266:
10240:
10220:
10191:
10162:
10142:
10117:
10073:
10053:
9985:
9873:
9768:
9721:
9692:we still have the
9682:
9653:
9580:
9512:
9474:
9445:
9410:
9390:
9349:
9293:
9255:
9220:
9143:
9114:
9085:
9059:
9022:
9002:
8982:
8958:
8917:
8885:
8850:
8830:
8761:
8735:
8649:
8629:
8609:
8541:
8454:
8341:
8224:
8107:
8018:
7961:
7920:
7889:, substituting in
7879:
7847:
7827:
7801:
7775:
7752:
7644:
7618:
7583:
7563:
7531:
7504:
7467:
7444:
7415:
7395:
7375:
7355:
7317:
7242:
7222:
7199:
7179:
7144:
7103:
7083:
7057:
7022:
7002:
6964:
6894:
6874:
6854:
6834:
6814:
6779:
6759:
6739:
6719:
6692:
6669:was computed. Let
6659:
6639:
6604:
6575:
6555:
6535:
6515:
6480:
6460:
6431:
6404:
6364:
6288:
6209:
6189:
6118:
6033:
6006:
5897:
5880:for all values of
5870:
5820:
5800:
5780:
5747:
5714:
5685:
5656:
5636:
5616:
5587:
5558:
5538:
5503:
5438:
5409:
5354:
5334:
5314:
5273:
5252:
5217:
5190:
5170:
5126:
5097:
5065:
5036:
5007:
4978:
4968:is the set of all
4958:
4938:
4909:
4889:
4869:
4842:
4815:
4785:
4629:
4606:
4502:
4366:
4296:
4269:
4242:
4222:
4202:
4182:
4158:
4138:
4118:
4098:
4075:
3995:
3967:
3927:
3900:
3873:
3830:
3734:
3673:
3658:
3633:
3618:
3531:
3386:
3359:
3332:
3305:
3275:
3248:
3221:
3179:
2895:
2750:
2723:
2696:
2669:
2631:
2616:
2583:
2559:
2542:
2522:
2502:
2478:
2461:
2434:
2371:
2338:
2318:
2298:
2278:
2246:
2214:
2001:
1955:
1878:and computes the 3
1741:
1718:
1281:
1204:
1129:
1094:
1067:
1032:
1012:
924:
893:
823:
789:This is a form of
768:
666:
631:
582:
549:security parameter
533:
500:
448:probability theory
415:If the commitment
377:secure computation
155:secure computation
11163:10.1063/1.5079407
10977:978-3-642-36362-7
10887:on 11 August 2017
10840:978-3-540-55188-1
10662:978-1-4684-6686-7
10596:, Proceedings of
10392:Key signing party
10331:quantum mechanics
10283:
10243:{\displaystyle y}
10165:{\displaystyle X}
10145:{\displaystyle k}
10076:{\displaystyle t}
9413:{\displaystyle G}
9025:{\displaystyle i}
9005:{\displaystyle y}
8985:{\displaystyle i}
8853:{\displaystyle q}
8652:{\displaystyle q}
8632:{\displaystyle p}
7850:{\displaystyle i}
7778:{\displaystyle e}
7721:
7716:
7702:
7586:{\displaystyle q}
7479:rational function
7470:{\displaystyle q}
7418:{\displaystyle G}
7398:{\displaystyle t}
7378:{\displaystyle q}
7330:This is equal to
7225:{\displaystyle q}
7202:{\displaystyle q}
7106:{\displaystyle i}
7025:{\displaystyle q}
6962:
6897:{\displaystyle q}
6877:{\displaystyle i}
6864:yields a root at
6857:{\displaystyle p}
6837:{\displaystyle y}
6782:{\displaystyle y}
6762:{\displaystyle i}
6742:{\displaystyle p}
6662:{\displaystyle C}
6578:{\displaystyle C}
6558:{\displaystyle t}
6538:{\displaystyle G}
6483:{\displaystyle C}
6212:{\displaystyle p}
6031:
5973:
5823:{\displaystyle t}
5803:{\displaystyle i}
5659:{\displaystyle H}
5639:{\displaystyle G}
5561:{\displaystyle p}
5357:{\displaystyle X}
5337:{\displaystyle n}
5276:{\displaystyle C}
5193:{\displaystyle C}
5100:{\displaystyle X}
4981:{\displaystyle y}
4961:{\displaystyle C}
4912:{\displaystyle C}
4892:{\displaystyle y}
4632:{\displaystyle X}
4245:{\displaystyle X}
4225:{\displaystyle C}
4205:{\displaystyle i}
4185:{\displaystyle X}
4161:{\displaystyle R}
4141:{\displaystyle X}
4121:{\displaystyle X}
4108:is computed from
4101:{\displaystyle C}
3998:{\displaystyle X}
3883:, the randomness
3285:has to be added.
3231:, the randomness
2545:{\displaystyle r}
2525:{\displaystyle m}
2341:{\displaystyle e}
2321:{\displaystyle q}
2301:{\displaystyle p}
2249:{\displaystyle N}
1487:are forwarded to
1228:
1156:
976:
944:
795:concrete security
726:
687:
525:
437:C=Commit (x,open)
425:C:=Commit(x,open)
343:verifiable hashes
335:digital signature
331:Lamport signature
325:Signature schemes
244:Lamport signature
134:commitment scheme
130:
129:
122:
104:
16:(Redirected from
11350:
11290:
11289:
11247:
11227:
11221:
11220:
11202:
11174:
11168:
11167:
11165:
11138:"A PUF taxonomy"
11133:
11127:
11126:
11100:
11098:quant-ph/9810068
11091:(7): 1447–1450.
11080:
11074:
11068:
11062:
11056:
11050:
11049:
11043:
11034:
11028:
11027:
11025:
11024:
11018:
11011:
11002:
10996:
10995:
10989:
10981:
10951:
10945:
10944:
10938:
10929:
10923:
10922:
10914:
10908:
10903:
10897:
10896:
10894:
10892:
10886:
10875:
10866:
10860:
10859:
10851:
10845:
10844:
10818:
10812:
10811:
10809:
10808:
10802:
10795:
10789:
10788:
10787:
10785:
10777:Midterm Solution
10771:
10765:
10761:
10755:
10751:
10745:
10739:
10733:
10732:
10724:
10718:
10701:
10695:
10671:
10665:
10648:David A. Klarner
10632:
10626:
10611:
10605:
10588:
10582:
10571:Claude Crépeau,
10569:
10560:
10559:
10549:
10525:
10519:
10516:
10510:
10509:
10499:
10489:
10465:
10459:
10450:
10444:
10424:
10311:
10309:
10308:
10303:
10291:
10275:
10273:
10272:
10267:
10249:
10247:
10246:
10241:
10229:
10227:
10226:
10221:
10200:
10198:
10197:
10192:
10171:
10169:
10168:
10163:
10151:
10149:
10148:
10143:
10126:
10124:
10123:
10118:
10082:
10080:
10079:
10074:
10062:
10060:
10059:
10054:
9994:
9992:
9991:
9986:
9984:
9983:
9941:
9940:
9882:
9880:
9879:
9874:
9872:
9871:
9777:
9775:
9774:
9769:
9730:
9728:
9727:
9722:
9691:
9689:
9688:
9683:
9681:
9680:
9675:
9662:
9660:
9659:
9654:
9652:
9651:
9589:
9587:
9586:
9581:
9521:
9519:
9518:
9513:
9483:
9481:
9480:
9475:
9473:
9472:
9467:
9454:
9452:
9451:
9446:
9419:
9417:
9416:
9411:
9399:
9397:
9396:
9391:
9358:
9356:
9355:
9350:
9302:
9300:
9299:
9294:
9264:
9262:
9261:
9256:
9229:
9227:
9226:
9221:
9152:
9150:
9149:
9144:
9142:
9141:
9136:
9123:
9121:
9120:
9115:
9113:
9112:
9107:
9094:
9092:
9091:
9086:
9068:
9066:
9065:
9060:
9031:
9029:
9028:
9023:
9011:
9009:
9008:
9003:
8991:
8989:
8988:
8983:
8967:
8965:
8964:
8959:
8926:
8924:
8923:
8918:
8894:
8892:
8891:
8886:
8859:
8857:
8856:
8851:
8839:
8837:
8836:
8831:
8770:
8768:
8767:
8762:
8744:
8742:
8741:
8736:
8658:
8656:
8655:
8650:
8638:
8636:
8635:
8630:
8618:
8616:
8615:
8610:
8550:
8548:
8547:
8542:
8463:
8461:
8460:
8455:
8453:
8452:
8410:
8409:
8350:
8348:
8347:
8342:
8233:
8231:
8230:
8225:
8116:
8114:
8113:
8108:
8027:
8025:
8024:
8019:
8017:
8016:
7970:
7968:
7967:
7962:
7929:
7927:
7926:
7921:
7888:
7886:
7885:
7880:
7878:
7877:
7872:
7856:
7854:
7853:
7848:
7836:
7834:
7833:
7828:
7810:
7808:
7807:
7802:
7784:
7782:
7781:
7776:
7761:
7759:
7758:
7753:
7719:
7718:
7717:
7715:
7710:
7705:
7700:
7653:
7651:
7650:
7645:
7627:
7625:
7624:
7619:
7592:
7590:
7589:
7584:
7572:
7570:
7569:
7564:
7540:
7538:
7537:
7532:
7530:
7529:
7513:
7511:
7510:
7505:
7503:
7502:
7476:
7474:
7473:
7468:
7453:
7451:
7450:
7445:
7443:
7442:
7437:
7424:
7422:
7421:
7416:
7404:
7402:
7401:
7396:
7384:
7382:
7381:
7376:
7364:
7362:
7361:
7356:
7326:
7324:
7323:
7318:
7316:
7315:
7303:
7302:
7292:
7281:
7251:
7249:
7248:
7243:
7231:
7229:
7228:
7223:
7208:
7206:
7205:
7200:
7188:
7186:
7185:
7180:
7153:
7151:
7150:
7145:
7112:
7110:
7109:
7104:
7092:
7090:
7089:
7084:
7067:is divisible by
7066:
7064:
7063:
7058:
7031:
7029:
7028:
7023:
7011:
7009:
7008:
7003:
6973:
6971:
6970:
6965:
6963:
6961:
6950:
6930:
6903:
6901:
6900:
6895:
6883:
6881:
6880:
6875:
6863:
6861:
6860:
6855:
6843:
6841:
6840:
6835:
6823:
6821:
6820:
6815:
6788:
6786:
6785:
6780:
6768:
6766:
6765:
6760:
6748:
6746:
6745:
6740:
6728:
6726:
6725:
6720:
6718:
6717:
6701:
6699:
6698:
6693:
6691:
6690:
6668:
6666:
6665:
6660:
6648:
6646:
6645:
6640:
6638:
6637:
6613:
6611:
6610:
6605:
6603:
6602:
6597:
6584:
6582:
6581:
6576:
6564:
6562:
6561:
6556:
6544:
6542:
6541:
6536:
6524:
6522:
6521:
6516:
6489:
6487:
6486:
6481:
6469:
6467:
6466:
6461:
6459:
6458:
6453:
6440:
6438:
6437:
6432:
6430:
6429:
6413:
6411:
6410:
6405:
6403:
6402:
6373:
6371:
6370:
6365:
6363:
6362:
6350:
6349:
6339:
6328:
6297:
6295:
6294:
6289:
6287:
6286:
6277:
6276:
6266:
6255:
6218:
6216:
6215:
6210:
6198:
6196:
6195:
6190:
6188:
6187:
6157:
6156:
6144:
6143:
6127:
6125:
6124:
6119:
6105:
6104:
6077:
6076:
6042:
6040:
6039:
6034:
6032:
6030:
6019:
6008:
6005:
5972:
5971:
5961:
5950:
5906:
5904:
5903:
5898:
5896:
5895:
5879:
5877:
5876:
5871:
5869:
5868:
5829:
5827:
5826:
5821:
5809:
5807:
5806:
5801:
5789:
5787:
5786:
5781:
5779:
5778:
5756:
5754:
5753:
5748:
5746:
5745:
5723:
5721:
5720:
5715:
5713:
5712:
5707:
5694:
5692:
5691:
5686:
5684:
5683:
5678:
5665:
5663:
5662:
5657:
5645:
5643:
5642:
5637:
5625:
5623:
5622:
5617:
5615:
5614:
5609:
5596:
5594:
5593:
5588:
5586:
5585:
5580:
5567:
5565:
5564:
5559:
5547:
5545:
5544:
5539:
5537:
5536:
5531:
5512:
5510:
5509:
5504:
5502:
5501:
5496:
5487:
5486:
5481:
5472:
5471:
5466:
5447:
5445:
5444:
5439:
5437:
5436:
5431:
5418:
5416:
5415:
5410:
5408:
5407:
5402:
5393:
5392:
5387:
5363:
5361:
5360:
5355:
5343:
5341:
5340:
5335:
5323:
5321:
5320:
5315:
5282:
5280:
5279:
5274:
5261:
5259:
5258:
5253:
5251:
5243:
5242:
5226:
5224:
5223:
5218:
5216:
5215:
5199:
5197:
5196:
5191:
5179:
5177:
5176:
5171:
5166:
5158:
5157:
5135:
5133:
5132:
5127:
5106:
5104:
5103:
5098:
5074:
5072:
5071:
5066:
5045:
5043:
5042:
5037:
5016:
5014:
5013:
5008:
4987:
4985:
4984:
4979:
4967:
4965:
4964:
4959:
4947:
4945:
4944:
4939:
4918:
4916:
4915:
4910:
4898:
4896:
4895:
4890:
4878:
4876:
4875:
4870:
4868:
4867:
4851:
4849:
4848:
4843:
4841:
4840:
4824:
4822:
4821:
4816:
4814:
4813:
4794:
4792:
4791:
4786:
4781:
4780:
4756:
4755:
4737:
4736:
4724:
4723:
4711:
4710:
4680:
4679:
4667:
4666:
4638:
4636:
4635:
4630:
4615:
4613:
4612:
4607:
4602:
4601:
4592:
4587:
4573:
4568:
4563:
4562:
4553:
4548:
4543:
4542:
4511:
4509:
4508:
4503:
4486:
4485:
4476:
4471:
4466:
4465:
4447:
4446:
4431:
4430:
4421:
4416:
4411:
4410:
4392:
4391:
4375:
4373:
4372:
4367:
4365:
4364:
4343:
4342:
4330:
4329:
4305:
4303:
4302:
4297:
4295:
4294:
4278:
4276:
4275:
4270:
4268:
4267:
4251:
4249:
4248:
4243:
4231:
4229:
4228:
4223:
4211:
4209:
4208:
4203:
4191:
4189:
4188:
4183:
4167:
4165:
4164:
4159:
4147:
4145:
4144:
4139:
4127:
4125:
4124:
4119:
4107:
4105:
4104:
4099:
4084:
4082:
4081:
4076:
4071:
4070:
4046:
4045:
4033:
4032:
4004:
4002:
4001:
3996:
3976:
3974:
3973:
3968:
3966:
3965:
3953:
3952:
3936:
3934:
3933:
3928:
3926:
3925:
3909:
3907:
3906:
3901:
3899:
3898:
3882:
3880:
3879:
3874:
3872:
3871:
3859:
3858:
3839:
3837:
3836:
3831:
3826:
3825:
3813:
3812:
3800:
3799:
3787:
3786:
3767:
3766:
3765:
3753:
3752:
3742:
3733:
3732:
3723:
3722:
3710:
3709:
3693:
3692:
3691:
3681:
3671:
3666:
3653:
3652:
3651:
3641:
3631:
3626:
3611:
3610:
3598:
3597:
3576:
3575:
3563:
3562:
3540:
3538:
3537:
3532:
3527:
3526:
3514:
3513:
3501:
3500:
3488:
3487:
3466:
3465:
3453:
3452:
3431:
3430:
3418:
3417:
3395:
3393:
3392:
3387:
3385:
3384:
3368:
3366:
3365:
3360:
3358:
3357:
3342:with randomness
3341:
3339:
3338:
3333:
3331:
3330:
3314:
3312:
3311:
3306:
3304:
3303:
3284:
3282:
3281:
3276:
3274:
3273:
3257:
3255:
3254:
3249:
3247:
3246:
3230:
3228:
3227:
3222:
3220:
3219:
3207:
3206:
3188:
3186:
3185:
3180:
3175:
3174:
3162:
3161:
3149:
3148:
3136:
3135:
3117:
3116:
3115:
3114:
3102:
3101:
3087:
3086:
3085:
3084:
3072:
3071:
3054:
3053:
3052:
3051:
3037:
3036:
3035:
3034:
3017:
3016:
3015:
3014:
3000:
2999:
2998:
2997:
2977:
2976:
2964:
2963:
2942:
2941:
2929:
2928:
2904:
2902:
2901:
2896:
2891:
2890:
2878:
2877:
2865:
2864:
2852:
2851:
2830:
2829:
2817:
2816:
2795:
2794:
2782:
2781:
2759:
2757:
2756:
2751:
2749:
2748:
2732:
2730:
2729:
2724:
2722:
2721:
2705:
2703:
2702:
2697:
2695:
2694:
2678:
2676:
2675:
2670:
2668:
2667:
2640:
2638:
2637:
2632:
2629:
2624:
2615:
2614:
2592:
2590:
2589:
2584:
2581:
2576:
2575:
2574:
2564:
2551:
2549:
2548:
2543:
2531:
2529:
2528:
2523:
2511:
2509:
2508:
2503:
2500:
2495:
2494:
2493:
2483:
2470:
2468:
2467:
2462:
2460:
2459:
2443:
2441:
2440:
2435:
2421:
2420:
2380:
2378:
2377:
2372:
2370:
2369:
2347:
2345:
2344:
2339:
2327:
2325:
2324:
2319:
2307:
2305:
2304:
2299:
2287:
2285:
2284:
2279:
2255:
2253:
2252:
2247:
2223:
2221:
2220:
2215:
2213:
2212:
2203:
2202:
2129:
2069:Alice chooses a
2010:
2008:
2007:
2002:
1964:
1962:
1961:
1956:
1771:he must recover
1750:
1748:
1747:
1742:
1727:
1725:
1724:
1719:
1630:one-way function
1575:and sends Bob H(
1432:is not known to
1342:sends "open" to
1290:
1288:
1287:
1282:
1280:
1279:
1278:
1259:
1258:
1246:
1235:
1234:
1229:
1226:
1213:
1211:
1210:
1205:
1203:
1202:
1201:
1182:
1181:
1163:
1162:
1157:
1154:
1138:
1136:
1135:
1130:
1128:
1103:
1101:
1100:
1095:
1093:
1092:
1076:
1074:
1073:
1068:
1066:
1065:
1041:
1039:
1038:
1033:
1021:
1019:
1018:
1013:
1008:
988:
977:
974:
945:
942:
933:
931:
930:
925:
923:
902:
900:
899:
894:
892:
857:
832:
830:
829:
824:
777:
775:
774:
769:
764:
744:
733:
732:
727:
724:
694:
693:
688:
685:
675:
673:
672:
667:
665:
640:
638:
637:
632:
630:
591:
589:
588:
583:
581:
542:
540:
539:
534:
532:
531:
526:
523:
509:
507:
506:
501:
499:
498:
125:
118:
114:
111:
105:
103:
62:
38:
30:
21:
11358:
11357:
11353:
11352:
11351:
11349:
11348:
11347:
11318:
11317:
11299:
11294:
11293:
11228:
11224:
11175:
11171:
11134:
11130:
11085:Phys. Rev. Lett
11081:
11077:
11069:
11065:
11057:
11053:
11041:
11035:
11031:
11022:
11020:
11016:
11009:
11003:
10999:
10987:
10978:
10952:
10948:
10936:
10930:
10926:
10915:
10911:
10904:
10900:
10890:
10888:
10884:
10873:
10867:
10863:
10852:
10848:
10841:
10819:
10815:
10806:
10804:
10797:
10796:
10792:
10783:
10781:
10772:
10768:
10762:
10758:
10752:
10748:
10740:
10736:
10725:
10721:
10702:
10698:
10672:
10668:
10633:
10629:
10612:
10608:
10589:
10585:
10570:
10563:
10526:
10522:
10517:
10513:
10487:10.1.1.420.1478
10466:
10462:
10451:
10447:
10425:
10421:
10416:
10378:
10367:
10351:quantum physics
10318:
10287:
10281:
10278:
10277:
10255:
10252:
10251:
10235:
10232:
10231:
10206:
10203:
10202:
10177:
10174:
10173:
10157:
10154:
10153:
10137:
10134:
10133:
10130:
10129:
10088:
10085:
10084:
10068:
10065:
10064:
10000:
9997:
9996:
9964:
9960:
9909:
9905:
9888:
9885:
9884:
9883:though, and if
9852:
9848:
9783:
9780:
9779:
9736:
9733:
9732:
9701:
9698:
9697:
9676:
9671:
9670:
9668:
9665:
9664:
9620:
9616:
9599:
9596:
9595:
9527:
9524:
9523:
9489:
9486:
9485:
9468:
9463:
9462:
9460:
9457:
9456:
9425:
9422:
9421:
9405:
9402:
9401:
9376:
9373:
9372:
9308:
9305:
9304:
9270:
9267:
9266:
9235:
9232:
9231:
9170:
9167:
9166:
9137:
9132:
9131:
9129:
9126:
9125:
9108:
9103:
9102:
9100:
9097:
9096:
9074:
9071:
9070:
9045:
9042:
9041:
9037:
9017:
9014:
9013:
8997:
8994:
8993:
8977:
8974:
8973:
8932:
8929:
8928:
8900:
8897:
8896:
8865:
8862:
8861:
8845:
8842:
8841:
8780:
8777:
8776:
8750:
8747:
8746:
8664:
8661:
8660:
8644:
8641:
8640:
8624:
8621:
8620:
8559:
8556:
8555:
8470:
8467:
8466:
8433:
8429:
8378:
8374:
8357:
8354:
8353:
8240:
8237:
8236:
8123:
8120:
8119:
8036:
8033:
8032:
8012:
8008:
7976:
7973:
7972:
7935:
7932:
7931:
7894:
7891:
7890:
7873:
7868:
7867:
7865:
7862:
7861:
7842:
7839:
7838:
7816:
7813:
7812:
7790:
7787:
7786:
7770:
7767:
7766:
7711:
7706:
7704:
7703:
7662:
7659:
7658:
7633:
7630:
7629:
7598:
7595:
7594:
7578:
7575:
7574:
7558:
7555:
7554:
7547:
7525:
7521:
7519:
7516:
7515:
7498:
7494:
7486:
7483:
7482:
7462:
7459:
7458:
7438:
7433:
7432:
7430:
7427:
7426:
7410:
7407:
7406:
7390:
7387:
7386:
7370:
7367:
7366:
7335:
7332:
7331:
7311:
7307:
7298:
7294:
7282:
7271:
7259:
7256:
7255:
7237:
7234:
7233:
7217:
7214:
7213:
7194:
7191:
7190:
7159:
7156:
7155:
7118:
7115:
7114:
7098:
7095:
7094:
7072:
7069:
7068:
7037:
7034:
7033:
7017:
7014:
7013:
6982:
6979:
6978:
6951:
6931:
6929:
6912:
6909:
6908:
6889:
6886:
6885:
6869:
6866:
6865:
6849:
6846:
6845:
6829:
6826:
6825:
6794:
6791:
6790:
6774:
6771:
6770:
6754:
6751:
6750:
6734:
6731:
6730:
6713:
6709:
6707:
6704:
6703:
6686:
6682:
6674:
6671:
6670:
6654:
6651:
6650:
6633:
6629:
6627:
6624:
6623:
6620:
6598:
6593:
6592:
6590:
6587:
6586:
6570:
6567:
6566:
6550:
6547:
6546:
6530:
6527:
6526:
6495:
6492:
6491:
6475:
6472:
6471:
6454:
6449:
6448:
6446:
6443:
6442:
6425:
6421:
6419:
6416:
6415:
6398:
6394:
6386:
6383:
6382:
6358:
6354:
6345:
6341:
6329:
6318:
6306:
6303:
6302:
6282:
6278:
6272:
6268:
6256:
6245:
6224:
6221:
6220:
6204:
6201:
6200:
6177:
6173:
6152:
6148:
6139:
6135:
6133:
6130:
6129:
6100:
6096:
6072:
6068:
6051:
6048:
6047:
6020:
6009:
6007:
5977:
5967:
5963:
5951:
5940:
5919:
5916:
5915:
5907:in our vector.
5891:
5887:
5885:
5882:
5881:
5864:
5860:
5843:
5840:
5839:
5836:
5815:
5812:
5811:
5795:
5792:
5791:
5774:
5770:
5762:
5759:
5758:
5741:
5737:
5729:
5726:
5725:
5708:
5703:
5702:
5700:
5697:
5696:
5679:
5674:
5673:
5671:
5668:
5667:
5651:
5648:
5647:
5631:
5628:
5627:
5610:
5605:
5604:
5602:
5599:
5598:
5581:
5576:
5575:
5573:
5570:
5569:
5553:
5550:
5549:
5532:
5527:
5526:
5518:
5515:
5514:
5497:
5492:
5491:
5482:
5477:
5476:
5467:
5462:
5461:
5453:
5450:
5449:
5432:
5427:
5426:
5424:
5421:
5420:
5403:
5398:
5397:
5388:
5383:
5382:
5380:
5377:
5376:
5349:
5346:
5345:
5329:
5326:
5325:
5300:
5297:
5296:
5289:
5268:
5265:
5264:
5247:
5238:
5234:
5232:
5229:
5228:
5211:
5207:
5205:
5202:
5201:
5185:
5182:
5181:
5162:
5153:
5149:
5141:
5138:
5137:
5112:
5109:
5108:
5092:
5089:
5088:
5081:
5051:
5048:
5047:
5022:
5019:
5018:
4993:
4990:
4989:
4973:
4970:
4969:
4953:
4950:
4949:
4924:
4921:
4920:
4904:
4901:
4900:
4884:
4881:
4880:
4863:
4859:
4857:
4854:
4853:
4836:
4832:
4830:
4827:
4826:
4809:
4805:
4803:
4800:
4799:
4776:
4772:
4745:
4741:
4732:
4728:
4719:
4715:
4700:
4696:
4675:
4671:
4662:
4658:
4647:
4644:
4643:
4624:
4621:
4620:
4597:
4593:
4588:
4583:
4569:
4564:
4558:
4554:
4549:
4544:
4538:
4534:
4520:
4517:
4516:
4481:
4477:
4472:
4467:
4461:
4457:
4442:
4438:
4426:
4422:
4417:
4412:
4406:
4402:
4387:
4383:
4381:
4378:
4377:
4360:
4356:
4338:
4334:
4325:
4321:
4319:
4316:
4315:
4312:
4290:
4286:
4284:
4281:
4280:
4263:
4259:
4257:
4254:
4253:
4237:
4234:
4233:
4217:
4214:
4213:
4197:
4194:
4193:
4177:
4174:
4173:
4153:
4150:
4149:
4133:
4130:
4129:
4113:
4110:
4109:
4093:
4090:
4089:
4088:The commitment
4066:
4062:
4041:
4037:
4028:
4024:
4013:
4010:
4009:
3990:
3987:
3986:
3983:
3961:
3957:
3948:
3944:
3942:
3939:
3938:
3921:
3917:
3915:
3912:
3911:
3894:
3890:
3888:
3885:
3884:
3867:
3863:
3854:
3850:
3848:
3845:
3844:
3821:
3817:
3808:
3804:
3795:
3791:
3782:
3778:
3761:
3757:
3748:
3744:
3743:
3738:
3728:
3724:
3718:
3714:
3705:
3701:
3687:
3683:
3682:
3677:
3667:
3662:
3647:
3643:
3642:
3637:
3627:
3622:
3606:
3602:
3593:
3589:
3571:
3567:
3558:
3554:
3546:
3543:
3542:
3522:
3518:
3509:
3505:
3496:
3492:
3483:
3479:
3461:
3457:
3448:
3444:
3426:
3422:
3413:
3409:
3401:
3398:
3397:
3380:
3376:
3374:
3371:
3370:
3353:
3349:
3347:
3344:
3343:
3326:
3322:
3320:
3317:
3316:
3299:
3295:
3293:
3290:
3289:
3269:
3265:
3263:
3260:
3259:
3242:
3238:
3236:
3233:
3232:
3215:
3211:
3202:
3198:
3196:
3193:
3192:
3170:
3166:
3157:
3153:
3144:
3140:
3131:
3127:
3110:
3106:
3097:
3093:
3092:
3088:
3080:
3076:
3067:
3063:
3062:
3058:
3047:
3043:
3042:
3038:
3030:
3026:
3025:
3021:
3010:
3006:
3005:
3001:
2993:
2989:
2988:
2984:
2972:
2968:
2959:
2955:
2937:
2933:
2924:
2920:
2912:
2909:
2908:
2886:
2882:
2873:
2869:
2860:
2856:
2847:
2843:
2825:
2821:
2812:
2808:
2790:
2786:
2777:
2773:
2765:
2762:
2761:
2744:
2740:
2738:
2735:
2734:
2717:
2713:
2711:
2708:
2707:
2706:and randomness
2690:
2686:
2684:
2681:
2680:
2663:
2659:
2657:
2654:
2653:
2650:
2625:
2620:
2610:
2606:
2598:
2595:
2594:
2577:
2570:
2566:
2565:
2560:
2557:
2554:
2553:
2537:
2534:
2533:
2517:
2514:
2513:
2496:
2489:
2485:
2484:
2479:
2476:
2473:
2472:
2455:
2451:
2449:
2446:
2445:
2416:
2412:
2386:
2383:
2382:
2365:
2361:
2353:
2350:
2349:
2333:
2330:
2329:
2313:
2310:
2309:
2293:
2290:
2289:
2261:
2258:
2257:
2241:
2238:
2237:
2234:
2208:
2204:
2198:
2194:
2186:
2183:
2182:
2127:
2073:of prime order
2067:
1996:
1993:
1992:
1950:
1947:
1946:
1897:=1 Alice sends
1821:
1736:
1733:
1732:
1671:
1668:
1667:
1626:
1551:model. Given a
1545:
1536:
1404:has control of
1373:and then tells
1305:
1274:
1267:
1263:
1254:
1250:
1239:
1230:
1225:
1224:
1219:
1216:
1215:
1197:
1190:
1186:
1177:
1173:
1158:
1153:
1152:
1147:
1144:
1143:
1121:
1113:
1110:
1109:
1088:
1084:
1082:
1079:
1078:
1061:
1057:
1055:
1052:
1051:
1048:
1027:
1024:
1023:
1001:
981:
973:
941:
939:
936:
935:
916:
908:
905:
904:
885:
850:
842:
839:
838:
806:
803:
802:
757:
737:
728:
723:
722:
689:
684:
683:
681:
678:
677:
658:
650:
647:
646:
623:
597:
594:
593:
574:
566:
563:
562:
527:
522:
521:
519:
516:
515:
494:
490:
488:
485:
484:
477:
423:is computed as
385:
360:
327:
315:
257:
252:
208:Gilles Brassard
126:
115:
109:
106:
63:
61:
51:
39:
28:
23:
22:
15:
12:
11:
5:
11356:
11346:
11345:
11340:
11338:Secret sharing
11335:
11330:
11316:
11315:
11310:
11305:
11298:
11297:External links
11295:
11292:
11291:
11232:Optics Express
11222:
11169:
11128:
11075:
11063:
11051:
11029:
10997:
10976:
10946:
10924:
10909:
10898:
10861:
10846:
10839:
10813:
10790:
10766:
10756:
10746:
10734:
10719:
10696:
10674:Oded Goldreich
10666:
10627:
10613:Shimon Even.
10606:
10583:
10561:
10540:(2): 151–158.
10520:
10511:
10480:(3): 690–728.
10460:
10445:
10427:Oded Goldreich
10418:
10417:
10415:
10412:
10411:
10410:
10404:
10399:
10394:
10389:
10384:
10377:
10374:
10366:
10363:
10317:
10314:
10301:
10298:
10295:
10290:
10286:
10265:
10262:
10259:
10239:
10219:
10216:
10213:
10210:
10190:
10187:
10184:
10181:
10161:
10141:
10116:
10113:
10110:
10107:
10104:
10101:
10098:
10095:
10092:
10083:is, let alone
10072:
10052:
10049:
10046:
10043:
10040:
10037:
10034:
10031:
10028:
10025:
10022:
10019:
10016:
10013:
10010:
10007:
10004:
9982:
9979:
9976:
9973:
9970:
9967:
9963:
9959:
9956:
9953:
9950:
9947:
9944:
9939:
9936:
9933:
9930:
9927:
9924:
9921:
9918:
9915:
9912:
9908:
9904:
9901:
9898:
9895:
9892:
9870:
9867:
9864:
9861:
9858:
9855:
9851:
9847:
9844:
9841:
9838:
9835:
9832:
9829:
9826:
9823:
9820:
9817:
9814:
9811:
9808:
9805:
9802:
9799:
9796:
9793:
9790:
9787:
9767:
9764:
9761:
9758:
9755:
9752:
9749:
9746:
9743:
9740:
9720:
9717:
9714:
9711:
9708:
9705:
9679:
9674:
9650:
9647:
9644:
9641:
9638:
9635:
9632:
9629:
9626:
9623:
9619:
9615:
9612:
9609:
9606:
9603:
9579:
9576:
9573:
9570:
9567:
9564:
9561:
9558:
9555:
9552:
9549:
9546:
9543:
9540:
9537:
9534:
9531:
9511:
9508:
9505:
9502:
9499:
9496:
9493:
9471:
9466:
9444:
9441:
9438:
9435:
9432:
9429:
9409:
9389:
9386:
9383:
9380:
9348:
9345:
9342:
9339:
9336:
9333:
9330:
9327:
9324:
9321:
9318:
9315:
9312:
9292:
9289:
9286:
9283:
9280:
9277:
9274:
9254:
9251:
9248:
9245:
9242:
9239:
9219:
9216:
9213:
9210:
9207:
9204:
9201:
9198:
9195:
9192:
9189:
9186:
9183:
9180:
9177:
9174:
9155:elliptic curve
9140:
9135:
9111:
9106:
9084:
9081:
9078:
9058:
9055:
9052:
9049:
9038:
9035:
9034:
9021:
9001:
8981:
8970:factor theorem
8957:
8954:
8951:
8948:
8945:
8942:
8939:
8936:
8916:
8913:
8910:
8907:
8904:
8884:
8881:
8878:
8875:
8872:
8869:
8849:
8829:
8826:
8823:
8820:
8817:
8814:
8811:
8808:
8805:
8802:
8799:
8796:
8793:
8790:
8787:
8784:
8760:
8757:
8754:
8734:
8731:
8728:
8725:
8722:
8719:
8716:
8713:
8710:
8707:
8704:
8701:
8698:
8695:
8692:
8689:
8686:
8683:
8680:
8677:
8674:
8671:
8668:
8648:
8628:
8608:
8605:
8602:
8599:
8596:
8593:
8590:
8587:
8584:
8581:
8578:
8575:
8572:
8569:
8566:
8563:
8552:
8551:
8540:
8537:
8534:
8531:
8528:
8525:
8522:
8519:
8516:
8513:
8510:
8507:
8504:
8501:
8498:
8495:
8492:
8489:
8486:
8483:
8480:
8477:
8474:
8464:
8451:
8448:
8445:
8442:
8439:
8436:
8432:
8428:
8425:
8422:
8419:
8416:
8413:
8408:
8405:
8402:
8399:
8396:
8393:
8390:
8387:
8384:
8381:
8377:
8373:
8370:
8367:
8364:
8361:
8351:
8340:
8337:
8334:
8331:
8328:
8325:
8322:
8319:
8316:
8313:
8310:
8307:
8304:
8301:
8298:
8295:
8292:
8289:
8286:
8283:
8280:
8277:
8274:
8271:
8268:
8265:
8262:
8259:
8256:
8253:
8250:
8247:
8244:
8234:
8223:
8220:
8217:
8214:
8211:
8208:
8205:
8202:
8199:
8196:
8193:
8190:
8187:
8184:
8181:
8178:
8175:
8172:
8169:
8166:
8163:
8160:
8157:
8154:
8151:
8148:
8145:
8142:
8139:
8136:
8133:
8130:
8127:
8117:
8106:
8103:
8100:
8097:
8094:
8091:
8088:
8085:
8082:
8079:
8076:
8073:
8070:
8067:
8064:
8061:
8058:
8055:
8052:
8049:
8046:
8043:
8040:
8015:
8011:
8007:
8004:
8001:
7998:
7995:
7992:
7989:
7986:
7983:
7980:
7971:, and letting
7960:
7957:
7954:
7951:
7948:
7945:
7942:
7939:
7919:
7916:
7913:
7910:
7907:
7904:
7901:
7898:
7876:
7871:
7846:
7826:
7823:
7820:
7800:
7797:
7794:
7774:
7763:
7762:
7751:
7748:
7745:
7742:
7739:
7736:
7733:
7730:
7727:
7724:
7714:
7709:
7699:
7696:
7693:
7690:
7687:
7684:
7681:
7678:
7675:
7672:
7669:
7666:
7643:
7640:
7637:
7617:
7614:
7611:
7608:
7605:
7602:
7582:
7562:
7546:
7543:
7528:
7524:
7501:
7497:
7493:
7490:
7466:
7441:
7436:
7414:
7394:
7374:
7354:
7351:
7348:
7345:
7342:
7339:
7328:
7327:
7314:
7310:
7306:
7301:
7297:
7291:
7288:
7285:
7280:
7277:
7274:
7270:
7266:
7263:
7241:
7221:
7198:
7178:
7175:
7172:
7169:
7166:
7163:
7143:
7140:
7137:
7134:
7131:
7128:
7125:
7122:
7102:
7082:
7079:
7076:
7056:
7053:
7050:
7047:
7044:
7041:
7021:
7001:
6998:
6995:
6992:
6989:
6986:
6975:
6974:
6960:
6957:
6954:
6949:
6946:
6943:
6940:
6937:
6934:
6928:
6925:
6922:
6919:
6916:
6893:
6873:
6853:
6833:
6813:
6810:
6807:
6804:
6801:
6798:
6778:
6758:
6738:
6716:
6712:
6689:
6685:
6681:
6678:
6658:
6636:
6632:
6619:
6616:
6601:
6596:
6574:
6554:
6534:
6514:
6511:
6508:
6505:
6502:
6499:
6479:
6457:
6452:
6428:
6424:
6401:
6397:
6393:
6390:
6375:
6374:
6361:
6357:
6353:
6348:
6344:
6338:
6335:
6332:
6327:
6324:
6321:
6317:
6313:
6310:
6285:
6281:
6275:
6271:
6265:
6262:
6259:
6254:
6251:
6248:
6244:
6240:
6237:
6234:
6231:
6228:
6208:
6186:
6183:
6180:
6176:
6172:
6169:
6166:
6163:
6160:
6155:
6151:
6147:
6142:
6138:
6117:
6114:
6111:
6108:
6103:
6099:
6095:
6092:
6089:
6086:
6083:
6080:
6075:
6071:
6067:
6064:
6061:
6058:
6055:
6044:
6043:
6029:
6026:
6023:
6018:
6015:
6012:
6004:
6001:
5998:
5995:
5992:
5989:
5986:
5983:
5980:
5976:
5970:
5966:
5960:
5957:
5954:
5949:
5946:
5943:
5939:
5935:
5932:
5929:
5926:
5923:
5894:
5890:
5867:
5863:
5859:
5856:
5853:
5850:
5847:
5835:
5832:
5819:
5799:
5777:
5773:
5769:
5766:
5744:
5740:
5736:
5733:
5711:
5706:
5682:
5677:
5655:
5635:
5613:
5608:
5584:
5579:
5557:
5535:
5530:
5525:
5522:
5500:
5495:
5490:
5485:
5480:
5475:
5470:
5465:
5460:
5457:
5435:
5430:
5406:
5401:
5396:
5391:
5386:
5353:
5333:
5313:
5310:
5307:
5304:
5288:
5287:KZG commitment
5285:
5272:
5250:
5246:
5241:
5237:
5214:
5210:
5189:
5169:
5165:
5161:
5156:
5152:
5148:
5145:
5125:
5122:
5119:
5116:
5096:
5080:
5077:
5064:
5061:
5058:
5055:
5035:
5032:
5029:
5026:
5006:
5003:
5000:
4997:
4977:
4957:
4937:
4934:
4931:
4928:
4908:
4888:
4866:
4862:
4839:
4835:
4812:
4808:
4796:
4795:
4784:
4779:
4775:
4771:
4768:
4765:
4762:
4759:
4754:
4751:
4748:
4744:
4740:
4735:
4731:
4727:
4722:
4718:
4714:
4709:
4706:
4703:
4699:
4695:
4692:
4689:
4686:
4683:
4678:
4674:
4670:
4665:
4661:
4657:
4654:
4651:
4628:
4617:
4616:
4605:
4600:
4596:
4591:
4586:
4582:
4579:
4576:
4572:
4567:
4561:
4557:
4552:
4547:
4541:
4537:
4533:
4530:
4527:
4524:
4501:
4498:
4495:
4492:
4489:
4484:
4480:
4475:
4470:
4464:
4460:
4456:
4453:
4450:
4445:
4441:
4437:
4434:
4429:
4425:
4420:
4415:
4409:
4405:
4401:
4398:
4395:
4390:
4386:
4363:
4359:
4355:
4352:
4349:
4346:
4341:
4337:
4333:
4328:
4324:
4311:
4310:Vector hashing
4308:
4293:
4289:
4266:
4262:
4241:
4221:
4201:
4181:
4157:
4137:
4117:
4097:
4086:
4085:
4074:
4069:
4065:
4061:
4058:
4055:
4052:
4049:
4044:
4040:
4036:
4031:
4027:
4023:
4020:
4017:
3994:
3982:
3981:Partial reveal
3979:
3964:
3960:
3956:
3951:
3947:
3924:
3920:
3897:
3893:
3870:
3866:
3862:
3857:
3853:
3829:
3824:
3820:
3816:
3811:
3807:
3803:
3798:
3794:
3790:
3785:
3781:
3777:
3774:
3771:
3764:
3760:
3756:
3751:
3747:
3741:
3737:
3731:
3727:
3721:
3717:
3713:
3708:
3704:
3700:
3697:
3690:
3686:
3680:
3676:
3670:
3665:
3661:
3657:
3650:
3646:
3640:
3636:
3630:
3625:
3621:
3617:
3614:
3609:
3605:
3601:
3596:
3592:
3588:
3585:
3582:
3579:
3574:
3570:
3566:
3561:
3557:
3553:
3550:
3530:
3525:
3521:
3517:
3512:
3508:
3504:
3499:
3495:
3491:
3486:
3482:
3478:
3475:
3472:
3469:
3464:
3460:
3456:
3451:
3447:
3443:
3440:
3437:
3434:
3429:
3425:
3421:
3416:
3412:
3408:
3405:
3383:
3379:
3356:
3352:
3329:
3325:
3302:
3298:
3272:
3268:
3245:
3241:
3218:
3214:
3210:
3205:
3201:
3178:
3173:
3169:
3165:
3160:
3156:
3152:
3147:
3143:
3139:
3134:
3130:
3126:
3123:
3120:
3113:
3109:
3105:
3100:
3096:
3091:
3083:
3079:
3075:
3070:
3066:
3061:
3057:
3050:
3046:
3041:
3033:
3029:
3024:
3020:
3013:
3009:
3004:
2996:
2992:
2987:
2983:
2980:
2975:
2971:
2967:
2962:
2958:
2954:
2951:
2948:
2945:
2940:
2936:
2932:
2927:
2923:
2919:
2916:
2894:
2889:
2885:
2881:
2876:
2872:
2868:
2863:
2859:
2855:
2850:
2846:
2842:
2839:
2836:
2833:
2828:
2824:
2820:
2815:
2811:
2807:
2804:
2801:
2798:
2793:
2789:
2785:
2780:
2776:
2772:
2769:
2747:
2743:
2720:
2716:
2693:
2689:
2666:
2662:
2649:
2646:
2628:
2623:
2619:
2613:
2609:
2605:
2602:
2580:
2573:
2569:
2563:
2541:
2521:
2499:
2492:
2488:
2482:
2458:
2454:
2433:
2430:
2427:
2424:
2419:
2415:
2411:
2408:
2405:
2402:
2399:
2396:
2393:
2390:
2368:
2364:
2360:
2357:
2337:
2317:
2297:
2277:
2274:
2271:
2268:
2265:
2245:
2236:Alice selects
2233:
2230:
2211:
2207:
2201:
2197:
2193:
2190:
2104:and publishes
2066:
2063:
2000:
1954:
1923:
1922:
1891:
1868:
1820:
1817:
1740:
1731:to Bob, where
1729:
1728:
1717:
1714:
1711:
1708:
1705:
1702:
1699:
1696:
1693:
1690:
1687:
1684:
1681:
1678:
1675:
1625:
1622:
1544:
1541:
1535:
1532:
1514:, who outputs
1346:, which sends
1304:
1301:
1277:
1273:
1270:
1266:
1262:
1257:
1253:
1249:
1245:
1242:
1238:
1233:
1223:
1200:
1196:
1193:
1189:
1185:
1180:
1176:
1172:
1169:
1166:
1161:
1151:
1127:
1124:
1120:
1117:
1091:
1087:
1064:
1060:
1047:
1044:
1031:
1011:
1007:
1004:
1000:
997:
994:
991:
987:
984:
980:
972:
969:
966:
963:
960:
957:
954:
951:
948:
922:
919:
915:
912:
891:
888:
884:
881:
878:
875:
872:
869:
866:
863:
860:
856:
853:
849:
846:
822:
819:
816:
813:
810:
767:
763:
760:
756:
753:
750:
747:
743:
740:
736:
731:
721:
718:
715:
712:
709:
706:
703:
700:
697:
692:
664:
661:
657:
654:
629:
626:
622:
619:
616:
613:
610:
607:
604:
601:
580:
577:
573:
570:
530:
497:
493:
476:
473:
453:Commit(x,open)
384:
381:
375:protocols for
372:secret sharing
359:
356:
326:
323:
314:
311:
302:
301:
298:
295:
292:
289:
277:
276:
273:
270:
256:
253:
251:
248:
216:Claude Crépeau
189:the commitment
181:
180:
173:
128:
127:
42:
40:
33:
26:
9:
6:
4:
3:
2:
11355:
11344:
11341:
11339:
11336:
11334:
11331:
11329:
11326:
11325:
11323:
11314:
11311:
11309:
11306:
11304:
11301:
11300:
11287:
11283:
11279:
11275:
11271:
11267:
11263:
11259:
11255:
11251:
11246:
11241:
11237:
11233:
11226:
11218:
11214:
11210:
11206:
11201:
11200:1721.1/103985
11196:
11192:
11188:
11184:
11180:
11173:
11164:
11159:
11155:
11151:
11148:(1): 011303.
11147:
11143:
11139:
11132:
11124:
11120:
11116:
11112:
11108:
11104:
11099:
11094:
11090:
11086:
11079:
11073:
11067:
11061:
11055:
11047:
11040:
11033:
11019:on 2014-12-22
11015:
11008:
11001:
10993:
10986:
10979:
10973:
10969:
10965:
10961:
10957:
10950:
10942:
10935:
10928:
10920:
10913:
10907:
10902:
10883:
10879:
10872:
10865:
10857:
10850:
10842:
10836:
10832:
10828:
10824:
10817:
10801:
10794:
10779:
10778:
10770:
10764:Cryptography.
10760:
10754:Cryptography.
10750:
10744:
10738:
10731:. 1998, June.
10730:
10723:
10716:
10712:
10711:
10706:
10705:Hugo Krawczyk
10700:
10693:
10690:
10688:
10683:
10682:Avi Wigderson
10679:
10678:Silvio Micali
10675:
10670:
10663:
10659:
10655:
10654:
10649:
10645:
10641:
10637:
10631:
10624:
10620:
10616:
10610:
10603:
10599:
10595:
10594:
10590:Manuel Blum,
10587:
10580:
10576:
10575:
10568:
10566:
10557:
10553:
10548:
10543:
10539:
10535:
10531:
10524:
10515:
10507:
10503:
10498:
10493:
10488:
10483:
10479:
10475:
10471:
10464:
10457:
10456:
10449:
10442:
10441:0-521-79172-3
10438:
10434:
10433:
10428:
10423:
10419:
10408:
10405:
10403:
10400:
10398:
10395:
10393:
10390:
10388:
10385:
10383:
10380:
10379:
10373:
10371:
10362:
10360:
10356:
10352:
10346:
10344:
10338:
10336:
10332:
10327:
10323:
10313:
10299:
10296:
10293:
10288:
10284:
10276:we divide by
10263:
10260:
10257:
10237:
10214:
10208:
10185:
10179:
10159:
10139:
10128:
10111:
10108:
10105:
10096:
10090:
10070:
10050:
10047:
10041:
10035:
10032:
10026:
10023:
10020:
10014:
10008:
10002:
9980:
9977:
9971:
9965:
9957:
9954:
9951:
9945:
9942:
9934:
9931:
9928:
9922:
9916:
9910:
9902:
9899:
9896:
9890:
9868:
9865:
9859:
9853:
9845:
9842:
9839:
9833:
9830:
9824:
9821:
9815:
9812:
9806:
9800:
9794:
9791:
9785:
9762:
9759:
9756:
9750:
9744:
9738:
9715:
9712:
9709:
9703:
9695:
9677:
9645:
9642:
9639:
9633:
9627:
9621:
9613:
9610:
9607:
9601:
9593:
9571:
9568:
9565:
9559:
9556:
9553:
9547:
9541:
9538:
9535:
9529:
9522:. We compute
9506:
9503:
9500:
9494:
9491:
9469:
9439:
9433:
9430:
9427:
9407:
9384:
9378:
9370:
9366:
9362:
9340:
9337:
9334:
9325:
9319:
9313:
9310:
9287:
9284:
9281:
9275:
9272:
9249:
9243:
9240:
9237:
9217:
9214:
9208:
9202:
9199:
9193:
9190:
9187:
9178:
9172:
9164:
9160:
9156:
9138:
9109:
9082:
9079:
9076:
9053:
9047:
9033:
9019:
8999:
8979:
8971:
8955:
8952:
8949:
8946:
8940:
8934:
8911:
8908:
8905:
8882:
8879:
8873:
8867:
8847:
8827:
8824:
8818:
8812:
8809:
8803:
8800:
8797:
8788:
8782:
8774:
8758:
8755:
8752:
8729:
8726:
8720:
8714:
8708:
8705:
8696:
8693:
8690:
8684:
8678:
8672:
8666:
8646:
8626:
8606:
8603:
8597:
8591:
8588:
8582:
8579:
8576:
8567:
8561:
8535:
8532:
8526:
8520:
8514:
8511:
8502:
8499:
8496:
8490:
8484:
8478:
8472:
8465:
8449:
8446:
8440:
8434:
8426:
8423:
8420:
8414:
8411:
8403:
8400:
8397:
8391:
8385:
8379:
8371:
8368:
8365:
8359:
8352:
8335:
8332:
8326:
8323:
8317:
8311:
8305:
8302:
8296:
8293:
8284:
8281:
8278:
8272:
8269:
8266:
8260:
8254:
8251:
8248:
8242:
8235:
8218:
8215:
8212:
8209:
8206:
8203:
8197:
8191:
8188:
8185:
8179:
8176:
8170:
8167:
8164:
8161:
8158:
8155:
8152:
8149:
8143:
8137:
8134:
8131:
8125:
8118:
8101:
8098:
8095:
8092:
8089:
8086:
8083:
8077:
8074:
8068:
8065:
8062:
8059:
8056:
8053:
8050:
8047:
8044:
8038:
8031:
8030:
8029:
8013:
8005:
8002:
7999:
7993:
7990:
7984:
7978:
7958:
7955:
7949:
7943:
7940:
7937:
7917:
7914:
7908:
7902:
7899:
7896:
7874:
7858:
7844:
7824:
7821:
7818:
7798:
7795:
7792:
7772:
7746:
7743:
7740:
7737:
7734:
7731:
7728:
7722:
7712:
7707:
7694:
7691:
7688:
7685:
7682:
7679:
7676:
7673:
7670:
7664:
7657:
7656:
7655:
7641:
7638:
7635:
7615:
7612:
7606:
7600:
7580:
7560:
7552:
7542:
7526:
7522:
7499:
7495:
7491:
7488:
7480:
7464:
7455:
7439:
7412:
7392:
7372:
7349:
7343:
7340:
7337:
7312:
7308:
7304:
7299:
7295:
7289:
7286:
7283:
7278:
7275:
7272:
7268:
7264:
7261:
7254:
7253:
7252:
7239:
7219:
7210:
7196:
7176:
7173:
7167:
7161:
7141:
7138:
7135:
7132:
7126:
7120:
7100:
7080:
7077:
7074:
7054:
7051:
7045:
7039:
7032:exists, then
7019:
7012:, because if
6999:
6996:
6990:
6984:
6958:
6955:
6952:
6947:
6944:
6938:
6932:
6926:
6920:
6914:
6907:
6906:
6905:
6891:
6871:
6851:
6831:
6811:
6808:
6802:
6796:
6776:
6756:
6736:
6714:
6710:
6687:
6683:
6679:
6676:
6656:
6634:
6630:
6615:
6599:
6572:
6552:
6532:
6509:
6503:
6500:
6497:
6477:
6455:
6426:
6422:
6399:
6395:
6391:
6388:
6380:
6359:
6355:
6351:
6346:
6342:
6336:
6333:
6330:
6325:
6322:
6319:
6315:
6311:
6308:
6301:
6300:
6299:
6283:
6279:
6273:
6269:
6263:
6260:
6257:
6252:
6249:
6246:
6242:
6238:
6232:
6226:
6206:
6184:
6181:
6178:
6174:
6170:
6167:
6164:
6161:
6158:
6153:
6149:
6145:
6140:
6136:
6115:
6112:
6109:
6106:
6101:
6097:
6093:
6087:
6081:
6078:
6073:
6069:
6065:
6059:
6053:
6027:
6024:
6021:
6016:
6013:
6010:
6002:
5999:
5996:
5993:
5990:
5987:
5984:
5981:
5978:
5974:
5968:
5964:
5958:
5955:
5952:
5947:
5944:
5941:
5937:
5933:
5927:
5921:
5914:
5913:
5912:
5910:
5892:
5888:
5865:
5861:
5857:
5851:
5845:
5831:
5817:
5797:
5775:
5771:
5767:
5764:
5742:
5738:
5734:
5731:
5709:
5680:
5653:
5633:
5611:
5582:
5555:
5533:
5523:
5520:
5498:
5483:
5473:
5468:
5458:
5455:
5433:
5404:
5394:
5389:
5374:
5370:
5365:
5351:
5331:
5308:
5302:
5294:
5284:
5270:
5248:
5244:
5239:
5235:
5212:
5208:
5187:
5163:
5159:
5154:
5150:
5143:
5120:
5114:
5094:
5086:
5076:
5059:
5053:
5030:
5024:
5001:
4995:
4975:
4955:
4932:
4926:
4906:
4886:
4864:
4860:
4837:
4833:
4810:
4806:
4777:
4773:
4769:
4766:
4763:
4760:
4757:
4752:
4749:
4746:
4742:
4738:
4733:
4729:
4725:
4720:
4716:
4712:
4707:
4704:
4701:
4697:
4693:
4690:
4687:
4684:
4681:
4676:
4672:
4668:
4663:
4659:
4655:
4652:
4642:
4641:
4640:
4626:
4598:
4594:
4580:
4577:
4574:
4559:
4555:
4539:
4535:
4528:
4525:
4522:
4515:
4514:
4513:
4499:
4496:
4493:
4490:
4482:
4478:
4462:
4458:
4451:
4448:
4443:
4439:
4435:
4427:
4423:
4407:
4403:
4396:
4393:
4388:
4384:
4361:
4357:
4353:
4350:
4347:
4344:
4339:
4335:
4331:
4326:
4322:
4307:
4291:
4287:
4264:
4260:
4239:
4219:
4199:
4179:
4171:
4155:
4135:
4115:
4095:
4067:
4063:
4059:
4056:
4053:
4050:
4047:
4042:
4038:
4034:
4029:
4025:
4018:
4015:
4008:
4007:
4006:
3992:
3978:
3962:
3958:
3954:
3949:
3945:
3922:
3918:
3895:
3891:
3868:
3864:
3860:
3855:
3851:
3841:
3822:
3818:
3814:
3809:
3805:
3801:
3796:
3792:
3788:
3783:
3779:
3772:
3769:
3762:
3758:
3754:
3749:
3745:
3739:
3735:
3729:
3719:
3715:
3711:
3706:
3702:
3695:
3688:
3684:
3678:
3674:
3668:
3663:
3659:
3655:
3648:
3644:
3638:
3634:
3628:
3623:
3619:
3615:
3607:
3603:
3599:
3594:
3590:
3583:
3580:
3572:
3568:
3564:
3559:
3555:
3548:
3523:
3519:
3515:
3510:
3506:
3502:
3497:
3493:
3489:
3484:
3480:
3473:
3470:
3462:
3458:
3454:
3449:
3445:
3438:
3435:
3427:
3423:
3419:
3414:
3410:
3403:
3381:
3377:
3354:
3350:
3327:
3323:
3300:
3296:
3286:
3270:
3266:
3243:
3239:
3216:
3212:
3208:
3203:
3199:
3189:
3171:
3167:
3163:
3158:
3154:
3150:
3145:
3141:
3137:
3132:
3128:
3121:
3118:
3111:
3107:
3103:
3098:
3094:
3089:
3081:
3077:
3073:
3068:
3064:
3059:
3055:
3048:
3044:
3039:
3031:
3027:
3022:
3018:
3011:
3007:
3002:
2994:
2990:
2985:
2981:
2973:
2969:
2965:
2960:
2956:
2949:
2946:
2938:
2934:
2930:
2925:
2921:
2914:
2906:
2887:
2883:
2879:
2874:
2870:
2866:
2861:
2857:
2853:
2848:
2844:
2837:
2834:
2826:
2822:
2818:
2813:
2809:
2802:
2799:
2791:
2787:
2783:
2778:
2774:
2767:
2745:
2741:
2718:
2714:
2691:
2687:
2664:
2660:
2645:
2642:
2626:
2621:
2617:
2611:
2607:
2603:
2600:
2578:
2571:
2567:
2539:
2519:
2497:
2490:
2486:
2456:
2452:
2431:
2428:
2417:
2413:
2406:
2403:
2400:
2394:
2391:
2388:
2366:
2362:
2358:
2355:
2335:
2315:
2295:
2275:
2272:
2269:
2266:
2263:
2243:
2229:
2225:
2209:
2205:
2199:
2195:
2191:
2188:
2180:
2176:
2172:
2168:
2164:
2159:
2157:
2153:
2149:
2144:
2142:
2138:
2134:
2130:
2123:
2119:
2115:
2111:
2107:
2103:
2099:
2095:
2091:
2087:
2082:
2080:
2076:
2072:
2062:
2060:
2056:
2051:
2049:
2045:
2041:
2037:
2033:
2029:
2025:
2021:
2017:
2013:
1998:
1990:
1986:
1982:
1978:
1974:
1969:
1967:
1952:
1944:
1940:
1936:
1932:
1928:
1920:
1916:
1912:
1908:
1904:
1900:
1896:
1892:
1889:
1885:
1881:
1877:
1873:
1869:
1866:
1862:
1858:
1854:
1853:
1852:
1850:
1846:
1842:
1838:
1834:
1830:
1825:
1816:
1814:
1810:
1806:
1802:
1798:
1794:
1790:
1786:
1782:
1778:
1774:
1770:
1766:
1762:
1758:
1754:
1751:denotes XOR,
1738:
1709:
1703:
1700:
1697:
1694:
1688:
1682:
1679:
1676:
1666:
1665:
1664:
1662:
1658:
1654:
1650:
1645:
1643:
1639:
1635:
1631:
1621:
1618:
1614:
1610:
1606:
1602:
1598:
1594:
1590:
1586:
1582:
1578:
1574:
1570:
1566:
1563:-bit message
1562:
1558:
1554:
1553:hash function
1550:
1549:random oracle
1540:
1531:
1529:
1525:
1521:
1517:
1513:
1509:
1505:
1501:
1497:
1492:
1490:
1486:
1482:
1479:are fed into
1478:
1474:
1470:
1466:
1462:
1457:
1455:
1451:
1447:
1443:
1440:will open to
1439:
1435:
1431:
1427:
1423:
1419:
1415:
1411:
1407:
1403:
1399:
1394:
1392:
1388:
1384:
1380:
1376:
1372:
1368:
1364:
1360:
1355:
1353:
1349:
1345:
1341:
1337:
1333:
1329:
1325:
1321:
1316:
1314:
1310:
1300:
1298:
1294:
1271:
1268:
1255:
1251:
1247:
1243:
1240:
1231:
1194:
1191:
1178:
1174:
1170:
1167:
1159:
1142:
1125:
1122:
1118:
1115:
1107:
1089:
1085:
1062:
1058:
1043:
1029:
1005:
1002:
998:
995:
992:
989:
985:
982:
970:
964:
961:
958:
955:
952:
949:
920:
917:
913:
910:
889:
886:
882:
879:
876:
873:
870:
867:
864:
861:
858:
854:
851:
847:
844:
836:
817:
814:
811:
800:
796:
792:
787:
785:
781:
761:
758:
754:
751:
748:
745:
741:
738:
729:
719:
713:
710:
707:
704:
701:
698:
690:
662:
659:
655:
652:
644:
627:
624:
620:
617:
614:
611:
608:
605:
602:
599:
578:
575:
571:
568:
560:
557:
554:Then for all
552:
550:
546:
528:
513:
495:
491:
482:
472:
470:
466:
462:
458:
454:
449:
445:
440:
438:
434:
430:
426:
422:
418:
413:
411:
407:
403:
399:
395:
391:
380:
378:
373:
369:
365:
355:
353:
347:
344:
341:, publishing
340:
336:
332:
322:
320:
310:
306:
299:
296:
293:
290:
287:
283:
282:
281:
274:
271:
268:
267:
266:
264:
263:
262:coin flipping
255:Coin flipping
247:
245:
241:
237:
233:
229:
225:
221:
217:
213:
209:
204:
202:
198:
194:
190:
185:
178:
174:
171:
167:
166:
165:
162:
158:
156:
152:
148:
144:
139:
135:
124:
121:
113:
102:
99:
95:
92:
88:
85:
81:
78:
74:
71: –
70:
66:
65:Find sources:
59:
55:
49:
48:
43:This article
41:
37:
32:
31:
19:
11235:
11231:
11225:
11185:(1): 17–28.
11182:
11178:
11172:
11145:
11141:
11131:
11088:
11084:
11078:
11066:
11054:
11045:
11032:
11021:. Retrieved
11014:the original
11000:
10991:
10959:
10949:
10940:
10927:
10921:. CRC press.
10918:
10912:
10901:
10889:. Retrieved
10882:the original
10877:
10864:
10855:
10849:
10822:
10816:
10805:. Retrieved
10793:
10782:, retrieved
10776:
10769:
10759:
10749:
10737:
10728:
10722:
10708:
10699:
10685:
10669:
10651:
10643:
10640:Mental Poker
10636:R. L. Rivest
10630:
10622:
10619:Allen Gersho
10614:
10609:
10591:
10586:
10572:
10537:
10533:
10523:
10514:
10477:
10473:
10463:
10453:
10448:
10430:
10422:
10397:Web of trust
10368:
10347:
10339:
10325:
10319:
10131:
9153:might be an
9039:
8553:
7859:
7764:
7548:
7456:
7329:
7211:
6976:
6621:
6376:
6219:, such that
6045:
5837:
5373:Tate pairing
5366:
5290:
5082:
4797:
4618:
4313:
4087:
3984:
3842:
3541:. Formally:
3287:
3190:
2907:
2905:. Formally:
2651:
2643:
2235:
2226:
2178:
2174:
2170:
2162:
2160:
2155:
2145:
2140:
2136:
2135:, such that
2132:
2125:
2121:
2117:
2113:
2105:
2101:
2097:
2093:
2089:
2085:
2083:
2078:
2074:
2068:
2058:
2054:
2052:
2047:
2043:
2039:
2035:
2031:
2027:
2023:
2019:
2015:
2011:
1988:
1984:
1980:
1976:
1975:, such that
1972:
1970:
1965:
1942:
1938:
1934:
1930:
1926:
1924:
1918:
1914:
1910:
1907:exclusive-or
1902:
1898:
1894:
1887:
1883:
1882:-bit vector
1879:
1875:
1874:-bit vector
1871:
1864:
1860:
1859:-bit vector
1856:
1848:
1844:
1840:
1836:
1832:
1826:
1822:
1812:
1808:
1804:
1800:
1796:
1792:
1788:
1784:
1780:
1776:
1772:
1768:
1764:
1760:
1756:
1752:
1730:
1660:
1656:
1652:
1648:
1646:
1627:
1616:
1612:
1608:
1604:
1600:
1599:such that H(
1596:
1592:
1591:exist where
1588:
1584:
1580:
1576:
1572:
1568:
1564:
1560:
1556:
1546:
1537:
1534:Construction
1527:
1523:
1519:
1515:
1511:
1507:
1503:
1499:
1495:
1493:
1488:
1484:
1480:
1476:
1472:
1468:
1464:
1460:
1458:
1453:
1449:
1448:can extract
1445:
1441:
1437:
1433:
1429:
1425:
1421:
1417:
1413:
1409:
1405:
1401:
1397:
1395:
1390:
1386:
1382:
1378:
1374:
1370:
1366:
1362:
1358:
1356:
1351:
1347:
1343:
1339:
1335:
1331:
1327:
1326:sends value
1323:
1319:
1317:
1312:
1306:
1105:
1049:
834:
798:
788:
783:
642:
561:that output
553:
544:
511:
480:
478:
468:
464:
460:
456:
452:
441:
436:
432:
428:
424:
420:
416:
414:
409:
405:
401:
397:
393:
386:
361:
348:
339:data packets
333:scheme is a
328:
316:
307:
303:
288:to her call,
285:
278:
260:
258:
250:Applications
235:
205:
200:
196:
192:
188:
186:
182:
177:reveal phase
176:
170:commit phase
169:
163:
159:
142:
133:
131:
116:
110:October 2014
107:
97:
90:
83:
76:
64:
52:Please help
47:verification
44:
10780:, p. 2
10634:A. Shamir,
9592:bilinearity
8968:due to the
6379:dot product
5626:), and let
5085:Merkle tree
5079:Merkle tree
4252:other than
2022:. However,
1571:bit string
1467:, corrupts
1313:extractable
1291:are equal,
1022:is at most
837:and output
556:non-uniform
419:to a value
402:CheckReveal
398:CheckReveal
228:Shimon Even
224:Manuel Blum
212:David Chaum
203:property).
197:the opening
11322:Categories
11245:1909.13094
11023:2013-11-20
10891:2 February
10807:2014-06-07
10784:26 October
10574:Commitment
10414:References
10152:values of
2348:such that
2256:such that
1863:and sends
1555:H with a 3
286:commitment
232:Adi Shamir
80:newspapers
11286:203593129
11270:1094-4087
11209:2190-8516
11070:A. Kent:
10482:CiteSeerX
10297:−
10285:∏
10261:−
10109:−
10048:−
10024:−
10015:⋅
9978:−
9932:−
9923:⋅
9866:−
9813:−
9795:⋅
9760:−
9751:⋅
9643:−
9634:⋅
9569:−
9560:⋅
9539:⋅
9504:−
9495:⋅
9431:⋅
9338:−
9314:⋅
9285:−
9276:⋅
9241:⋅
9215:−
9191:−
9080:−
8947:−
8909:−
8880:−
8825:−
8801:−
8727:−
8709:τ
8694:−
8685:⋅
8667:τ
8604:−
8580:−
8533:−
8515:τ
8500:−
8491:⋅
8473:τ
8447:−
8401:−
8392:⋅
8324:−
8306:⋅
8282:−
8273:⋅
8252:⋅
8210:⋅
8204:−
8189:⋅
8168:⋅
8162:−
8156:⋅
8135:⋅
8093:⋅
8087:−
8066:⋅
8060:−
8054:⋅
8045:π
7979:τ
7956:⋅
7915:⋅
7897:π
7822:⋅
7796:⋅
7738:⋅
7732:−
7692:⋅
7686:−
7680:⋅
7671:π
7639:−
7613:−
7561:π
7492:⋅
7341:⋅
7287:−
7269:∑
7262:π
7240:π
7133:−
7078:−
7052:−
6956:−
6945:−
6501:⋅
6392:⋅
6334:−
6316:∑
6261:−
6243:∑
6182:−
6025:−
6014:−
6000:≠
5982:≤
5975:∏
5956:−
5938:∑
5768:⋅
5735:⋅
5524:∈
5489:→
5474:×
5245:
5160:
4705:−
3955:⋅
3861:⋅
3789:⋅
3712:⋅
3656:⋅
3581:⋅
3490:⋅
3436:⋅
3019:⋅
2947:⋅
2800:⋅
2579:∗
2498:∗
2407:ϕ
2273:⋅
2131:<>
1999:⊕
1953:⊕
1867:to Alice.
1843:bits to 3
1779:). Since
1739:⊕
1701:⊕
1634:injective
1444:, unless
1338:. Later,
1272:∈
1195:∈
1119:≠
1030:ϵ
914:≠
818:ϵ
656:≠
11278:31684673
11217:15713318
10556:15002247
10429:(2001).
10407:Anagrams
10402:Zerocoin
10376:See also
10353:but not
6441:. Since
2288:, where
2165:under a
1791:) from
1632:that is
1420:to tell
1400:. Here,
1244:′
1126:′
1006:′
986:′
921:′
890:′
855:′
762:′
742:′
663:′
628:′
579:′
11250:Bibcode
11150:Bibcode
11123:8823466
11103:Bibcode
10650:, ed.,
10621:, ed.,
10506:2389804
9420:to get
9369:pairing
7551:pairing
5369:pairing
2152:IND-CPA
1921:to Bob.
370:. In a
201:binding
143:binding
94:scholar
11284:
11276:
11268:
11215:
11207:
11121:
10974:
10837:
10680:, and
10660:
10598:CRYPTO
10554:
10504:
10484:
10439:
9484:, so,
8775:). If
7765:where
7720:
7701:
7545:Verify
6618:Reveal
6128:. Let
5834:Commit
5513:. Let
2108:. The
2030:) and
1917:) and
1839:takes
1607:) = H(
1520:m' = m
1379:π
1359:π
1227:Commit
1155:Commit
975:Commit
943:Commit
799:Commit
725:Commit
686:Commit
524:Commit
410:Commit
406:Commit
394:Commit
352:hashes
230:, and
214:, and
193:hiding
153:, and
96:
89:
82:
75:
67:
11282:S2CID
11240:arXiv
11213:S2CID
11119:S2CID
11093:arXiv
11042:(PDF)
11017:(PDF)
11010:(PDF)
10988:(PDF)
10937:(PDF)
10885:(PDF)
10874:(PDF)
10552:S2CID
10502:S2CID
8927:, so
7113:, so
6844:from
6649:when
4825:from
2552:from
2088:from
1937:) or
1295:, or
778:is a
427:with
136:is a
101:JSTOR
87:books
11274:PMID
11266:ISSN
11205:ISSN
10972:ISBN
10893:2019
10835:ISBN
10786:2015
10658:ISBN
10437:ISBN
9265:and
7930:and
5988:<
5757:and
5695:and
5646:and
5597:and
4852:and
3910:and
3369:and
3315:and
3258:and
2733:and
2679:and
2381:and
2359:>
2308:and
2071:ring
1983:) =
1753:i.e.
1647:Let
1214:and
1139:the
1050:Let
934:and
676:and
592:and
481:open
479:Let
461:open
459:and
446:and
429:open
396:and
329:The
175:the
168:the
141:are
73:news
11258:doi
11195:hdl
11187:doi
11158:doi
11111:doi
10964:doi
10827:doi
10646:In
10617:In
10542:doi
10492:doi
10324:if
9069:by
8639:or
7425:of
6904:as
5236:log
5151:log
4168:in
2092:to
1909:of
1893:If
1350:to
1330:to
801:is
782:in
240:bit
56:by
11324::
11280:.
11272:.
11264:.
11256:.
11248:.
11236:27
11234:.
11211:.
11203:.
11193:.
11181:.
11156:.
11144:.
11140:.
11117:.
11109:.
11101:.
11089:83
11087:.
11044:.
10990:.
10970:.
10958:.
10939:.
10876:.
10833:.
10713:,
10707:,
10684:,
10676:,
10564:^
10550:.
10536:.
10532:.
10500:.
10490:.
10478:38
10476:.
10472:.
10337:.
10127:.
9032:.
7857:.
7541:.
7454:.
6614:.
5283:.
3977:.
3840:.
2641:.
2224:.
2139:=
2100:=
2081:.
2061:.
2048:Y'
2036:Y'
2020:Y'
1991:)
1981:Y'
1973:Y'
1968:.
1945:)
1890:).
1851::
1611:||
1605:m′
1603:||
1601:R′
1595:≠
1593:m′
1589:m′
1587:,
1585:R′
1579:||
1516:m′
1508:m′
1491:.
1354:.
1299:.
1042:.
786:.
551:.
471:.
439:.
226:,
220:NP
210:,
157:.
132:A
11288:.
11260::
11252::
11242::
11219:.
11197::
11189::
11183:3
11166:.
11160::
11152::
11146:6
11125:.
11113::
11105::
11095::
11048:.
11026:.
10994:.
10980:.
10966::
10943:.
10895:.
10843:.
10829::
10810:.
10689:,
10656:(
10644:.
10642:"
10604:.
10558:.
10544::
10538:4
10508:.
10494::
10443:.
10300:i
10294:x
10289:i
10264:i
10258:x
10238:y
10218:)
10215:k
10212:(
10209:O
10189:)
10186:1
10183:(
10180:O
10160:X
10140:k
10115:)
10112:i
10106:t
10103:(
10100:)
10097:t
10094:(
10091:q
10071:t
10051:y
10045:)
10042:t
10039:(
10036:p
10033:=
10030:)
10027:i
10021:t
10018:(
10012:)
10009:t
10006:(
10003:q
9981:y
9975:)
9972:t
9969:(
9966:p
9962:)
9958:H
9955:,
9952:G
9949:(
9946:e
9943:=
9938:)
9935:i
9929:t
9926:(
9920:)
9917:t
9914:(
9911:q
9907:)
9903:H
9900:,
9897:G
9894:(
9891:e
9869:y
9863:)
9860:t
9857:(
9854:p
9850:)
9846:H
9843:,
9840:G
9837:(
9834:e
9831:=
9828:)
9825:H
9822:,
9819:)
9816:y
9810:)
9807:t
9804:(
9801:p
9798:(
9792:G
9789:(
9786:e
9766:)
9763:i
9757:t
9754:(
9748:)
9745:t
9742:(
9739:q
9719:)
9716:H
9713:,
9710:G
9707:(
9704:e
9678:T
9673:G
9649:)
9646:i
9640:t
9637:(
9631:)
9628:t
9625:(
9622:q
9618:)
9614:H
9611:,
9608:G
9605:(
9602:e
9578:)
9575:)
9572:i
9566:t
9563:(
9557:H
9554:,
9551:)
9548:t
9545:(
9542:q
9536:G
9533:(
9530:e
9510:)
9507:i
9501:t
9498:(
9492:H
9470:2
9465:G
9443:)
9440:x
9437:(
9434:q
9428:G
9408:G
9388:)
9385:x
9382:(
9379:q
9347:)
9344:)
9341:i
9335:x
9332:(
9329:)
9326:x
9323:(
9320:q
9317:(
9311:G
9291:)
9288:i
9282:x
9279:(
9273:G
9253:)
9250:x
9247:(
9244:q
9238:G
9218:y
9212:)
9209:x
9206:(
9203:p
9200:=
9197:)
9194:i
9188:x
9185:(
9182:)
9179:x
9176:(
9173:q
9139:1
9134:G
9110:1
9105:G
9083:i
9077:x
9057:)
9054:x
9051:(
9048:q
9020:i
9000:y
8980:i
8956:0
8953:=
8950:y
8944:)
8941:i
8938:(
8935:p
8915:)
8912:i
8906:x
8903:(
8883:y
8877:)
8874:x
8871:(
8868:p
8848:q
8828:y
8822:)
8819:x
8816:(
8813:p
8810:=
8807:)
8804:i
8798:x
8795:(
8792:)
8789:x
8786:(
8783:q
8759:t
8756:=
8753:x
8733:)
8730:y
8724:)
8721:t
8718:(
8715:p
8712:(
8706:=
8703:)
8700:)
8697:i
8691:t
8688:(
8682:)
8679:t
8676:(
8673:q
8670:(
8647:q
8627:p
8607:y
8601:)
8598:x
8595:(
8592:p
8589:=
8586:)
8583:i
8577:x
8574:(
8571:)
8568:x
8565:(
8562:q
8539:)
8536:y
8530:)
8527:t
8524:(
8521:p
8518:(
8512:=
8509:)
8506:)
8503:i
8497:t
8494:(
8488:)
8485:t
8482:(
8479:q
8476:(
8450:y
8444:)
8441:t
8438:(
8435:p
8431:)
8427:H
8424:,
8421:G
8418:(
8415:e
8412:=
8407:)
8404:i
8398:t
8395:(
8389:)
8386:t
8383:(
8380:q
8376:)
8372:H
8369:,
8366:G
8363:(
8360:e
8339:)
8336:H
8333:,
8330:)
8327:y
8321:)
8318:t
8315:(
8312:p
8309:(
8303:G
8300:(
8297:e
8294:=
8291:)
8288:)
8285:i
8279:t
8276:(
8270:H
8267:,
8264:)
8261:t
8258:(
8255:q
8249:G
8246:(
8243:e
8222:)
8219:H
8216:,
8213:y
8207:G
8201:)
8198:t
8195:(
8192:p
8186:G
8183:(
8180:e
8177:=
8174:)
8171:i
8165:H
8159:t
8153:H
8150:,
8147:)
8144:t
8141:(
8138:q
8132:G
8129:(
8126:e
8105:)
8102:H
8099:,
8096:y
8090:G
8084:C
8081:(
8078:e
8075:=
8072:)
8069:i
8063:H
8057:t
8051:H
8048:,
8042:(
8039:e
8014:x
8010:)
8006:H
8003:,
8000:G
7997:(
7994:e
7991:=
7988:)
7985:x
7982:(
7959:G
7953:)
7950:t
7947:(
7944:p
7941:=
7938:C
7918:G
7912:)
7909:t
7906:(
7903:q
7900:=
7875:T
7870:G
7845:i
7825:i
7819:H
7799:t
7793:H
7773:e
7750:)
7747:H
7744:,
7741:y
7735:G
7729:C
7726:(
7723:e
7713:?
7708:=
7698:)
7695:i
7689:H
7683:t
7677:H
7674:,
7668:(
7665:e
7642:i
7636:x
7616:y
7610:)
7607:x
7604:(
7601:p
7581:q
7527:i
7523:x
7500:i
7496:t
7489:G
7465:q
7440:1
7435:G
7413:G
7393:t
7373:q
7353:)
7350:t
7347:(
7344:q
7338:G
7313:i
7309:t
7305:G
7300:i
7296:q
7290:1
7284:n
7279:0
7276:=
7273:i
7265:=
7220:q
7197:q
7177:y
7174:=
7171:)
7168:i
7165:(
7162:p
7142:0
7139:=
7136:y
7130:)
7127:i
7124:(
7121:p
7101:i
7081:i
7075:x
7055:y
7049:)
7046:x
7043:(
7040:p
7020:q
7000:y
6997:=
6994:)
6991:i
6988:(
6985:p
6959:i
6953:x
6948:y
6942:)
6939:x
6936:(
6933:p
6927:=
6924:)
6921:x
6918:(
6915:q
6892:q
6872:i
6852:p
6832:y
6812:y
6809:=
6806:)
6803:i
6800:(
6797:p
6777:y
6757:i
6737:p
6715:i
6711:x
6688:i
6684:x
6680:=
6677:y
6657:C
6635:i
6631:x
6600:1
6595:G
6573:C
6553:t
6533:G
6513:)
6510:t
6507:(
6504:p
6498:G
6478:C
6456:1
6451:G
6427:i
6423:p
6400:i
6396:t
6389:G
6360:i
6356:t
6352:G
6347:i
6343:p
6337:1
6331:n
6326:0
6323:=
6320:i
6312:=
6309:C
6284:i
6280:x
6274:i
6270:p
6264:1
6258:n
6253:0
6250:=
6247:i
6239:=
6236:)
6233:x
6230:(
6227:p
6207:p
6185:1
6179:n
6175:p
6171:,
6168:.
6165:.
6162:.
6159:,
6154:1
6150:p
6146:,
6141:0
6137:p
6116:.
6113:.
6110:.
6107:,
6102:1
6098:x
6094:=
6091:)
6088:1
6085:(
6082:p
6079:,
6074:0
6070:x
6066:=
6063:)
6060:0
6057:(
6054:p
6028:j
6022:i
6017:j
6011:x
6003:i
5997:j
5994:,
5991:n
5985:j
5979:0
5969:i
5965:x
5959:1
5953:n
5948:0
5945:=
5942:i
5934:=
5931:)
5928:x
5925:(
5922:p
5893:i
5889:x
5866:i
5862:x
5858:=
5855:)
5852:i
5849:(
5846:p
5818:t
5798:i
5776:i
5772:t
5765:H
5743:i
5739:t
5732:G
5710:2
5705:G
5681:1
5676:G
5654:H
5634:G
5612:2
5607:G
5583:1
5578:G
5556:p
5534:p
5529:F
5521:t
5499:T
5494:G
5484:2
5479:G
5469:1
5464:G
5459::
5456:e
5434:T
5429:G
5405:2
5400:G
5395:,
5390:1
5385:G
5352:X
5332:n
5312:)
5309:1
5306:(
5303:O
5271:C
5249:n
5240:2
5213:i
5209:x
5188:C
5168:)
5164:n
5155:2
5147:(
5144:O
5124:)
5121:1
5118:(
5115:O
5095:X
5063:)
5060:n
5057:(
5054:O
5034:)
5031:1
5028:(
5025:O
5005:)
5002:n
4999:(
4996:O
4976:y
4956:C
4936:)
4933:n
4930:(
4927:O
4907:C
4887:y
4865:i
4861:m
4838:i
4834:x
4811:i
4807:y
4783:)
4778:n
4774:y
4770:,
4767:.
4764:.
4761:.
4758:,
4753:1
4750:+
4747:i
4743:y
4739:,
4734:i
4730:m
4726:,
4721:i
4717:x
4713:,
4708:1
4702:i
4698:y
4694:,
4691:.
4688:.
4685:.
4682:,
4677:2
4673:y
4669:,
4664:1
4660:y
4656:,
4653:i
4650:(
4627:X
4604:)
4599:n
4595:y
4590:|
4585:|
4581:.
4578:.
4575:.
4571:|
4566:|
4560:2
4556:y
4551:|
4546:|
4540:1
4536:y
4532:(
4529:H
4526:=
4523:C
4500:.
4497:.
4494:.
4491:,
4488:)
4483:2
4479:m
4474:|
4469:|
4463:2
4459:x
4455:(
4452:H
4449:=
4444:2
4440:y
4436:,
4433:)
4428:1
4424:m
4419:|
4414:|
4408:1
4404:x
4400:(
4397:H
4394:=
4389:1
4385:y
4362:n
4358:m
4354:.
4351:.
4348:.
4345:,
4340:2
4336:m
4332:,
4327:1
4323:m
4292:i
4288:x
4265:i
4261:x
4240:X
4220:C
4200:i
4180:X
4156:R
4136:X
4116:X
4096:C
4073:)
4068:n
4064:x
4060:,
4057:.
4054:.
4051:.
4048:,
4043:2
4039:x
4035:,
4030:1
4026:x
4022:(
4019:=
4016:X
3993:X
3963:2
3959:m
3950:1
3946:m
3923:2
3919:r
3896:1
3892:r
3869:2
3865:m
3856:1
3852:m
3828:)
3823:2
3819:r
3815:+
3810:1
3806:r
3802:,
3797:2
3793:m
3784:1
3780:m
3776:(
3773:C
3770:=
3763:2
3759:r
3755:+
3750:1
3746:r
3740:m
3736:g
3730:e
3726:)
3720:2
3716:m
3707:1
3703:m
3699:(
3696:=
3689:2
3685:r
3679:m
3675:g
3669:e
3664:2
3660:m
3649:1
3645:r
3639:m
3635:g
3629:e
3624:1
3620:m
3616:=
3613:)
3608:2
3604:r
3600:,
3595:2
3591:m
3587:(
3584:C
3578:)
3573:1
3569:r
3565:,
3560:1
3556:m
3552:(
3549:C
3529:)
3524:2
3520:r
3516:+
3511:1
3507:r
3503:,
3498:2
3494:m
3485:1
3481:m
3477:(
3474:C
3471:=
3468:)
3463:2
3459:r
3455:,
3450:2
3446:m
3442:(
3439:C
3433:)
3428:1
3424:r
3420:,
3415:1
3411:m
3407:(
3404:C
3382:2
3378:r
3355:1
3351:r
3328:2
3324:m
3301:1
3297:m
3271:2
3267:r
3244:1
3240:r
3217:2
3213:m
3209:+
3204:1
3200:m
3177:)
3172:2
3168:r
3164:+
3159:1
3155:r
3151:,
3146:2
3142:m
3138:+
3133:1
3129:m
3125:(
3122:C
3119:=
3112:2
3108:r
3104:+
3099:1
3095:r
3090:h
3082:2
3078:m
3074:+
3069:1
3065:m
3060:g
3056:=
3049:2
3045:r
3040:h
3032:2
3028:m
3023:g
3012:1
3008:r
3003:h
2995:1
2991:m
2986:g
2982:=
2979:)
2974:2
2970:r
2966:,
2961:2
2957:m
2953:(
2950:C
2944:)
2939:1
2935:r
2931:,
2926:1
2922:m
2918:(
2915:C
2893:)
2888:2
2884:r
2880:+
2875:1
2871:r
2867:,
2862:2
2858:m
2854:+
2849:1
2845:m
2841:(
2838:C
2835:=
2832:)
2827:2
2823:r
2819:,
2814:2
2810:m
2806:(
2803:C
2797:)
2792:1
2788:r
2784:,
2779:1
2775:m
2771:(
2768:C
2746:2
2742:r
2719:1
2715:r
2692:2
2688:m
2665:1
2661:m
2627:r
2622:m
2618:g
2612:e
2608:m
2604:=
2601:c
2572:2
2568:N
2562:Z
2540:r
2520:m
2491:2
2487:N
2481:Z
2457:m
2453:g
2432:1
2429:=
2426:)
2423:)
2418:2
2414:N
2410:(
2404:,
2401:e
2398:(
2395:d
2392:c
2389:g
2367:2
2363:N
2356:e
2336:e
2316:q
2296:p
2276:q
2270:p
2267:=
2264:N
2244:N
2210:r
2206:h
2200:x
2196:g
2192:=
2189:c
2179:r
2175:h
2171:x
2163:x
2156:x
2141:c
2137:g
2133:x
2128:′
2126:x
2122:x
2118:x
2114:c
2106:c
2102:g
2098:c
2094:p
2090:0
2086:x
2079:g
2075:p
2059:G
2055:G
2044:R
2040:R
2034:(
2032:G
2028:Y
2026:(
2024:G
2016:Y
2012:R
1989:Y
1987:(
1985:G
1979:(
1977:G
1966:R
1943:Y
1941:(
1939:G
1935:Y
1933:(
1931:G
1927:Y
1919:R
1915:Y
1913:(
1911:G
1903:Y
1901:(
1899:G
1895:b
1888:Y
1886:(
1884:G
1880:n
1876:Y
1872:n
1865:R
1861:R
1857:n
1849:b
1845:n
1841:n
1837:G
1833:G
1813:x
1811:(
1809:f
1805:f
1801:f
1797:x
1795:(
1793:f
1789:x
1787:(
1785:h
1781:h
1777:x
1775:(
1773:h
1769:b
1765:x
1763:(
1761:f
1757:x
1716:)
1713:)
1710:x
1707:(
1704:h
1698:b
1695:,
1692:)
1689:x
1686:(
1683:f
1680:,
1677:h
1674:(
1661:x
1657:b
1653:h
1649:f
1617:m
1613:m
1609:R
1597:m
1581:m
1577:R
1573:R
1569:k
1565:m
1561:k
1557:k
1528:R
1524:m
1512:R
1504:S
1500:m
1496:C
1489:C
1485:S
1481:S
1477:C
1473:S
1469:R
1465:C
1461:S
1454:R
1450:m
1446:S
1442:m
1438:F
1434:S
1430:m
1426:F
1422:C
1418:S
1414:F
1410:R
1406:C
1402:S
1398:S
1391:C
1387:F
1383:m
1375:C
1371:m
1367:C
1363:C
1352:R
1348:m
1344:F
1340:C
1336:R
1332:F
1328:m
1324:C
1320:F
1276:N
1269:k
1265:}
1261:)
1256:k
1252:U
1248:,
1241:x
1237:(
1232:k
1222:{
1199:N
1192:k
1188:}
1184:)
1179:k
1175:U
1171:,
1168:x
1165:(
1160:k
1150:{
1123:x
1116:x
1106:k
1090:k
1086:2
1063:k
1059:U
1010:)
1003:n
999:e
996:p
993:o
990:,
983:x
979:(
971:=
968:)
965:n
962:e
959:p
956:o
953:,
950:x
947:(
918:x
911:x
887:n
883:e
880:p
877:o
874:,
871:n
868:e
865:p
862:o
859:,
852:x
848:,
845:x
835:t
821:)
815:,
812:t
809:(
784:k
766:)
759:n
755:e
752:p
749:o
746:,
739:x
735:(
730:k
720:=
717:)
714:n
711:e
708:p
705:o
702:,
699:x
696:(
691:k
660:x
653:x
643:k
625:n
621:e
618:p
615:o
612:,
609:n
606:e
603:p
600:o
576:x
572:,
569:x
545:k
529:k
512:k
496:k
492:2
469:x
465:C
457:x
421:x
417:C
123:)
117:(
112:)
108:(
98:·
91:·
84:·
77:·
50:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
