[PDF] E?cient Indi?erentiable Hashing into Ordinary Elliptic Curves

View - Download E?cient Indi?erentiable Hashing into Ordinary Elliptic Curves

Previous PDF

Next PDF

Efficient Indifferentiable Hashing into Ordinary Elliptic Curves?

Eric Brier

1, Jean-S´ebastien Coron2, Thomas Icart2??, David Madore3, Hugues Randriam3, and

Mehdi Tibouchi

2,4? ? ?

1

Ingenico

eric.brier@ingenico.com

2Universit´e du Luxembourg

3TELECOM-ParisTech

{david.madore,randriam}@enst.fr

4´Ecole normale sup´erieure

mehdi.tibouchi@ens.fr

Abstract.We provide the first construction of a hash function into ordinary elliptic curves that is indif-

ferentiable from a random oracle, based on Icart"s deterministic encoding from Crypto 2009. While almost

as efficient as Icart"s encoding, this hash function can be plugged into any cryptosystem that requires

hashing into elliptic curves, while not compromising proofs of security in the random oracle model.

We also describe a more general (but less efficient) construction that works for a large class of encodings

into elliptic curves, for example the Shallue-Woestijne-Ulas (SWU) algorithm. Finally we describe the first

deterministic encoding algorithm into elliptic curves in characteristic 3.

1 Introduction

Hashing into Elliptic Curves.Many elliptic curve cryptosystems require to hash into an elliptic curve. For example in the Boneh-Franklin IBE scheme [6], thepublic-key for identityid? {0,1}?is a pointQid=H1(id) on the curve. This is also the case in many other pairing-based cryptosystems in- cluding IBE and HIBE schemes [1,19,22], signature and identity-based signature schemes [5,7,8,13,35] and identity-based signcryption schemes [10,25]. Hashing into elliptic curves is also required for some passwords based authentication protocols, for instance the SPEKE (Simple Password Exponential Key Exchange) [24] and the PAK (Password

Authenticated Key exchange) [11], and also for discrete-log based signature schemes such as [14] when

instantiated over an elliptic curve. In all those previous cryptosystems, security is proven when the

hash function is seen as a random oracle into the curve. However, it remains to determine which hashing algorithm should be used, and whether it is reasonable to see it as a random oracle. In [6], Boneh and Franklin use a particular supersingular elliptic curveEfor which, in addition to the pairing operation, there exists a one-to-one mappingffrom the base fieldFptoE(Fp). This enables to hash usingH1(m) =f(h(m)) wherehis a classical hash function from{0,1}?toFp. The authors show that their IBE scheme remains secure whenhis seen as a random oracle intoFp(instead ofH1being seen as a random oracle intoE(Fp)). However, when no pairing operation is required (as

in [11,14,24]), it is more efficient to use ordinary elliptic curves, since supersingular curves require

much larger security parameters due to the MOV attack [27]. For hashing into an ordinary elliptic curve, the classical approach is inherently probabilistic: one can first compute an integer hash valuex=h(m) and then determine whetherxis the abscissa of a ?An extended abstract of this paper will appear atcrypto2010. This is the full version. ??Research carried out while working at Sagem S´ecurit´e.

? ? ?Research carried out while on a visit to the Okamoto Research Laboratory at the NTT Information Sharing Platform.

point on the elliptic curve: y

2=x3+ax+b

otherwise one can tryx+1 and so on. Using this approach the number of operations required to hash a messagemdepends onm, which can lead to a timing attack (see [9]). To avoid this attack, one can

smallest suchi; herekis a security parameter that gives an error probability of roughly 2-k. However,

this leads to a very lengthy hash computation. The first algorithm to generate elliptic curve points indeterministicpolynomial time was published in ANTS 2006 by Shallue and Woestijne [31]. The algorithm hasrunning timeO(log4p) for anyp, andO(log3p) whenp≡3 (mod 4), using standard multiplications. The rational maps in [31] were

later simplified and generalized to hyper-elliptic curves by Ulas in [34]; we refer to this algorithm

as the Shallue-Woestijne-Ulas (SWU) algorithm. Lettingf:Fp→E(Fp) be the function defined by SWU, one can then hash in deterministic polynomial time usingH(m) =f(h(m)) wherehis any hash function intoFp. Another deterministic hash algorithm for ordinary elliptic curves was recently published by Icart in [23]. The algorithm works forp≡2 (mod 3), with complexityO(log3p). Given any elliptic curve Edefined overFp, Icart defines a functionfthat is an algebraic function fromFpinto the curve. As previously given any hash functionhintoFp, one can useH(m) =f(h(m)) to hash intoE(Fp). As shown in [23],His one-way ifhis one-way. The Random Oracle Model (ROM).Many cryptosystems based on elliptic curves have been

proven secure in the random oracle model, see for example [1,5,6,7,8,10,11,13,19,22,24,25,35]. In the

random oracle model [3], the hash function is replaced by a publicly accessible random function (the random oracle); the adversary cannot compute the hash function by himself but instead he must query the random oracle. Obviously, a proof in the random oracle model is not fully satisfactory, because such a proof does not imply that the scheme will remain securewhen the random oracle is replaced by a concrete hash function. Numerous papers have shown artificial schemes that are provably secure in the ROM but completely insecure when the RO is instantiated with any function family (see [12]).

Despite these separation results, a proof in the ROM is believed to indicate that there are no structural

flaws in the design of the system, and that no flaw will suddenlyappear when a "well designed" hash function is used instead. For a cryptosystem that requires a hash functionHinto an ordinary elliptic curve (such as [11,24]), one possibility could be to useH(m) =f(h(m)) wherefis either Icart or SWU"s function andh is a hash function intoFp. However we know that neither Icart nor SWU"s function generate all the

points ofE; for example, Icart"s function covers only about 5/8 of the points [17,18]; moreover it is

easy to see that the distribution off(h(m)) is not uniform in the image off. Therefore the current proofs in the random oracle model forHdo not guarantee the security of the resulting scheme when

H(m) =f(h(m)) is used instead (even ifhis assumed to be ideal). In other words, even if a proof in the

random oracle forHcan indicate that there are no structural flaws in the design of the cryptosystem, usingH(m) =f(h(m)) could introduce a flaw that would make the resulting cryptosystem completely insecure (we give an example in Section 5.2). Our Results.We provide the first construction of a hash functionHinto ordinary elliptic curves with the property thatany cryptosystemproven secure assumingHis a random oracle remains secure when

our construction is plugged instead (still assuming that the underlyinghis a random oracle). For this

we use the indifferentiability framework of Maureret al.[26]. As shown in [15], when a construction His indifferentiable from a random oracle, such a construction can then replace a random oracle in any cryptosystem, and the resulting scheme remains secure in the random oracle model forh. Since the output of Icart and SWU functions only covers a fraction of the elliptic curve points, we cannot use the constructionH(m) =f(h(m)) for indifferentiable hashing. Our main result is to show that for Icart"s functionf, we can use the following alternative construction which isalmost as efficient:

H(m) :=f(h1(m)) +f(h2(m))

whereh1,h2are two hash functions intoFp, and + denotes elliptic curve addition. ThereforeH(m) can be used in any cryptosystem provably secure with random oracle into elliptic curves, and the resulting cryptosystem remains secure in the random oraclemodel forh1andh2. However the proof involves somewhat technical tools from algebraic geometry, and it is not so simple to adapt to other encodings such as the SWU algorithm.Therefore we describe a more general

(but less efficient) construction that applies to a large class of encoding functions satisfying a few simple

axioms. Those encodings include Icart"s function, the SWU algorithm, new deterministic encodings in characteristic 3, etc. More precisely, given an ellipticcurveEdefined overFpwhose group of points is cyclic of orderNwith generatorG, our general construction is as follows:

H(m) :=f(h1(m)) +h2(m)G

whereh1:{0,1}?→Fpandh2:{0,1}?→ZNare two hash functions, andfis SWU or Icart"s function. We show thatH(m) is indifferentiable from a random oracle whenh1andh2are seen as random oracles. Intuitively, the termh2(m)Gplays the role of a one-time pad; this ensures thatH(m) can behave as a random oracle even thoughf(h1(m)) does not reach all the points inE. Note that one could not useH(m) =h2(m)Gonly since in this case the discrete logarithm ofH(m) would be known, which would make most protocols insecure. 5 We also show how to extend the two previous constructions to hashing into a subgroup of an

elliptic curve (whether its group of points is cyclic or not)and to hash functions into strings (rather

thanFp). We also describe a slightly more efficient variant of the SWUalgorithm whenp≡3 (mod 4).

Finally, we describe the first deterministic encoding algorithms into elliptic curves in characteristic 3.

2 Preliminaries

2.1 Deterministic Encodings to Elliptic Curves

The indifferentiable hash function constructions proposedin this paper can be based on variousde- terministic encoding functionsto elliptic curves. The first example of such an encoding is the one introduced by Boneh and Franklin in [6] forsupersingularelliptic curves (see below). For ordinary (i.e.non-supersingular) elliptic curves, the two main encodingfunctions introduced thus far are due to Shallue and Woestijne with later improvements by Ulas (SWU) [31,34] on the one hand, and to

Icart [23] on the other. They are defined on ordinary curves over finite fields of characteristic>3; we

describe them succinctly below. They also admit variants over binary fields. Supersingular Curves and Boneh-Franklin Admissible EncodingAn elliptic curveEoverFp

is called supersingular when it has exactlyp+1 points overFp. Whenp≡2 (mod 3), the mapx?→x3

is a bijection, therefore the curvesY2=X3+bare supersingular. One can then define the encoding f:u?→? (u2-b)1/3,u?

5For example in Boneh-Franklin IBE one could then decrypt any ciphertext.

and the hash functionH(m) :=f(h(m)), wherehis a classical hash function intoFp. In the Boneh-Franklin scheme [6], one actually works in a subgroupGof prime orderqofEa,b(Fp); one lets?be the co-factor such thatp+ 1 =?·q. One requires thatqdoes not divide?(i.e.thatq2 does not dividep+ 1). In order to hash intoG, one can therefore use the encodingfG(u) :=?f(u) and the hash function intoG: H

G(u) :=fG(h(m))(1)

In [6], Boneh and Franklin introduced the following notion of admissible encoding: Definition 1 (Boneh-Franklin admissible encoding [6]).A functionf:S→Rbetween finite sets is an admissible encoding if it satisfies the following properties:

1. Computable:fis computable in deterministic polynomial time;

2.?-to-1: for anyr?R,#f-1(r) =?;

3. Samplable: there exists a probabilistic polynomial timealgorithm that for anyr?Rreturns a

random element inf-1(r). The authors of [6] show that iff:S→Gis an admissible encoding in this sense, then the Boneh- Franklin scheme is secure withH(m) =f(h(m)), in the random oracle model forh:{0,1}?→S. Since the functionfGis easily seen to be an admissible encoding under the previous definition, this shows that withHGBoneh-Franklin is provably secure in the random oracle model forh. In this paper, we introduce a new notion of admissible encoding that is more general than the

previous notion. This enables us to define admissible encodings to ordinary elliptic curves as well as

supersingular ones. Moreover, we show that the resulting hash functions are indifferentiable from a random oracle; therefore, they can be used in any cryptosystem, not only in Boneh-Franklin. The Shallue-Woestijne-Ulas Algorithm.The first algorithm to generate elliptic curve points in deterministicpolynomial time was published in ANTS 2006 by Shallue and Woestijne [31]. The maps

were later simplified and generalized to hyperelliptic curves by Ulas in [34]; we recall those maps in

the following result. Lemma 1 (Ulas [34]).LetFqbe a finite field and letg(x) :=x3+ax+b, wherea,b?= 0. Let: X

1(t,u) =u X2(t,u) =-b

a? 1 +

1t4g(u)2+t2g(u)?

X

3(t,u) =t2g(u)X2(t,u)U(t,u) =t3g(u)2g(X2(t,u))

Then U(t,u)2=g(X1(t,u))·g(X2(t,u))·g(X3(t,u)) (2) From equation (2) at least one ofg(X1(t,u)),g(X2(t,u)) andg(X3(t,u)) must be a quadratic residue. Therefore, eitherX1(t,u),X2(t,u) orX3(t,u) is the abscissa of a point on the curvey2=g(x). Computing the correspondingyrequires to compute a square root; whenq≡3 (mod 4), this is simply an exponentiation. However forq≡1 (mod 4), no deterministic algorithm is known for computing square roots. The Tonelli-Shanks algorithm [30] requires to use a non-quadratic residue, and it is unknown how to generate such non-quadratic residue deterministically. One of the main contributions

of [31] is to show a deterministic variant of the Tonelli-Shanks algorithm when an equality of the form

a

0a1a2=b2holds, as with equation (2); this gives a deterministic encoding algorithm even forq≡1

(mod 4). In Section 7, we provide a simplified version of the Ulas maps whenq≡3 (mod 4). This enables to slightly improve the efficiency of the SWU algorithm. Icart"s Function.Consider an elliptic curveEover a finite fieldFq, withqodd and congruent to

2 mod 3, with equation:

Y

2=X3+aX+b

Icart"s function is defined in [23] as the mapfa,b:Fq→E(Fq) such thatfa,b(u) = (x,y) where: x=? v

2-b-u6

27?
1/3 +u23y=ux+v v=3a-u46u foru?= 0, andfa,b(0) =O, the neutral element of the elliptic curve. Whenq≡2 (mod 3) we have thatx?→x3is a bijection inFqso cube roots are uniquely defined withx1/3=x(2q-1)/3. We recall the following properties offa,b: Lemma 2 (Icart).The functionfa,bis computable in deterministic polynomial time. For any point ??fa,b(Fq), the setf-1 a,b(?)is computable in polynomial time and#f-1 #fa,b(Fq)< q. We note that Icart"s function can also be defined in a field of characteristic 2 (see Appendix D). Summary.Table 1 lists currently published encoding algorithms intoordinary elliptic curves and their properties. char(K)normal formdiscriminantΔencodingcondition ?= 2,3y2=x3+ax+b-16(4a3+ 27b2)

Icart [23]p≡2 (mod 3)

SW [31]-

SWU [34]-

SWU, Sec. 7p≡3 (mod 4)

2y2+xy=x3+ax2+bbIcart [23]oddn

SW [31]-

3y2=x3+ax2+b-a3b

Sec. 8.1Δ?Q

Sec. 8.2Δ /?Q

Sec. 8.3-

Table 1.Known deterministic hashing algorithms into ordinary elliptic curves with discriminantΔ?= 0. We denote by

Qthe set of quadratic residues. In char 2 we denote bynthe extension degree.

2.2 Indifferentiability

We recall the notion of indifferentiability introduced by Maureret al.in [26]. We define anideal

primitiveas an algorithmic entity which receives inputs from one of the parties and delivers its output

immediately to the querying party. Arandom oracle[3] into a finite setSis an ideal primitive which provides a random output inSfor each new query; identical input queries are given the same answer. Definition 2 (Indifferentiability [26]).A Turing machineCwith oracle access to an ideal primi-

tivehis said to be(tD,tS,qD,ε)-indifferentiable from an ideal primitiveHif there exists a simulator

Swith oracle access toHand running in time at mosttS, such that for any distinguisherDrunning in time at mosttDand making at mostqDqueries, it holds that:???Pr?

DCh,h= 1?

-Pr?

DH,SH= 1?

C his said to be indifferentiable fromHifεis a negligible function of the security parameterk, for polynomially boundedqD,tDandtS.

F◦hhHS

D 0/1

Fig.1.The indifferentiability notion, illustrated with constructionCh=F◦hfor some functionF, and random oracles

handH. It is shown in [26] that the indifferentiability notion is the"right" notion for substituting one ideal primitive by a construction based on another ideal primitive. That is, if the constructionCh is indifferentiable from an ideal primitiveH, thenChcan replaceHin any cryptosystem, and the resulting cryptosystem is at least as secure in thehmodel as in theHmodel; see [26] or [15] for a proof. We also recall the definition of statistically indistinguishable distributions. Definition 3.LetXandYbe two random variables over a setS. The distributions ofXandYare

ε-statistically indistinguishable if:

s?S??

The two distributions are statistically indistinguishable ifεis a negligible function of the security

parameter.

3 Admissible Encodings and Indifferentiability

Our goal is to construct a hash function into elliptic curvesthat is indifferentiable from a random oracle. First, we introduce our new notion ofadmissible encoding. Definition 4 (Admissible Encoding).A functionF:S→Rbetween finite sets is anε-admissible encoding if it satisfies the following properties:

1. Computable:Fis computable in deterministic polynomial time.

2. Regular: forsuniformly distributed inS, the distribution ofF(s)isε-statistically indistinguishable

from the uniform distribution inR.

3. Samplable: there is an efficient randomized algorithmIsuch that for anyr?R,I(r)induces a

distribution that isε-statistically indistinguishable from the uniform distribution inF-1(r). Fis an admissible encoding ifεis a negligible function of the security parameter. Our new definition can be seen as a generalization of Definition 1 recalled in Section 2.1. Namely

Criterion 2 of our definition gives:

r?R????

Prs[F(s) =r]-1

#R???? r?R???? #F-1(r)#S-1#R???? whereas Criterion 2 from Definition 1 requires #F-1(r) = #S/#Rfor allr?R; this is equivalent to

ε= 0 in (3).

The following theorem shows that ifF:S→Ris an admissible encoding, then the hash function

H:{0,1}?→Rwith:

H(m) :=F(h(m))

is indifferentiable from a random oracle intoRwhenh:{0,1}?→Sis seen as a random oracle. This shows that the constructionH(m) =F(h(m)) can replace a random oracle intoR, and the resulting scheme remains secure in the random oracle model forh. Theorem 1.LetF:S→Rbe anε-admissible encoding. The constructionH(m) =F(h(m))is

(tD,tS,qD,ε?)-indifferentiable from a random oracle, in the random oracle model forh:{0,1}?→S,

withε?= 4qDεandtS= 2qD·tI, wheretIis the maximum running time ofF"s sampling algorithm.

Proof.We first describe our simulator; then we prove the indistinguishability property. As illustrated

in Figure 1, the simulator must simulate random oraclehto the distinguisherD, and the simulator has oracle access to random oracleH. It maintains a listLof previously answered queries. Our simulator is based on sampling algorithmIfromF.

SimulatorS:

Input:m? {0,1}?

Output:s?S

1. If (m,s)?L, then returns

2. QueryH(m) =rand lets← I(r)

3. Append (m,s) toLand returns.

We must show that the systems (Ch,h) and (H,SH) are indistinguishable. We consider a distin- guisher making at mostqDqueries. Without loss of generality, we can assume that the distinguisher makes all queries toh(m) (orSH) for which there was a query toCh(m) (orH(m)), and conversely; this gives a total of at most 2qDqueries. We can then describe the full interaction between the distinguisher and the system as a sequence of triples: wheresi=h(mi) (orSH(mi)) andri=Ch(mi) (orH(mi)). Without loss of generality we assume that themi"s are distinct. In system (Ch,h) we have thatsi=h(mi). Therefore thesi"s are uniformly and independently distributed inS. Moreover we haveri=Ch(mi) =F(si) for alli. In system (H,SH) we have thatri=H(mi). Therefore theri"s are uniformly and independently distributed inR. Moreover we havesi=I(ri) for alli. Lemma 3.Forruniformly distributed inR, the distribution ofs=I(r)is2ε-statistically indistin- guishable from the uniform distribution inS. s?S????

Prω,r[I(r) =s]-1

#S???? Givens?S, we haveI(r) =sonly ifr=f(s). Therefore, Prω,r[I(r) =s] = Prω[I(r) =s]/#Rwith r=f(s). This gives: r?R? s?F-1(r)1 #R????

Prω[I(r) =s]-#R#S????

(4) 1:=? r?R????

Prs[f(s) =r]-1

#R???? r?R???? #F-1(r)#S-1#R???? r?R? s?F-1(r)1#R???? #R#S-1#F-1(r)???? (5) Moreover by definition for allr?Rthe distribution ofI(r) isε-statistically indistinguishable from the uniform distribution inF-1(r); this gives for allr?R: s?F-1(r)????

Prω[I(r) =s]-1

#F-1(r)???? which gives by summation overr?R: 2:=? r?R? s?F-1(r)1 #R????

Prω[I(r) =s]-1#F-1(r)????

< ε(6) From Lemma 3 we obtain that in system (H,SH) the distribution ofsi=I(ri) is 2ε-indistinguisha- ble from the uniform distribution inS. Moreover from the definition of algorithmIwe have that r i=F(si) except ifsi=?. Therefore, the statistical distance betweenViewin system (Ch,h) and Viewin system (H,SH) is at most 4qDε. This concludes the proof of Theorem 1.??

4 Our Main Construction

LetEbe an elliptic curve over a finite fieldFqwithq≡2 (mod 3). Letf:Fq→E(Fq) denote Icart"s

function toE. It is easy to see that Icart"s functionfisnotan admissible encoding intoEsince as mentioned previously, the image offcomprises only a fraction of the elliptic curve points. Therefore we cannot use the constructionH(m) =f(h(m)) for indifferentiable hashing (not even on the image fsince the distribution off(u) is not uniform inf(Fq) for uniformu?Fq). In this section, we describe a different construction which is almost as efficient. We consider the following mapF: (Fq)2?→E(Fq) introduced by Icart in [23]:

F(u1,u2) =f(u1) +f(u2) (7)

and we letH(m) :=F(h1(m),h2(m)). We prove the following theorem: Theorem 2.Ifq >213is any2k-bit prime power congruent to2 mod 3(even or odd), and if the j-invariant ofEis not in{0;2592}, then the function

H(m) :=f(h1(m)) +f(h2(m))

is(tD,tS,qD,ε?)-indifferentiable from a random oracle, whereε?= 210·qD·2-k, in the random oracle

model forh1,h2:{0,1}?→Fq. Theorem 2 implies that this constructionH(m) can be used in any cryptosystem provably secure with random oracles into elliptic curves, and the resultingcryptosystem remains secure in the random oracle model forh1andh2. We note that to prevent timing attacks (as in [9]), our constructionHcan easily be implemented in constant time since Icart"s function can be implemented in constant time.

To prove this result, it is enough, in view of Theorem 1, to show that the functionF: (Fq)2→E(Fq)

given by is anε-admissible encoding withε= 28·q-1/2. Fis clearly computable in deterministic polynomial time, soCriterion 1 of admissible encodings is satisfied. To prove Criterion 2, we denote for any??E(Fq):

N(?) = #{(u,v)?(Fq)2|f(u) +f(v) =?}= #F-1(?)

Proposition 1.Ifqis an odd prime power congruent to2 mod 3, and if thej-invariant ofEis not in{0;2592}, then for every point??E(Fq)except at most144, we have q Sections A.1 and A.2 in Appendix are devoted to the proof of this proposition. Intuitively, the idea of the proof is to show that, for all points??E(Fq) except a few exceptional ones,F-1(?) is an irreducible algebraic curve of bounded genus in the affine planeA2overFq. The estimate for the number of points then follows from the Hasse-Weil bound. We also show in Appendix A.3 that the result extends to Icart"s functionfin characteristic 2.

4.1 Admissibility ofF(u,v) =f(u) +f(v)

We can now prove thatε-admissibility, and hence Theorem 2, easily follow from Proposition 1. Since

Fis clearly computable, it suffices to show that it isε-regular andε-samplable. Now, for any?not

among the exceptional points, we have ?#F-1(?) #(Fq)2-1#E(Fq)???? +????1q-1#E(Fq)???? 27

And on the other hand, for exceptional points?:

?#F-1(?) #(Fq)2-1#E(Fq)???? Thus, the statistical distance between the distribution ofF(u,v) for uniform (u,v) and the uniform distribution on the curve can be bounded as ??E(Fq)???? N(?) q2-1#E(Fq)???? forq >213, as required. This provesε-regularity, withε= 28·q-1/2. To see thatFisε-samplable, one can consider the following randomized sampling algorithm, where cis some constant to be determined later. Note that computingthe setSin step 3 amounts to solving univariate polynomial equations overFq, which is easily done in polynomial time using an algorithm such as Berlekamp"s [4].

Algorithm 1Sampling algorithm forF

1:repeat?c·lgq?times

2: pickv?Fquniformly at random

3:S←f-1??-f(v)?

4:ifS=∅then

5: next iteration

6:else

7: pickiuniformly at random in{1,2,3,4}

9:u←i-th element ofS

10:return(u,v)

11:else

12: next iteration

13:end if

14:end if

15:end repeat

16:return?

Since the image offcontains roughly 5/8·#E(Fq) points (as proved in [17,18]), a pigeonhole argument shows thatS?=∅with probability at least 2·5/8-1 = 1/4. Furthermore, we always have c=1

2lg(16/15), we find that Algorithm 1 succeeds with probability greater than 1-ε/2, and steps

7-13 ensure that it yields the uniform distribution onF-1(?). This concludes the proof thatFis an

admissible encoding.

5 A More General Construction

Our construction of Section 4 has the advantage of being simple and efficient as it only requires two

evaluations of Icart"s function. However, the proof involves somewhat technical tools from algebraic geometry, and it is not so simple to adapt to other encoding functions, such as the SWU algorithm. At the cost of a small performance penalty, however, we describe a more general construction that applies to a large class of encoding functions satisfying a few simple axioms. Those encoding

functions include Icart"s function, a simpler variant of the SWU function, new deterministic encodings

in characteristic 3, etc. We call themweak encodings. They are defined as follows. Definition 5 (Weak Encoding).A functionf:S→Rbetween finite sets is said to be anα-weak encoding if it satisfies the following properties:

1. Computable:fis computable in deterministic polynomial time.

2.α-bounded: forsuniformly distributed inS, the distribution off(s)isα-bounded inR,i.e.the

3. Samplable: there is an efficient randomized algorithmIsuch thatI(r)induces the uniform distri-

bution inf-1(r)for anyr?R. AdditionallyI(r)returnsNr= #f-1(r)for allr?R. The functionfis aweak encodingifαis a polynomial function of the security parameter. The main difference with an admissible encoding is that in Criterion 2, the distribution off(s)

is only required to beα-bounded instead of beingε-indistinguishable from the uniform distribution.

More precisely Criterion 2 for a weak encoding requires: ?r?R,Prs[f(s) =r] =#f-1(r)quotesdbs_dbs17.pdfusesText_23

[PDF] idesign data solutions private limited

[PDF] idfc bank forex rates

[PDF] idioms and phrases with meaning and sentences pdf

[PDF] idioms speech therapy goals

[PDF] idubbbz twitter account

[PDF] ied paris 8

[PDF] ieee 1588

[PDF] ieee abstract format

[PDF] ieee abstract size

[PDF] ieee citation

[PDF] ieee citation example

[PDF] ieee conference paper structure

[PDF] ieee font download

[PDF] ieee heading font

[PDF] ieee paper format