Tag Info

If we encrypt $m_1$, and send it to the server, can the server "somehow" find $E(m_1)$ and remove it? Nope; FHE allows a server that knows $E(m_1)$ and $E(m_2)$ to produce a ciphertext which is a representation of the value $E(m_1 \odot m_2)$ (for pretty much arbitrary functions $\odot$); what it doesn't allow a server to do is determine whether $m_1 = ... 2 I'm not sure I completely understand the point of your question. First of all, the property Additive implies the property MultiByScalar. Indeed, to multiply a ciphertext$E(a)$by a scalar$b$, you can simply use a square and multiply algorithm, adding a ciphertext to itself to multiply its plaintext by two, which allows to multiply in polynomial time$E(a)$... 1 Security goals like confidentiality is the reason to ask for encryption. Modulus is chosen (for particular group types) on the grounds of hard problems associated with that groups; encryption strength is defined by level of hardness of that problems. It would be nice to discover a hard problem related to some change of modulus, comparable to ... 1 For the first part of the question, I couldn't find where the authors Quantify their security, what I understood that they build their scheme based on the hardness of GCD problem. As for the second part, According to NIST recommendation which is a non-regulatory federal agency within the U.S. Commerce Department's Technology Administration. a secure value ... 2 As you point out, there is the DHGV 2010 scheme over the integers based on the approximate GCD problem but asymptotics are not great with this scheme, for eg. one of the parameters for DHGV is around$2^{\mathcal{O}(\theta^{5})}$where$\theta$is the security parameter. Of the so called second generation schemes, I would say that BGV has been pretty well ... 4 Basically, this part of the paper aims at proving that, as long as the approximate GCD problem is hard, the DGHV scheme is "secure". So, as it is standard in reduction proofs, you go and prove the contrapositive: you show that if there exists an adversary$\mathcal{A}$that is able to break the DGHV scheme, then there exist an adversary$\mathcal{B}$that ... 0 The homomorphic encryption over the integers variants are much simpler to understand. The idea is that your key is a random odd integer. to encrypt a bit, you add it (0 or 1) to the key multiplied by some integer (to hide the key better) and then add in a random even number to hide the key and value better. To decrypt a bit, you mod by the key, then mod by ... 0 If we refer to the original SV paper we'll find that they compute the security level (although it is assumed to be based on Gentry original work, and without taking their changes into consideration) so for certain values of parameters we can figure out the security level. However, what is really weird is the work that implemented their model, they changed ... 3 How does an average voter know that his vote actually counted? He doesn't have any way of performing the summation and obtaining the private key to decrypt. This is not actually true. He does have a way of performing the summation. From the spec, "all captured votes are displayed (in encrypted form) for all to see". Given the encrypted votes, you can do ... 2 As I read the comments on your question, I felt like I might react to it, even though it is not a formal answer. First, you seemed to wonder why you got some downvotes - I agree that downvoting without explaining why is far from useful. So, let me try to explain what might have provoked those negative reactions in your questions (I'm not saying that this ... 3 I am stuck at the point where I proved that the complexity is$O(2^\rho)$using brute-force approach. How shall I proceed? Well, a proof that assumed a specific attack strategy is of limited use, as that proof would be inapplicable if the attacker used some other strategy. Instead, what we typically do in a proof is assume that the adversary had some ... 0 Homomorphic encryption allows you to perform operations on the ciphertext that are reflected in the plaintext. These operations are not used to keep the plaintext confidential, that's performed by the homomorphic encryption itself. Homomorphic encryption has nothing to do with obfuscation techniques, which is probably what you're looking for. 4 In short, the operations may be different, but they do not must be. For instance, in the scheme presented on the pages 6 and 7 of this paper the homomorphic addition is simply a addition, but the homomorphic multiplication is a complex operation involving auxiliary functions and operations... About your question: Can somebody clear up which one is ... 6 Yes, preprocessing Beaver triples in an offline phase leads to a faster online phase. The online phase of an AND gate requires just two openings plus local computations. But there are other advantages as well. Define a "linear representation"$[x]$to be any way of representing/distributing a value$x$among parties such that the following properties hold: ... 5 The operation does not have to be the same. For example, with Paillier, we multiply ciphertexts to get the addition of the plaintexts. That said, I think what the 2nd quotation is saying is that the operation that is passed to the oracle is the desired operation in the plaintext domain. The oracle knows how to translate that operation into something that, ... 2 Paillier cryptosystem has the property that the product of 2 ciphertexts decrypt to the sum of the plaintexts. Strings are integers. Only that they are usually large. So this algorithm is also available for strings. This algorithm doesn't allow you to find encrypted string in a ciphertext. If you want an encryption scheme in which you can do any operation ... 3 I am not sure why you think that "homomorphic schemes and big integers are not a very efficient combination". In most homomorphic public-key cryptosystem, the message space is very large. For example, the Paillier cryptosystem (probably one of the most used for secure voting) has a plaintext space size of$2^{2048}$with current security parameters. This ... 4 If the value$x$is in the set$\{0, 1, 2, .., p-1\}$, which is the "natural" set of residues moduli$p$, then, you just have to check if$x$is greater than$\frac{p}{2}$and if so, subtract$p$. If$x$does not belong to$\{0, 1, 2, .., p-1\}$, then you can first do the usual modular reduction to transform$x$in a element of this set and then, do the ... 0 For a prime number p, the cardinality of finite field Fp is #$F_p\;= \;p$, and$F_p=\{0,1,\cdots,p-1\}$. To define positive and negative number in$F_p$by convention negative elements are those with most significant bit msb=1. Then with this convention, there are$\frac{p-1}{2}$negative numbers and$\frac{p+1}{2}$positive numbers!$F_p=[-\frac{p-1}{2}, ...