5,495 reputation
11123
bio website people.scs.carleton.ca/~clark
location Ottawa, Canada
age 33
visits member for 3 years, 4 months
seen Jan 5 at 22:55

Postdoctoral fellow interested in authentication and cryptographic voting.


Jun
26
comment How is SSL secure from rogue Certificate Authorities?
In basic HTTPS, there is no protection against this attack. And it has been conducted in real life. However, there are a number of proposals to address this attack that have reached various stages of deployment but generally require either the client or the server to opt-in. For a history of these attacks and a list and evaluation of solutions, see this paper: people.scs.carleton.ca/~clark/papers/2013_sp.pdf (In particular, the first 8 rows in Table 1)
Mar
25
comment Can Elgamal be made additively homomorphic and how could it be used for E-voting?
Reading between the lines of what you are asking, the answer is no. Elgamal can handle both multiplication and addition, but you cannot mix the two operations on any given ciphertexts. You must decide when you encrypt to lock the ciphertext into only doing addition or only doing multiplication. The ability to do both is a "fully homomorphic" cryptosystem, of which there are some, but they are mainly theoretical and too slow to be practical. One efficient scheme, BGN, allows a single multiplication and as many additions as you want.
Jan
16
comment Why is proof-by-reduction needed (for Elgamal proof of security, for example)?
@Maeher is correct. What is amiss is that you are not considering all the values (that are functionally dependent on x,r,m) that you have available. As for a step-by-step proof, see: shoup.net/papers/games.pdf (Section 3). And read the whole paper if you want more intuition into how to structure proofs.
Oct
16
comment Can Elgamal be made additively homomorphic and how could it be used for E-voting?
I don't know of any publications that directly compare Paillier with Elgamal in Gq or with ECC; although I haven't look too hard either. It is just accepted as folk wisdom I guess.
Sep
11
comment What is a “rewinding argument”?
It is a little long, but I illustrate it in my answer to another question here: crypto.stackexchange.com/a/1412/64
Aug
13
comment Approach towards anonymous e-voting
P.S., since you are correct about the billions of e-voting systems (slight exaggeration perhaps), I summarize the literature in Chapters 3 and 9 of my dissertation. The bit you are asking about is in 3.3.5: people.scs.carleton.ca/~clark/theses/phd_electronic.pdf
Aug
13
comment Approach towards anonymous e-voting
Paillier is patented so it is questionable if you can use the Baudron et al. approach for an implementation. It inherently requires Paillier because of the way multiple candidates are packed into a single ciphertext. A slightly less efficient but much simpler approach is given by Hirt in Chapter 5 of his dissertation: ftp.inf.ethz.ch/pub/crypto/publications/Hirt01.pdf
Jul
23
comment Additive ElGamal cryptosystem using a finite field
An additional note to augment great answers below: $g$ generates a group of size $q$ but the group is not $\mathbb{Z}_q$. In other words, it is not $1,2,3,\ldots,q$. Rather it is a random looking subset of numbers in $\mathbb{Z}_p^*$; i.e., numbers between $1$ and $p-1$. This is why everything is done $\mod p$.
Jul
11
comment Feedback on rolling my own entropy gatherer
Hash functions cannot be shown to be good extractors. There is a theory-practice gap on this point, but given that there are very simple constructions that can be shown to be good extractors, one should use them. See Section 1 of this paper: iacr.org/archive/crypto2004/31520493/clean.pdf
Jun
30
comment Using bad generator in ElGamal Encryption
Your first point is semantics, but all modern crypto textbooks do not consider the secure version (order q instead of p-1) a variant. Elgamal with order p-1 leaks Legrange, not Jacobi, but it is true both Elgamal and RSA leak a bit. Padding is necessary for RSA to have CPA (and likely CCA) security, but Elgamal is CPA secure in prime order subgroups without padding. Padding is essentially never used with Elgamal, either because you want the homomorphic properties or you use a hybrid variant (e.g., hash Elgamal).
Jun
29
comment Using bad generator in ElGamal Encryption
Typo: should be "not generally (always) be hard". Also FWIW, if you try and encrypt an $M$ that is not in the group generated by $g$, then you can end up with a different set of problems.
Jun
29
comment Using bad generator in ElGamal Encryption
If $g$ generates a prime-ordered group that is small (e.g., less than 160 bits), then discrete logs become feasible. If $g$ has composite order, the discrete log will not generally (always) not be hard (there are ways to setup composite groups that are). If $g$ has large prime order, then it is secure even if it is not the order that was intended (but you may have trouble encoding $M$ into $\mathbb{G}_q$).
May
7
comment RSA reencryption scheme
Section 4.3 of this paper has an example for RSA but it is unidirectional: www.isoc.org/isoc/conferences/ndss/03/proceedings/papers/14.pdf
May
7
comment RSA reencryption scheme
This is called proxy re-encryption and there are a lot of ways of doing it: en.wikipedia.org/wiki/Proxy_re-encryption
Mar
30
comment What challenge should I use in a challenge-response proof-of-work?
Good point about multiple connections. You are right, in DoS prevention, I guess parallalization doesn't matter much. Yeah, scrypt is a nice way to meter based on processing power and memory accesses.
Mar
27
comment ZKIP for Paillier public key correctness
Yes, the proof is very complicated. I would consider using the exponential version of Elgamal ($\mathsf{Enc}(g^m)$ instead of $\mathsf{Enc}(m)$, see tinyurl.com/CGS1997) instead of Paillier if possible.
Mar
13
comment Division in paillier cryptosystem
@user996522 It depends on how you define "makes sense." If $a/b = c$, then $c \cdot b=a$. It is the same thing here. If you compute $a/b$ under encryption, you will get the encryption of the value $c$ such that $c \cdot b \bmod{n} = a$. You can think of it as "discrete division" akin to a discrete logarithm.
Mar
9
comment Why do we use encrypt-decrypt-encrypt (EDE) in 3DES, rather than encrypting three times?
Duplicate on Security SE: security.stackexchange.com/questions/1886/…
Mar
8
comment RSA-OAEP versus RSA with Fujisaki-Okamoto construction
In terms of your RSA construction, it is hard to say without trying to find a reduction. These things are very tricky. It does have a larger ciphertext than RSA-OAEP which is a drawback. (Also, "easier" isn't typically a design parameter. Unless if you mean more efficient or a more direct reduction to a known intractable problem. But easier to implement, to understand, etc., get trumped by efficiency.).
Mar
8
comment RSA-OAEP versus RSA with Fujisaki-Okamoto construction
(That was in reply to your previous comment).