Public Key Cryptography – PKC 2007

We give a short constant-size group signature scheme, which we prove fully secure under reasonable assumptions in bilinear groups, in the standard model. We achieve this result by using a new NIZK proof technique, related to the BGN cryptosystem and the GOS proof system, but that allows us to hide integers from the full domain rather than individual bits.

Direct anonymous attestation (DAA) is an anonymous authentication scheme adopted by the Trusted Computing Group in its specifications for trusted computing platforms. This paper presents an efficient construction that implements all anonymous authentication features specified in DAA, including authentication with total anonymity, authentication with variable anonymity, and rogue TPM tagging. The current DAA construction is mainly targeted for powerful devices such as personal computers, and their corresponding application areas, but is not entirely suitable for embedded devices with limited computing capabilities (e.g., cell phones or hand-held PDAs). We propose a new construction with more efficient sign and verify protocols, making it more attractive for embedded devices. We prove that the new construction is secure under the strong RSA assumption and the decisional Diffie-Hellman assumption.

At PKC 2006, Yang, Wong, Deng and Wang proposed the notion of anonymous signature schemes where signatures do not reveal the signer’s identity, as long as some parts of the message are unknown. They also show how to modify the RSA scheme and the Schnorr scheme to derive anonymous signatures in the random oracle model. Here we present a general and yet very efficient approach to build such anonymous schemes from ordinary signature schemes. When instantiated in the random oracle model, our solution is essentially as efficient as the original scheme, whereas our construction also supports an almost as efficient instantiation in the standard model.

For controlling the public verifiability of ordinary digital signatures, designated confirmer signature (DCS) schemes were introduced by Chaum at Eurocrypt 1994. In such schemes, a signature can be verified only with the help of a semi-trusted third party, called the designated confirmer. The confirmer can further selectively convert individual designated confirmer signatures into ordinary signatures so that anybody can check their validity. In the last decade, a number of DCS schemes have been proposed. However, most of those schemes are either inefficient or insecure. At Asiacrypt 2005, Gentry, Molnar and Ramzan presented a generic transformation to convert any signature scheme into a DCS scheme, and proved the scheme is secure in their security model. Their DCS scheme not only has efficient instantiations but also gets rid of both random oracles and general zero-knowledge proofs. In this paper, we first show that their DCS transformation does not meet the desired security requirements by identifying two security flaws. Then, we point out the reasons that cause those flaws and further propose a secure improvement to fix the flaws. Finally, we present a new generic and efficient DCS scheme without using any public key encryption and prove its security. To the best of our knowledge, this is the first secure DCS scheme that does not require public key encryption.

We introduce a new approach for cryptanalysis of key agreement protocols based on noncommutative groups. Our approach uses functions that estimate the distance of a group element to a given subgroup. We test it against the Shpilrain-Ushakov protocol, which is based on Thompson’s group

F

, and show that it can break about half the keys within a few seconds on a single PC.

The length based attack on Anshel-Anshel-Goldfeld commutator key-exchange protocol [1] was initially proposed by Hughes and Tannenbaum in [9]. Several attempts have been made to implement the attack [6], but none of them had produced results convincing enough to believe that attack works. In this paper we show that accurately designed length based attack can successfully break a random instance of the simultaneous conjugacy search problem for certain parameter values and argue that the public/private information chosen uniformly random leads to weak keys.

We present new and efficient key-recovery chosen-ciphertext attacks on

NTRUencrypt

. Our attacks are somewhat intermediate between chosen-ciphertext attacks on

NTRUencrypt

previously published at CRYPTO ’00 and CRYPTO ’03. Namely, the attacks only work in the presence of decryption failures; we only submit valid ciphertexts to the decryption oracle, where the plaintexts are chosen uniformly at random; and the number of oracle queries is small. Interestingly, our attacks can also be interpreted from a provable security point of view: in practice, if one had access to a

NTRUencrypt

decryption oracle such that the parameter set allows decryption failures, then one could recover the secret key. For instance, for the initial NTRU-1998 parameter sets, the output of the decryption oracle on a single decryption failure is enough to recover the secret key.

At PKC 2003 Paeng, Jung, and Ha proposed a lattice based public key cryptosystem(PJH). It is originated from GGH, and designed as a hybrid of GGH and NTRUEncrypt in order to reduce the key size. They claimed that PJH is secure against all possible attacks, especially against lattice attacks. However, in this paper, we present a key recovery attack, based on lattice theory, against PJH. The running time of our attack is drastically short. For example, we could recover all secret keys within 10 minutes even for the system with

n

 = 1001 on a single PC. Unlike other lattice attacks against NTRUEncrypt and GGH, the attack may be applied well to the system with much larger parameters. We present some clues why we believe so. Based on this belief, we declare that PJH should not be used in practice.

This paper addresses the security of

optimistic fair exchange

in a

multi-user

setting. While the security of public key encryption and public key signature schemes in a single-user setting guarantees the security in a multi-user setting, we show that the situation is different in the optimistic fair exchange. First, we show how to break, in the multi-user setting, an optimistic fair exchange scheme provably secure in the single-user setting. This example separates the security of optimistic fair exchange between the single-user setting and the multi-user setting. We then define the formal security model of optimistic fair exchange in the multi-user setting, which is the first complete security model of optimistic fair exchange in the multi-user setting. We prove the existence of a generic construction meeting our multi-user security based on one-way functions in the random oracle model and trapdoor one-way permutations in the standard model. Finally, we revisit two well-known methodologies of optimistic fair exchange, which are based on the verifiably encrypted signature and the sequential two-party multisignature, respectively. Our result shows that these paradigms remain valid in the multi-user setting.

In this paper, we first demonstrate a gap between the security of verifiably committed signatures in the two-party setting and the security of verifiably committed signatures in the multi-party setting. We then extend the state-of-the-art security model of verifiably committed signatures in the two-party setting to that of multi-party setting. Since there exists trivial setup-driven solutions to multi-party verifiably committed signatures (e.g., two-signature based solutions, we propose solutions to the multi-party stand-alone verifiably committed signatures in the setup-free model, and show that our implementation is provably secure under the joint assumption that the underlying Zhu’s signature scheme is secure against adaptive chosen-message attack, Fujisaki-Okamoto’s commitment scheme is statistically hiding and computationally binding and Paillier’s encryption is semantically secure and one-way as well as the existence of collision-free one-way hash functions.

We prove in a non-black-box way that every bounded list and set commitment scheme is

knowledge-binding

. This is a new and rather strong security condition, which makes the security definitions for time-stamping much more natural compared to the previous definitions, which assume

unpredictability

of adversaries. As a direct consequence, list and set commitment schemes with partial opening property are sufficient for secure time-stamping if the number of elements has an explicit upper bound

N

. On the other hand, white-box reductions are in a sense strictly weaker than black-box reductions. Therefore, we also extend and generalize the previously known reductions. The corresponding new reductions are

$\Theta(\sqrt{N})$

times more efficient, which is important for global-scale time-stamping schemes where

N

is very large.

We describe the first efficient ring signature scheme secure, without random oracles, based on standard assumptions. Our ring signatures are based in bilinear groups. For

l

members of a ring our signatures consist of 2

l

 + 2 group elements and require 2

l

 + 3 pairings to verify. We prove our scheme secure in the strongest security model proposed by Bender, Katz, and Morselli: namely, we show our scheme to be anonymous against full key exposure and unforgeable with respect to insider corruption. A shortcoming of our approach is that all the users’ keys must be defined in the same group.

The ring signature allows a signer to leak secrets anonymously, without the risk of identity escrow. At the same time, the ring signature provides great flexibility: No group manager, no special setup, and the dynamics of group choice. The ring signature is, however, vulnerable to malicious or irresponsible signers in some applications, because of its anonymity. In this paper, we propose a traceable ring signature scheme. A traceable ring scheme is a ring signature except that it can restrict “excessive” anonymity. The traceable ring signature has a

tag

that consists of a list of ring members and an

issue

that refers to, for instance, a social affair or an election. A ring member can make any signed but anonymous opinion regarding the issue, but only once (per tag). If the member submits another signed opinion, possibly pretending to be another person who supports the first opinion, the identity of the member is immediately revealed. If the member submits the same opinion, for instance, voting “yes” regarding the same issue twice, everyone can see that these two are linked. The traceable ring signature can suit to many applications, such as an anonymous voting on a BBS. We formalize the security definitions for this primitive and show an efficient and simple construction in the random oracle model.

We provide a positive result about the Fiat-Shamir (FS) transform in the standard model, showing how to use it to convert three-move identification protocols into

two-tier signature schemes

with a proof of security that makes a standard assumption on the hash function rather than modeling it as a random oracle. The result requires security of the starting protocol against

concurrent

attacks. We can show that numerous protocols have the required properties and so obtain numerous efficient two-tier schemes. Our first application is a two-tier scheme based transform of any unforgeable signature scheme into a strongly unforgeable one. (This extends Boneh, Shen and Waters [8] whose transform only applies to a limited class of schemes.) The second application is new one-time signature schemes that, compared to one-way function based ones of the same computational cost, have smaller key and signature sizes.

At PKC 2006 Crutchfield, Molnar, Turner and Wagner proposed a generic threshold version of on-line/off-line signature schemes based on the “hash-sign-switch” paradigm introduced by Shamir and Tauman. Such a paradigm strongly relies on

chameleon hash functions

which are collision-resistant functions, with a secret trapdoor which actually allows to find arbitrary collisions efficiently. The “hash-sign-switch” paradigm works as follows. In the off-line phase, the signer hashes and signs a random message

s

. When, during the on-line phase, he is given a message

m

to sign the signer uses its knowledge of the hash trapdoor to find a second preimage and “switches”

m

with the random

s

. As shown by Crutchfield

et al.

adapting this paradigm to the threshold setting is not trivial. The solution they propose introduces additional computational assumptions which turn out to be implied by the so-called one-more discrete logarithm assumption.

In this paper we present an alternative solution to the problem. As in the previous result by Crutchfield

et al.

, our construction is

generic

and can be based on any threshold signature scheme, combined with a chameleon hash function based on discrete log. However we show that, by appropriately modifying the chameleon function, our scheme can be proven secure based

only

on the traditional discrete logarithm assumption. While this produces a slight increase in the cost of the off-line phase, the efficiency of the on-line stage (the most important when optimizing signature computation) is unchanged. In other words the

efficiency

is essentially preserved. Finally, we show how to achieve

robustness

for our scheme. Compared to the work by Crutchfield

et al.

, our main solution tolerates at most

${\left\lceil n/4 \right\rceil}$

(arbitrarily) malicious players instead of

$\left\lceil n/3 \right\rceil$

however we stress that we do not rely on random oracles in our proofs. Moreover we briefly present a variant which can achieve robustness in the presence of

$\left\lceil n/3 \right\rceil$

malicious players.

In the CT-track of the 2006 RSA conference, a new multivariate public key cryptosystem, which is called the Medium Field Equation (MFE) multivariate public key cryptosystem, is proposed by Wang, Yang, Hu and Lai. We use the second order linearization equation attack method by Patarin to break MFE. Given a ciphertext, we can derive the plaintext within 2

23

$\mathbb {F}_{2^{16}}$

-multiplications, after performing once for any given public key a computation of complexity less than 2

52

. We also propose a high order linearization equation (HOLE) attack on multivariate public key cryptosystems, which is a further generalization of the (first and second order) linearization equation (LE). This method can be used to attack extensions of the current MFE.

Multivariate Cryptography has been an active line of research for almost twenty years. While most multivariate cryptosystems have been under attack, variations of the basic schemes came up as potential repairs. In this paper, we study the Internal Perturbation variation of HFE recently proposed by Ding and Schmidt. Although several results indicate that HFE is vulnerable against algebraic attacks for moderate size parameters, Ding and Schmidt claim that the cryptosystem with internal perturbation should be immune against them. However in this paper, we apply the recently discovered method of differential analysis to the Internal Perturbation of HFE and we find a subtle property which allows to disclose the kernel of the perturbation. Once this has been achieved, the public key can be inverted by attacking the underlying HFE provided the parameters were taken low enough to make the perturbed scheme of competitive performance.

We propose a new basic trapdoor

$\mathcal{\ell}$

IC (ℓ-Invertible Cycles) of the mixed field type for

$\mathcal{M}$

ultivariate

$\mathcal{Q}$

uadratic public key cryptosystems. This is the first new basic trapdoor since the invention of Unbalanced Oil and Vinegar in 1997.

$\mathcal{\ell}$

IC can be considered an extended form of the well-known Matsumoto-Imai Scheme A (also MIA or

C

 ∗ 

), and share some features of stagewise triangular systems. However

${\mathcal{\ell}}$

IC has very distinctive properties of its own. In practice,

${\mathcal{\ell}}$

IC is much faster than MIA, and can even match the speed of single-field

${\mathcal{MQ}}$

schemes.

We propose a practical key encapsulation mechanism with a simple and intuitive design concept. Security against chosen-ciphertext attacks can be proved in the standard model under a new assumption, the Gap Hashed Diffie-Hellman (GHDH) assumption. The security reduction is tight and simple.

Secure key encapsulation, combined with an appropriately secure symmetric encryption scheme, yields a hybrid public-key encryption scheme which is secure against chosen-ciphertext attacks. The implied encryption scheme is very efficient: compared to the previously most efficient scheme by Kurosawa and Desmedt [Crypto 2004] it has 128 bits shorter ciphertexts, between 25-50% shorter public/secret keys, and it is slightly more efficient in terms of encryption/decryption speed. Furthermore, our scheme enjoys (the option of) public verifiability of the ciphertexts and it inherits all practical advantages of secure hybrid encryption.

Key-insulated cryptography is a crucial technique for protecting private keys. To strengthen the security of key-insulated protocols, Hanaoka, Hanaoka and Imai recently introduced the idea of parallel key-insulated encryption (PKIE) where distinct physically-secure devices (called helpers) are independently used in key updates. Their motivation was to reduce the risk of exposure for helpers by decreasing the frequency of their connections to insecure environments. Hanaoka

et al.

showed that it was non-trivial to achieve a PKIE scheme fitting their model and proposed a construction based on the Boneh-Franklin identity-based encryption (IBE) scheme. The security of their system was only analyzed in the idealized random oracle model. In this paper, we provide a fairly efficient scheme which is secure in the standard model (i.e. without random oracles). To do so, we first show the existence of a relation between PKIE and the notion of aggregate signatures (AS) suggested by Boneh

et al.

We then describe our random oracle-free construction using bilinear maps. Thus, our contributions are both on the concrete side, namely the first realization of parallel key-insulated encryption without the random oracle idealization, and on the conceptual side revealing the relationships between two seemingly unrelated primitives.

We propose multi-bit versions of several single-bit cryptosystems based on lattice problems, the error-free version of the Ajtai-Dwork cryptosystem by Goldreich, Goldwasser, and Halevi [CRYPTO ’97], the Regev cryptosystems [JACM 2004 and STOC 2005], and the Ajtai cryptosystem [STOC 2005]. We develop a universal technique derived from a general structure behind them for constructing their multi-bit versions without increase in the size of ciphertexts. By evaluating the trade-off between the decryption errors and the hardness of underlying lattice problems, it is shown that our multi-bit versions encrypt

O

(log

n

)-bit plaintexts into ciphertexts of the same length as the original ones with reasonable sacrifices of the hardness of the underlying lattice problems. Our technique also reveals an algebraic property, named

pseudohomomorphism

, of the lattice-based cryptosystems.

Yao’s classical

millionaires’ problem

is about securely determining whether

x

 > 

y

, given two input values

x

,

y

, which are held as private inputs by two parties, respectively. The output

x

 > 

y

becomes known to both parties.

In this paper, we consider a variant of Yao’s problem in which the inputs

x

,

y

as well as the output bit

x

 > 

y

are encrypted. Referring to the framework of secure

n

-party computation based on threshold homomorphic cryptosystems as put forth by Cramer, Damgård, and Nielsen at Eurocrypt 2001, we develop solutions for integer comparison, which take as input two lists of encrypted bits representing

x

and

y

, respectively, and produce an encrypted bit indicating whether

x

 > 

y

as output. Secure integer comparison is an important building block for applications such as secure auctions.

In this paper, our focus is on the two-party case, although most of our results extend to the multi-party case. We propose new logarithmic-round and constant-round protocols for this setting, which achieve simultaneously very low communication and computational complexities. We analyze the protocols in detail and show that our solutions compare favorably to other known solutions.

Damgård

et al.

[11] showed a novel technique to convert a polynomial sharing of secret

a

into the sharings of the bits of

a

in constant rounds, which is called the bit-decomposition protocol. The bit-decomposition protocol is a very powerful tool because it enables bit-oriented operations even if shared secrets are given as elements in the field. However, the bit-decomposition protocol is relatively expensive.

In this paper, we present a simplified bit-decomposition protocol by analyzing the original protocol. Moreover, we construct more efficient protocols for a comparison, interval test and equality test of shared secrets without relying on the bit-decomposition protocol though it seems essential to such bit-oriented operations. The key idea is that we do computation on secret

a

with

c

and

r

where

c

 = 

a

 + 

r

,

c

is a revealed value, and

r

is a random bitwise-shared secret. The outputs of these protocols are also shared without being revealed.

The realized protocols as well as the original protocol are constant-round and run with less communication rounds and less data communication than those of [11]. For example, the round complexities are reduced by a factor of approximately 3 to 10.

We present the first identity-based traitor tracing scheme. The scheme is shown to be secure in the standard model, assuming the bilinear decision Diffie-Hellman (DBDH) is hard in the asymmetric bilinear pairing setting, and that the DDH assumption holds in the group defining the first coordinate of the asymmetric pairing. Our traitor tracing system allows adaptive pirates to be traced. The scheme makes use of a two level identity-based encryption scheme with wildcards (WIBE) based on Waters’ identity-based encryption scheme.

A shuffle is a permutation and rerandomization of a set of ciphertexts. Among other things, it can be used to construct mix-nets that are used in anonymization protocols and voting schemes. While shuffling is easy, it is hard for an outsider to verify that a shuffle has been performed correctly. We suggest two efficient honest verifier zero-knowledge (HVZK) arguments for correctness of a shuffle. Our goal is to minimize round-complexity and at the same time have low communicational and computational complexity.

The two schemes we suggest are both 3-move HVZK arguments for correctness of a shuffle. We first suggest a HVZK argument based on homomorphic integer commitments, and improve both on round complexity, communication complexity and computational complexity in comparison with state of the art. The second HVZK argument is based on homomorphic commitments over finite fields. Here we improve on the computational complexity and communication complexity when shuffling large ciphertexts.

In this paper we survey the notion of Single-Database Private Information Retrieval (PIR). The first Single-Database PIR was constructed in 1997 by Kushilevitz and Ostrovsky and since then Single-Database PIR has emerged as an important cryptographic primitive. For example, Single-Database PIR turned out to be intimately connected to collision-resistant hash functions, oblivious transfer and public-key encryptions with additional properties. In this survey, we give an overview of many of the constructions for Single-Database PIR (including an abstract construction based upon homomorphic encryption) and describe some of the connections of PIR to other primitives.

For RSA, May showed a deterministic polynomial time equivalence of computing

d

to factoring

N

( = 

pq

). On the other hand, Takagi showed a variant of RSA such that the decryption algorithm is faster than the standard RSA, where

N

 = 

p

r

q

while

$ed=1 \bmod (p-1)(q-1)$

. In this paper, we show that a deterministic polynomial time equivalence also holds in this variant. The coefficient matrix

T

to which LLL algorithm is applied is no longer lower triangular, and hence we develop a new technique to overcome this problem.

A family of pseudorandom generators based on the decisional Diffie-Hellman assumption is proposed. The new construction is a modified and generalized version of the Dual Elliptic Curve generator proposed by Barker and Kelsey. Although the original Dual Elliptic Curve generator is shown to be insecure, the modified version is provably secure and very efficient in comparison with the other pseudorandom generators based on discrete log assumptions.

Our generator can be based on any group of prime order provided that an additional requirement is met (i.e., there exists an efficiently computable function that in some sense enumerates the elements of the group). Two specific instances are presented. The techniques used to design the instances, for example, the new probabilistic randomness extractor are of independent interest for other applications.

We propose an efficient batch verification of multiple signatures generated by

different signers

as well as a single signer. We first introduce a method to generate width-

w

Non-Adjacent Forms (

w

-NAFs) uniformly. We then propose a batch verification algorithm of exponentiations using

w

-NAF exponents, and apply this to batch verification for the modified DSA and ECDSA signatures. The performance analysis shows that our proposed method is asymptotically seven and four times as fast as individual verification in case of a single signer and multiple signers, respectively. Further, the proposed algorithm can be generalized into

τ

-adic

w

-NAFs over Koblitz curves and requires asymptotically only six elliptic curve additions per each signature for batch verification of the modified ECDSA signatures by a single singer. Our result is the first one to efficiently verify multiple signatures by multiple signers that can introduce much wider applications.

In this paper we take a closer look at the security and efficiency of public-key encryption and signature schemes in public-key infrastructures (PKI). Unlike traditional analyses which assume an “ideal” implementation of the PKI, we focus on the security of joint constructions that consider the certification authority (CA) and the users, and include a key-registration protocol and the algorithms of an encryption or a signature scheme. We therefore consider significantly broader adversarial capabilities. Our analysis clarifies and validates several crucial aspects such as the amount of trust put in the CA, the necessity and specifics of proofs of possession of secret keys, and the security of the basic primitives in this more complex setting. We also provide constructions for encryption and signature schemes that provably satisfy our strong security definitions and are more efficient than the corresponding traditional constructions that assume a digital certificate issued by the CA must be verified whenever a public key is used. Our results address some important aspects for the design and standardization of PKIs, as targeted for example in the standards project ANSI X9.109.

Certificateless Public Key Cryptography (CL-PKC) has very appealing features, namely it does not require any public key certification (cf. traditional Public Key Cryptography) nor having key escrow problem (cf. Identity-Based Cryptography). However, it does suffer to the Denial-of-Decryption (DoD) Attack called by Liu and Au [1], as its nature is similar to the well known Denial-of-Service (DoS) Attack. Based on CL-PKC, they introduced a new paradigm called Self-Generated-Certificate Public Key Cryptography (SGC-PKC) that captured the DoD Attack and proposed a first scheme derived from a novel application of Water’s Identity-Based Encryption scheme. In this paper, we propose a new SGC-PKE scheme that does not depend on the bilinear pairings, which make it be more efficient and more short public keys than Liu and Au’s scheme. More importantly, our scheme reaches Girault’s trusted level 3 (cf. Girault’s trusted level 2 of Liu and Au’s scheme), the same level as is enjoyed in a traditional PKI.