RST model: Difference between revisions

Revision as of 19:07, 5 August 2013

In 1997, Moni Naor and Omer Reingold described efficient constructions for various cryptographic primitives in private key as well as public-key cryptography. Their result is the construction of an efficient pseudorandom function. Let p and l be prime numbers with l |p-1. Select an element g ∈ ${𝔽_{p}}^{*}$ of multiplicative order l. Then for each n-dimensional vector a = (a₁, ..., a_n)∈ $(𝔽_{l})^{n}$ they define the function

f_{a} (x) = g^{a_{1}^{x_{1}} a_{2}^{x_{2}} ... a_{n}^{x_{n}}} \in 𝔽_{p}

where x = x₁ ... x_n is the bit representation of integer x, 0 ≤ x ≤ 2^n-1, with some extra leading zeros if necessary.^[1]

Example

Let p = 7, p – 1 = 6, and l = 3, l |p-1. Select g = 4 ∈ ${𝔽_{7}}^{*}$ of multiplicative order 3 (since 4³ = 64 ≡ 1 mod 7). For n = 3, a = (1, 2, 1) and x = 5 (the bit representation of 5 is 101), we can compute $f_{a} (5)$ as follows:

f_{a} (x) = g^{a_{1}^{x_{1}} a_{2}^{x_{2}} ... a_{n}^{x_{n}}}

f_{a} (5) = 4^{1^{1} 2^{0} 1^{1}} = 4^{1} = 4 \in 𝔽_{7}

Efficiency

The evaluation of function $f_{a} (x)$ in the Naor-Reingold construction can be done very efficiently. Computing the value of the function $f_{a} (x)$ at any given point is comparable with one modular exponentiation and n-modular multiplications. This function can be computed in parallel by threshold circuits of bounded depth and polynomial size.

The Naor-Reingold function can be used as the basis of many cryptographic schemes including symmetric encryption, authentication and digital signatures.

Security of the Function

Assume that an attacker sees several outputs of the function, e.g. $f_{a} (1) = g^{a_{1}}, f_{a} (2) = g^{a_{2}}, f_{a} (3) = g^{a_{1} a_{2}}$ , ... $f_{a} (k) = g^{a_{1}^{x_{1}} a_{2}^{x_{2}} ... a_{n}^{x_{n}}}$ and wants to compute $f_{a} (k + 1)$ . Assume for simplicity that x₁ = 0, then the attacker needs to solve the Computational Diffie-Hellman (CDH) between $f_{a} (1) = g^{a_{1}}$ and $f_{a} (k) = g^{a_{2}^{x_{2}} ... a_{n}^{x_{n}}}$ to get $f_{a} (k + 1) = g^{a_{1} a_{2}^{x_{2}} \dots a_{n}^{x_{n}}}$ . In general, moving from k to k +1 changes the bit pattern and unless k + 1 is a power of 2 one can split the exponent in $f_{a} (k + 1)$ so that the computation corresponds to computing the Diffie-Hellman key between two of the earlier results. This attacker wants to predict the next sequence element. Such an attack would be very bad—but it's also possible to fight it off by working in groups with a hard Diffie-Hellman problem (DHP).

Example: An attacker sees several outputs of the function e.g. $f_{a} (5) = 4^{1^{1} 2^{0} 1^{1}} = 4^{1} = 4$ , as in the previous example, and $f_{a} (1) = 4^{1^{0} 2^{0} 1^{1}} = 4^{1} = 4$ . Then, the attacker wants to predict the next sequence element of this function, $f_{a} (6)$ . However, the attacker cannot predict the outcome of $f_{a} (6)$ from knowing $f_{a} (1)$ and $f_{a} (5)$ .

There are other attacks that would be very bad for a Pseudorandom Number Generator: the user expects to get random numbers from the output, so of course the stream should not be predictable, but even more, it should be indistinguishable from a random string. Let $𝒜^{f}$ denote the algorithm $𝒜$ with access to an oracle for evaluating the function $f_{a} (x)$ . Suppose the Decisional Diffie-Hellman assumption holds for $𝔽_{p}$ , Naor and Reingold show that for every probabilistic polynomial time algorithm $𝒜$ and sufficiently large n

Pr [𝒜^{f_{a} (x)} (p, g) \to 1] - Pr [𝒜^{R} (p, g) \to 1]

is negligible.

The first probability is taken over the choice of the seed s = (p, g, a) and the second probability is taken over the random distribution induced on p, g by $ℐ 𝒢 (n)$ , instance generator, and the random choice of the function $R_{a} (x)$ among the set of all ${0, 1}^{n} \to 𝔽_{p}$ functions.^[2]

Linear Complexity

One natural measure of how useful a sequence may be for cryptographic purposes is the size of its linear complexity. The linear complexity of an n-element sequence W(x), x = 0,1,2,…,n – 1, over a ring $ℛ$ is the length l of the shortest linear recurrence relation W (x + l) = A_l-1 W (x +l-1) + … + A₀ W(x), x = 0,1,2,…, n – l –1 with A₀, …, A_l-1 ∈ $ℛ$ , which is satisfied by this sequence.

For some $γ$ > 0,n ≥ (1+ $γ$ ) $\log l$ , for any $δ > 0$ , sufficiently large l, the linear complexity of the sequence $f_{a} (x)$ ,0 ≤ x ≤ 2^n-1, denoted by $L_{a}$ satisfies

L_{a} ⩾ {\begin{matrix} l^{1 - δ} & , if γ ⩾ 2 \\ l^{(\frac{γ}{2 - δ})} & , if γ < 2 \end{matrix}

for all except possibly at most $3 (l - 1)^{n - δ}$ vectors a ∈ $(𝔽_{l})^{n}$ .^[3] The bound of this work has disadvantages, namely it does not apply to the very interesting case $\log p \approx \log n \approx n .$

Uniformity of Distribution

The statistical distribution of $f_{a} (x)$ is exponentially close to uniform distribution for almost all vectors a ∈ $(𝔽_{l})^{n}$ .

Let $𝐃_{a}$ be the discrepancy of the set ${f_{a} (x) | 0 \leq x \leq 2^{n - 1}}$ . Thus, if $n = \log p$ is the bit length of p then for all vectors a ∈ $(𝔽_{l})^{n}$ the bound $𝐃_{a} \leq Δ (l, p)$ holds, where

$Δ (l, p) = {\begin{matrix} p^{(\frac{1 - γ}{2})} l^{(\frac{- 1}{2})} \log^{2} p & , if l ⩾ p^{γ} \\ p^{(\frac{1}{2})} l^{- 1} \log^{2} p & , if p^{γ} > l ⩾ p^{(\frac{2}{3})} \\ p^{(\frac{1}{4})} l^{(\frac{- 5}{8})} \log^{2} p & , if p^{(\frac{2}{3})} > l ⩾ p^{(\frac{1}{2})} \\ p^{(\frac{1}{8})} l^{(\frac{- 3}{8})} \log^{2} p & , if p^{(\frac{1}{2})} > l ⩾ p^{(\frac{1}{3})} \end{matrix}$

and $γ$ = 2.5 - $\log 3$ = 0.9150....

Although this property does not seem to have any immediate cryptographic implications, the inverse fact, namely non uniform distribution, if true would have disastrous consequences for applications of this function.^[4]

Sequences in Elliptic Curve

The elliptic curve version of this function is of interest as well. In particular, it may help to improve the cryptographic security of the corresponding system. Let p > 3 be prime and let E be an elliptic curve over $𝔽_{p}$ , then each vector a defines a finite sequence in the subgroup $⟨ G ⟩$ as:

F_{a} (x) = (a_{1}^{x_{1}} a_{2}^{x_{2}} \dots a_{n}^{x_{n}}) G

where $x = x_{1} \dots x_{n}$ is the bit representation of integer $x, 0 \leq x \leq 2^{n - 1}$ . The Naor-Reingold elliptic curve sequence is defined as

u_{k} = X (f_{a} (k)) where X (P) is the abscissa of P \in E .

^[5]

If the Decisional Diffie-Hellman assumption holds, the index k is not enough to compute $u_{k}$ in polynomial time, even if an attacker performs polynomially many queries to a random oracle.

Notes

43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.

References

Many property agents need to declare for the PIC grant in Singapore. However, not all of them know find out how to do the correct process for getting this PIC scheme from the IRAS. There are a number of steps that you need to do before your software can be approved.

Naturally, you will have to pay a safety deposit and that is usually one month rent for annually of the settlement. That is the place your good religion deposit will likely be taken into account and will kind part or all of your security deposit. Anticipate to have a proportionate amount deducted out of your deposit if something is discovered to be damaged if you move out. It's best to you'll want to test the inventory drawn up by the owner, which can detail all objects in the property and their condition. If you happen to fail to notice any harm not already mentioned within the inventory before transferring in, you danger having to pay for it yourself.

In case you are in search of an actual estate or Singapore property agent on-line, you simply should belief your intuition. It's because you do not know which agent is nice and which agent will not be. Carry out research on several brokers by looking out the internet. As soon as if you end up positive that a selected agent is dependable and reliable, you can choose to utilize his partnerise in finding you a home in Singapore. Most of the time, a property agent is taken into account to be good if he or she locations the contact data on his website. This may mean that the agent does not mind you calling them and asking them any questions relating to new properties in singapore in Singapore. After chatting with them you too can see them in their office after taking an appointment.

Have handed an trade examination i.e Widespread Examination for House Brokers (CEHA) or Actual Property Agency (REA) examination, or equal; Exclusive brokers are extra keen to share listing information thus making certain the widest doable coverage inside the real estate community via Multiple Listings and Networking. Accepting a severe provide is simpler since your agent is totally conscious of all advertising activity related with your property. This reduces your having to check with a number of agents for some other offers. Price control is easily achieved. Paint work in good restore-discuss with your Property Marketing consultant if main works are still to be done. Softening in residential property prices proceed, led by 2.8 per cent decline within the index for Remainder of Central Region

Once you place down the one per cent choice price to carry down a non-public property, it's important to accept its situation as it is whenever you move in – faulty air-con, choked rest room and all. Get round this by asking your agent to incorporate a ultimate inspection clause within the possibility-to-buy letter. HDB flat patrons routinely take pleasure in this security net. "There's a ultimate inspection of the property two days before the completion of all HDB transactions. If the air-con is defective, you can request the seller to repair it," says Kelvin.

15.6.1 As the agent is an intermediary, generally, as soon as the principal and third party are introduced right into a contractual relationship, the agent drops out of the image, subject to any problems with remuneration or indemnification that he could have against the principal, and extra exceptionally, against the third occasion. Generally, agents are entitled to be indemnified for all liabilities reasonably incurred within the execution of the brokers´ authority.

To achieve the very best outcomes, you must be always updated on market situations, including past transaction information and reliable projections. You could review and examine comparable homes that are currently available in the market, especially these which have been sold or not bought up to now six months. You'll be able to see a pattern of such report by clicking here It's essential to defend yourself in opposition to unscrupulous patrons. They are often very skilled in using highly unethical and manipulative techniques to try and lure you into a lure. That you must also protect your self, your loved ones, and personal belongings as you'll be serving many strangers in your home. Sign a listing itemizing of all of the objects provided by the proprietor, together with their situation. HSR Prime Recruiter 2010
Many property agents need to declare for the PIC grant in Singapore. However, not all of them know find out how to do the correct process for getting this PIC scheme from the IRAS. There are a number of steps that you need to do before your software can be approved.

Naturally, you will have to pay a safety deposit and that is usually one month rent for annually of the settlement. That is the place your good religion deposit will likely be taken into account and will kind part or all of your security deposit. Anticipate to have a proportionate amount deducted out of your deposit if something is discovered to be damaged if you move out. It's best to you'll want to test the inventory drawn up by the owner, which can detail all objects in the property and their condition. If you happen to fail to notice any harm not already mentioned within the inventory before transferring in, you danger having to pay for it yourself.

In case you are in search of an actual estate or Singapore property agent on-line, you simply should belief your intuition. It's because you do not know which agent is nice and which agent will not be. Carry out research on several brokers by looking out the internet. As soon as if you end up positive that a selected agent is dependable and reliable, you can choose to utilize his partnerise in finding you a home in Singapore. Most of the time, a property agent is taken into account to be good if he or she locations the contact data on his website. This may mean that the agent does not mind you calling them and asking them any questions relating to new properties in singapore in Singapore. After chatting with them you too can see them in their office after taking an appointment.

Have handed an trade examination i.e Widespread Examination for House Brokers (CEHA) or Actual Property Agency (REA) examination, or equal; Exclusive brokers are extra keen to share listing information thus making certain the widest doable coverage inside the real estate community via Multiple Listings and Networking. Accepting a severe provide is simpler since your agent is totally conscious of all advertising activity related with your property. This reduces your having to check with a number of agents for some other offers. Price control is easily achieved. Paint work in good restore-discuss with your Property Marketing consultant if main works are still to be done. Softening in residential property prices proceed, led by 2.8 per cent decline within the index for Remainder of Central Region

Once you place down the one per cent choice price to carry down a non-public property, it's important to accept its situation as it is whenever you move in – faulty air-con, choked rest room and all. Get round this by asking your agent to incorporate a ultimate inspection clause within the possibility-to-buy letter. HDB flat patrons routinely take pleasure in this security net. "There's a ultimate inspection of the property two days before the completion of all HDB transactions. If the air-con is defective, you can request the seller to repair it," says Kelvin.

15.6.1 As the agent is an intermediary, generally, as soon as the principal and third party are introduced right into a contractual relationship, the agent drops out of the image, subject to any problems with remuneration or indemnification that he could have against the principal, and extra exceptionally, against the third occasion. Generally, agents are entitled to be indemnified for all liabilities reasonably incurred within the execution of the brokers´ authority.

To achieve the very best outcomes, you must be always updated on market situations, including past transaction information and reliable projections. You could review and examine comparable homes that are currently available in the market, especially these which have been sold or not bought up to now six months. You'll be able to see a pattern of such report by clicking here It's essential to defend yourself in opposition to unscrupulous patrons. They are often very skilled in using highly unethical and manipulative techniques to try and lure you into a lure. That you must also protect your self, your loved ones, and personal belongings as you'll be serving many strangers in your home. Sign a listing itemizing of all of the objects provided by the proprietor, together with their situation. HSR Prime Recruiter 2010

↑ Cite error: Invalid <ref> tag; no text was provided for refs named "NaorReingold".
↑ Cite error: Invalid <ref> tag; no text was provided for refs named "DDHBoneh".
↑ Cite error: Invalid <ref> tag; no text was provided for refs named "ShparlinskiLinearComplexity".
↑ Cite error: Invalid <ref> tag; no text was provided for refs named "ShparlinskiUniformity".
↑ Cite error: Invalid <ref> tag; no text was provided for refs named "EllipticNaor".

[NaorReingold-1] Cite error: Invalid <ref> tag; no text was provided for refs named "NaorReingold".

[DDHBoneh-2] Cite error: Invalid <ref> tag; no text was provided for refs named "DDHBoneh".

[ShparlinskiLinearComplexity-3] Cite error: Invalid <ref> tag; no text was provided for refs named "ShparlinskiLinearComplexity".

[ShparlinskiUniformity-4] Cite error: Invalid <ref> tag; no text was provided for refs named "ShparlinskiUniformity".

[EllipticNaor-5] Cite error: Invalid <ref> tag; no text was provided for refs named "EllipticNaor".

[1]

[2]

[3]

[4]

[5]

@@ Line 1: / Line 1: @@
-Dremel is the brand name of a higher-speed rotary tool that is hand-held and versatile, generating woodworking fun as effectively as inventive and practical. Plastic mold grinding wheel and workpiece is to rely on relative motion to reach, it not only has a precision rotary grinding wheel movement, but also the components with Plastic mold linear motion, its accuracy should be within the .1�/100mm.  Given that I use my rotary tool typically, I stick with Dremel for the speed manage and for the reason that [http://Www.Thefreedictionary.com/I+trust I trust] Bosch a bit much more than I'd trust a B&D copycat. I never actually have an opinion on the tool itself.<br><br>In his lifetime, Mr. Dremel owned 55 patents on a wide range of items-from electric erasers to a gas-powered rotary lawn mower.  Higher speed rotary tools for engraving is the quickest, easiest way to engrave shapes or letters, numbers onto components such as glass or metal or even wood.  Nice factor about making use of a tool like the Dremel is that it has a number of interchangeable bits.  But, with a small practice, anybody can use a Dremel tool and get superb results.<br><br>Expertise of these components also aids in the effective and effective use of the tool.  It is also vital to note that bigger rotary hammer drills may possibly not have a reversing feature. A rotary hammer drill should definitely be capable of drilling the largest hole into masonry you will ever have to have to drill.  Try to remember to guarantee it is a 3-mode model if you call for a tool for light chiseling and breaking needs.<br><br>Though making use of the golf club style, you hold the rotary tool so your palm faces up against the tool and your thumb points towards the small business end of the tool.  An significant component of each hold style is that the vents have to remain open so the motor can breathe and stay cool, so do not cover the air vents when applying the rotary tool.  Also, permit the Craftsman rotary tool to full the function at its own pace.<br><br>The rotary cutters consist of a few parts, the manage which consists of a molded deal with and the head with a bolt for the blade to be attached and the nut that fits more than the bolt, securing the blade in place.  The 1st blades manufactured for the [http://statigr.am/tag/fabric+rotary fabric rotary] cutters have been straight edges, but now there are ones with a fluted, curved edge which offers a unique flare to the material applied in the quilt. You have to get the feel� for how a rotary tool handles.<br><br>The one complaint we did uncover was that the user had difficulty getting all the accessories back in the kit appropriately. The Dremel 4000 Rotary Kit is a great rotary tool kit that truly performs as the manufacturer claims.  Made for light-duty jobs, the Dremel 7300-N/eight Cordless Two-Speed Rotary Tool Kit can quickly drill, sand, shape, or detail a wide variety of materials utilizing Dremel accessories with up to an 1/eight-inch shank.<br><br>Insert smaller sized rotary bits for grinding, gouging and shaping your project as it begins to mold into the type you wish. The tool will grind off less wood at slower speeds, providing you more handle more than your carving. Put on safety goggles when working with your Dremel tool to stay clear of getting sawdust in your eyes. You never have to blow the bank on a single of these tools just to get the rotary tool that fits your requirements.<br><br>There are also smaller sized rotary tools which run on low revolutions per minute (RPM).  Effectively, at the finish of this getting guide you will be capable to determine the right power tool for your construction projects. First of all, rotary tools present heightened speeds during a variety of construction applications.   If you loved this information and you would love to receive details concerning [http://www.bestoscillatingtoolreviews.com/belt-sander-reviews-find-the-best-model/ Http://www.bestoscillatingtoolreviews.com/] please visit the web page. Moreover you need to invest in rotary tools that incorporate speed adjustment knobs, which give less difficult management more than each and every phase of the construction task.
+In 1997, [[Moni Naor]] and [[Omer Reingold]] described efficient constructions for various [[cryptographic primitive]]s in private key as well as [[public-key cryptography]]. Their result is the construction of an efficient [[pseudorandom function family|pseudorandom function]]. Let ''p'' and ''l'' be [[prime number]]s with ''l'' |''p''-1. Select an element ''g'' ∈ <math> {\mathbb F_p}^*</math> of [[multiplicative order]] ''l''. Then for each n-dimensional [[coordinate vector|vector]] ''a'' = (''a''<sub>''1''</sub>, ..., ''a''<sub>''n''</sub>)∈ <math> (\mathbb F_{l})^{n} </math> they define the function
+:<math>f_{a}(x) = g^{a_{1}^{x_{1}} a_{2}^{x_{2}}...a_{n}^{x_{n}}} \in \mathbb F_p </math>
+where x = x<sub>''1''</sub> ... x<sub>''n''</sub> is the [[Binary_numeral_system#Representation|bit representation]] of integer x, 0 ≤ x ≤ 2<sup>n-1</sup>, with some extra leading zeros if necessary.<ref name="NaorReingold"/>
+==Example==
+Let ''p'' = 7, ''p'' – 1 = 6, and ''l'' = 3, ''l'' |''p''-1. Select ''g'' = 4 ∈ <math> {\mathbb F_7}^*</math> of multiplicative order 3 (since 4<sup>3</sup> = 64 ≡ 1 mod 7).  For n = 3, a = (1, 2, 1) and x = 5 (the bit representation of 5 is 101), we can compute <math> f_{a}\;(5)</math> as follows:
+:<math>f_{a}(x) = g^{a_{1}^{x_{1}} a_{2}^{x_{2}}...a_{n}^{x_{n}}}</math>
+:<math>f_{a}(5) = 4^{1^{1} 2^{0} 1^{1}} = 4^{1} = 4 \in \mathbb F_7 </math>
+==Efficiency==
+The evaluation of function <math> f_{a}\;(x)</math> in the '''Naor-Reingold''' construction can be done very efficiently. Computing the value of the function <math> f_{a}\;(x)</math> at any given point is comparable with one [[modular exponentiation]] and  n-modular multiplications. This function can be computed in parallel by threshold circuits of bounded depth and polynomial size.
+The '''Naor-Reingold''' function can be used as the basis of many [[cryptography|cryptographic]]  schemes including [[Symmetric-key algorithm|symmetric encryption]], [[authentication]] and [[digital signatures]].
+==Security of the Function==
+	Assume that an attacker sees several outputs of the function, e.g. <math> f_{a}(1) = g^{a_{1}}, f_{a}(2) = g^{a_{2}}, f_{a}(3) = g^{a_{1}a_{2}}</math>, ... <math>f_{a}(k) = g^{a_{1}^{x_{1}} a_{2}^{x_{2}}...a_{n}^{x_{n}}}</math> and wants to compute <math> f_{a}\;(k + 1)</math>. Assume for simplicity that x<sub>1</sub> = 0, then the attacker needs to solve the [[Computational Diffie–Hellman assumption|Computational Diffie-Hellman (CDH)]] between <math> f_a (1)= g^{a_{1}} </math> and <math>f_{a}(k) = g^{a_{2}^{x_{2}} ...a_{n}^{x_{n}}}</math> to get <math>f_{a}(k+1) = g^{a_{1}a_{2}^{x_{2}} \dots a_{n}^{x_{n}}}</math>. In general, moving from ''k'' to ''k'' +1 changes the bit pattern and unless ''k'' + 1 is a power of 2 one can split the exponent in <math> f_{a}\;(k + 1)</math> so that the computation corresponds to computing the [[Diffie-Hellman problem|Diffie-Hellman]] key between two of the earlier results. This attacker wants to predict the next [[sequence]] element. Such an attack would be very bad—but it's also possible to fight it off by working in [[Group (mathematics)|groups]] with a hard [[Diffie-Hellman problem]] (DHP).
+'''Example:'''
+An attacker sees several outputs of the function e.g. <math>f_{a}(5) = 4^{1^{1} 2^{0} 1^{1}} = 4^{1} = 4 </math>, as in the previous example, and <math>f_{a}(1) = 4^{1^{0} 2^{0} 1^{1}} = 4^{1} = 4 </math>. Then, the attacker wants to predict the next sequence element of this function, <math> f_{a}\;(6)</math>. However, the attacker cannot predict the outcome of <math> f_{a}\;(6) </math> from knowing <math>  f_{a}\;(1)</math> and <math> f_{a}\;(5)</math>.
+There are other attacks that would be very bad for a [[Pseudorandom Number Generator]]: the user expects to get random numbers from the output, so of course the stream should not be predictable, but even more, it should be indistinguishable from a random string. Let <math> \mathcal{A}^f </math> denote the algorithm <math> \mathcal{A} </math>  with access to an oracle for evaluating the function <math> f_{a}\;(x)</math> . Suppose the [[Decisional Diffie-Hellman assumption]] holds for <math> \mathbb F_p </math>, '''Naor and Reingold''' show that for every [[PP (complexity)|probabilistic polynomial time]] algorithm <math> \mathcal{A} </math>  and sufficiently large ''n''
+: <math> \text{Pr }[\mathcal{A}^{f_{a}(x)}(p,g) \to 1] - \text{Pr }[\mathcal{A}^{R} (p,g)\to 1] </math>  is [[Negligible function|negligible]].
+The first probability is taken over the choice of the seed s = (p, g, a)  and the second probability is taken over the random distribution induced on p, g by <math> \mathcal{I}\mathcal{G} (n) </math>, instance generator, and the random choice of the function <math> R_{a}\;(x) </math> among the set of all <math> \{0,1\}^{n} \to \mathbb F_p </math> functions.<ref name="DDHBoneh"/>
+==Linear Complexity==
+One natural measure of how useful a sequence may be for [[cryptography|cryptographic]] purposes is the size of its '''linear complexity'''. The linear complexity of an ''n''-element sequence W(x), x = 0,1,2,…,n – 1, over a ring <math> \mathcal{R}</math> is the length ''l'' of the shortest linear [[recurrence relation]] W (x + ''l'') = A<sub>''l''-1</sub> W (x +''l''-1) + … + A<sub>0</sub> W(x),  x = 0,1,2,…, ''n'' – ''l'' –1 with A<sub>0</sub>, …, A<sub>''l''-1</sub> ∈ <math> \mathcal{R}</math>, which is satisfied by this sequence.
+For some <math>\gamma</math> > 0,n ≥ (1+ <math>\gamma</math>) <math>\log l</math>, for any <math>\delta > 0 </math>, sufficiently large ''l'', the linear complexity of the sequence <math> f_{a}\;(x)</math>,0 ≤ x ≤ 2<sup>n-1</sup>, denoted by <math>L_a</math> satisfies
+:<math>L_{a} \geqslant \begin{cases}
+l^{1-\ \delta\,\!} &\text{, if } \gamma\,\! \geqslant 2\\
+l^{\left (\tfrac{\ \gamma\,\!}{2-\ \delta\,\!}\right )} &\text{, if }  \gamma\,\! < 2
+\end{cases}</math>
+for all except possibly at most <math>3(l - 1)^{n - \delta}</math> vectors a ∈ <math> (\mathbb F_{l})^{n} </math>.<ref name="ShparlinskiLinearComplexity"/>  The bound of this work has disadvantages, namely it does not apply to the very interesting case <math>\log p \approx \log n \approx {n.} </math>
+==Uniformity of Distribution==
+The statistical distribution of <math> f_{a}\;(x)</math>  is exponentially close to [[Uniform distribution (discrete)|uniform distribution]] for almost all vectors a ∈ <math> (\mathbb F_{l})^{n} </math>.
+Let <math>{\mathbf D}_a</math> be the [[Inversive congruential generator|discrepancy]] of the set <math>\{f_a (x)| 0 \leq x \leq 2^{n-1}\}</math>. Thus, if <math>n = \log  p </math> is the bit length of ''p'' then for all vectors a ∈ <math> (\mathbb F_{l})^{n} </math> the bound <math>{\mathbf D}_a\leq \Delta (l,p)</math> holds, where
+<math>\Delta (l,p) = \begin{cases}
+p^{\left (\tfrac{1-\ \gamma\,\!}{2}\right )}l^{\left (\tfrac{-1}{2}\right )}\log^{2}p &\text{, if } l \geqslant p^{\gamma\,\!}\\
+p^{\left (\tfrac{1}{2}\right )}l^{-1}\log^{2}p &\text{, if } p^{\gamma\,\!} > l \geqslant p^{\left (\tfrac{2}{3}\right )}  \\
+p^{\left (\tfrac{1}{4}\right )}l^{\left (\tfrac{-5}{8}\right )}\log^{2}p &\text{, if } p^{\left (\tfrac{2}{3}\right )} > l \geqslant p^{\left (\tfrac{1}{2}\right )}  \\
+p^{\left (\tfrac{1}{8}\right )}l^{\left (\tfrac{-3}{8}\right )}\log^{2}p &\text{, if } p^{\left (\tfrac{1}{2}\right )} > l \geqslant p^{\left (\tfrac{1}{3}\right )}  \\
+\end{cases}</math>
+and <math>\gamma</math> = 2.5 - <math>\log 3 </math>= 0.9150....
+Although this property does not seem to have any immediate cryptographic implications, the inverse fact, namely non uniform distribution, if true would have disastrous consequences for applications of this function.<ref name="ShparlinskiUniformity"/>
+==Sequences in Elliptic Curve==
+The [[elliptic curve]] version of this function is of interest as well. In particular, it may help to improve the cryptographic security of the corresponding system. Let ''p'' > 3 be prime and let E be an elliptic curve  over <math> \mathbb F_p </math>, then each vector '''a''' defines a [[Sequence#Finite_and_infinite|finite sequence]] in the [[subgroup]] <math>\langle G\rangle</math> as:
+:<math>F_{a}(x) = (a_{1}^{x_{1}} a_{2}^{x_{2}}\dots a_{n}^{x_{n}})G </math>
+where <math>x = x_1 \dots  x_n</math>  is the bit representation of integer <math>x, 0 \leq x \leq 2^{n-1}</math>.
+The '''Naor-Reingold''' elliptic curve sequence is defined as
+: <math> u_{k} = X (f_{a}(k))\; \mbox{where } X (P) \mbox{ is the abscissa of}\; P \in E. </math><ref name="EllipticNaor"/>
+If the Decisional Diffie-Hellman assumption holds, the index ''k'' is not enough to compute <math>u_k</math> in polynomial time, even if an attacker performs polynomially many queries to a random oracle.
+==See also==
+*[[Decisional Diffie-Hellman assumption]]
+*[[Finite Field]]
+*[[Inversive congruential generator]]
+*[[Generalized inversive congruential pseudorandom numbers]]
+==Notes==
+{{Reflist|refs=
+<ref name="NaorReingold">Naor, M., Reingold, O. "Number-theoretic constructions of efficient pseudo-random functions," Proc 38th IEEE Symp. on Foundations of Comp. Sci, (1997), 458-467.</ref>
+<ref name="ShparlinskiLinearComplexity">Shparlinski, Igor E. "Linear Complexity of the Naor-Reingold pseudo-random function," Inform. Process Lett, 76 (2000), 95-99.</ref>
+<ref name="ShparlinskiUniformity">Shparlinski, Igor E. "On the uniformity of distribution of the Naor-Reingold pseudo-random function," Finite Fields and Their Applications, 7 (2001), 318-326</ref>
+<ref name="EllipticNaor">Cruz, M., Gomez, D., Sadornil, D. "On the linear complexity of the Naor-Reingold sequence with elliptic curves," Finite Fields and Their Applications, 16 (2010), 329-333</ref>
+<ref name="DDHBoneh">Boneh, Dan. "The Decision Diffie–Hellman Problem,"ANTS-III: Proceedings of the Third International Symposium on Algorithmic Number Theory,1998,48–63.</ref>
+  }}
+==References==
+*{{citation
+| last=Shparlinski
+| first=Igor
+| title=Cryptographic Applications of Analytic Number Theory: Complexity Lower Bounds and Pseudorandomness
+| year=2003
+| edition=first
+| publisher=Birkhäuser Basel
+| isbn=978-3-7643-6654-4
+}}
+*{{citation
+| last=Goldreich
+| first=Oded
+| title=Modern Cryptography, Probabilistic Proofs and Pseudorandomness
+| year=1998
+| edition=first
+| publisher=Springer
+| isbn=978-3-540-64766-9
+}}
+[[Category:Pseudorandom number generators]]
+[[Category:Cryptography]]

RST model: Difference between revisions

en>Bibcode Bot

Revision as of 19:07, 5 August 2013

Contents

Example

Efficiency

Security of the Function

Linear Complexity

Uniformity of Distribution

Sequences in Elliptic Curve

See also

Notes

References

Navigation menu

RST model: Difference between revisions

en>Bibcode Bot

Revision as of 19:07, 5 August 2013

Example

Efficiency

Security of the Function

Linear Complexity

Uniformity of Distribution

Sequences in Elliptic Curve

See also

Notes

References

Navigation menu

Search