# Presentation: 215454

##     Emmanuel Bresson 
	(ENS, France)

Olivier Chevassut (LBNL, USA)
David Pointcheval (ENS, France)

- 	(ENS, France)
- Olivier Chevassut (LBNL, USA)
- David Pointcheval (ENS, France)

**The Group Diffie-Hellman ****Problems**

- SAC  ’02 -- St-John, Newfoundland, Canada -- August 15-16, 2002

## OUTLINE

- Motivation
- Related Work
- Two-party Diffie-Hellman key exchange
- Group Diffie-Hellman key exchange
- Relation between the group DH problems and the DH problems
- Conclusion

- SAC  ’02 -- St-John, Newfoundland, Canada -- August 15-16, 2002

##  Motivation

- An increasing number of distributed applications need to communicate within groups, e.g.
-  collaboration and videoconferencing tools
-  replicated servers and distributed computations
- An increasing number of applications have security requirements
-  privacy of data
-  protection from hackers, viruses and trojan horses
- A method to establish a group session key is needed

- SAC  ’02 -- St-John, Newfoundland, Canada -- August 15-16, 2002

## Objectives

- Studying algorithmic problems in the discrete logarithm setting
- Diffie-Hellman problems
- Group Diffie-Hellman problems
- Why finding reductions between the group DH and the  two-party DH problems
- To get confindence in the group DH problems
- To correctly chooose security parameters for them
- To securely design group key agreement protocols

- SAC  ’02 -- St-John, Newfoundland, Canada -- August 15-16, 2002

## Related Work 

- Design methodology
- based on complexity theory
- successful at avoiding flaws
- useful to validate cryptographic algorithms
- Prior Results
- « Group DH key exchange under standard assumptions », Eurocrypt ’02
- « Provably authenticated group DH key exchange - dynamic case », Asiacrypt ’01
- « Provably authenticated group DH key exchange », ACM CCS ’01

- SAC  ’02 -- St-John, Newfoundland, Canada -- August 15-16, 2002

## Provable Security Methodology  

- 1. Specification of a model of computation
- 2. Definition of the security goals
- 3. Statement of the intractability assumptions
- computational/decisonal Diffie-Hellman problems (CDH/DDH)
- group computational/decisional DH problems (GCDH/DDH)
- 4. Description of a group DH key exchange scheme
-  and its proof of security
- proof shows by contradiction that the algorithm achieves the security goals under the intractability assumptions

- SAC  ’02 -- St-John, Newfoundland, Canada -- August 15-16, 2002

**Notes:**
The process of proving security of a cryptographic algorithm comes in 4 stages. In the 1st stage, a formal model of computation is defined. One style of model, the one we use through this talk, is the Bellare-Rogaway wherein each player is modeled by an oracle and the adversary ’s capabilities are modeled via queries to these oracles. In this model, the adversary is seen as playing a game against the oracles in order to defeat the security of the protocol. These security goals, formally defined using this model, aims to capture what it means to securely exchanging a shared secret key (this AKE) or even that already agrees shared keys remains secret if the adversary compromise some players’ instances (this FS). The third stage of the process is to identify reasonable intractability assumptions upon which could build a cryptographic algorithm that would exchange a shared key among two principals. The oldest one introduced by DH in 1976 is the computational DH assumption but this has later been refined into the Decisional DH assumption. The last stage of this process is to describe a cryptographic algorithm and to prove that this algorithm securely exchange a session key among the principals. Proving that the algorithm is secure consist of showing by contradiction that the protocol satisfies the security goals under the assumption that the intractability assumptions in effect really holds. 

## The Diffie-Hellman protocol [DH76]

*g**x*1

*sk*=*g**x*1*x*2

*x**1*

*x**2*

- 2-party key exchange protocol

*g**x*2

- Establishing a secure channel between two parties is reduced to the problem of generating a session key sk
- The session key is used to achieve data secrecy and integrity

- SAC  ’02 -- St-John, Newfoundland, Canada -- August 15-16, 2002

## The Diffie-Hellman problems

- Computational problem (CDH)
- Given *g**x*1*, **g**x*2*, *is the ennemy able to compute the shared secret *g**x*1*x*2 ?
- Decisional problem (DDH)
- Given *g**x*1*, **g**x*2*,* is the ennemy able to distinguish the shared secret *g**x*1*x*2 from a given random value *g**r *?

- SAC  ’02 -- St-John, Newfoundland, Canada -- August 15-16, 2002

## Security of the DH protocol

*g**x*1

*x**1*

*x**2*

*g**x*2

- CDH assumption (weaker than DDH)
- If CDH holds, the key H(*g**x*1*x*2) is semantically secure, in the random oracle model
- DDH assumption
- If DDH holds, the key *g**x*1*x*2 is semantically secure

- SAC  ’02 -- St-John, Newfoundland, Canada -- August 15-16, 2002

## Basic reductions to the discrete logarithm problem

- Fix a multiplicative group G, and an element g
- Discrete logarithm problem (DL)
- Given *y*<*g*>, find *x* such that *y*=*g**x*
- One easily gets
- DL => CDH => DDH

- SAC  ’02 -- St-John, Newfoundland, Canada -- August 15-16, 2002

## Group Diffie-Hellman Protocols

- Defined by three algorithms
*SETUP**	**	**(all cases)*
*REMOVE**	**	**(dynamic case)*
*JOIN**	**	**	**(dynamic case)*
- The session key is
*sk*=H(*g**x*1*x*2...*x**n*)

- SAC  ’02 -- St-John, Newfoundland, Canada -- August 15-16, 2002

## The SETUP Algorithm

*g, g**x*1

*g**x*2*,*
*g**x*1*,*
*g**x*1*x*2

*g**x*2*x*3 ,

*sk*=H(*g**x*1*x*2*x**3*)

*x**1*

*x**2*

*x**3*

- Ring-based protocols
- Compute step by step a generalized DH values

*g**x*1*x*3

- SAC  ’02 -- St-John, Newfoundland, Canada -- August 15-16, 2002

## The REMOVE Algorithm

**The *****REMOVE***** Algorithm**

*x**1*

*x**3*

*x’**2*

*g**x’*2*x*3

- SAC  ’02 -- St-John, Newfoundland, Canada -- August 15-16, 2002

## The JOIN Algorithm

*g**x*2*x’*3*x*4  ,*    g**x*1*x’*3*x*4,            *g**x*1*x*2*x*4

*x**2*

*x**1*

*x’**3*

*x**4*

*g**x*2*x’*3*, g**x*1*x’*3*, g**x*1*x*2, *g**x*1*x*2*x’*3

*sk*=H(*g**x*1*x*2*x’*3*x**4*)

- Ugc

- Initiated by player with the highest index in group

- SAC  ’02 -- St-John, Newfoundland, Canada -- August 15-16, 2002

## The Group Computational DH Assumption

- The CDH generalized to the multi-party case
- given *some* subsets of indices in *I=*{1*,...,n*} and all the values *g** ****i****J** x**i** *for  every given subset* J *of *I, **	*
- one has to compute the value *g**x*1*..x**n*
- Example with four parties (*n=4 *and *I=*{1*,2,3,4*})
- given the values
- compute the last value *g**x*1*x*2*x*3*x*4

*	**	**	**	**	**     **, g**x*1* **	**  , g*
*	**	**               **,  g**x*1*x*2 *      , g**x*1*        , g**x*2
*	**	**   **, g**x*1*x*2*x*3*,**	**g**x*1*x*2*      , g**x*1*x*3*     , g**x*2*x*3
*	** *??* **	**   ,g**x*1*x*2*x*3 *,* 	*g**x*1*x*2*x*4 *   , g**x*1*x*3*x*4  *, g**x*2*x*3*x*4

- SAC  ’02 -- St-John, Newfoundland, Canada -- August 15-16, 2002

## The Group Decisional DH Assumption

- The DDH generalized to the multi-party case
- given *some* subsets of indices in *I=*{1*,...,n*} and all the values *g** ****i****J** x**i** *for  every given subset* J *of *I, **	*
- one has to distinguish the value *g**x*1*..x**n *from a random one
- Example with four parties (*n=4 *and *I=*{1*,2,3,4*})
- given the values
- distinguish the last value *g**x*1*x*2*x*3*x*4 from a random one

*	**	**	**	**	**     **, g**x*1* **	**  , g*
*	**	**               **,  g**x*1*x*2 *      , g**x*1*        , g**x*2
*	**	**   **, g**x*1*x*2*x*3*,**	**g**x*1*x*2*      , g**x*1*x*3*     , g**x*2*x*3
*	** *??* **	**   ,g**x*1*x*2*x*3 *,* 	*g**x*1*x*2*x*4 *   , g**x*1*x*3*x*4  *, g**x*2*x*3*x*4

- SAC  ’02 -- St-John, Newfoundland, Canada -- August 15-16, 2002

## Reducing GDDH to DDH

- Let ***n* be a collection of subsets of *I**n*={1,...,*n*}
- E.g., the above triangular structure (flows)
- For a « good » type of collection of subsets,
- advgddh(t)  (2n-3)advddh(t’)
- with t’  t+tGi and where i  is the size of  ***i*
- We can see GDDH as a standard assumption !

- SAC  ’02 -- St-John, Newfoundland, Canada -- August 15-16, 2002

## Reducing GCDH to DDH and CDH

- Let ***n* be a collection of subsets of *I**n*={1,...,*n*}
- E.g., the above triangular structure (flows)
- For a « good » type of collection of subsets,
- sucgcdh(t)  succdh(t) + (n-2)advddh(t’)
- with t’  t+tGi and where i  is the size of  ***i*
- Can we see GCDH as a (hybrid) standard assumption ?

- SAC  ’02 -- St-John, Newfoundland, Canada -- August 15-16, 2002

## Hierarchy among problems

- DL

- CDH

- DDH

- GCDH

- GDDH

- Theorem 2

- Theorem 1

- SAC  ’02 -- St-John, Newfoundland, Canada -- August 15-16, 2002

## Conclusion and Future Work

- Contributions
- Formalizing the group Diffie-Hellman problems
- Studying the case where a reduction applies
- Reducing GDH assumptions to DDH or, better, CDH
- Furture work
- Reducing GCDH to CDH only ?

- SAC  ’02 -- St-John, Newfoundland, Canada -- August 15-16, 2002