Public Key Cryptography - PKC 2006

It is well-known that there is an efficient method for decrypting/signing with RSA when the secret exponent

d

is small modulo

p

–1 and

q

–1. We call such an exponent

d

a small CRT-exponent. It is one of the major open problems in attacking RSA whether there exists a polynomial time attack for small CRT-exponents, i.e. a result that can be considered as an equivalent to the Wiener and Boneh-Durfee bound for small

d

. At Crypto 2002, May presented a partial solution in the case of an RSA modulus

N

=

pq

with unbalanced prime factors

p

and

q

. Based on Coppersmith’s method, he showed that there is a polynomial time attack provided that

q

 < 

N

0.382

. We will improve this bound to

q

 < 

N

0.468

. Thus, our result comes close to the desired normal RSA case with balanced prime factors. We also present a second result for balanced RSA primes in the case that the public exponent

e

is significantly smaller than

N

. More precisely, we show that there is a polynomial time attack if

$d_{p}, d_{q} \leq min\{(N/e)^{\frac{2}{5}},N^{\frac{1}{4}}\}$

. The method can be used to attack two fast RSA variants recently proposed by Galbraith, Heneghan, McKee, and by Sun, Wu.

In [1] a Niederreiter-type public-key cryptosystem based on subcodes of generalized Reed-Solomon codes is presented. In this paper an algorithm is proposed which is able to recover the private key of the aforementioned system from the public key and which is considerably faster than a brute force attack. It is shown that the example parameters proposed in [1] are insecure.

At PKC 2005, Bangerter, Camenisch and Maurer proposed an efficient protocol to prove knowledge of discrete logarithms in groups of unknown order. We describe an attack that enables the verifier to recover the full secret with essentially no computing power beyond what is required to run the protocol and after only a few iterations of it. We also describe variants of the attack that apply when some additional simple checks are performed by the prover.

We study the design of efficient and private protocols for polynomial operations in the shared-coefficients setting. We propose efficient protocols for

polynomial multiplication

,

division with remainder

,

polynomial interpolation

,

polynomial gcd

, and a few other operations. All the protocols introduced in this paper are

constant-round

, and more efficient than the

general

MPC. The protocols are all composable, and can be combined to perform more complicated functionalities. We focus on using a

threshold additively homomorphic public key scheme

due to the applications of our protocols. But, our protocols can also be securely computed in the

information-theoretic

setting. Finally, we mention some applications of our protocols to

privacy-preserving set-operations

.

We present

generic on-line/off-line threshold signatures

, in which the bulk of signature computation can take place “off-line” during lulls in service requests [6]. Such precomputation can help systems using threshold signatures quickly respond to requests. For example, tests of the Pond distributed file system showed that computation of a threshold RSA signature consumes roughly 86% of the time required to service writes to small files [12]. We apply the “hash-sign-switch” paradigm of Shamir and Tauman [16] and the distributed key generation protocol of Gennaro et al. [7] to convert any existing secure threshold digital signature scheme into a threshold on-line/off-line signature scheme. We show that the straightforward attempt at proving security of the resulting construction runs into a subtlety that does not arise for Shamir and Tauman’s construction. We resolve the subtlety and prove our signature scheme secure against a static adversary in the partially synchronous communication model under the one-more-discrete-logarithm assumption [2]. The on-line phase of our scheme is efficient: computing a signature takes one round of communication and a few modular multiplications in the common case.

We introduce the notion of Linear Integer Secret-Sharing (LISS) schemes, and show constructions of such schemes for any access structure. We show that any LISS scheme can be used to build a secure distributed protocol for exponentiation in any group. This implies, for instance, distributed RSA protocols for arbitrary access structures and with arbitrary public exponents.

ElGamal encryption is the most extensively used alternative to RSA. Easily adaptable to many kinds of cryptographic groups, ElGamal encryption enjoys homomorphic properties while remaining semantically secure providing that the DDH assumption holds on the chosen group. Its practical use, unfortunately, is intricate: plaintexts have to be encoded into group elements before encryption, thereby requiring awkward and ad hoc conversions which strongly limit the number of plaintext bits or may partially destroy homomorphicity. Getting rid of the group encoding (

e.g.

, with a hash function) is known to ruin the standard model security of the system.

This paper introduces a new alternative to group encodings and hash functions which remains

fully compatible

with standard model security properties. Partially homomorphic in customizable ways, our encryptions are comparable to plain ElGamal in efficiency, and boost the encryption ratio from about 13 for classical parameters to the optimal value of 2.

Security is constantly been infringed by inadvertent loss of secret keys, and as a solution, Dodis, Katz, Xu, and Yung [11], in Eurocrypt 2002, proposed a new paradigm called key-insulated security which provides tolerance against key exposures. Their scheme introduces a “helper key” which is used to periodically update the decryption key. The most attractive part of this scheme is that even if a decryption key of a time period is exposed, the security of the rest of the periods are unaffected. But how does this helper key managed? Can it be done efficiently? As, to alleviate the damage caused by key exposures, decryption key has to be updated at very short intervals, although frequent updating will, in contrary, increase the risk of helper key exposure. In this paper, we propose

parallel key-insulated public key encryption

in which two distinct helper keys

alternately

update a decryption key. The helper key of one system is independent from the other. Not only does it decrease the chance of helper key exposures, it also allows frequent updating of the decryption key, and over all, increases the security of the system.

The goal of steganography is to pass secret messages by disguising them as innocent-looking covertexts. Real world stegosystems are often broken because they make invalid assumptions about the system’s ability to sample covertexts. We examine whether it is possible to weaken this assumption. By modeling the covertext distribution as a stateful Markov process, we create a sliding scale between real world and provably secure stegosystems. We also show that insufficient knowledge of past states can have catastrophic results.

A signature scheme constructed according to the hash-and-sign paradigm—hash the message and then sign the hash, symbolically

σ

(

H

(

M

))—is no more secure than the hash function

H

against a collision-finding attack. Recent attacks on standard hash functions call the paradigm into question. It is well known that a simple modification of the hash-and-sign paradigm may replace the collision-resistant hash with a weaker primitive—a target-collision resistant hash function (also known as a universal one-way hash, UOWHF). The signer generates a random key

k

and outputs the pair (

k

,

σ

(

k

||

H

k

(

M

))) as a signature on

M

. The apparent problem with this approach is the increase in the signature size. In this paper we demonstrate that for three concrete signature schemes, DSA, PSS-RSA, and Cramer-Shoup, the message can be hashed simultaneously with computing the signature, using one of the signature’s components as the key for the hash function. We prove that our constructions are as secure as the originals for DSA and PSS-RSA in the random oracle model and for the Cramer-Shoup signature scheme in the standard model.

Universal One-Way Hash Functions (UOWHFs) may be used in place of collision-resistant functions in many public-key cryptographic applications. At Asiacrypt 2004, Hong, Preneel and Lee introduced the stronger security notion of higher order UOWHFs to allow construction of long-input UOWHFs using the Merkle-Damgård domain extender. However, they did not provide any provably secure constructions for higher order UOWHFs.

We show that the subset sum hash function is a

k

th order Universal One-Way Hash Function (hashing

n

bits to

m

<

n

bits) under the Subset Sum assumption for

k

=

O

(log

m

). Therefore we strengthen a previous result of Impagliazzo and Naor, who showed that the subset sum hash function is a UOWHF under the Subset Sum assumption. We believe our result is of theoretical interest; as far as we are aware, it is the first example of a natural and computationally efficient UOWHF which is also a provably secure higher order UOWHF under the same well-known cryptographic assumption, whereas this assumption does not seem sufficient to prove its collision-resistance. A consequence of our result is that one can apply the Merkle-Damgård extender to the subset sum compression function with ‘extension factor’

k

+1, while losing (at most) about

k

bits of UOWHF security relative to the UOWHF security of the compression function. The method also leads to a saving of up to

m

log(

k

+1) bits in key length relative to the Shoup XOR-Mask domain extender applied to the subset sum compression function.

Recently, Shirokauer’s algorithm to solve the discrete logarithm problem modulo a prime

p

has been modified by Matyukhin, yielding an algorithm with running time

$L_{p}[\frac{1}{3},1.09018...]$

, which is, at the present time, the best known estimate of the complexity of finding discrete logarithms over prime finite fields and which coincides with the best known theoretical running time for factoring integers, obtained by Coppersmith. In this paper, another algorithm to solve the discrete logarithm problem in

$\mathbb{F}^{*}_{p}$

for

p

prime is presented. The global running time is again

$L_{p}[\frac{1}{3},1.09018...]$

, but in contrast with Matyukhins method, this algorithm enables us to calculate individual logarithms in a separate stage in time

$L_{p}[\frac{1}{3},3^{1/3}]$

, once a

$L_{p}[\frac{1}{3},1.09018...]$

time costing pre-computation stage has been executed. We describe the algorithm as derived from [6] and estimate its running time to be

$L_{p}[\frac{1}{3},(\frac{64}{9})^{1/3}]$

, after which individual logarithms can be calculated in time

$L_{p}[\frac{1}{3},3^{1/3}]$

.

On an elliptic curve, the degree of an isogeny corresponds essentially to the degrees of the polynomial expressions involved in its application. The multiplication–by–ℓ map [ℓ] has degree ℓ

2

, therefore the complexity to directly evaluate [ℓ](

p

) is

O

(ℓ

2

). For a small prime ℓ (= 2, 3) such that the additive binary representation provides no better performance, this represents the true cost of application of scalar multiplication. If an elliptic curve admits an isogeny

ϕ

of degree ℓ then the costs of computing

ϕ

(

P

) should in contrast be

O

(ℓ) field operations. Since we then have a product expression [ℓ]=

$\hat{\varphi}\varphi$

, the existence of an ℓ-isogeny

ϕ

on an elliptic curve yields a theoretical improvement from

O

(ℓ

2

) to

O

(ℓ) field operations for the evaluation of [ℓ](

p

) by naïve application of the defining polynomials. In this work we investigate actual improvements for small ℓ of this asymptotic complexity. For this purpose, we describe the general construction of families of curves with a suitable decomposition [ℓ]=

$\hat{\varphi}\varphi$

, and provide explicit examples of such a family of curves with simple decomposition for [3]. Finally we derive a new tripling algorithm to find complexity improvements to triplication on a curve in certain projective coordinate systems, then combine this new operation to non-adjacent forms for ℓ-adic expansions in order to obtain an improved strategy for scalar multiplication on elliptic curves.

This paper explains the design and implementation of a high-security elliptic-curve-Diffie-Hellman function achieving record-setting speeds: e.g., 832457 Pentium III cycles (with several side benefits: free key compression, free key validation, and state-of-the-art timing-attack protection), more than twice as fast as other authors’ results at the same conjectured security level (with or without the side benefits).

A signature system is said to be strongly unforgeable if the signature is existentially unforgeable and, given signatures on some message

m

, the adversary cannot produce a new signature on

m

. Strongly unforgeable signatures are used for constructing chosen-ciphertext secure systems and group signatures. Current efficient constructions in the standard model (i.e. without random oracles) depend on relatively strong assumptions such as Strong-RSA or Strong-Diffie-Hellman. We construct an efficient strongly unforgeable signature system based on the standard Computational Diffie-Hellman problem in bilinear groups.

We generalize the selective-ID security model for HIBE by introducing two new security models. Both these models allow the adversary to commit to a set of identities and in the challenge phase choose any one of the previously committed identities. Two constructions of HIBE are presented which are secure in the two models. One of the HIBE constructions supports an unbounded number of levels, i.e., the maximum number of levels does not need to be specified during the set-up. Further, we show that this HIBE can be modified to obtain a multiple receiver IBE which is secure in the selective-ID model without the random oracle assumption.

An

aggregate signature

is a single short string that convinces any verifier that, for all 1 ≤

i

≤

n

, signer

S

i

signed message

M

i

, where the

n

signers and

n

messages may all be distinct. The main motivation of aggregate signatures is compactness. However, while the aggregate signature itself may be compact, aggregate signature verification might require potentially lengthy additional information – namely, the (at most)

n

distinct signer public keys and the (at most)

n

distinct messages being signed. If the verifier must obtain and/or store this additional information, the primary benefit of aggregate signatures is largely negated.

This paper initiates a line of research whose ultimate objective is to find a signature scheme in which the

total information needed to verify

is minimized. In particular, the verification information should preferably be as close as possible to the theoretical minimum: the complexity of describing which signer(s) signed what message(s). We move toward this objective by developing

identity-based

aggregate signature schemes. In our schemes, the verifier does not need to obtain and/or store various signer public keys to verify; instead, the verifier only needs a description of who signed what, along with two constant-length “tags”: the short aggregate signature and the single public key of a Private Key Generator. Our scheme is secure in the random oracle model under the computational Diffie-Hellman assumption over pairing-friendly groups against an adversary that chooses its messages and its target identities adaptively.

By a generic transformation by Canetti, Halevi, and Katz (CHK) every Identity-based encryption (IBE) scheme implies a chosen-ciphertext secure public-key encryption (PKE) scheme. In the same work it is claimed that this transformation maps the two existing IBE schemes to two

new and different

chosen-ciphertext secure encryption schemes, each with individual advantages over the other.

In this work we reconsider one of the two specific instantiations of the CHK transformation (when applied to the “second Boneh/Boyen IBE scheme”). We demonstrate that by applying further simplifications the resulting scheme can be proven secure under a weaker assumption than the underlying IBE scheme.

Surprisingly, our simplified scheme nearly converges to a recent encryption scheme due to Boyen, Mei, and Waters which itself was obtained from the other specific instantiation of the CHK transformation (when applied to the “first Boneh/Boyen IBE scheme”). We find this particularly interesting since the two underlying IBE schemes are completely different.

The bottom line of this paper is that the claim made by Canetti, Halevi, and Katz needs to be reformulated to: the CHK transformation maps the two known IBE schemes to nearly one single encryption scheme.

We demonstrate how to prevent differential attacks on multivariate public key cryptosystems using the Plus (+) method of external perturbation. In particular, we prescribe adding as few as 10 Plus polynomials to the Perturbed Matsumoto-Imai (PMI) cryptosystem when

g

=1 and

r

=6, where

θ

is the Matsumoto-Imai exponent,

n

is the message length,

g

 = 

gcd

(

θ

,

n

), and

r

is the internal perturbation dimension; or as few as

g

+10 when

g

≠ 1. The external perturbation does not significantly decrease the efficiency of the system, and in fact has the additional benefit of resolving the problem of finding the true plaintext among several preimages of a given ciphertext. We call this new scheme the Perturbed Matsumoto-Imai-Plus (PMI+) cryptosystem.

Motivated by cryptographic applications, we study subgroups of braid groups

B

n

generated by a small number of random elements of relatively small lengths compared to

n

. Our experiments show that “most” of these subgroups are equal to the whole

B

n

, and “almost all” of these subgroups are generated by positive braid words. We discuss the impact of these experimental results on the security of the Anshel-Anshel-Goldfeld key exchange protocol [2] with originally suggested parameters as well as with recently updated ones.

Exponent splitting is a classical technique to protect modular exponentiation against side-channel attacks. Although it is rarely implemented due to efficiency reasons, it is widely considered as a highly-secure solution. Therefore it is often used as a reference to benchmark new countermeasure proposals.

In this paper, we make new observations about the statistical behavior of the splitting of the exponent. We look at the correlations between the two shares, and show an important imbalance. Later, we show how to use this imbalance in higher-order attacks (mostly based on address-bit, safe-error and fault analysis). We also present experimental results to estimate their feasibility.

In this paper, we propose new signature schemes provably secure under the strong RSA assumption in the standard model. Our proposals utilize Shamir-Tauman’s generic construction for building EF-CMA secure online/offline signature schemes from trapdoor commitments and less secure basic signature schemes. We introduce a new natural intractability assumption for hash functions, which can be interpreted as a generalization of second pre-image collision resistance. Assuming the validity of this assumption, we are able to construct new signature schemes provably secure under the strong RSA assumption without random oracles. In contrast to Cramer-Shoup’s signature scheme based on strong RSA in the standard model, no costly generation of prime numbers is required for the signer in our proposed schemes. Moreover, the security of our schemes relies on weaker assumptions placed on the hash function than Gennaro, Halevi and Rabin’s solution.

Digital signature is one of the most important primitives in public key cryptography. It provides authenticity, integrity and non-repudiation to many kinds of applications. On signer privacy however, it is generally unclear or suspicious of whether a signature scheme itself can guarantee the anonymity of the signer. In this paper, we give some affirmative answers to it. We formally define the signer anonymity for digital signature and propose some schemes of this type. We show that a signer anonymous signature scheme can be very useful by proposing a new anonymous key exchange protocol which allows a client Alice to establish a session key with a server Bob securely while keeping her identity secret from eavesdroppers. In the protocol, the anonymity of Alice is already maintained when Alice sends her signature to Bob in clear, and no additional encapsulation or mechanism is needed for the signature. We also propose a method of using anonymous signature to solve the collusion problem between organizers and reviewers of an anonymous paper review system.

In this paper, we show that identification schemes (ID-schemes) are very powerful in some areas of cryptography. We first prove an equivalence between non-interactive trapdoor commitment schemes and a natural class of identification schemes. We next propose a more efficient on-line/off-line signature transformation than Shamir-Tauman. As an application, we present a variant of Boneh-Boyen (BB) signature scheme which is not only on-line/off-line but also has a smaller public key size than the original BB scheme. Finally, we present the first identity-based ID-scheme which is secure against concurrent man-in-the-middle attack without random oracles by using our variant of BB signature scheme.

KEA is a Diffie-Hellman based key-exchange protocol developed by NSA which provides mutual authentication for the parties. It became publicly available in 1998 and since then it was neither attacked nor proved to be secure. We analyze the security of KEA and find that the original protocol is susceptible to a class of attacks. On the positive side, we present a simple modification of the protocol which makes KEA secure. We prove that the modified protocol, called KEA+, satisfies the strongest security requirements for authenticated key-exchange and that it retains some security even if a secret key of a party is leaked. Our security proof is in the random oracle model and uses the Gap Diffie-Hellman assumption. Finally, we show how to add a key confirmation feature to KEA+ (we call the version with key confirmation KEA+C) and discuss the security properties of KEA+C.

Key agreement protocols are frequently based on the Diffie-Hellman protocol but require authenticating the protocol messages in two ways. This can be made by a cross-authentication protocol. Such protocols, based on the assumption that a channel which can authenticate short strings is available (SAS-based), have been proposed by Vaudenay. In this paper, we survey existing protocols and we propose a new one. Our proposed protocol requires three moves and a single SAS to be authenticated in two ways. It is provably secure in the random oracle model. We can further achieve security with a generic construction (e.g. in the standard model) at the price of an extra move. We discuss applications such as secure peer-to-peer VoIP.

Key derivation refers to the process by which an agreed upon large random number, often named master secret, is used to derive keys to encrypt and authenticate data. Practitioners and standardization bodies have usually used the random oracle model to get key material from a Diffie-Hellman key exchange. However, formal proofs in the standard model require

randomness extractors

to formally extract the entropy of the random master secret into a seed prior to deriving other keys. Whereas this is a quite simple tool, it is not easy to use in practice –or it is easy to misuse it–.

In addition, in many standards, the acronym PRF (Pseudo-Random Functions) is used for several tasks, and namely the randomness extraction. While randomness extractors and pseudo-random functions are

a priori

distinct tools, we first study whether such an application is correct or not. We thereafter study the case of

$\mathbb{Z}^{*}_{p}$

where

p

is a safe-prime and the case of elliptic curve since in IPSec for example, only these two groups are considered. We present

very efficient

and

provable

randomness extraction techniques for these groups under the DDH assumption. In the special case of elliptic curves, we present a new technique —the so-called

’Twist-AUgmented’

technique— which exploits specific properties of some elliptic curves, and avoids the need of any randomness extractor. We finally compare the efficiency of this method with other solutions.

With the development of grids, distributed applications are spread across multiple computing resources and require efficient security mechanisms among the processes. Although protocols for authenticated group Diffie-Hellman key exchange protocols seem to be the natural mechanisms for supporting these applications, current solutions are either limited by the use of public key infrastructures or by their scalability, requiring a number of rounds linear in the number of group members. To overcome these shortcomings, we propose in this paper the first provably-secure password-based constant-round group key exchange protocol. It is based on the protocol of Burmester and Desmedt and is

provably-secure

in the random-oracle and ideal-cipher models, under the Decisional Diffie-Hellman assumption. The new protocol is very efficient and fully scalable since it only requires four rounds of communication and four multi-exponentiations per user. Moreover, the new protocol avoids intricate authentication infrastructures by relying on passwords for authentication.

We introduce a new notion of

conditional oblivious cast

(COC), which involves three parties: a sender

S

and two receivers

A

and

B

. Receivers

A

and

B

own their secrets

x

and

y

, respectively, and the sender

S

holds the message

m

. In a COC scheme for the predicate

Q

(Q-COC),

A

and

B

send

x

and

y

in a masked form to

S

, and then

S

sends

m

to

A

and

B

such that they get

m

if and only if

Q

(

x

,

y

)=1. Besides, the secrets

x

and

y

can not be revealed to another receiver nor the sender. We also extend COC to 1-out-of-2 COC (COC

$^{\rm 1}_{\rm 2}$

) in which

S

holds two messages

m

0

and

m

1

, and

A

and

B

get

m

1

if

Q

(

x

,

y

)=1 and

m

0

otherwise. We give the definitions for COC and COC

$^{\rm 1}_{\rm 2}$

, and propose several COC and COC

$^{\rm 1}_{\rm 2}$

schemes for “equality”, “inequality”, and “greater than” predicates. These are fundamental schemes that are useful in constructing more complex secure interactive protocols. Our schemes are efficiently constructed via homomorphic encryption schemes and proved secure under the security of these encryption schemes.

We study efficiency tradeoffs for secure two-party computation in presence of malicious behavior. We investigate two main approaches for defending against malicious behavior in

Yao’s garbled circuit

method: (1)

Committed-input

scheme, (2)

Equality-checker

scheme. We provide asymptotic and concrete analysis of communication and computation costs of the designed protocols. We also develop a weaker definition of security (

k-leaked model

) for malicious two-party computation that allows for disclosure of some information to a malicious party. We design more efficient variations of

Yao’s

protocol that are secure in the proposed model.

Certificateless cryptography (CL-PKC) is a concept that aims at enjoying the advantages of identity based cryptography without suffering from its inherent key escrow. Several methods were recently suggested to generically construct a certificateless encryption (CLE) scheme by combining identity based schemes with ordinary public key cryptosystems. Whilst the security of one of these generic compositions was proved in a relaxed security model, we show that all them are insecure against chosen-ciphertext attacks in the strongest model of Al-Riyami and Paterson. We show how to easily fix these problems and give a method to achieve generic CLE constructions which are provably CCA-secure in the random oracle model. We finally propose a new efficient pairing-based scheme that performs better than previous proposals without pre-computation. We also prove its security in the random oracle model.

Signcryption schemes aim to provide all of the advantages of simultaneously signing and encrypting a message. Recently, Dent [8, 9]and Bjørstad [4] investigated the possibility of constructing provably secure signcryption schemes using hybrid KEM-DEM techniques [7]. We build on this work by showing that more efficient insider secure hybrid signcryption schemes can be built using tag-KEMs [1]. To prove the effectiveness of this construction, we will provide several examples of secure signcryption tag-KEMs, including a brand new construction based on the Chevallier-Mames signature scheme [5] which has the tightest known security reductions for both confidentiality and unforgeability.

We introduce the notion of security-mediated certificateless (SMC) cryptography. This allows more lightweight versions of mediated cryptography while maintaining the ability for instantaneous revocation of keys. Moreover, our solutions avoid key escrow, which has been used in all previous mediated cryptography algorithms. We provide a model of security against a fully-adaptive chosen ciphertext attacker, who may be a rogue key generation centre or any coalition of rogue users. We present a generic construction and also a concrete algorithm based on bilinear pairings. Our concrete scheme is more efficient than the identity-based mediated encryption scheme of Baek and Zheng in PKC 2004 which is provably secure in a comparable security model. In addition, our proposals can be easily extended to support distributed security mediators.

A

k

-Times Anonymous Authentication (

k

-TAA) scheme allows users to be authenticated anonymously so long as the number of times that they are authenticated is within an allowable number. Some promising applications are e-voting, e-cash, e-coupons, and trial browsing of contents. However, the previous schemes are not efficient in the case where the allowable number

k

is large, since they require both users and verifiers to compute

O

(

k

) exponentiation in each authentication. We propose a

k

-TAA scheme where the numbers of exponentiations required for the entities in an authentication are independent of

k

. Moreover, we propose a notion of public detectability in a

k

-TAA scheme and present an efficient publicly verifiable

k

-TAA scheme, where the number of modular exponentiations required for the entities is

O

(log(

k

)).