Fdtxjr

Should I join office cleaning event for free?

Can I make popcorn with any corn?

Circuitry of TV splitters

Why is the design of haulage companies so “special”?

Why was the small council so happy for Tyrion to become the Master of Coin?

What makes Graph invariants so useful/important?

Can Medicine checks be used, with decent rolls, to completely mitigate the risk of death from ongoing damage?

Motorized valve interfering with button?

Chess with symmetric move-square

What typically incentivizes a professor to change jobs to a lower ranking university?

How can bays and straits be determined in a procedurally generated map?

Infinite past with a beginning?

Why are 150k or 200k jobs considered good when there are 300k+ births a month?

What Brexit solution does the DUP want?

What defenses are there against being summoned by the Gate spell?

Patience, young "Padovan"

How can I fix this gap between bookcases I made?

Validation accuracy vs Testing accuracy

Why has Russell's definition of numbers using equivalence classes been finally abandoned? ( If it has actually been abandoned).

Schwarzchild Radius of the Universe

Email Account under attack (really) - anything I can do?

If Manufacturer spice model and Datasheet give different values which should I use?

Why Is Death Allowed In the Matrix?

When blogging recipes, how can I support both readers who want the narrative/journey and ones who want the printer-friendly recipe?

What does this paraphrase of the birthday problem mean?

What are the differences between collision attack and birthday attack?k(k-1)/2: Combinations and the Birthday boundIs there any function that does not suffers birthday problem?Why k-lists generalized birthday problem when $k=2$ is classical birthday problem?Time complexity of birthday attack type problemHow does hashing twice protect against birthday attacks?What is a wide block cipher and why does it avoid birthday bound problems?Can the birthday attack be extended in this case?On a lower bound for the birthday problemWhat is the error in this collision probability approximation?

6

2

$begingroup$

The following is an excerpt from A Generalized Birthday Problem - David Wagner:

One of the best-known combinatorial tools in cryptology is the birthday problem:

Problem 1. Given two lists $L_1, space L_2$ of elements drawn uniformly and independently at random from $0, 1^n$, find $x_1 in L_1$ and $x_2 in L_2$ such that $x_1 oplus x_2 = 0$.

It's not so intuitive for me to understand. In my understanding, the birthday problem is about the probability that at least 2 people in a room have the same birthday. How does the birthday problem transfers to this? Please give me some hints.

birthday-attack

share|improve this question

edited Mar 22 at 13:51

Squeamish Ossifrage

22.2k132100

asked Mar 22 at 3:20

Cedric SunCedric Sun

314

$endgroup$

add a comment | 

6

2

$begingroup$

The following is an excerpt from A Generalized Birthday Problem - David Wagner:

One of the best-known combinatorial tools in cryptology is the birthday problem:

Problem 1. Given two lists $L_1, space L_2$ of elements drawn uniformly and independently at random from $0, 1^n$, find $x_1 in L_1$ and $x_2 in L_2$ such that $x_1 oplus x_2 = 0$.

It's not so intuitive for me to understand. In my understanding, the birthday problem is about the probability that at least 2 people in a room have the same birthday. How does the birthday problem transfers to this? Please give me some hints.

birthday-attack

share|improve this question

edited Mar 22 at 13:51

Squeamish Ossifrage

22.2k132100

asked Mar 22 at 3:20

Cedric SunCedric Sun

314

$endgroup$

add a comment | 

$begingroup$

The following is an excerpt from A Generalized Birthday Problem - David Wagner:

One of the best-known combinatorial tools in cryptology is the birthday problem:

Problem 1. Given two lists $L_1, space L_2$ of elements drawn uniformly and independently at random from $0, 1^n$, find $x_1 in L_1$ and $x_2 in L_2$ such that $x_1 oplus x_2 = 0$.

It's not so intuitive for me to understand. In my understanding, the birthday problem is about the probability that at least 2 people in a room have the same birthday. How does the birthday problem transfers to this? Please give me some hints.

birthday-attack

share|improve this question

edited Mar 22 at 13:51

Squeamish Ossifrage

22.2k132100

asked Mar 22 at 3:20

Cedric SunCedric Sun

314

$endgroup$

share|improve this question

edited Mar 22 at 13:51

Squeamish Ossifrage

22.2k132100

asked Mar 22 at 3:20

Cedric SunCedric Sun

314

share|improve this question

edited Mar 22 at 13:51

Squeamish Ossifrage

22.2k132100

asked Mar 22 at 3:20

Cedric SunCedric Sun

314

edited Mar 22 at 13:51

Squeamish Ossifrage

22.2k132100

edited Mar 22 at 13:51

Squeamish Ossifrage

22.2k132100

asked Mar 22 at 3:20

Cedric SunCedric Sun

314

asked Mar 22 at 3:20

Cedric SunCedric Sun

314

2 Answers
2

active

oldest

votes

5

$begingroup$

$x_1 oplus x_2 = 0$ is equivalent to $x_1=x_2$ (because $oplus$ is bitwise XOR, and that equivalence stands for bits, and multibit quantities being equal in all their respective bits is equivalent to these quantities being equal).

Now assume that $x_i$ is the birthday of person $i$ in the room, expressed as days since the first day of the year, in binary, with a year of $2^n$ days, and what's meant should be clear.

Notice that the problem studied in the quote is about two lists/rooms, rather than one in the standard birthday problem.

share|improve this answer

edited Mar 23 at 11:31

answered Mar 22 at 7:22

fgrieufgrieu

82k7178350

$endgroup$

add a comment | 

3

$begingroup$

Note that $x_1=x_2$, i.e., there is a birthday collision in $0,1^n$ if and only if $x_1oplus x_2=0.$
In a general additive group $G$, $x_1=x_2$, i.e., there is a birthday collision in $G$ if and only if $x_1-x_2=0.$

If you have two lists $L_1,L_2,$ then with probability roughly
$$expleft-frac2^n+1right$$
there will be no collisions.

In the birthday paradox, for $N=2^n$ bins, the probability of no collisions after $m$ balls is roughly
$$expleft-fracm^22Nright$$
while here we have $|L_1||L_2|$ pairs to consider so $m=|L_1||L_2|.$

Wagner's paper is about finding efficient algorithms for vectors adding to zero for higher numbers (e.g., 4) of lists.

share|improve this answer

edited Mar 22 at 6:19

answered Mar 22 at 4:14

kodlukodlu

9,30811331

$endgroup$

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "281"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f68206%2fwhat-does-this-paraphrase-of-the-birthday-problem-mean%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

5

$begingroup$

$x_1 oplus x_2 = 0$ is equivalent to $x_1=x_2$ (because $oplus$ is bitwise XOR, and that equivalence stands for bits, and multibit quantities being equal in all their respective bits is equivalent to these quantities being equal).

Now assume that $x_i$ is the birthday of person $i$ in the room, expressed as days since the first day of the year, in binary, with a year of $2^n$ days, and what's meant should be clear.

Notice that the problem studied in the quote is about two lists/rooms, rather than one in the standard birthday problem.

share|improve this answer

edited Mar 23 at 11:31

answered Mar 22 at 7:22

fgrieufgrieu

82k7178350

$endgroup$

add a comment | 

5

$begingroup$

$x_1 oplus x_2 = 0$ is equivalent to $x_1=x_2$ (because $oplus$ is bitwise XOR, and that equivalence stands for bits, and multibit quantities being equal in all their respective bits is equivalent to these quantities being equal).

Now assume that $x_i$ is the birthday of person $i$ in the room, expressed as days since the first day of the year, in binary, with a year of $2^n$ days, and what's meant should be clear.

Notice that the problem studied in the quote is about two lists/rooms, rather than one in the standard birthday problem.

share|improve this answer

edited Mar 23 at 11:31

answered Mar 22 at 7:22

fgrieufgrieu

82k7178350

$endgroup$

add a comment | 

$begingroup$

$x_1 oplus x_2 = 0$ is equivalent to $x_1=x_2$ (because $oplus$ is bitwise XOR, and that equivalence stands for bits, and multibit quantities being equal in all their respective bits is equivalent to these quantities being equal).

Now assume that $x_i$ is the birthday of person $i$ in the room, expressed as days since the first day of the year, in binary, with a year of $2^n$ days, and what's meant should be clear.

Notice that the problem studied in the quote is about two lists/rooms, rather than one in the standard birthday problem.

share|improve this answer

edited Mar 23 at 11:31

answered Mar 22 at 7:22

fgrieufgrieu

82k7178350

$endgroup$

share|improve this answer

edited Mar 23 at 11:31

answered Mar 22 at 7:22

fgrieufgrieu

82k7178350

answered Mar 22 at 7:22

fgrieufgrieu

82k7178350

answered Mar 22 at 7:22

fgrieufgrieu

82k7178350

3

$begingroup$

Note that $x_1=x_2$, i.e., there is a birthday collision in $0,1^n$ if and only if $x_1oplus x_2=0.$
In a general additive group $G$, $x_1=x_2$, i.e., there is a birthday collision in $G$ if and only if $x_1-x_2=0.$

If you have two lists $L_1,L_2,$ then with probability roughly
$$expleft-frac2^n+1right$$
there will be no collisions.

In the birthday paradox, for $N=2^n$ bins, the probability of no collisions after $m$ balls is roughly
$$expleft-fracm^22Nright$$
while here we have $|L_1||L_2|$ pairs to consider so $m=|L_1||L_2|.$

Wagner's paper is about finding efficient algorithms for vectors adding to zero for higher numbers (e.g., 4) of lists.

share|improve this answer

edited Mar 22 at 6:19

answered Mar 22 at 4:14

kodlukodlu

9,30811331

$endgroup$

add a comment | 

3

$begingroup$

Note that $x_1=x_2$, i.e., there is a birthday collision in $0,1^n$ if and only if $x_1oplus x_2=0.$
In a general additive group $G$, $x_1=x_2$, i.e., there is a birthday collision in $G$ if and only if $x_1-x_2=0.$

If you have two lists $L_1,L_2,$ then with probability roughly
$$expleft-frac2^n+1right$$
there will be no collisions.

In the birthday paradox, for $N=2^n$ bins, the probability of no collisions after $m$ balls is roughly
$$expleft-fracm^22Nright$$
while here we have $|L_1||L_2|$ pairs to consider so $m=|L_1||L_2|.$

Wagner's paper is about finding efficient algorithms for vectors adding to zero for higher numbers (e.g., 4) of lists.

share|improve this answer

edited Mar 22 at 6:19

answered Mar 22 at 4:14

kodlukodlu

9,30811331

$endgroup$

add a comment | 

$begingroup$

Note that $x_1=x_2$, i.e., there is a birthday collision in $0,1^n$ if and only if $x_1oplus x_2=0.$
In a general additive group $G$, $x_1=x_2$, i.e., there is a birthday collision in $G$ if and only if $x_1-x_2=0.$

If you have two lists $L_1,L_2,$ then with probability roughly
$$expleft-frac2^n+1right$$
there will be no collisions.

In the birthday paradox, for $N=2^n$ bins, the probability of no collisions after $m$ balls is roughly
$$expleft-fracm^22Nright$$
while here we have $|L_1||L_2|$ pairs to consider so $m=|L_1||L_2|.$

Wagner's paper is about finding efficient algorithms for vectors adding to zero for higher numbers (e.g., 4) of lists.

share|improve this answer

edited Mar 22 at 6:19

answered Mar 22 at 4:14

kodlukodlu

9,30811331

$endgroup$

share|improve this answer

edited Mar 22 at 6:19

answered Mar 22 at 4:14

kodlukodlu

9,30811331

answered Mar 22 at 4:14

kodlukodlu

9,30811331

answered Mar 22 at 4:14

kodlukodlu

9,30811331