Distributed point function - Revision history

Citation bot: Added isbn. | Use this bot. Report bugs. | Suggested by Abductive | Category:Cryptographic primitives | #UCB_Category 30/37

2024-11-30T03:59:53Z

Added isbn. | Use this bot. Report bugs. | Suggested by Abductive | Category:Cryptographic primitives | #UCB_Category 30/37

← Previous revision		Revision as of 03:59, 30 November 2024
Line 35:		Line 35:
	\| volume = 8441		\| volume = 8441
	\| year = 2014\| doi-access = free		\| year = 2014\| doi-access = free
			\| isbn = 978-3-642-55219-9
	}}</ref>		}}</ref>

David Eppstein: It's the same citation as everything else

2024-06-03T06:33:41Z

It's the same citation as everything else

← Previous revision		Revision as of 06:33, 3 June 2024
Line 1:		Line 1:

	In [[cryptography]], a '''distributed point function''' is a [[cryptographic primitive]] that allows two distributed processes to share a piece of information, and compute functions of their shared information, without revealing the information itself to either process. It is a form of [[secret sharing]].		In [[cryptography]], a '''distributed point function''' is a [[cryptographic primitive]] that allows two distributed processes to share a piece of information, and compute functions of their shared information, without revealing the information itself to either process. It is a form of [[secret sharing]].{{r\|gi}}

	Given any two values <math>a</math> and <math>b</math> one can define a ''point function'' <math>P_{a,b}(x)</math> (a variant of the [[Kronecker delta]] function) by		Given any two values <math>a</math> and <math>b</math> one can define a ''point function'' <math>P_{a,b}(x)</math> (a variant of the [[Kronecker delta]] function) by
Line 7:		Line 7:
	0 \qquad \text{for } x\ne a		0 \qquad \text{for } x\ne a
	\end{cases}</math>		\end{cases}</math>
	That is, it is zero everywhere except at <math>a</math>, where its value is <math>b</math>.		That is, it is zero everywhere except at <math>a</math>, where its value is <math>b</math>.{{r\|gi}}

	A distributed point function consists of a family of functions <math>f_k</math>, parameterized by keys <math>k</math>, and a method for deriving two keys <math>q</math> and <math>r</math> from any two input values <math>a</math> and <math>b</math>, such that for all <math>x</math>,		A distributed point function consists of a family of functions <math>f_k</math>, parameterized by keys <math>k</math>, and a method for deriving two keys <math>q</math> and <math>r</math> from any two input values <math>a</math> and <math>b</math>, such that for all <math>x</math>,
	:<math>P_{a,b}(x) = f_q(x) \oplus f_r(x),</math>		:<math>P_{a,b}(x) = f_q(x) \oplus f_r(x),</math>
	where <math>\oplus</math> denotes the [[bitwise operation\|bitwise exclusive or]] of the two function values. However, given only one of these two keys, the values of <math>f</math> for that key should be indistinguishable from random.		where <math>\oplus</math> denotes the [[bitwise operation\|bitwise exclusive or]] of the two function values. However, given only one of these two keys, the values of <math>f</math> for that key should be indistinguishable from random.{{r\|gi}}

	It is known ~~{{Citation needed\|date=March 2019}}~~ how to construct an efficient distributed point function from another cryptographic primitive, a [[one-way function]].		It is known how to construct an efficient distributed point function from another cryptographic primitive, a [[one-way function]].{{r\|gi}}

	In the other direction, if a distributed point function is known, then it is possible to perform [[private information retrieval]].		In the other direction, if a distributed point function is known, then it is possible to perform [[private information retrieval]].
	As a simplified example of this, it is possible to test whether a key <math>a</math> belongs to replicated distributed database without revealing to the database servers (unless they collude with each other) which key was sought. To find the key <math>a</math> in the database, create a distributed point function for <math>P_{a,1}(x)</math> and send the resulting two keys <math>q</math> and <math>r</math> to two different servers holding copies of the database. Each copy applies its function <math>f_q</math> or <math>f_r</math> to all the keys in its copy of the database, and returns the exclusive or of the results. The two returned values will differ if <math>a</math> belongs to the database, and will be equal otherwise.		As a simplified example of this, it is possible to test whether a key <math>a</math> belongs to replicated distributed database without revealing to the database servers (unless they collude with each other) which key was sought. To find the key <math>a</math> in the database, create a distributed point function for <math>P_{a,1}(x)</math> and send the resulting two keys <math>q</math> and <math>r</math> to two different servers holding copies of the database. Each copy applies its function <math>f_q</math> or <math>f_r</math> to all the keys in its copy of the database, and returns the exclusive or of the results. The two returned values will differ if <math>a</math> belongs to the database, and will be equal otherwise.{{r\|gi}}

	==References==		==References==
			{{reflist\|refs=
⚫	*{{citation

		⚫	<ref name=gi>{{citation
	\| last1 = Gilboa \| first1 = Niv		\| last1 = Gilboa \| first1 = Niv
	\| last2 = Ishai \| first2 = Yuval		\| last2 = Ishai \| first2 = Yuval
Line 33:		Line 35:
	\| volume = 8441		\| volume = 8441
	\| year = 2014\| doi-access = free		\| year = 2014\| doi-access = free
	}}		}}</ref>

			}}

	[[Category:Cryptographic primitives]]		[[Category:Cryptographic primitives]]

Pancho507: de orphaned

2024-05-09T02:49:48Z

de orphaned

← Previous revision		Revision as of 02:49, 9 May 2024
Line 1:		Line 1:
	{{Orphan\|date=June 2018}}

	In [[cryptography]], a '''distributed point function''' is a [[cryptographic primitive]] that allows two distributed processes to share a piece of information, and compute functions of their shared information, without revealing the information itself to either process. It is a form of [[secret sharing]].		In [[cryptography]], a '''distributed point function''' is a [[cryptographic primitive]] that allows two distributed processes to share a piece of information, and compute functions of their shared information, without revealing the information itself to either process. It is a form of [[secret sharing]].

OAbot: Open access bot: doi added to citation with #oabot.

2021-05-06T10:00:50Z

Open access bot: doi added to citation with #oabot.

← Previous revision		Revision as of 10:00, 6 May 2021
Line 33:		Line 33:
	\| url = http://www.bgu.ac.il/~gilboan/publications/dpfcameraready5.pdf		\| url = http://www.bgu.ac.il/~gilboan/publications/dpfcameraready5.pdf
	\| volume = 8441		\| volume = 8441
	\| year = 2014}}		\| year = 2014\| doi-access = free
			}}

	[[Category:Cryptographic primitives]]		[[Category:Cryptographic primitives]]

David Eppstein: Elisabeth Oswald

2020-10-02T17:06:14Z

Elisabeth Oswald

← Previous revision		Revision as of 17:06, 2 October 2020
Line 24:		Line 24:
	\| last2 = Ishai \| first2 = Yuval		\| last2 = Ishai \| first2 = Yuval
	\| editor1-last = Nguyen \| editor1-first = Phong Q.		\| editor1-last = Nguyen \| editor1-first = Phong Q.
	\| editor2-last = Oswald \| editor2-first = Elisabeth		\| editor2-last = Oswald \| editor2-first = Elisabeth \|editor2-link = Elisabeth Oswald
	\| contribution = Distributed point functions and their applications		\| contribution = Distributed point functions and their applications
	\| doi = 10.1007/978-3-642-55220-5_35		\| doi = 10.1007/978-3-642-55220-5_35

AnomieBOT: Dating maintenance tags: {{Citation needed}}

2019-03-14T17:08:09Z

Dating maintenance tags: {{Citation needed}}

← Previous revision		Revision as of 17:08, 14 March 2019
Line 14:		Line 14:
	where <math>\oplus</math> denotes the [[bitwise operation\|bitwise exclusive or]] of the two function values. However, given only one of these two keys, the values of <math>f</math> for that key should be indistinguishable from random.		where <math>\oplus</math> denotes the [[bitwise operation\|bitwise exclusive or]] of the two function values. However, given only one of these two keys, the values of <math>f</math> for that key should be indistinguishable from random.

	It is known {{Citation needed}} how to construct an efficient distributed point function from another cryptographic primitive, a [[one-way function]].		It is known {{Citation needed\|date=March 2019}} how to construct an efficient distributed point function from another cryptographic primitive, a [[one-way function]].

	In the other direction, if a distributed point function is known, then it is possible to perform [[private information retrieval]].		In the other direction, if a distributed point function is known, then it is possible to perform [[private information retrieval]].

192.114.91.232 at 15:07, 14 March 2019

2019-03-14T15:07:39Z

← Previous revision		Revision as of 15:07, 14 March 2019
Line 14:		Line 14:
	where <math>\oplus</math> denotes the [[bitwise operation\|bitwise exclusive or]] of the two function values. However, given only one of these two keys, the values of <math>f</math> for that key should be indistinguishable from random.		where <math>\oplus</math> denotes the [[bitwise operation\|bitwise exclusive or]] of the two function values. However, given only one of these two keys, the values of <math>f</math> for that key should be indistinguishable from random.

	It is known how to construct an efficient distributed point function from another cryptographic primitive, a [[one-way function]].		It is known {{Citation needed}} how to construct an efficient distributed point function from another cryptographic primitive, a [[one-way function]].

	In the other direction, if a distributed point function is known, then it is possible to perform [[private information retrieval]].		In the other direction, if a distributed point function is known, then it is possible to perform [[private information retrieval]].

Josve05a: /* top */cleanup, added orphan tag using AWB

2018-06-12T00:43:52Z

top: cleanup, added orphan tag using AWB

← Previous revision		Revision as of 00:43, 12 June 2018
Line 1:		Line 1:
			{{Orphan\|date=June 2018}}

	In [[cryptography]], a '''distributed point function''' is a [[cryptographic primitive]] that allows two distributed processes to share a piece of information, and compute functions of their shared information, without revealing the information itself to either process. It is a form of [[secret sharing]].		In [[cryptography]], a '''distributed point function''' is a [[cryptographic primitive]] that allows two distributed processes to share a piece of information, and compute functions of their shared information, without revealing the information itself to either process. It is a form of [[secret sharing]].

David Eppstein: Category:Cryptographic primitives (thanks for the reminder)

2017-10-29T07:40:42Z

Category:Cryptographic primitives (thanks for the reminder)

← Previous revision		Revision as of 07:40, 29 October 2017
Line 33:		Line 33:
	\| year = 2014}}		\| year = 2014}}

			[[Category:Cryptographic primitives]]
	{{uncategorised\|date=October 2017}}

BiggySmoov: Added tags to the page using Page Curation (uncategorised)

2017-10-29T07:12:44Z

Added tags to the page using Page Curation (uncategorised)

← Previous revision		Revision as of 07:12, 29 October 2017
Line 32:		Line 32:
	\| volume = 8441		\| volume = 8441
	\| year = 2014}}		\| year = 2014}}

			{{uncategorised\|date=October 2017}}