Entry Brandt:2008:EUP from tissec.bib
Last update: Sun Oct 15 02:58:48 MDT 2017
Top |
Symbols |
Numbers |
Math |
A |
B |
C |
D |
E |
F |
G |
H |
I |
J |
K |
L |
M |
N |
O |
P |
Q |
R |
S |
T |
U |
V |
W |
X |
Y |
Z
BibTeX entry
@Article{Brandt:2008:EUP,
author = "Felix Brandt and Tuomas Sandholm",
title = "On the Existence of Unconditionally Privacy-Preserving
Auction Protocols",
journal = j-TISSEC,
volume = "11",
number = "2",
pages = "6:1--6:??",
month = mar,
year = "2008",
CODEN = "ATISBQ",
DOI = "https://doi.org/10.1145/1330332.1330338",
ISSN = "1094-9224 (print), 1557-7406 (electronic)",
ISSN-L = "1094-9224",
bibdate = "Thu Jun 12 17:52:41 MDT 2008",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/tissec.bib",
abstract = "We investigate whether it is possible to preserve
privacy in sealed-bid auctions to a maximal extent. In
particular, this paper focuses on
{$<$}it{$>$}unconditional full privacy{$<$}/it{$>$}, i.
e. , privacy that relies neither on trusted third
parties (like auctioneers), nor on computational
intractability assumptions (like the hardness of
factoring). These constraints imply a scenario in which
bidders exchange messages according to some predefined
protocol in order to jointly determine the auction
outcome without revealing any additional information.
It turns out that the first-price sealed-bid auction
can be emulated by an unconditionally fully private
protocol. However, the protocol's round complexity is
exponential in the bid size, and there is no more
efficient protocol. On the other hand, we prove the
impossibility of privately emulating the second-price
sealed-bid auction for more than two bidders. This
impossibility holds even when relaxing various privacy
constraints such as allowing the revelation of all but
one losing bid (while maintaining anonymity) or
allowing the revelation of the second highest bidder's
identity.",
acknowledgement = ack-nhfb,
articleno = "6",
fjournal = "ACM Transactions on Information and System Security",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J789",
keywords = "auctions; multiparty computation",
}
Related entries
- $>$,
11(2)1,
11(2)2
- $<$,
11(2)1,
11(2)2
- /it,
11(2)1,
11(2)2
- according,
13(3)28,
14(1)10
- additional,
2(1)3,
9(2)181,
10(4)4,
11(2)3,
12(3)18,
13(4)33,
15(2)6,
17(1)1
- all,
1(1)93,
2(2)159,
2(3)332,
2(4)416,
10(1)4,
10(2)5,
10(4)2,
10(4)4,
11(2)1,
11(2)3,
11(2)4,
11(2)5,
11(3)13,
11(4)18,
11(4)20,
11(4)22,
12(2)10,
12(3)18,
13(1)10,
13(3)25,
13(3)28,
13(4)38,
13(4)41,
14(1)6,
14(1)14,
14(3)27,
15(1)4,
15(2)9,
15(3)14,
15(4)16,
15(4)17,
16(1)4,
17(1)2,
17(3)9,
17(3)11,
18(1)2,
18(2)5
- allowing,
11(3)16,
12(3)17,
15(2)6
- anonymity,
1(1)66,
2(3)230,
2(4)354,
2(4)390,
11(2)3,
12(3)15,
13(2)13,
13(4)29,
13(4)39,
13(4)41,
14(1)4,
14(4)29,
15(1)5,
15(3)11,
15(3)12,
15(3)14,
17(1)4
- any,
1(1)66,
1(1)93,
2(4)390,
9(4)461,
10(3)10,
10(3)12,
10(4)1,
10(4)4,
11(2)4,
11(3)13,
11(3)16,
11(4)20,
12(1)3,
12(1)5,
12(1)6,
12(2)8,
12(2)9,
12(2)10,
12(3)14,
12(3)18,
12(3)19,
12(4)20,
13(1)10,
13(3)28,
13(4)33,
13(4)39,
14(1)6,
14(1)8,
14(1)9,
14(4)32,
15(1)2,
15(2)9,
15(2)10,
15(4)17,
16(2)6,
16(2)7,
16(3)12,
16(4)13,
16(4)15,
17(2)8,
17(3)9,
17(3)11,
18(1)1
- assumption,
2(3)230,
2(3)332,
3(3)161,
9(2)181,
11(2)3,
11(4)20,
12(1)1,
12(1)3,
12(2)9,
12(4)21,
13(4)38,
15(1)4,
15(3)12,
16(1)4,
16(2)5,
16(4)13,
18(3)10
- complexity,
2(1)65,
9(4)391,
9(4)421,
10(2)5,
10(4)5,
12(3)16,
12(3)18,
12(4)20,
13(4)36,
13(4)40,
14(1)3,
14(1)14,
15(4)16,
16(1)3,
16(1)4,
16(3)10,
17(4)16,
18(2)6,
18(3)10,
18(4)13
- computation,
1(1)26,
2(3)332,
9(4)461,
12(1)6,
13(3)22,
13(4)29,
14(1)5,
14(4)29,
14(4)31,
15(1)2,
15(2)9,
16(3)11,
17(3)11
- computational,
10(2)5,
12(1)3,
12(4)21,
13(3)28,
13(4)40,
15(1)3,
15(2)9,
16(3)12,
16(4)17,
17(3)10,
17(3)12,
17(4)15,
18(2)7,
18(4)12
- constraint,
2(1)65,
3(4)207,
6(4)501,
7(3)392,
9(2)162,
10(1)2,
10(2)5,
10(2)7,
10(4)2,
11(1)3,
11(3)14,
11(4)20,
12(2)8,
12(2)10,
12(3)19,
13(1)5,
13(3)22,
13(3)25,
13(4)40,
14(4)32,
15(2)10,
15(3)13,
15(4)15,
16(1)3,
16(1)4,
16(4)17,
17(1)3,
17(2)8,
18(2)6
- determine,
1(1)3,
11(2)3,
11(3)16,
12(4)20,
13(3)26,
13(4)38,
13(4)40,
14(1)2,
14(4)32,
16(2)5,
17(1)1,
17(2)8
- e.,
10(3)11,
10(4)4,
10(4)5,
11(2)4,
11(2)5
- efficient,
1(1)26,
3(2)63,
6(2)258,
6(3)365,
7(1)21,
9(4)391,
9(4)461,
10(1)3,
10(2)5,
10(2)6,
10(4)2,
11(1)3,
11(2)4,
11(3)15,
11(4)19,
12(1)1,
12(3)15,
12(3)18,
12(4)21,
13(1)9,
13(1)10,
13(3)24,
13(3)27,
13(4)31,
13(4)32,
13(4)34,
13(4)38,
14(1)5,
14(1)14,
15(1)4,
15(2)6,
15(2)9,
15(4)16,
16(1)2,
16(1)4,
17(3)10,
17(4)15,
18(3)11
- even,
1(1)66,
2(3)332,
2(4)416,
10(1)2,
11(1)4,
11(4)22,
12(2)11,
12(4)20,
13(1)10,
13(4)30,
13(4)35,
13(4)41,
14(3)25,
14(3)27,
15(1)5,
16(3)12,
17(3)11,
17(3)12,
18(1)1
- exchange,
2(3)230,
9(2)181,
10(3)9,
10(3)10,
14(4)28,
16(4)15,
17(2)7,
18(1)2
- existence,
11(2)4,
13(3)25,
17(1)1
- exponential,
10(4)1
- extent,
11(2)3,
18(2)7
- factoring,
13(3)20
- focus,
10(4)2,
11(3)12,
11(4)19,
12(1)3,
12(2)12,
14(3)23,
15(4)16,
16(3)10,
18(4)13
- full,
10(4)5,
13(3)24,
13(3)25,
13(4)37,
15(2)8,
16(3)12,
17(2)6
- fully,
9(4)421,
10(3)12,
13(4)35,
16(3)11
- hand,
16(4)15,
18(1)1
- hold,
10(4)1,
15(1)5,
16(1)4,
17(1)2
- however,
2(3)269,
10(2)5,
10(2)8,
11(3)15,
11(4)18,
11(4)20,
11(4)22,
13(3)20,
13(3)22,
13(4)35,
13(4)38,
13(4)39,
14(1)14,
14(3)24,
14(4)28,
14(4)29,
15(2)10,
16(2)7,
16(3)11,
17(1)2,
17(1)4,
17(3)12,
17(4)15,
18(1)1,
18(2)7,
18(4)13
- i.,
10(4)4,
11(2)4,
11(2)5
- identity,
2(2)177,
2(4)390,
10(3)9,
12(3)15,
13(4)36,
13(4)41,
14(1)10,
14(3)25,
14(4)29,
15(1)4,
15(3)12,
17(1)4
- imply,
11(3)13
- investigate,
10(3)12,
12(1)2,
15(2)7,
15(4)15,
16(1)3,
16(2)8,
18(1)2
- like,
2(2)159,
10(4)3,
12(2)8,
12(2)11,
13(3)24,
17(3)11
- maintaining,
2(4)390,
13(1)5,
13(3)20,
16(3)12,
17(4)15
- message,
2(2)177,
2(3)332,
9(4)461,
10(2)8,
11(2)4,
11(3)15,
11(4)23,
12(1)3,
13(4)31,
13(4)37,
14(4)32,
17(3)9,
17(4)13
- more,
2(1)3,
2(1)65,
2(3)332,
9(2)181,
9(4)391,
9(4)421,
9(4)461,
10(1)4,
10(3)9,
10(4)1,
10(4)4,
10(4)6,
11(2)3,
11(2)4,
11(3)14,
11(4)21,
12(1)1,
12(2)8,
12(2)10,
12(2)12,
12(2)13,
12(3)18,
13(1)10,
13(3)20,
13(3)21,
13(3)22,
13(3)28,
13(4)32,
13(4)34,
13(4)39,
14(3)27,
14(4)31,
15(1)2,
15(1)5,
15(2)8,
15(2)9,
15(3)11,
15(3)12,
15(4)16,
16(1)2,
16(2)8,
16(3)10,
16(3)11,
16(4)17,
17(1)2,
17(1)3,
17(3)9,
17(4)14,
17(4)16,
18(1)1,
18(3)11,
18(4)13
- multiparty,
10(3)10,
12(1)3,
14(4)31
- neither,
2(4)390,
13(3)21,
14(1)5
- nor,
2(4)390,
13(3)21,
14(1)5
- one,
1(1)26,
1(1)93,
2(1)3,
2(1)65,
2(3)295,
9(4)461,
10(1)2,
10(2)5,
10(2)8,
10(3)12,
10(4)3,
11(3)14,
12(1)1,
12(1)5,
12(2)13,
12(3)14,
13(3)21,
13(3)25,
13(3)26,
13(3)27,
13(4)41,
14(1)3,
14(1)5,
14(4)30,
14(4)32,
15(2)10,
15(3)11,
15(4)16,
15(4)18,
16(1)3,
16(1)4,
16(3)9,
16(4)14,
17(2)8,
17(4)13,
18(1)1,
18(3)11,
18(4)13
- order,
1(1)3,
9(2)181,
9(4)391,
9(4)461,
10(1)4,
10(2)5,
10(3)12,
12(1)1,
12(1)3,
12(3)18,
13(3)24,
15(4)17,
16(1)4,
17(2)6,
17(3)11,
18(1)2
- other,
1(1)93,
2(4)354,
9(4)461,
10(3)9,
10(3)10,
10(3)11,
10(3)12,
10(4)1,
10(4)5,
11(2)2,
11(3)15,
11(4)18,
11(4)23,
12(1)3,
12(2)8,
12(2)10,
12(3)14,
12(3)17,
12(4)22,
13(3)24,
13(3)25,
13(4)40,
14(3)23,
14(3)27,
14(4)30,
15(1)5,
15(2)6,
15(3)11,
15(3)14,
15(4)15,
16(4)15,
17(2)8,
17(3)9,
18(1)1,
18(1)3,
18(2)6,
18(4)12
- outcome,
14(1)8,
18(1)1
- paper,
1(1)66,
1(1)93,
2(1)34,
2(1)105,
2(2)138,
2(2)177,
2(3)269,
2(4)390,
7(2)319,
9(2)162,
9(2)181,
9(4)421,
10(1)2,
10(1)4,
10(2)5,
10(2)7,
10(3)9,
10(3)10,
10(3)11,
10(3)12,
10(4)2,
10(4)4,
11(1)2,
11(2)1,
12(2)12,
14(4)28,
14(4)32
- particular,
2(2)177,
2(4)390,
10(4)1,
10(4)2,
10(4)3,
12(4)21,
13(4)40,
14(1)2,
15(3)14,
16(2)5,
17(3)9,
17(4)14
- party,
9(4)421,
10(2)8,
10(4)3,
11(2)4,
12(1)6,
12(2)12,
13(3)22,
13(4)39,
14(4)29,
15(2)9,
17(3)9
- possible,
2(1)105,
10(2)5,
10(4)2,
10(4)4,
11(3)16,
11(4)22,
12(1)6,
12(2)10,
13(3)28,
13(4)33,
13(4)35,
13(4)39,
14(1)3,
14(1)14,
14(3)25,
14(4)32,
15(2)10,
17(1)2,
17(3)9,
18(1)4,
18(3)9
- predefined,
17(1)2
- preserve,
2(4)390,
14(3)26,
15(2)7,
15(3)12
- Preserving, Privacy-,
17(3)10,
18(3)10
- privacy,
1(1)66,
2(4)390,
7(2)319,
10(3)12,
11(2)3,
11(3)16,
12(1)6,
12(2)8,
12(2)9,
12(3)16,
12(4)21,
13(1)7,
13(2)16,
13(3)22,
13(3)24,
13(4)39,
14(1)4,
14(3)26,
14(4)29,
14(4)30,
14(4)31,
15(2)7,
15(3)12,
16(3)11,
16(3)12,
17(1)3,
17(3)10,
18(1)2,
18(4)12
- Privacy-Preserving,
17(3)10,
18(3)10
- private,
2(2)177,
2(3)230,
2(4)416,
6(4)472,
12(1)6,
12(2)9,
12(3)16,
12(3)17,
12(3)18,
13(4)37,
14(3)26
- prove,
10(2)8,
10(4)1,
11(3)16,
11(4)18,
12(2)8,
12(3)16,
12(3)19,
13(3)28,
15(2)9,
16(1)4,
16(2)5,
16(4)17,
17(2)5,
17(4)15,
18(2)8
- rely,
10(4)3,
10(4)6,
12(1)3,
13(4)38,
14(1)9,
15(1)3,
16(1)1,
16(4)13,
16(4)14,
18(1)2
- revealing,
2(4)390,
12(1)6,
12(3)15,
16(3)12,
17(1)4
- round,
9(4)461
- scenario,
2(3)230,
11(4)19,
12(1)2,
12(1)4,
12(3)16,
13(3)22,
14(3)25,
15(1)4,
17(3)9,
17(4)16
- second,
9(2)181,
9(4)461,
11(2)3,
11(4)22,
12(1)3,
12(1)5,
12(2)11,
13(4)31,
13(4)37,
16(3)9,
16(3)10,
16(3)12,
17(3)10,
18(3)9
- size,
2(3)295,
10(3)11,
10(4)5,
11(3)13,
11(4)18,
12(3)16,
12(4)20,
14(1)3,
14(4)29,
17(4)15,
18(1)4,
18(4)12
- than,
2(1)3,
2(1)65,
2(3)332,
9(4)391,
9(4)461,
10(1)4,
11(2)3,
11(3)14,
12(1)1,
12(2)10,
12(3)16,
12(4)22,
13(1)10,
13(3)21,
13(4)29,
13(4)31,
13(4)35,
14(3)27,
14(4)31,
15(1)5,
15(2)9,
15(2)10,
15(4)15,
15(4)16,
16(2)8,
16(4)17,
17(1)2,
17(3)9,
17(3)10,
17(3)12,
17(4)14,
17(4)16,
18(4)13
- there,
12(1)2,
12(2)8,
12(4)20,
13(3)21,
13(4)34,
14(1)9,
14(4)30,
14(4)31,
15(4)18,
16(1)4,
17(1)2
- third,
9(2)181,
11(2)3,
11(2)4,
12(2)12,
13(4)31,
13(4)39,
14(4)29,
15(2)9
- trusted,
2(2)138,
2(3)269,
8(2)153,
10(4)3,
11(3)14,
12(1)3,
13(4)39,
14(1)8,
14(3)27,
14(4)29,
15(2)9,
16(2)5,
16(2)7,
16(4)15,
17(2)6,
18(2)8
- turn,
11(2)1,
12(1)6,
15(4)17,
18(2)7
- two,
1(1)26,
2(4)416,
9(4)391,
10(1)4,
10(2)6,
10(2)8,
10(3)10,
10(4)4,
11(2)1,
11(2)4,
11(3)13,
11(4)22,
12(1)2,
12(1)3,
12(1)4,
12(1)6,
12(3)14,
12(4)20,
13(3)22,
13(3)27,
13(4)40,
14(1)4,
14(1)5,
14(4)30,
15(1)2,
15(1)5,
15(2)6,
15(3)11,
15(3)12,
16(1)1,
16(1)2,
16(1)4,
16(3)9,
16(3)10,
16(4)15,
17(4)13,
18(2)5,
18(4)12,
18(4)13,
18(4)14
- various,
10(1)3,
10(3)11,
10(4)2,
11(1)3,
11(2)3,
11(3)14,
11(3)15,
12(1)4,
13(4)35,
14(1)13,
14(4)28,
18(1)1,
18(2)5
- when,
2(3)295,
10(2)7,
10(3)12,
10(4)4,
10(4)6,
11(2)3,
11(3)15,
11(3)16,
11(4)17,
11(4)18,
12(2)10,
12(2)11,
12(4)20,
12(4)22,
13(1)10,
13(3)27,
13(4)32,
13(4)34,
13(4)35,
13(4)37,
15(2)6,
15(2)9,
15(2)10,
15(3)14,
16(1)3,
16(2)8,
17(3)9,
17(4)13,
18(3)9,
18(4)12
- whether,
1(1)3,
1(1)26,
10(2)5,
10(4)2,
10(4)5,
11(2)3,
11(3)16,
12(1)1,
12(4)20,
13(3)26,
13(4)40,
14(3)25,
14(4)32,
16(1)3,
16(1)4,
17(1)1,
17(1)2
- while,
2(3)230,
2(4)354,
9(4)391,
9(4)421,
9(4)461,
10(2)5,
10(4)2,
11(1)4,
11(2)2,
11(4)18,
11(4)19,
11(4)22,
12(2)9,
12(3)16,
13(1)5,
13(3)22,
13(3)25,
13(4)39,
13(4)41,
14(3)25,
14(3)26,
14(4)31,
15(3)12,
15(4)15,
15(4)17,
16(3)9,
16(3)12,
16(4)16,
17(1)4,
17(3)9,
17(4)15,
18(1)1,
18(2)7