In this section we describe theq-power knowledge-of-exponent (q-PKE) fam-ily of assumptions, which was introduced by Groth in 2010 [19], and we prove two theorems which indicate that this family of assumptions is increasing in strength as the parameter q grows (i.e., that assumptions with a higher value of q imply those with a lower value). We note that Groth showed in [19] thatq-PKE holds in the generic group model for any q.
Assumption 3.9 (The q-power knowledge-of-exponent assumption (q-PKE)) Let G be a group generator, and q ∈ N. We say that q-PKE holds (relative to G) if for every non-uniform probabilistic adversary A there is a non-uniform probabilistic extractor χA such that
Pr
(Gp,[1])← G;x, α←Fp;
σ := (Gp,[1],[x], . . . ,[xq],[α],[αx], . . . ,[αxq]);
([u],[v]); (k0, . . . , kq)
←(A||χA)(σ) : [v] =α[u]
∧ [u]6=Pq
i=0ki[xi]
≤negl.
CHAPTER 3 THEQ-PKE FAMILY OF ASSUMPTIONS 30 Remark 3.10
We can allow the parameter q to be any function of the security parameter κ; in that case, the experiment on security parameterκhasσ:= (Gp,[1],[x], . . . ,[xq(κ)], [α],[αx], . . . ,[αxq(κ)]). Of course, since our algorithms run in time polynomial in κ, we can assume that q(κ) is polynomial as well. To ease notation, we will always simply write q.
We note that KEA1 is 0-PKE and that KEA3 is 1-PKE. As previously mentioned, it was shown by Bellare and Palacio [3] that 1-PKE implies 0-PKE;
the proof there readily extends to show that, for any q, q-PKE implies 0-PKE.
For completeness and as a warm-up for what follows, we restate it here.
Theorem 3.11 (Generalisation of Proposition 2 from [3])
Let G be a group generator, and q ∈N. If q-PKE holds for G, then 0-PKE holds for G.
Proof. LetA be an adversary against 0-PKE; we first construct an adversary B againstq-PKE that usesA in a black-box manner. B has input
(Gp,[1],[x], . . . ,[xq],[α],[αx], . . . ,[αxq]);
it runs A on input (Gp,[1],[α]) and with its own random tape, and outputs the pair ([u],[v]) output byA. Sinceq-PKE holds, there is an extractorχB forBwith negligible error probabilityν; we construct an extractorχA forA that usesχB in a black-box manner. χA proceeds as follows on input (Gp,[1],[α]).
• x←Fp.
• σ:= (Gp,[1],[x], . . . ,[xq],[α],[αx], . . . ,[αxq]).
• (k0, . . . , kq)←χB(σ).
• OutputPq
i=0kixi.
We claim that χA has (negligible) error probabilityν.
We run the 0-PKE experiment. Firstly, A is run on input (Gp,[1],[α]), and we let ([u],[v]) be its output. Then χA is run, again on input (Gp,[1],[α]) and with the same random tape as A, and it runs χB on input σ and with its own random tape. Now, observe thatσ is distributed identically to the input toχB in the experiment for q-PKE, and so, letting ([u′],[v′]); (k0, . . . , kq)
be the output
CHAPTER 3 THEQ-PKE FAMILY OF ASSUMPTIONS 31 of B||χB on input σ and with the same random tape as that of A, we have
[v′] =α[u′]
∧Xq
i=0
ki[xi]6= [u′]
with probabilityν. SinceBon inputσruns Aon input (Gp,[1],[α]) and with the same random tape as that with which A was run originally, we have ([u′],[v′]) = ([u],[v]). Observing that
q
X
i=0
ki[xi] =Xq
i=0
kixi [1]
completes the proof.
As mentioned, the above result shows in particular that 1-PKE implies 0-PKE. A natural question is then to ask whether this can be generalised to show that in general (q+ 1)-PKE impliesq-PKE. We show that this is the case under a variant of the decisional Diffie-Hellman exponent (DDHE) assumption.*1) Assumption 3.12 (The q-decisional Diffie-Hellman exponent (q-DDHE) as-sumption)
Let G be a group generator, A be a non-uniform probabilistic adversary, q∈N∗, b∈ {0,1}. Consider the following experiment ExpqG,A-ddhe-b(κ).
• (Gp,[1]) ← G;x, r←Fp.
• Ifb= 0, thenσ:= (Gp,[1],[x], . . . ,[xq],[r]); otherwise,σ := (Gp,[1],[x], . . . , [xq],[xq+1]).
• b′ ← A(σ).
• Output b′. We let
AdvqG,A-ddhe(κ) = Pr
ExpqG,A-ddhe-1(κ) = 1
−Pr
ExpqG,A-ddhe-0(κ) = 1
be the advantage ofA (in q-DDHE) relative toG, and we say thatq-DDHE holds in G if every non-uniform adversary has negligible advantage, i.e., if for every non-uniform adversary A, we have AdvqG,A-ddhe ≤negl.
∗1) Unfortunately, since our proof relies on a decisional assumption, it does not apply in the bi-linear setting, which is the setting in whichq-PKE was introduced in [19] and subsequently used in [13, 25].
CHAPTER 3 THEQ-PKE FAMILY OF ASSUMPTIONS 32 Theorem 3.13
LetG be a group generator, andq ∈N∗. If q-DDHE and (q+ 1)-PKE hold forG, then q-PKE holds for G.
Proof. LetA be an adversary against q-PKE; we first construct an adversary B against (q+ 1)-PKE that usesA in a black-box manner. B has input
Gp,[1],[x], . . . ,[xq+1],[α],[αx], . . . ,[αxq+1]
; it runsA on input
Gp,[1],[x], . . . ,[xq],[α],[αx], . . . ,[αxq]
and with its own random tape, and outputs the pair ([u],[v]) output byA. Since (q+ 1)-PKE holds, there is an extractor χB for B with negligible error probabil-ity ν; we construct an extractor χA for A that uses χB in a black-box manner.
χA proceeds as follows on input (Gp,[1],[x], . . . ,[xq],[α],[αx], . . . ,[αxq]).
• r←Fp.
• σ:= (Gp,[1], . . . ,[xq],[r],[α], . . . ,[αxq],[αr]).
• (k0, k1, . . . , kq+1)←χB(σ).
• Output (k0+kq+1r, k1, . . . , kq).
We claim that χA has negligible error probability.
We run the q-PKE experiment. Firstly, A is run on input (Gp,[1],[x], . . . ,[xq],[α],[αx], . . . ,[αxq]),
and we let ([u],[v]) be its output. Then χA is run, on the same input and with the same random tape asA, and it runsχB on inputσ and with its own random tape. We claim that, letting ([u′],[v′]); (k0, . . . , kq+1)
be the output ofB||χB on input σ, we have
[v′] =α[u′]
∧ kq+1[r] +
q
X
i=0
ki[xi]6= [u′]
with negligible probability. Intuitively, this follows from the fact that, under q-DDHE, σ is indistinguishable from the input to B||χB in the (q + 1)-PKE experiment. To show it formally, we consider the following adversary Z against q-DDHE, which uses B and χB in a black-box manner.
Z proceeds as follows on input (Gp,[1],[x], . . . ,[xq],[z]) (where x is random and z is eitherxq+1 or random).
CHAPTER 3 THEQ-PKE FAMILY OF ASSUMPTIONS 33
• α←Fp.
• σ:= (Gp,[1],[x], . . . ,[xq],[z],[α],[αx], . . . ,[αxq],[αz]).
• ([u],[v]); (k0, k1, . . . , kq+1)
←(B||χB)(σ).
• If [v] =α[u] and kq+1[z] +Pq
i=0ki[xi]6= [u], output 1; else, output 0.
Ifz =xq+1, theq-DDHE experiment forZ is exactly the (q+ 1)-PKE experiment forB||χB, and so Z outputs 1 with (negligible) probabilityν. On the other hand, if z is random, then σ is distributed identically to the input to B||χB when it is run by χA in the q-PKE experiment. Let µ be the probability that Z outputs 1 in that latter case; then |ν−µ| is negligible since q-DDHE holds, and since ν is negligible as well, so is µ.
Finally, since B on input σ runs A on input (Gp,[1], . . . ,[xq],[α], . . . ,[αxq]) and with the same random tape as that with whichAwas run originally, we have ([u′],[v′]) = ([u],[v]). Observing that
kq+1[r] +
q
X
i=0
ki[xi] = (k0+kq+1r)[1] +
q
X
i=1
ki[xi] completes the proof.
Chapter 4
Rational KEAs (RKEAs)
In this chapter, we propose a definition of a large class of assumptions, with the goal of capturing not only the KEAs that have appeared in the literature thus far, but also some that are likely to appear in the future. We then show that this large class is implied by a slightly smaller subclass.
4.1 Definition of RKEAs
Along the lines of the definition of target assumptions by Ghadafi and Groth [15], we generalise the PKE family of assumptions by allowing arbitrary rational functions of several variables instead of just powers of x. We call the result-ing class of assumptions rational knowledge-of-exponent assumptions (RKEAs).
Analogously to the target assumptions of [15], RKEAs are parameterised by three integers*1)d(the maximal degree of the polynomials involved),m (the number of variables) and n (the number of rational functions). We first define a very gen-eral notion of non-interactive knowledge assumptions (NIKAs) analogous to the non-interactive computational assumptions of Ghadafi and Groth [15]. (The in-tuitive meanings of the quoted terms should be clear from the previous examples of KEAs.)
Definition 4.1 (Non-interactive knowledge assumptions (NIKAs))
A non-interactive knowledge assumption consists of an instance generator I, a verifier V, and a knowledge verifier V, defined as follows.
∗1) Again, we can allow d, m, nto be any functions of the security parameter κ, and assume that they are polynomial.
34
CHAPTER 4 RATIONAL KEAS (RKEAS) 35
• (pub,priv) ← I: I is a uniform probabilistic algorithm which, on input 1κ (where κis a security parameter), outputs a pair of public/private informa-tion (pub,priv). We omit the input 1κ as usual.
• 0/1 ← V(pub,priv,sol): V is a uniform deterministic algorithm which, on input (pub,priv) and a purported solution sol, outputs 1 if the solution is
“correct” and 0 otherwise.
• 0/1 ← V(pub,priv,sol,sec): V is a uniform deterministic algorithm which, on input (pub,priv,sol) and a purported “secret” sec, outputs 1 if the secret is “correct” and 0 otherwise.
We say that the assumption holds if for any non-uniform probabilistic algorithmA (the adversary) there is a non-uniform probabilistic algorithm χA (the knowledge extractor, or just the extractor) such that
Pr
(pub,priv)← I; (sol;sec)←(A||χA)(pub) : V(pub,priv,sol) = 1∧ V(pub,priv,sol,sec) = 0
≤negl.
We call the above probability the error probabilityof χArelative to A, and express it as a function of the security parameterκ; thus the assumption holds if for every adversaryAthere is an extractorχA with negligible error probability relative toA.
We also say that χA is successful (relative to A) if the condition above does not hold, i.e., if χA “successfully extracts” A’s secret (hence the error probability is the probability that the extractor is not successful).
Definition 4.2 (Rational knowledge-of-exponent assumptions (RKEAs))
For d, m, n ∈ N∗ and a group generator G, we say that (I,V,V) is a (d, m, n)-RKEA if there is a uniform probabilistic algorithm Icore such that I, V and V are of the following forms.
• (pub,priv)← I:
– (Gp,[1])← G.
– n
ai(X) bi(X)
on
i=1,pub′,priv′
← Icore(Gp), where the ais and bis are poly-nomials in m variables and of total degree at most d.
– x←Fmp conditioned on bi(x)6= 0 for all i.
– α ←Fp. – pub:=
Gp,nh
ai(x) bi(x)
ion i=1,nh
α·ai(x) bi(x)
ion i=1,n
ai(X) bi(X)
on
i=1,pub′ .
CHAPTER 4 RATIONAL KEAS (RKEAS) 36 – Return pub,priv:= ([1],x, α,priv′)
.
• 0/1← V pub,priv,sol= ([u],[v])
: if [v] =α[u], return 1; else, return 0.
• 0/1← V pub,priv,sol,sec= (k1, . . . , kn)
: if Pn i=1ki
ai(x) bi(x)
= [u], return 1;
else, return0.
Remark 4.3
We note that in an RKEA the knowledge verifierV does not use the private in-formationpriv; thus RKEAs would also satisfy an alternative definition of NIKAs whereV is not given priv.
Example 4.4 (q-PKE)
q-PKE is a (q,1, q+1)-RKEA, meaning thatIcoregeneratesq+1 rational functions consisting of polynomials in one variable and of degree at most q. Namely, we haveai(x) = xi−1 and bi(x) = 1 for all i= 1, . . . , q+ 1.
4.2 Simplifications of RKEAs
As a first step towards identifying Uber-assumptions for the class of RKEAs, in this section we definesimple RKEAs analogously to the simple target assump-tions of Ghadafi and Groth [15], and we show that simple RKEAs imply all RKEAs.
Definition 4.5 (Simple RKEAs)
We say that an RKEA is simple if bi(X) = 1 for all i = 1, . . . , n, i.e., all the rational functions output by Icore are just polynomials.
Theorem 4.6
For any (d, m, n)-RKEA A = (IA,VA,VA) there is an (nd, m, n)-simple RKEA B= (IB,VB,VB) such that B implies A.
Proof. The algorithm IBcore of B proceeds as follows on input Gp.
•
nai(X) bi(X)
on
i=1,pub′A,priv′A
← IAcore(Gp).
• ci(X) :=ai(X)·Q
j6=ibj(X) for all i= 1, . . . , n.
• pub′B :=n
ai(X) bi(X)
on
i=1,pub′A
; priv′B :=priv′A.
• Return
ci(X) ni=1,pub′B,priv′B .
CHAPTER 4 RATIONAL KEAS (RKEAS) 37 Let A be an adversary against A; we first construct an adversary B against Bwhich uses A in a black-box manner. B’s input is
pubB = Gp,
ci(x) ni=1,
α·ci(x) ni=1,
ci(X) ni=1,pub′B
; it runsA on input
Gp,
ci(x) ni=1,
α·ci(x) ni=1,
ai(X) bi(X)
n
i=1
,pub′A
and with its own random tape, and outputs the pair output byA. Since we as-sume thatBholds, there is an extractorχB forBwith negligible error probability ν; we construct an extractorχAforAwhich usesχB in a black-box manner. χA’s input is
pubA =
Gp,
ai(x) bi(x)
n
i=1
,
α·ai(x) bi(x)
n
i=1
,
ai(X) bi(X)
n
i=1
,pub′A
and its random tape is the same as that of A. χA runs χB on input σB =
Gp,
ai(x) bi(x)
n i=1
,
α·ai(x) bi(x)
n i=1
,
ci(X) ni=1,pub′B
and with its own random tape, and outputs the values (k1, . . . , kn) output by χB. We claim thatχA is an extractor forAwith (negligible) error probability at most ν+dnp .
We run the NIKA experiment for A. Firstly, A is run on input pubA, and we let ([u],[v]) be its output. Then,χA is run, again on inputpubA and with the same random tape as A, and it runs χB on input σB and with its own random tape, outputting the output (k1, . . . , kn) of χB. We claim that σB is distributed identically topubB except with negligible probability. To see this, observe thatIA
generates the polynomialsai(X) andbi(X) as well as the vectorx independently of the generator [1] output byG. Further, assuming thatQn
i=1bi(x)6= 0, the only difference between pubB and σB is the choice of generator; namely, if choosing the generator [1] yields the inputpubB, then choosing the generator Qn
i=1bi(x) yields σB.
By the Schwartz-Zippel lemma, the probability that Qn
i=1bi(x) = 0 is at most dnp . Thus, letting ([u′],[v′]) be the pair output by B we have
[v′] =α[u′]
∧ n
X
i=1
ki
ai(x) bi(x)
6= [u′]
CHAPTER 4 RATIONAL KEAS (RKEAS) 38 with probability at most ν+dnp . Observing that B, when run on input σB, runs A on input pubA and with the same random tape as that with which A was run originally shows that ([u′],[v′]) = ([u],[v]), which completes the proof.
Chapter 5 Conclusion
In this thesis we have initiated an analysis of knowledge-of-exponent assumptions (KEAs), with the goal of obtaining a classification of those assumptions analogous to that obtained by Ghadafi and Groth for target assumptions [15]. Namely, we sought to identify a large class of KEAs, and then a small subclass thereof such that if all the assumptions in the small class hold, then all the assumptions in the large class hold as well. (The assumptions in the small class are then called
“Uber-assumptions”.) The aim of such a classification is to provide designers of cryptographic systems with a wide range of assumptions from which they may choose the most suitable one for their purposes, while at the same time ensuring that their validity relies on a small number of assumptions, which can then be thoroughly studied.
In Chapter 3 we studied the internal structure of theq-power knowledge-of-exponent (q-PKE) family of assumptions. This family of assumptions was intro-duced by Groth [19] as a generalisation of assumptions that had been introintro-duced earlier by Damg˚ard [8] and by Bellare and Palacio [3] (the latter as a modification of a faulty assumption of Hada and Tanaka [21, 22]), and was the most general instance of KEAs in the literature. We proved two results which give evidence that the assumptions in theq-PKE family increase in strength as the parameterq grows. Namely, we showed that, for anyq,q-PKE unconditionally implies 0-PKE, and implies (q−1)-PKE under a decisional Diffie-Hellman-type assumption. The first result is an extension of a prior result of Bellare and Palacio (due to Halevi) [3], which showed merely that 1-PKE implies 0-PKE. Regarding the second re-sult, we remark that its reliance on a decisional assumption is unfortunate, since it means that it does not apply in bilinear groups.
39
CHAPTER 5 CONCLUSION 40 In Chapter 4, we introduced a further generalisation of the q-PKE fam-ily of assumptions, which we named rational knowledge-of-exponent assumptions (RKEAs), with the aim of capturing not only existing assumptions, but also oth-ers which may appear in the future. This is again motivated by the desire to have as large a class of assumptions as possible. Then, as a first step towards identifying Uber-assumptions for RKEAs, we show that all RKEAs are implied by the smaller subclass of simple RKEAs.
All our results were obtained using the proof technique from [3], which to our knowledge, is thus far the only known method for proving implications between KEAs. Indeed, to our knowledge, Proposition 4.2 from [3] was prior to this work the only result in the literature that proved an implication between two KEAs. Many directions for future work remain open, which might require the introduction of new proof techniques.
• Is theq-PKE familystrictly increasing? In other words, can it be shown in some sense that q-PKE does not imply (q+ 1)-PKE?
• Can RKEAs be simplified further as in [15]? In particular, can Uber-assumptions be found? If not, can RKEAs be proved secure in the generic group model [6, 24, 29]?
• Can RKEAs be generalised further, for instance by allowingV andV to be of a more general form?
• Perhaps most importantly, can a similar analysis be done in the bilinear setting, where KEAs are now primarily used?
Bibliography
[1] M. Abe and S. Fehr, Perfect NIZK with Adaptive Soundness. S. P. Vadhan (Ed.), TCC 2007, Lecture Notes in Computer Science, vol. 4392, pp. 118–
136, Springer, 2007.
doi:10.1007/978-3-540-70936-7_7
[2] S. Arora and B. Barak, Computational Complexity: A Modern Approach.
Cambridge University Press, New York, 2009.
http://theory.cs.princeton.edu/complexity/(Accessed 9 July 2019.) [3] M. Bellare and A. Palacio,The Knowledge-of-Exponent Assumptions and
3-Round Zero-Knowledge Protocols. M. Franklin (Ed.),CRYPTO 2004,Lecture Notes in Computer Science, vol. 3152, pp. 273–289, Springer, 2004.
doi:10.1007/978-3-540-28628-8_17
[4] D. Boneh, X. Boyen, and E.-J. Goh,Hierarchical Identity Based Encryption with Constant Size Ciphertext. R. Cramer (Ed.), EUROCRYPT 2005, Lec-ture Notes in Computer Science, vol. 3494, pp. 440–456, Springer, 2005.
doi:10.1007/11426639_26
[5] D. Boneh, C. Gentry, and B. Waters,Collusion Resistant Broadcast Encryp-tion with Short Ciphertexts and Private Keys. V. Shoup (Ed.), CRYPTO 2005, Lecture Notes in Computer Science, vol. 3621, pp. 258–275, Springer, 2005.
doi:10.1007/11535218_16
[6] M. Chateauneuf, A. C. H. Ling, and D. R. Stinson,Slope Packings and Cov-erings, and Generic Algorithms for the Discrete Logarithm Problem.Journal of Combinatorial Designs, vol. 11, no. 1, pp. 36–50, Wiley, 2003.
doi:10.1002/jcd.10033
41
BIBLIOGRAPHY 42 [7] R. Crandall and C. Pomerance,Prime Numbers: A Computational
Perspec-tive, second edition. Springer, New York, 2005.
doi:10.1007/0-387-28979-8
[8] I. Damg˚ard, Towards Practical Public Key Systems Secure Against Chosen Ciphertext Attacks. J. Feigenbaum (Ed.), CRYPTO ’91, Lecture Notes in Computer Science, vol. 576, pp. 445–456, Springer, 1992.
doi:10.1007/3-540-46766-1_36
[9] A. W. Dent,The Hardness of the DHK Problem in the Generic Group Model.
Cryptology ePrint Archive, Report 2006/156, 2006.
https://ia.cr/2006/156 (Accessed 9 July 2019.)
[10] W. Diffie and M. E. Hellman,New Directions in Cryptography.IEEE Trans-actions on Information Theory, vol. 22, no. 6, pp. 644–654, IEEE, 1976.
doi:10.1109/TIT.1976.1055638
[11] T. ElGamal, A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms.IEEE Transactions on Information Theory, vol. 31, no. 4, pp. 469–472, IEEE, 1985.
doi:10.1109/TIT.1985.1057074
[12] J. B. Fraleigh,A First Course in Abstract Algebra, seventh edition. Pearson, 2003.
[13] R. Gennaro, C. Gentry, B. Parno, and M. Raykova,Quadratic Span Programs and Succinct NIZKs without PCPs. T. Johansson and P. Nguyen (Eds.), EUROCRYPT 2013,Lecture Notes in Computer Science, vol. 7881, pp. 626–
645, Springer, 2013.
doi:10.1007/978-3-642-38348-9_37
[14] C. Gentry and D. Wichs, Separating Succinct Non-Interactive Arguments From All Falsifiable Assumptions.STOC ’11: Proc. of the Forty-third Annual ACM Symposium on Theory of Computing, pp. 99–108, ACM, 2011.
doi:10.1145/1993636.1993651
[15] E. Ghadafi and J. Groth, Towards a Classification of Non-interactive Com-putational Assumptions in Cyclic Groups. T. Takagi and T. Peyrin (Eds.), ASIACRYPT 2017, Part II, Lecture Notes in Computer Science, vol. 10625,
BIBLIOGRAPHY 43 pp. 66–96, Springer, 2017.
doi:10.1007/978-3-319-70697-9_3
[16] O. Goldreich,On the Foundations of Modern Cryptography. B. S. Kaliski Jr.
(Ed.), CRYPTO ’97,Lecture Notes in Computer Science, vol. 1294, pp. 46–
74, Springer, 1997.
doi:10.1007/BFB0052227
[17] O. Goldreich, S. Micali, and A. Widgerson,Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. Journal of the ACM, vol. 38, no. 3, pp. 690–728, ACM, 1991.
doi:10.1145/116825.116852
[18] S. Goldwasser and S. Micali, Probabilistic Encryption. Journal of Computer and System Sciences, vol. 28, no. 2, pp. 270–299, Academic Press, 1984.
doi:10.1016/0022-0000(84)90070-9
[19] J. Groth, Short Pairing-Based Non-interactive Zero-Knowledge Arguments.
M. Abe (Ed.), ASIACRYPT 2010, Lecture Notes in Computer Science, vol. 6477, pp. 321–340, Springer, 2010.
doi:10.1007/978-3-642-17373-8_19
[20] A. Gut, Probability: A Graduate Course, second edition. Springer Texts in Statistics, Springer, New York, 2013.
doi:10.1007/978-1-4614-4708-5
[21] S. Hada and T. Tanaka, On the existence of 3-round zero-knowledge proto-cols. H. Krawczyk (Ed.),CRYPTO ’98, Lecture Notes in Computer Science, vol. 1462, pp. 408–423, Springer, 1998. (Preliminary version of [22].)
doi:10.1007/BFB0055744
[22] S. Hada and T. Tanaka,On the Existence of 3-Round Zero-Knowledge Proto-cols.Cryptology ePrint Archive, Report 1999/009, 1999. (Full version of [21].) https://ia.cr/1999/009 (Accessed 9 July 2019.)
[23] M. Naor, On Cryptographic Assumptions and Challenges. D. Boneh (Ed.), CRYPTO 2003, Lecture Notes in Computer Science, vol. 2729, pp. 96–109, Springer, 2003.
doi:10.1007/978-3-540-45146-4_6
BIBLIOGRAPHY 44 [24] V. I. Nechaev, Complexity of a determinate algorithm for the discrete
loga-rithm. Mathematical Notes, vol. 55, no. 2, pp. 165–172, Plenum, 1994.
doi:10.1007/BF02113297
[25] B. Parno, J. Howell, C. Gentry, and M. Raykova,Pinocchio: Nearly Practical Verifiable Computation. 2013 IEEE Symposium on Security and Privacy, pp. 238–252, IEEE, 2013.
doi:10.1109/SP.2013.47
[26] M. O. Rabin, Probabilistic Algorithms. J. F. Traub (Ed.), Algorithms and Complexity: New Directions and Recent Results, pp. 21–39, Academic Press, New York, 1976.
[27] R. L. Rivest, A. Shamir, and L. Adleman, A Method for Obtaining Digi-tal Signatures and Public-Key Cryptosystems.Communications of the ACM, vol. 21, no. 2, pp. 120–126, ACM, 1978.
doi:10.1145/359340.359342
[28] C. E. Shannon, Communication Theory of Secrecy Systems. Bell System Technical Journal, vol. 28, no. 4, pp. 656–715, AT&T, 1949.
[29] V. Shoup, Lower Bounds for Discrete Logarithms and Related Problems.
W. Fumy (Ed.), EUROCRYPT ’97, Lecture Notes in Computer Science, vol. 1233, pp. 256–266, Springer, 1997.
doi:10.1007/3-540-69053-0_18
[30] Zerocoin Electric Coin Company, What are zk-SNARKs?.
https://z.cash/technology/zksnarks/ (Accessed 9 July 2019.)