Multiplexing schemes for homomorphic cryptosystems


We present in this article two secure multiplexing and demul- tiplexing schemes that use homomorphic properties from known public key cryptosystems. One scheme is suitable for cryptosystems with addi- tive homomorphic properties such as Paillier and Benaloh cryptosystems. The proposed scheme employs a modification of Hadamard codes to generate a set of orthogonal codes over Z3. The other one is suitable for cryptosystems with multiplicative homomorphic properties such as RSA and ElGamal. Both schemes might be used in voting and auction systems where anonymity of the individuals is crucial.


Abe, M. and Suzuki, K.: M+1-st price auction using homomorphic encryption. Public Key Cryptography, pages 115–124, (2002)

Adida, B. and Rivest, R. L.: Scratch & vote: self-contained paper-based crypto- graphic voting. WPES ’06: Proceedings of the 5th ACM workshop on Privacy in electronic society, pages 29–40, New York, NY, USA, ACM. (2006)

Baudron O., Fouque P. A., Pointcheval, D., Stern, J. and Poupard G.: Practical multi-candidate election system. PODC ’01: Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, pages 274–283, New York, NY, USA, ACM. (2001)

Benaloh, J. C. and Tuinstra, D.: Receipt-free secret-ballot elections (extended abstract). In STOC, pages 544–553, (1994)

Clarkson, J. B.: Dense probabilistic encryption. Proceedings of the Workshop on Selected Areas of Cryptography, pages 120–128, (1994)

Cramer, R., Gennaro, R. and Schoenmakers, B.: A secure and optimally efficient multi-authority election scheme. EUROCRYPT, pages 103–118, (1997)

Cramer, R. J., Franklin, M., Schoenmakers, L. A. and Yung, M.: Multi-authority secret-ballot elections with linear work. Technical report, Amsterdam, The Nether- lands, (1995)

ElGamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, 31(4):469–472, (1985)

Kikuchi, H., Harkavy, M. and Tygar, J. D.: Multi-round anonymous auction protocols. Proceedings of the First IEEE Workshop on Dependable and Real-Time E-Commerce Systems, pages 62–69. Springer-Verlag, (1999)

Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. EUROCRYPT, pages 223–238, (1999)

Rivest, R. L., Shamir A., and Adleman, L. M.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM, 21(2):120–126, (1978)

Viterbi, A. J.: CDMA: principles of spread spectrum communication. Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, USA, (1995)

Los autores/as que publiquen en la Revista ELEMENTOS aceptan las siguientes condiciones: 

    1. Los autores/as conservan los derechos de autor y ceden a la revista el derecho de la primera publicación, con el trabajo registrado con Creative Commons: Reconocimiento - No Comercial -Sin Obra Derivada, que permite a terceros utilizar lo publicado siempre que mencionen la autoría del trabajo y a la primera publicación en esta revista.
    2. Los autores/as pueden realizar otros acuerdos contractuales independientes y adicionales para la distribución no exclusiva de la versión del artículo publicado en esta revista (p. ej., incluirlo en un repositorio institucional o publicarlo en un libro) siempre que indiquen claramente que el trabajo se publicó por primera vez en esta revista.
    3. Se permite y recomienda a los autores/as a publicar su trabajo en Internet (por ejemplo en páginas institucionales o personales) antes y durante el proceso de revisión y publicación, ya que puede conducir a intercambios productivos y a una mayor y más rápida difusión del trabajo publicado.

Licencia de Creative Commons

Panorama by Institución Universitaria Politécnico Grancolombiano is licensed under a Creative Commons Reconocimiento-NoComercial-SinObraDerivada 4.0 Unported License.