Attack and Correction: How to Design a Secure and Efficient Mix Network
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Shuffling is an effective method to build a publicly verifiable mix network to implement verifiable anonymous channels that can be used for important cryptographic applications like electronic voting and electronic cash. One shuffling scheme by Groth is claimed to be secure and efficient. However, its soundness has not been formally proven. An attack against the soundness of this shuffling scheme is presented in this paper. Such an attack compromises the soundness of the mix network based on it. Two new shuffling protocols are designed on the basis of Groth's shuffling and batch verification techniques. The first new protocol is not completely sound, but is formally analyzed in regards to soundness, so it can be applied to build a mix network with formally proven soundness. The second new protocol is completely sound, so is more convenient to apply. Formal analysis in this paper guarantees that both new shuffling protocols can be employed to build mix networks with formally provable soundness. Both protocols prevent the attack against soundness in Groth's scheme. Both new shuffling protocols are very efficient as batch-verification-based efficiency-improving mechanisms have been adopted. The second protocol is even simpler and more elegant than the first one as it is based on a novel batch cryptographic technique.
Abstract
Shuffling is an effective method to build a publicly verifiable mix network to implement verifiable anonymous channels that can be used for important cryptographic applications like electronic voting and electronic cash. One shuffling scheme by Groth is claimed to be secure and efficient. However, its soundness has not been formally proven. An attack against the soundness of this shuffling scheme is presented in this paper. Such an attack compromises the soundness of the mix network based on it. Two new shuffling protocols are designed on the basis of Groth's shuffling and batch verification techniques. The first new protocol is not completely sound, but is formally analyzed in regards to soundness, so it can be applied to build a mix network with formally proven soundness. The second new protocol is completely sound, so is more convenient to apply. Formal analysis in this paper guarantees that both new shuffling protocols can be employed to build mix networks with formally provable soundness. Both protocols prevent the attack against soundness in Groth's scheme. Both new shuffling protocols are very efficient as batch-verification-based efficiency-improving mechanisms have been adopted. The second protocol is even simpler and more elegant than the first one as it is based on a novel batch cryptographic technique.
참고문헌 (22)
- M Abe., "Mix-networks on permutation net-works", In ASIACRYPT '98, pp.258~273 (1998)
- M Abe, "Remarks on mix-network based on permutation networks", In PKC '01, pp.317~324 (2001)
- R Aditya, "Batch verification for equality of discrete logarithms and threshold decryptions", In ACNS '04, pp.494~508 (2004)
- M Bellare, "Fast batch verification for modular exponentiation and digital signatures", In EUROCRYPT '98, pp.236~250 (1998)
- C Boyd, "Attacking and repairing batch verification schemes", In ASIACRYPT '00, pp.58~71 (2000)
- D Chaum., "ntraceable electronic mail, return address and digital pseudonym", Communications of the ACM, 24(2), pp.84~88 (1981)
- D Chaum, "Wallet databases with observers", In CRYPTO '92, pp.89~105 (1992)
- J Furukawa, "An efficient scheme for proving a shuffle", In CRYPTO '01, pp.368~387 (2001)
- E Gabber, "How to make personalized web browsing simple, secure, and anonymous", In FC '97, pp.17~31 (1997)
- P Golle, "Optimistic mixing for exit-polls", In ASIACRYPT '02, pp.451~465 (2002)
- J Groth, "Sub-linear zero-knowledge argument for correctness of a shuffle", In EUROCRYPT '08, pp.379~396 (2008)
- J Groth, "Verifiable shuffle of large size ciphertexts", In PKC '07, pp.377~392 (2007)
- J Groth., "A verifiable secret shuffle of homomorphic encryptions", In Public Key Cryptography 2003, pp.145~160 (2003)
- L Guillou, "A``paradoxical'' identity-based signature scheme resulting from zero knowledge", In Shafi Goldwasser, editor, CRYPTO '88, pp.216~231 (1988)
- F Hoshino, "Lenient", Strict batch verification in several groups, 2001, 81~94
- C Neff., "A verifiable secret shuffle and its application to e-voting", In ACM CCS '01, pp.116~125 (2001)
- P Paillier., "Public key cryptosystem based on composite degree residuosity classes", In EUROCRYPT '99, pp.223~238 (1999)
- K Peng, "Simple and efficient shuffling with provable correctness and ZK privacy", In CRYPTO '05, pp.188~204 (2005)
- K Peng, "Efficient implementation of relative bid privacy in sealed-bid auction", In WISA '03, pp.244~256 (2003)
- K Peng, "A correct, private and efficient mix network", In PKC '04, pp.439~454 (2004)
- C Schnorr., "Efficient signature generation by smart cards", Journal of Cryptology, 4, pp.161~174 (1991)
- D Wikstrom, "A sender verifiable mix-net and a new proof of a shuffle", In ASIACRYPT '05, pp.273~292 (2005)