Transcript asiacrypt2005

Spreading Alerts Quietly
and the Subgroup Escape
Problem
Aleksandr Yampolskiy (Yale)
Joint work with James Aspnes,
Zoë Diamadi, Kristian Gjøsteen,
and René Peralta
Outline
Motivation
 Blind coupon mechanism
 Abstract group structure
 Instantiating the abstract group structure
 How to spread alerts
 Conclusions and open problems

Our model
Message-passing network of n nodes.
 Two types of nodes: regular or sentinel.
 Sentinel nodes run Intrusion Detection
Software which looks for attacker’s presence.

The attacker…
Observes all network traffic.
 Controls the timing and content of
delivered messages.

Our goal


Can sentinel nodes quickly alert all network
nodes to attacker’s presence?
We want to prevent the attacker from
- fabricating false alerts
- identifying the presence or source of alert
We are
attacked!
We are
attacked!
We are
attacked!
We are
attacked!
Blind coupon mechanism
A blind coupon mechanism (BCM) is a
PPT tuple (G, V, C, D):
 Key generation G(1k):


Outputs public and secret keys (PK, SK)
and two strings (d, s).
 Secret key defines the sets of dummy
coupons DSK and signal coupons SSK. We
call (DSK  SSK) valid coupons. Also,
d2 DSK, s2 SSK.
Blind coupon mechanism (cont.)
Verification algorithm VPK(y) returns 1 if y
is valid, 0 otherwise.
 Decoding algorithm DSK(y) outputs 0 if y is
a dummy coupon; 1 if it is a signal coupon.
 Combining algorithm z à CPK(x, y) outputs
a signal coupon iff one of the inputs is a
signal coupon.

Blind coupon mechanism (cont.)
Def: A BCM (G, V, C, D) is secure if

signal and dummy coupons look similar
¼
0

cannot generate a signal coupon from
scratch
Pr[

1
]=
1
combining algorithm is blinding
C(
0
,
0
)¼
0
c C(
0
1
1
,
,
,
1
0
1
)¼
1
c
Abstract group structure (U, G, D)



Special group structure yields an efficient BCM.
A finite set U, a cyclic group GµU, generated
by s, and its subgroup D·G, generated by d.
|G|/|D| is prime. Also, |G|/|U| and |D|/|G| are
small.
signal
dummy
D
G
invalid
U
Hardness assumptions

Subgroup Membership Problem: given a
tuple (U, G, D, d, s) and y2 G, it is hard to
decide whether y2 D or y2 GnD.

Many examples: DDH, QRA, Paillier, etc.
D
G
¼
???
G
Hardness assumptions (cont.)

Subgroup Escape Problem: given a tuple
(U, G, D, d), it is hard to find an element
y2 GnD

Has not appeared in the literature before.
???
G
¼
D
G
The BCM construction on (U, G, D)

The BCM (G, C, V, D) is as follows:

Key generation: Let PK=(U, G, d) and SK=|D|.
Combining algorithm: CPK(x, y) outputs
dr0◦xr1◦yr2, where r0,r1,r22r {0,…, 22k-1}
Verification algorithm: VPK(y) checks that y2G.
Decoding algorithm: DSK(y) outputs 0 (dummy) if
ySK=1 and outputs 1 (signal) otherwise.



Security theorem
Theorem: If the subgroup membership problem and
subgroup escape problems for (U, G, D) are hard,
then our BCM is secure.
Proof idea:
 CPK(x, y)=dr0◦xr1◦yr2 ) it is blinding




x,y2 D ) CPK(x,y) uniform in D
x 2 G\D) xr1D uniform in G\D ) CPK(x, y) uniform in G
subgroup membership hard )
subgroup escape hard )
Pr [
0
1
¼
1
]=
Security theorem (cont.)
Challenge: Find concrete (U, G, D) for
which subgroup membership and
subgroup escape problems are hard.
Answer:
 Elliptic curves over Zn, where n=pq.
 Bilinear groups with specific order.
Elliptic Curves over Zn




Set of (x:y:z) such that y2 z ≡ x3 + axz2 +
bz3 (mod n) where gcd(4a2-27b3,n)=1.
Fact: Points of elliptic curve form an
P
P1 2
additive group E(Zn) for n=pq.
P1 + P2
Key property of E(Zn): hard to find new
group elements except by using group
operation on previously known group
elements.
Previously considered a nuisance [Lenstra
‘87, Demytko ‘98] rather than a useful
cryptographic property [Gjøsteen ’04].
Elliptic Curves over Zn (cont.)
Challenge: Find (x:y:z) such that
y2z ≡ x3 + axz2 + bz3 (mod n).
Answer: It seems hard!
 Choose x and solve for y: compute √mod n.
 Choose y and solve for x: solve cubic equation.
 Find x and y simultaneously: not obvious.
 LLL-based methods don’t seem to pose a
threat.
 Finding rational non-torsion points on curves
over Q seems hard.
Elliptic Curves over Zn (cont.)




Let p,q,l1,l2,l3 be primes.
Using complex multiplication techniques [LayZimmer ‘94], we can find curves Ep/Fp and Eq/Fq
with #Ep(Fp)=l1l2, #Eq(Fq)=l3.
Let n=pq. Then E(Zn) ¼ Ep(Fp)£Eq(Fq) with
#E(Zn)=l1l2l3.
Let U be projective plane, G be E(Zn), and D·G
be its subgroup of order l1l3. Let PK=(G,D,n),
SK=(p,q,l1,l2,l3).
signal
dummy
invalid
D G
U
Elliptic Curves over Zn (cont.)


Verification Algorithm: Given a coupon (x:y:z), it is easy to
check if y2z ≡ x3+axz2+bz3 (mod n).
Subgroup Membership Problem: Hard to distinguish
elements of D (order l1l3) from elements of GnD.




For EP(FP), distinguishing elements of prime order from elements of
composite order is hard unless can factor #EP(FP) [Gjo05].
Computing #E(Zn) is as hard as factoring n [Kunihiro-Koyama ’98].
Thus, #Ep(Fp) is hidden.
Subgroup Escape Problem: Hard as long as adversary
cannot find random group elements in G=E(Zn).
Spreading alerts with the BCM


During initial network setup, the administrator
generates keys for BCM (G, C, V, D).
He gives dummy coupons to all nodes.
Sentinel nodes also receive signal coupons.
0
0
0
1
0
Spreading alerts with the BCM


Nodes continually broadcast coupons to their
neighbors.
- Initially, everyone transmits dummy coupons.
- Sentinel nodes switch to sending signal coupons
upon detecting an attacker.
Attacker may tamper with messages.
0
0
1
$#!@
0
1
1
0
Spreading alerts with the BCM

Upon receiving a coupon, a node verifies that
the coupon is valid.
0
0
1 )=0
V( $#!@
V(
1
V(
1
)=1
0
0
)=1
Spreading alerts with the BCM


Upon receiving a coupon, a node verifies that
the coupon is valid.
If the coupon is valid, the node combines it
with its own coupon. Otherwise, the coupon
is discarded.
0
0
C(
1
C(
1
,
0
)
1
0
,
0
)
Security theorem
Theorem: If the BCM is secure, then so is
the alert propagation mechanism.
Proof idea: Because adversary cannot
distinguish between dummy and signal
coupons, he cannot test their presence or
absence in the network traffic. Same for
coupon forgery.
Efficiency
Synchronous flooding model: All nodes
receive an alert in  steps, where  is the
diameter of the subgraph of non-faulty
nodes.
 Simple epidemic model: Communication
graph is complete. All nodes receive an
alert in O(n log n) steps.

Conclusion





Useful crypto primitive BCM (Æ-homomorphic bit
commitment).
It can be used to construct an undetectable
anonymous private channel.
New crypto tool? Subgroup escape assumption.
Non-interactive proofs of circuit satisfiability of
length linear in the number of Æ gates.
Applications to i-voting [Chaum et al. ’04].
Open problems
Can BCM with constant expansion ratio be
constructed using standard assumptions?
 Can we transmit multiple bits without a linear
blow up in message size?

?