Good read on the $subject

There are solutions for data-at-rest, but they are far from perfect for cloud scenarios. In my opinion, the most challenging one is the data-in-process. There are some basic solutions to perform computation over encrypted data, but they are quite limited. This is mainly due to the fact that we still don't have efficient fully homomorphic encryption schemes. I think in the next decade, we will see better techniques to perform computation over encrypted data without decrypting them.

## Tuesday, February 22, 2011

## Monday, February 21, 2011

### Homomorphism in Shamir's secret sharing

The homomorphism property in the Shamir's secret sharing scheme is a simple but a very powerful idea that could be useful to reduce the trust we have to put on the dealer to correctly distribute secret shares to users. (See my previous post for an introduction on verifiable secret sharing).

Let's look a simple example to see what this property means.

Assume that we have two degree two polynomials

We have three users with the following secret shares given from the two secret sharing polynomials where the secrets are 2 and 3 for

Let's call the combination of the two sub-secrets as the

It is not difficult to see that if the three users releases the sum of their secret shares, that is (1, 12), (2, 27) and (3, 50), and do the polynomial interpolation on in it, the combined function gives the super-secret 5. So, the sum of the shares of the secrets are the shares of the sum of the secrets. This is what the homomorphism property is.

The above relationship is defined as the (+, +)-homomorphism. It could be two different operators. For example, Shamir's secret sharing scheme can be converted to (*, +)-homomorphism by using discrete log of secret shares.

References:

Josh Cohen Benaloh,

Let's look a simple example to see what this property means.

Assume that we have two degree two polynomials

*g*and*f*which we can use to create two 3-out-of-n secret sharing schemes where at least 3 out of n users should get together to obtain the secret.*f(x) = 2 + x + x*^{2}*g(x) = 3 + 2x + 3x*^{2}We have three users with the following secret shares given from the two secret sharing polynomials where the secrets are 2 and 3 for

*f*and*g*respectively. Let's call them*sub-secrets*.User | f | g |

u_{1} | (1,4) | (1,8) |

u_{2} | (2,8) | (2,19) |

u_{3} | (3,14) | (1,36) |

Let's call the combination of the two sub-secrets as the

*super-secret*, which is equal to 5. The problem we have at hand is "how can the users construct the super-secret revealing as little information about the sub-secrets as possible?".It is not difficult to see that if the three users releases the sum of their secret shares, that is (1, 12), (2, 27) and (3, 50), and do the polynomial interpolation on in it, the combined function gives the super-secret 5. So, the sum of the shares of the secrets are the shares of the sum of the secrets. This is what the homomorphism property is.

The above relationship is defined as the (+, +)-homomorphism. It could be two different operators. For example, Shamir's secret sharing scheme can be converted to (*, +)-homomorphism by using discrete log of secret shares.

References:

Josh Cohen Benaloh,

**Secret Sharing Homomorphisms: Keeping Shares of a Secret**,*Proceedings on Advances in cryptology---CRYPTO*, 1986## Friday, February 18, 2011

### A simple construction of a veribable secret sharing scheme

In a SS (Secret Sharing) scheme a secret is split among many people and some of them need to corporate to build the secret from their shares of the secret. In in it is basic form, a dealer who possesses the secret

In a normal SS scheme, the dealer is assumed to be honest. What if the dealer can be malicious? That's where VSS (Verifiable Secret Sharing) comes to play. VSS is similar to SS except that it allows each party to verify that the share given to them,

Here's a simple VSS scheme using Shamir's secret sharing and additive homomorphic encryption.

An additive homomorphic encryption scheme (e.g. ElGamal cryptosystem) allows us to perform addition over encrypted data. In particular, we use the following properties. Let

The dealer generates secret shares just like in the Shamir's SS scheme. For (

The dealer sends the secret share (

In order to verify their secret shares, the dealer distribute an additional piece of information. The dealer generates public and private key pair for the additive homomorphic encryption

How to Share a Secret, 1979, Adi Shamir

A Practical Scheme for Non-interactive Verifiable Secret Sharing, 1987, Paul Feldman

*s*splits the secret and gives the secret share*s*to each party P_{i}_{i},*i = 1, 2, ..., n*. The protocol makes sure that there should be at least*t+1*parties to derive the master secret*s*. In other words,*t*or less number of parties cannot derive the secret.In a normal SS scheme, the dealer is assumed to be honest. What if the dealer can be malicious? That's where VSS (Verifiable Secret Sharing) comes to play. VSS is similar to SS except that it allows each party to verify that the share given to them,

*s*, is a valid one._{i}Here's a simple VSS scheme using Shamir's secret sharing and additive homomorphic encryption.

An additive homomorphic encryption scheme (e.g. ElGamal cryptosystem) allows us to perform addition over encrypted data. In particular, we use the following properties. Let

*E*be the encryption algorithm and*m*two numbers._{1}, m_{2}*E(m*_{1})E(m_{2}) = E(m_{1}+ m_{2})*E(m*_{1})^{m2}= E(m_{1}m_{2})The dealer generates secret shares just like in the Shamir's SS scheme. For (

*n, t+1*) (i.e. out of*n*parties, there should be at least*t + 1*parties to construct the secret, the dealer selects a random degree*t*polynomial*f*with*f(0) = s*:*f(x) = s + a*_{1}x + a_{2}x^{2}+ ... + a_{t}x^{t}The dealer sends the secret share (

*i, f(i)*) (*f(i) = s*) to each party P_{i}_{i}through a private communication channel. Now*t + 1*parties can perform a polynomial interpolation and obtain a unique polynomial which is equal to*f*and get the secret*f(o)*.In order to verify their secret shares, the dealer distribute an additional piece of information. The dealer generates public and private key pair for the additive homomorphic encryption

*E*and broadcasts the encrypted coefficients of*f*, that is,*E(s), E(a*. A party P_{1}), E(a_{2}), ..., E(a_{t})_{i}, first encrypts it share and compare if the following holds. If it is true, it concludes that the dealer has given a valid secret share.*E(s*References:_{i}) ==? E(s)E(a_{1})^{i}E(a_{2})^{i2}... E(a_{t})^{it}How to Share a Secret, 1979, Adi Shamir

A Practical Scheme for Non-interactive Verifiable Secret Sharing, 1987, Paul Feldman

## Tuesday, February 15, 2011

### Flat table based group key management

Flat table (FT) key management is a simple way to manage group key. In it is basic form, it is quite efficient, but it is susceptible to collusion attacks.

First the notations:

GC - Group Controller - the centralized entity that manages the group key

GM - Group Member - a participant who wants to obtains the group key

K - the group key, it is also called DEK (Data Encryption Key) and is used to encrypt broadcast messages to the group.

KEK - Key Encryption Key - a key used to encrypt K.

Each GM in the group is assiged an identifier, ID. ID is an

GC maintains

Each GM is given

Let's assume that the ID of the joing GM is

Let's assume that the ID of the leaving GM is

However, we need to use a different approach to update the keys since we cannot reuse the old keys to do the job. GC decides a new group key K' and encrypts with the remaining

There are proposals for optimizing for multiple leaves. In one work, the use Boolean function minimization techniques to reduce the complexity.

Collusion attacks:

When multiple users are removed at once, the FT key management approach is not resistant to collusion attacks.

References:

Waldvogel et. al. The VersaKey framework: versatile group key management, 1999

Chang et. al. Key management for secure internet multicast using Boolean function minimization techniques, INFOCOM 1999

First the notations:

GC - Group Controller - the centralized entity that manages the group key

GM - Group Member - a participant who wants to obtains the group key

K - the group key, it is also called DEK (Data Encryption Key) and is used to encrypt broadcast messages to the group.

KEK - Key Encryption Key - a key used to encrypt K.

Each GM in the group is assiged an identifier, ID. ID is an

*n*-bit binary number which is denoted as*X*, where_{n-1}X_{n-2}...X_{0}*X*is either_{i}*0*or*1*. The maximum size of the group*N*=*2*.^{n}GC maintains

*2n*KEKs, {*k*}. That is for each bit position, there are two keys, one for_{i,b}| i ∈ Z_{n}, b ∈ Z_{2}*0*and one for*1*.Each GM is given

*n + 1*keys. Half of the KEKs (i.e.*n*) which correspond to the*n*bits in its ID and K.**Join**:Let's assume that the ID of the joing GM is

*X*. In order to provide backward secrecy (i.e. not allow the joining GM to access previous keys), we need to update K and_{n-1}X_{n-2}...X_{0}*n*KEKs {*k*} corresponding to this ID. New K and KEKs are encrtypted with their old K and KEKs respectively and broadcast to the group. GC gives the new K and KEKs to the joining GC though a secure private communication channel._{i,Xi}| i ∈ Z_{n}**Leave**:Let's assume that the ID of the leaving GM is

*X*. In order to provide to provide forward secrecy (i.e. not allowing the leaving GM to access new keys), again K and the_{n-1}X_{n-2}...X_{0}*n*KEKs held by the leaving GM are updated.However, we need to use a different approach to update the keys since we cannot reuse the old keys to do the job. GC decides a new group key K' and encrypts with the remaining

*n*keys that the leaving GM does not possess and broadcasts the encrypted messages. An existing group member can decrypt at least one of those messages and obtain the new group key K'. Then GC encrypts each new KEK corresponding to those of the leaving GM twice. First GC encrypts with K' and then encrypts with the old KEK, and then broadcast to the group. It make sure only the existing users can access new KEKs who already had old KEKs. Notice that the leaving GM cannot access since it does not have K' to remove one layer of encryption.There are proposals for optimizing for multiple leaves. In one work, the use Boolean function minimization techniques to reduce the complexity.

Collusion attacks:

When multiple users are removed at once, the FT key management approach is not resistant to collusion attacks.

References:

Waldvogel et. al. The VersaKey framework: versatile group key management, 1999

Chang et. al. Key management for secure internet multicast using Boolean function minimization techniques, INFOCOM 1999

## Wednesday, February 9, 2011

### What should we have in a security definition/protocol?

There are three key components that should be specified in any security definition/protocol.

1. Adversarial power under which the protocol is secure

2. Network model in which the protocol operates

3. Security guarantees that the protocol provides

Security is not something absolute. We may not be able to protect a protocol against any type of adversary. A security protocol is meaningless if it does not specify the capabilities of the adversaries under which the protocol is still secure. The capabilities of adversaries are specified in the adversarial model. For example, if the adversary is computationally bounded or have unbounded computational power, if the adversary is honest, semi-honest or malicious, etc.

Your protocol may need a trusted third party to work. It may not be secure without a trusted third party. Your protocols may need certain parties to online at all times. Such information is specified in the network model. Like the adversarial power, your protocol is meaningless without a proper network model.

As I mentioned earlier, security is moving line; your protocol may solve only certain problems. It is crucial to specify what problems it solves up front as part of the security guarantees.

In short, you need to specify what security guarantees your security protocol provides under which adversarial and network model. Otherwise, a security protocol is as useless as zero security protocol.

A big mistake people, especially in the database community, make is to say "our protocol is secure for this data set and it does not reveal any useful information to the adversary". This is very wrong. You cannot define security based on a input data set. What happens when you have a different data set? Will your protocol still be secure? Probably not. Security should never be analyzed by a set of examples. Rather, it should be based on the above 3 objective measures.

1. Adversarial power under which the protocol is secure

2. Network model in which the protocol operates

3. Security guarantees that the protocol provides

Security is not something absolute. We may not be able to protect a protocol against any type of adversary. A security protocol is meaningless if it does not specify the capabilities of the adversaries under which the protocol is still secure. The capabilities of adversaries are specified in the adversarial model. For example, if the adversary is computationally bounded or have unbounded computational power, if the adversary is honest, semi-honest or malicious, etc.

Your protocol may need a trusted third party to work. It may not be secure without a trusted third party. Your protocols may need certain parties to online at all times. Such information is specified in the network model. Like the adversarial power, your protocol is meaningless without a proper network model.

As I mentioned earlier, security is moving line; your protocol may solve only certain problems. It is crucial to specify what problems it solves up front as part of the security guarantees.

In short, you need to specify what security guarantees your security protocol provides under which adversarial and network model. Otherwise, a security protocol is as useless as zero security protocol.

A big mistake people, especially in the database community, make is to say "our protocol is secure for this data set and it does not reveal any useful information to the adversary". This is very wrong. You cannot define security based on a input data set. What happens when you have a different data set? Will your protocol still be secure? Probably not. Security should never be analyzed by a set of examples. Rather, it should be based on the above 3 objective measures.

Subscribe to:
Posts (Atom)