Cryptography Watch

Johnathan Katz and Moti Yung have published a paper[1] in the Journal of Cryptology detailing a scalable solution to the problem of authenticated group key exchange on an insecure public network.

[1] Katz, J., Yung, M. Scalable Protocols for Authenticated Group Key Exchange. Journal of Cryptology, 20:1, 2007, pp. 85-113.

Abstract:
Abstract. We consider the problem of authenticated group key exchange among n
parties communicating over an insecure public network. A number of solutions to this
problem have been proposed; however, all prior provably secure solutions do not scale
well and, in particular, require O(n) rounds. Our main contribution is the first scalable
protocol for this problem along with a rigorous proof of security in the standard model
under the DDH assumption; our protocol uses a constant number of rounds and requires
only O(1) “full” modular exponentiations per user. Toward this goal (and adapting
work of Bellare, Canetti, and Krawczyk), we first present an efficient compiler that
transforms any group key-exchange protocol secure against a passive eavesdropper to
an authenticated protocol which is secure against an active adversary who controls all
communication in the network. This compiler adds only one round and O(1) communication
(per user) to the original scheme. We then prove secure—against a passive
adversary—a variant of the two-round group key-exchange protocol of Burmester and
Desmedt. Applying our compiler to this protocol results in a provably secure threeround
protocol for authenticated group key exchange which also achieves forward
secrecy.

A new paper on polynomial selection in the General Number Field Sieve has been published[1]. The new method involves the creation of nonmonic linears. It is not expected to greatly increase the yield over Murphy’s method [2]. This code has been implemented in the pol5 code of Monico’s GGNFS.

[1] Kleinjund, T., On Polynomial Selection for the General Number Field Sieve, Mathematics of Computation, 75(256), 2006, pp 2037-2047.

Abstract:
The general number field sieve (GNFS) is the asymptotically fastest algorithm for factoring large integers. Its runtime depends on a good choice of a polynomial pair. In this article we present an improvement of the polynomial selection method of Montgomery and Murphy which has been used in recent GNFS records.

[2] Murphy, B. A., Brent, R. P. On Quadratic Polynomials for the Number Field Sieve, Computing Theory 98, ACSC 20(3), 1998, pp 199-215.

K. Rubin, A. Silverberg, Torus-based cryptography, Advances in Cryptology - CRYPTO 2003, Lect. Notes in Comp. Sci. 2729 (2003), pp. 349–365.

R. L. Rivest, A. Shamir, L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, 21(2), 1978, pp 120 - 126.

Abstract

An encryption method is presented with the novel property that publicly revealing an encryption key does not thereby reveal the corresponding decryption key. This has two important consequences: (1) Couriers or other secure means are not needed to transmit keys, since a message can be enciphered using an encryption key publicly revealed by the intented recipient. Only he can decipher the message, since only he knows the corresponding decryption key. (2) A message can be “signed” using a privately held decryption key. Anyone can verify this signature using the corresponding publicly revealed encryption key. Signatures cannot be forged, and a signer cannot later deny the validity of his signature. This has obvious applications in “electronic mail” and “electronic funds transfer” systems. A message is encrypted by representing it as a number M, raising M to a publicly specified power e, and then taking the remainder when the result is divided by the publicly specified product, n, of two large secret primer numbers p and q. Decryption is similar; only a different, secret, power d is used, where e * d ≡ 1(mod (p - 1) * (q - 1)). The security of the system rests in part on the difficulty of factoring the published divisor, n.