Made permutation a responsibility of cmix in the precomputation phase.

8 files changed, 113 insertions, 48 deletions

diff --git a/libcmix-crypto/api.h b/libcmix-crypto/api.h
index d52ab95..caf97b6 100644
--- a/libcmix-crypto/api.h
+++ b/libcmix-crypto/api.h
@@ -108,6 +108,11 @@ typedef GroupElement (*Inverter)(GroupElement);
 /*!
  *
  */
+typedef unsigned int (*UniformIntGetter)(unsigned int);
+
+/*!
+ *
+ */
 typedef GroupElement (*DecryptionShareGetter)(GroupElement, GroupElement);
 
 /*!
@@ -132,6 +137,7 @@ struct Api {
 	SharedKeyDeleter free_shared_key; ///< Pointer to shared key deleter function
 	Encrypter encrypt; ///< encrypt value with key;
 	Inverter invert; ///< Invert the group element;
+	UniformIntGetter get_uniform_int; ///< Get a uniform int [0 .. argument);
 	Deinitializer deinitialize; ///< Function that will deinitialize the crypto library.
 };
 
diff --git a/libcmix-crypto/elgamal/elgamal.c b/libcmix-crypto/elgamal/elgamal.c
index 7eea0f3..8f26a3c 100644
--- a/libcmix-crypto/elgamal/elgamal.c
+++ b/libcmix-crypto/elgamal/elgamal.c
@@ -22,6 +22,7 @@ struct Api get_elgamal_implementation()
 		.free_shared_key = elgamal_delete_shared_key,
 		.encrypt = elgamal_encrypt,
 		.invert = elgamal_invert,
+		.get_uniform_int = elgamal_get_uniform_int,
 		.deinitialize = elgamal_deinitialize
 	};
 }
diff --git a/libcmix-crypto/elgamal/elgamal.h b/libcmix-crypto/elgamal/elgamal.h
index 1054e3e..f937899 100644
--- a/libcmix-crypto/elgamal/elgamal.h
+++ b/libcmix-crypto/elgamal/elgamal.h
@@ -46,6 +46,8 @@ extern Encrypter elgamal_encrypt;
 
 extern Inverter elgamal_invert;
 
+extern UniformIntGetter elgamal_get_uniform_int;
+
 extern Deinitializer elgamal_deinitialize;
 
 /*!
diff --git a/libcmix-crypto/elgamal/gcrypt/gcrypt_elgamal.c b/libcmix-crypto/elgamal/gcrypt/gcrypt_elgamal.c
index 6a03fb1..e25ba72 100644
--- a/libcmix-crypto/elgamal/gcrypt/gcrypt_elgamal.c
+++ b/libcmix-crypto/elgamal/gcrypt/gcrypt_elgamal.c
@@ -284,6 +284,31 @@ GroupElement gcrypt_elgamal_invert(GroupElement const x) {
 	return inv_x;
 }
 
+unsigned int gcrypt_elgamal_get_uniform_int(unsigned int upper) {
+	unsigned int random_value;
+	
+	if(upper == 0) {
+		void* buffer = gcry_random_bytes_secure(nr_bytes, GCRY_STRONG_RANDOM);
+
+		memcpy(&random_value, buffer, sizeof(unsigned int));
+		
+		gcry_free(buffer);
+		return random_value;
+	}
+	
+	unsigned int lower = -upper % upper;
+	do {
+		void* buffer = gcry_random_bytes_secure(nr_bytes, GCRY_STRONG_RANDOM);
+
+		memcpy(&random_value, buffer, sizeof(unsigned int));
+		
+		if (random_value >= lower)
+			return random_value % upper;
+		
+		gcry_free(buffer);
+	} while(true);
+}
+
 void gcrypt_elgamal_deinitialize(void) {
 	gcry_mpi_release(p);
 	gcry_mpi_release(q);
@@ -308,4 +333,5 @@ SharedKeyDeriver elgamal_derive_shared_key = &gcrypt_elgamal_derive_shared_key;
 SharedKeyDeleter elgamal_delete_shared_key = &gcrypt_elgamal_delete_shared_key;
 Encrypter elgamal_encrypt = &gcrypt_elgamal_encrypt;
 Inverter elgamal_invert = &gcrypt_elgamal_invert;
+UniformIntGetter elgamal_get_uniform_int = &gcrypt_elgamal_get_uniform_int;
 Deinitializer elgamal_deinitialize = &gcrypt_elgamal_deinitialize;
\ No newline at end of file
diff --git a/libcmix/cmix.c b/libcmix/cmix.c
index f6eb2e8..68a638f 100644
--- a/libcmix/cmix.c
+++ b/libcmix/cmix.c
@@ -120,13 +120,31 @@ enum cmix_error start_mix(struct CMixContext* ctx, size_t nr_participants) {
 	return alloc_mix(ctx);
 }
 
+enum cmix_error generate_permutation(struct CMixContext* ctx) {
+	ctx->permutation = (unsigned int*) calloc(ctx->nr_participants, sizeof(unsigned int));
+	for(unsigned int i = 0; i < ctx->nr_participants; ++i) {
+		ctx->permutation[i] = i;
+	}
+	
+	//Fisher-Yates shuffle
+	unsigned int temp = 0;
+	for(unsigned int i = ctx->nr_participants - 1; i > 0; --i) {
+		unsigned int rand = ctx->api.get_uniform_int(i+1);
+		temp = ctx->permutation[i];
+		ctx->permutation[i] = ctx->permutation[rand];
+		ctx->permutation[rand] = temp;
+	}
+
+	return no_error;
+}
+
 enum cmix_error initialize_mix_randomness(struct CMixContext* ctx) {
 	for(size_t i = 0; i < ctx->nr_participants; ++i) {
 		ctx->r[i] = ctx->api.get_group_element(true);
 		ctx->s[i] = ctx->api.get_group_element(true);
-		ctx->permutation[i] = i;
 	}
-	return no_error;
+	
+	return generate_permutation(ctx);
 }
 
 enum cmix_error generate_random_message(struct CMixContext* ctx, char* buffer) {
@@ -185,27 +203,30 @@ enum cmix_error encrypt_r_and_multiply(struct CMixContext const* ctx, char* rand
 	return no_error;
 }
 
-enum cmix_error multiply_encrypted_s(struct CMixContext const* ctx, char* r_out_buffer, char* m_out_buffer, char const* r_in_buffer, char const* m_in_buffer, size_t index) {
+enum cmix_error permute_and_multiply_encrypted_s(struct CMixContext const* ctx, char** random_buffer, char** message_buffer, char const** random_element, char const** message_element, size_t nr_elements) {
 	size_t el_size = get_group_element_array_size(ctx);
 	
-	GroupElement random_r = ctx->api.array_to_element(r_in_buffer, el_size, true);
-	GroupElement message_r = ctx->api.array_to_element(m_in_buffer, el_size, true);
-	
-	GroupElement random_s;
-	GroupElement message_s;
-	
-	ctx->api.encrypt(&random_s, &message_s, ctx->s[ctx->permutation[index]], ctx->network_key);
-	
-	GroupElement random_pirs = ctx->api.multiply(random_r, random_s, true);
-	GroupElement message_pirs = ctx->api.multiply(message_r, message_s, true);
-	
-	element_to_buffer(ctx, r_out_buffer, random_pirs);
-	element_to_buffer(ctx, m_out_buffer, message_pirs);
+	for(size_t i = 0; i < nr_elements; ++i) {
+		unsigned int new_pos = ctx->permutation[i];
+		GroupElement random_r = ctx->api.array_to_element(random_element[i], el_size, true);
+		GroupElement message_r = ctx->api.array_to_element(message_element[i], el_size, true);
 	
-	ctx->api.free_group_element(random_r);
-	ctx->api.free_group_element(message_r);
-	ctx->api.free_group_element(random_s);
-	ctx->api.free_group_element(message_s);
+		GroupElement random_s;
+		GroupElement message_s;
+		
+		ctx->api.encrypt(&random_s, &message_s, ctx->s[new_pos], ctx->network_key);
+		
+		GroupElement random_pirs = ctx->api.multiply(random_r, random_s, true);
+		GroupElement message_pirs = ctx->api.multiply(message_r, message_s, true);
+		
+		element_to_buffer(ctx, random_buffer[new_pos], random_pirs);
+		element_to_buffer(ctx, message_buffer[new_pos], message_pirs);
+		
+		ctx->api.free_group_element(random_r);
+		ctx->api.free_group_element(message_r);
+		ctx->api.free_group_element(random_s);
+		ctx->api.free_group_element(message_s);
+	}
 	
 	return no_error;
 }
diff --git a/libcmix/cmix.h b/libcmix/cmix.h
index 89a6ad3..53212fe 100644
--- a/libcmix/cmix.h
+++ b/libcmix/cmix.h
@@ -110,7 +110,7 @@ enum cmix_error encrypt_r(struct CMixContext const* ctx, char* random_buffer, ch
 
 enum cmix_error encrypt_r_and_multiply(struct CMixContext const* ctx, char* random_buffer, char* message_buffer, char const* random_element, char const* message_element, size_t index);
 
-enum cmix_error multiply_encrypted_s(struct CMixContext const* ctx, char* r_out_buffer, char* m_out_buffer, char const* r_in_buffer, char const* m_in_buffer, size_t index);
+enum cmix_error permute_and_multiply_encrypted_s(struct CMixContext const* ctx, char** random_buffer, char** message_buffer, char const** random_element, char const** message_element, size_t nr_elements);
 
 enum cmix_error multiply_s(struct CMixContext const* ctx, char* out_buffer, char const* message, size_t index);
 
diff --git a/node/node.cpp b/node/node.cpp
index 0f2bae5..a6ad1e1 100644
--- a/node/node.cpp
+++ b/node/node.cpp
@@ -167,6 +167,13 @@ void Node::start_precomputation() {
 		exit(-1);
 	}
 	
+	std::stringstream ss; 
+	ss << "permutation:";
+	for(auto i = 0; i < cmix_ctx.nr_participants; ++i) {
+		ss << " " << cmix_ctx.permutation[i];
+	}
+	BOOST_LOG_TRIVIAL(trace) << ss.str();
+	
 	cmix_proto::PrePre prepre;
 	
 	for(size_t i = 0; i < cmix_ctx.nr_participants; ++i) {
diff --git a/node/node_node.cpp b/node/node_node.cpp
index 7b745ed..1742035 100644
--- a/node/node_node.cpp
+++ b/node/node_node.cpp
@@ -11,6 +11,13 @@ cmix_proto::PrePre fill_precomputation_pre_message(CMixContext& ctx, T const& rs
 		exit(-1);
 	}
 	
+	std::stringstream ss; 
+	ss << "permutation:";
+	for(auto i = 0; i < ctx.nr_participants; ++i) {
+		ss << " " << ctx.permutation[i];
+	}
+	BOOST_LOG_TRIVIAL(trace) << ss.str();
+	
 	cmix_proto::PrePre prepre;
 	
 	for(size_t i = 0; i < ms.size(); ++i) {
@@ -50,36 +57,32 @@ template <typename T>
 cmix_proto::PreMix fill_precomputation_mix_message(CMixContext const& ctx, T const& rs, T const& ms) {
 	cmix_proto::PreMix premix;
 	
+	size_t el_len = get_group_element_array_size(&ctx);
+	std::vector<char*> r_epirs(ms.size(), nullptr);
+	std::vector<char*> m_epirs(ms.size(), nullptr);
+	std::vector<char const*> rsv(ms.size(), nullptr);
+	std::vector<char const*> msv(ms.size(), nullptr);
 	for(size_t i = 0; i < ms.size(); ++i) {
-		premix.add_r_epirs();
-		premix.add_m_epirs();
-	}
-	for(size_t i = 0; i < ms.size(); ++i) {
-		auto new_pos = ctx.permutation[i];
-		size_t el_len = get_group_element_array_size(&ctx);
-		
-		premix.mutable_r_epirs(new_pos)->resize(el_len);
-		premix.mutable_m_epirs(new_pos)->resize(el_len);
+		std::string* r = premix.add_r_epirs();
+		r->resize(el_len);
+		r_epirs[i] = &(*r)[0];
 		
-		{
-			std::stringstream ss;
-			ss << "s: ";
-			std::string s = to_string(ctx.s[i], ctx);
-			for(auto&& c : s) {
-				ss << "\\" << std::setw(3) << std::setfill('0') << std::oct << (unsigned int) c;
-			}
-			BOOST_LOG_TRIVIAL(trace) << ss.str();
-		}
+		std::string* m = premix.add_m_epirs();
+		m->resize(el_len);
+		m_epirs[i] = &(*m)[0];
 		
-		multiply_encrypted_s(
-			&ctx,
-			&(*premix.mutable_r_epirs(new_pos))[0],
-			&(*premix.mutable_m_epirs(new_pos))[0],
-			rs.Get(i).data(),
-			ms.Get(i).data(),
-			i
-		);
+		rsv[i] = rs.Get(i).data();
+		msv[i] = ms.Get(i).data();
 	}
+	
+	permute_and_multiply_encrypted_s(
+		&ctx,
+		r_epirs.data(),
+		m_epirs.data(),
+		rsv.data(),
+		msv.data(),
+		ms.size()
+	);
 	return premix;
 }
 
@@ -114,7 +117,6 @@ cmix_proto::PrePost fill_precomputation_post_message(CMixContext& ctx, T const&
 			}
 			BOOST_LOG_TRIVIAL(trace) << ss.str();
 		} 
-		
 	}
 	
 	return prepost;