共查询到20条相似文献,搜索用时 62 毫秒
1.
Victor Shoup 《Journal of Cryptology》2008,15(4):223-249
The OAEP encryption scheme was introduced by Bellare and Rogaway at Eurocrypt '94. It converts any trapdoor permutation scheme
into a public key encryption scheme. OAEP is widely believed to provide resistance against adaptive chosen ciphertext attack.
The main justification for this belief is a supposed proof of security in the random oracle model, assuming the underlying
trapdoor permutation scheme is one way.
This paper shows conclusively that this justification is invalid. First, it observes that there appears to be a non-trivial
gap in the OAEP security proof. Second, it proves that this gap cannot be filled, in the sense that there can be no standard
``black box' security reduction for OAEP. This is done by proving that there exists an oracle relative to which the general
OAEP scheme is insecure.
The paper also presents a new scheme OAEP+ , along with a complete proof of security in the random oracle model. OAEP+ is essentially just as efficient as OAEP.
It should be stressed that these results do not imply that a particular instantiation of OAEP, such as RSA-OAEP, is insecure.
They simply undermine the original justification for its security. In fact, it turns out—essentially by accident, rather than
by design—that RSA-OAEP is secure in the random oracle model; however, this fact relies on special algebraic properties of
the RSA function, and not on the security of the general OAEP scheme. 相似文献
2.
David Mandell Freeman Oded Goldreich Eike Kiltz Alon Rosen Gil Segev 《Journal of Cryptology》2013,26(1):39-74
We propose new and improved instantiations of lossy trapdoor functions (Peikert and Waters in STOC’08, pp. 187–196, 2008), and correlation-secure trapdoor functions (Rosen and Segev in TCC’09, LNCS, vol. 5444, pp. 419–436, 2009). Our constructions widen the set of number-theoretic assumptions upon which these primitives can be based, and are summarized as follows:
- Lossy trapdoor functions based on the quadratic residuosity assumption. Our construction relies on modular squaring, and whereas previous such constructions were based on seemingly stronger assumptions, we present the first construction that is based solely on the quadratic residuosity assumption. We also present a generalization to higher-order power residues.
- Lossy trapdoor functions based on the composite residuosity assumption. Our construction guarantees essentially any required amount of lossiness, where at the same time the functions are more efficient than the matrix-based approach of Peikert and Waters.
- Lossy trapdoor functions based on the d-Linear assumption. Our construction both simplifies the DDH-based construction of Peikert and Waters and admits a generalization to the whole family of d-Linear assumptions without any loss of efficiency.
- Correlation-secure trapdoor functions related to the hardness of syndrome decoding.
3.
A.A. Chari 《Microelectronics Reliability》1994,34(6)
This paper considers the problem of optimal redundancy of K-out-of-n:G systems. The model highlights the occurrence of two types of common-course failures, namely, lethal and non-lethal CCFs, in addition to random failures. The optimum number of redundant components (n*) in K-out-of-n: G systems are derived with two types of CCF. The optimization is approached by a minimization of the mean cost rate (C1(n*)) which is established to be finite and unique. Numerical evidence indicates the reduction of optimal redundancy with two types of CCF when compared to random failures alone. 相似文献
4.
On the Security of a Practical Identification Scheme 总被引:3,自引:0,他引:3
Victor Shoup 《Journal of Cryptology》1999,12(4):247-260
We analyze the security of an interactive identification scheme. The scheme is the obvious extension of the original square
root scheme of Goldwasser, Micali, and Rackoff to 2
m
th roots. This scheme is quite practical, especially in terms of storage and communication complexity. Although this scheme
is certainly not new, its security was apparently not fully understood. We prove that this scheme is secure if factoring integers
is hard, even against active attacks where the adversary is first allowed to pose as a verifier before attempting impersonation.
Received 29 July 1996 and revised 30 June 1998 相似文献
5.
An Efficient Noninteractive Zero-Knowledge Proof System for NP with General Assumptions 总被引:1,自引:0,他引:1
We consider noninteractive zero-knowledge proofs in the shared random string model proposed by Blum et al. [5]. Until recently
there was a sizable polynomial gap between the most efficient noninteractive proofs for NP based on general complexity assumptions
[11] versus those based on specific algebraic assumptions [7]. Recently, this gap was reduced to a polylogarithmic factor
[17]; we further reduce the gap to a constant factor. Our proof system relies on the existence of one-way permutations (or
trapdoor permutations for bounded provers).
Our protocol is stated in the hidden bit model introduced by Feige et al. [11]. We show how to prove that an n -gate circuit is satisfiable, with error probability 1/n
O(1)
, using only O(n lg n) random committed bits. For this error probability, this result matches to within a constant factor the number of committed
bits required by the most efficient known interactive proof systems.
Received 20 November 1995 and revised 7 October 1996 相似文献
6.
7.
We present a polynomial-time algorithm that provably recovers the signer's secret DSA key when a few consecutive bits of
the random nonces k (used at each signature generation) are known for a number of DSA signatures at most linear in log q (q denoting as usual the small prime of DSA), under a reasonable assumption on the hash function used in DSA. For most significant
or least significant bits, the number of required bits is about log
1/2
q , but can be decreased to log log q with a running time q
O(1/log log
q
) subexponential in log q , and even further to two in polynomial time if one assumes access to ideal lattice basis reduction, namely an oracle for
the lattice closest vector problem for the infinity norm. For arbitrary consecutive bits, the attack requires twice as many
bits. All previously known results were only heuristic, including those of Howgrave-Graham and Smart who recently introduced
that topic. Our attack is based on a connection with the hidden number problem (HNP) introduced at Crypto '96 by Boneh and Venkatesan in order to study the bit-security of the Diffie—Hellman key exchange.
The HNP consists, given a prime number q , of recovering a number α ∈ F
q
such that for many known random t ∈ F
q
a certain approximation of t α is known. To handle the DSA case, we extend Boneh and Venkatesan's results on the HNP to the case where t has not necessarily perfectly uniform distribution, and establish uniformity statements on the DSA signatures, using exponential
sum techniques. The efficiency of our attack has been validated experimentally, and illustrates once again the fact that one
should be very cautious with the pseudo-random generation of the nonce within DSA. 相似文献
8.
We present a new cryptosystem based on ideal arithmetic in quadratic orders. The method of our trapdoor is different from
the Diffie—Hellman key distribution scheme or the RSA cryptosystem. The plaintext m is encrypted by mp
r
, where p is a fixed element and r is a random integer, so our proposed cryptosystem is a probabilistic encryption scheme and has the homomorphy property.
The most prominent property of our cryptosystem is the cost of the decryption, which is of quadratic bit complexity in the
length of the public key. Our implementation shows that it is comparably as fast as the encryption time of the RSA cryptosystem
with e=2
16
+1 . The security of our cryptosystem is closely related to factoring the discriminant of a quadratic order. When we choose
appropriate sizes of the parameters, the currently known fast algorithms, for example, the elliptic curve method, the number
field sieve, the Hafner—McCurley algorithm, are not applicable. We also discuss that the chosen ciphertext attack is not applicable
to our cryptosystem.
Received 29 June 1998 and revised 15 November 1998 相似文献
9.
A protocol for secure computation is fair if either both parties learn the output or else neither party does. A seminal result of Cleve (STOC ’86) is that, in general,
complete fairness is impossible to achieve in two-party computation. In light of this, various techniques for obtaining partial fairness have been suggested in the literature. We propose a definition of partial fairness within the standard real-/ideal-world
paradigm. We also show broad feasibility results with respect to our definition: partial fairness is possible for any (randomized)
functionality f:X×Y→Z
1×Z
2 at least one of whose domains or ranges is polynomial in size. Our protocols are always private, and when one of the domains
has polynomial size our protocols also achieve the usual notion of security with abort. We work in the standard communication
model (in particular, we do not assume simultaneous channels) and, in contrast to some prior work, rely only on standard cryptographic
assumptions (e.g., enhanced trapdoor permutations). 相似文献
10.
Deterministic public-key encryption, introduced by Bellare, Boldyreva, and O’Neill (CRYPTO ’07), provides an alternative to randomized public-key encryption in various scenarios where the latter exhibits inherent drawbacks. A deterministic encryption algorithm, however, cannot satisfy any meaningful notion of security when the plaintext is distributed over a small set. Bellare et al. addressed this difficulty by requiring semantic security to hold only when the plaintext has high min-entropy from the adversary’s point of view. In many applications, however, an adversary may obtain auxiliary information that is related to the plaintext. Specifically, when deterministic encryption is used as a building block of a larger system, it is rather likely that plaintexts do not have high min-entropy from the adversary’s point of view. In such cases, the framework of Bellare et al. might fall short from providing robust security guarantees. We formalize a framework for studying the security of deterministic public-key encryption schemes with respect to auxiliary inputs. Given the trivial requirement that the plaintext should not be efficiently recoverable from the auxiliary input, we focus on hard-to-invert auxiliary inputs. Within this framework, we propose two schemes: the first is based on the d-linear assumption for any d≥1 (including, in particular, the decisional Diffie–Hellman assumption), and the second is based on a rather general class of subgroup indistinguishability assumptions (including, in particular, the quadratic residuosity assumption and Paillier’s composite residuosity assumption). Our schemes are secure with respect to any auxiliary input that is subexponentially hard to invert (assuming the standard hardness of the underlying computational assumptions). In addition, our first scheme is secure even in the multi-user setting where related plaintexts may be encrypted under multiple public keys. Constructing a scheme that is secure in the multi-user setting (even without considering auxiliary inputs) was identified by Bellare et al. as an important open problem. 相似文献
11.
Stronger Security Proofs for RSA and Rabin Bits 总被引:1,自引:0,他引:1
The RSA and Rabin encryption functions are respectively defined as E
N
(x) = x
e
mod N and E
N
(x) = x
2
mod N , where N is a product of two large random primes p , q and e is relatively prime to φ (N) . We present a simpler and tighter proof of the result of Alexi et al. [ACGS] that the following problems are equivalent
by probabilistic polynomial time reductions: (1) given E
N
(x) find x; (2) given E
N
(x) predict the least-significant bit of x with success probability 1/2 + 1/poly(n) , where N has n bits. The new proof consists of a more efficient algorithm for inverting the RSA/ Rabin function with the help of an oracle that predicts the least-significant bit of x . It yields provable security guarantees for RSA message bits and for the RSA random number generator for modules N of practical size.
Received 12 July 1996 and revised 8 January 1999 相似文献
12.
13.
RSA Full Domain Hash (RSA-FDH) is a digital signature scheme, secure against chosen message attacks in the random oracle model. The best known security reduction from the RSA assumption is non-tight, i.e., it loses a factor of \(q_s\), where \(q_s\) is the number of signature queries made by the adversary. It was furthermore proven by Coron (Advances in cryptology—EUROCRYPT 2002, Lecture notes in computer science, vol 2332. Springer, Berlin, pp 272–287, 2002) that a security loss of \(q_s\) is optimal and cannot possibly be improved. In this work, we uncover a subtle flaw in Coron’s impossibility result. Concretely, we show that it only holds if the underlying trapdoor permutation is certified. Since it is well known that the RSA trapdoor permutation is (for all practical parameters) not certified, this renders Coron’s impossibility result moot for RSA-FDH. Motivated by this, we revisit the question whether there is a tight security proof for RSA-FDH. Concretely, we give a new tight security reduction from a stronger assumption, the Phi-Hiding assumption introduced by Cachin et al. (Advances in Cryptology—EUROCRYPT’99. Lecture notes in computer science, vol 1592. Springer, Berlin, pp 402–414, 1999). This justifies the choice of smaller parameters in RSA-FDH, as it is commonly used in practice. All of our results (positive and negative) extend to the probabilistic signature scheme PSS (with message recovery). 相似文献
14.
Morteza Esmaeili Mokhtar Salahian Mohammad-Hesam Tadayon 《AEUE-International Journal of Electronics and Communications》2011,65(12):1069-1072
Construction of q-ary quasi-cyclic low-density parity-check (QC-LDPC) codes based on two-dimensional multiplicative arrays over Zq−1, q = 2m, is studied. In particular, two-dimensional arrays formed by the set of quadratic-residue numbers modulo prime numbers less than q are considered. 相似文献
15.
Eiichiro Fujisaki Tatsuaki Okamoto David Pointcheval Jacques Stern 《Journal of Cryptology》2004,17(2):81-104
Recently Victor Shoup noted that there is a gap in the widely believed security
result of OAEP against adaptive chosen-ciphertext attacks. Moreover, he showed
that, presumably, OAEP cannot be proven secure from the one-wayness of the underlying
trapdoor permutation. This paper establishes another result on the security of OAEP.
It proves that OAEP offers semantic security against adaptive chosen-ciphertext attacks,
in the random oracle model, under the partial-domain one-wayness of the underlying
permutation. Therefore, this uses a formally stronger assumption. Nevertheless, since
partial-domain one-wayness of the RSA function is equivalent to its (full-domain) onewayness,
it follows that the security of RSA-OAEP can actually be proven under the
sole RSA assumption, although the reduction is not tight. 相似文献
16.
Goldwasser and Micali (J Comput Syst Sci 28(2):270–299, 1984) highlighted the importance of randomizing the plaintext for public-key encryption and introduced the notion of semantic security. They also realized a cryptosystem meeting this security notion under the standard complexity assumption of deciding quadratic residuosity modulo a composite number. The Goldwasser–Micali cryptosystem is simple and elegant but is quite wasteful in bandwidth when encrypting large messages. A number of works followed to address this issue and proposed various modifications. This paper revisits the original Goldwasser–Micali cryptosystem using \(2^k\)-th power residue symbols. The so-obtained cryptosystems appear as a very natural generalization for \(k \ge 2\) (the case \(k=1\) corresponds exactly to the Goldwasser–Micali cryptosystem). Advantageously, they are efficient in both bandwidth and speed; in particular, they allow for fast decryption. Further, the cryptosystems described in this paper inherit the useful features of the original cryptosystem (like its homomorphic property) and are shown to be secure under a similar complexity assumption. As a prominent application, this paper describes an efficient lossy trapdoor function-based thereon. 相似文献
17.
现有的广义指定验证者签名方案的安全性大都是在随机预言机模型下证明的,但是在该模型下的可证安全并不意味着在现实中是安全的.基于Zhang等人提出的无随机预言机模型下的短签名方案,提出了一个在标准模型下可证安全的广义指定验证者签名方案,其强不可伪造性基于k+1平方根假设和指数知识假设,证明了提出方案在选择公钥和选择消息攻击下是无条件不可传递的.方案的签名长度为1366 bits,比现有方案的签名长度要短. 相似文献
18.
Brassard and Crépeau [BCr] introduced a simple technique for producing zero-knowledge proof systems based on blobs. As is to be expected, their implementation rests on an unproven cryptographic assumption, specifically, that it is easy to generate numbers that are difficult to factor. In this paper we present an implementation of blobs based on a different cryptographic assumption, specifically, that it is easy to generate primes p over which it is difficult to compute discrete logarithms. If, in addition, we can produce a generator for Z
p
*
, this implementation then has the advantage that it leads to proof systems which are perfect zeroknowledge, rather than only almost perfect zero-knowledge.The relationship between factoring and finding discrete logarithms is not well understood, although Bach [Bac1] is an important contribution. Given our current state of number theoretic knowlege, there is no reason to prefer the cryptographic assumption required by one of these implementations over that required by the other. In any event, we introduce the notion of a product blob, whose favorable properties depend only on at least one of these assumptions holding.The first author was supported in part by NSA Grant MDA 904-84-H-00171. The second author was supported in part by NSF Grant DCR-8602562. 相似文献
19.
An almost k -wise independent sample space is a small subset of m bit sequences in which any k bits are ``almost independent'. We show that this idea has close relationships with useful cryptologic notions such as
multiple authentication codes (multiple A -codes), almost strongly universal hash families, almost k -resilient functions, almost correlation-immune functions, indistinguishable random variables and k -wise decorrelation bias of block ciphers.
We use almost k -wise independent sample spaces to construct new efficient multiple A -codes such that the number of key bits grows linearly as a function of k (where k is the number of messages to be authenticated with a single key). This improves on the construction of Atici and Stinson
\cite{AS96}, in which the number of key bits is Ω (k
2
) .
We introduce the concepts of ɛ -almost k -resilient functions and almost correlation-immune functions, and give a construction for almost k -resilient functions that has parameters superior to k -resilient functions. We also point out the connection between almost k -wise independent sample spaces and pseudorandom functions that can be distinguished from truly random functions, by a distinguisher
limited to k oracle queries, with only a small probability. Vaudenay \cite{Vaudenay99} has shown that such functions can be used to construct
block ciphers with a small decorrelation bias.
Finally, new bounds (necessary conditions) are derived for almost k -wise independent sample spaces, multiple A -codes and balanced ɛ -almost k -resilient functions.
Received September 1999 and revised January 2001 Online publication 29 August 2001 相似文献
20.
Bit commitment using pseudorandomness 总被引:4,自引:0,他引:4
Moni Naor 《Journal of Cryptology》1991,4(2):151-158
We show how a pseudorandom generator can provide a bit-commitment protocol. We also analyze the number of bits communicated when parties commit to many bits simultaneously, and show that the assumption of the existence of pseudorandom generators suffices to assure amortized O(1) bits of communication per bit commitment.Part of this work was done while the author was at the University of California at Berkeley. This research was supported by NSF Grant CCR 88-13632. 相似文献