#### DMCA

## THE RANDOM ORACLE MODEL: A TWENTY-YEAR RETROSPECTIVE

Citations: | 2 - 0 self |

### Citations

3322 | Handbook of applied cryptography
- Menezes, Oorschot, et al.
- 1996
(Show Context)
Citation Context ... is unshaken.”1 1It has long been known that one has to use the random oracle assumption carefully if the protocol uses an iterated hash function, because of the extension attack (see example 9.64 in =-=[56]-=-). That is, the random oracle assumption essentially says that a deterministic function H(K,M) behaves like a random function to someone who does not know the key K. However, if a message is obtained ... |

1631 | Random oracles are practical: A paradigm for designing efficient protocols
- Bellare, Rogaway
- 1993
(Show Context)
Citation Context ...n for these two schemes. If one shuns these models, then no provable security result is known for them. 1. Introduction The random oracle model is a powerful tool introduced by Bellare and Rogaway in =-=[8]-=- in order to make it possible to give rigorous “proofs of security” for certain basic cryptographic protocols, such as Full Domain Hash signatures [8] and OAEP encryption [9]. Typically it is a hash f... |

753 | Short signature from the Weil pairing
- Boneh, Lynn, et al.
- 2001
(Show Context)
Citation Context ...signing protocols so as not to need random oracles in a proof—doing so might open up new vulnerabilities to attacks that are outside the security model used in the proof. 4. Boneh-Boyen Signatures In =-=[16]-=- Boneh, Lynn, and Shacham constructed pairing-based short signatures that they showed to be secure in the random oracle model assuming intractability of the Computational Diffie–Hellman (CDH) problem.... |

735 |
Efficient signature generation by smart cards
- Schnorr
- 1991
(Show Context)
Citation Context ...to the use of the random oracle model, which leads to more substantive results. 7.3. A further modification of ECDSA. 9 In §5 of [47] we discussed security reductions for the Schnorr signature scheme =-=[67]-=- and compared that scheme to DSA. Informally speaking, the security of both schemes is based on intractability of the discrete log problem in a finite field. However, the security reductions for Schno... |

405 | On the importance of checking cryptographic protocols for faults
- Boneh, DeMillo, et al.
- 1997
(Show Context)
Citation Context ...antly lower security than the ROM-protocol of Boneh–Lynn– Shacham that it replaced. The price of avoiding random oracles was quite steep. 5. Fault Attacks on Pairing-Based Protocols In a fault attack =-=[15]-=- the adversary causes an error in a cryptographic device that’s performing an operation with a secret key. The adversary uses the incorrect output, perhaps with other available data, to obtain some in... |

393 | Short Signatures Without Random Oracles
- Boneh, Boyen
- 2004
(Show Context)
Citation Context ...hrase somewhere in the paper, as of June 6, 2013.) Our purpose is not to comment on 286 papers. Rather, we examine three of the most important efforts to construct replacements for ROM-protocols (see =-=[38, 14, 45]-=-) and find that all of the non-ROM constructions have potential security weaknesses that were not present in the original ROM-versions. Following [26], we also describe a remarkable fact about pairing... |

375 | Security arguments for digital signatures and blind signatures, Journal of Cryptology 13 (3) (2000) 361–396. Please cite this article in press as - Pointcheval, Stern |

348 | On the (im)possibility of obfuscating programs
- Barak, Impagliazzo, et al.
- 2001
(Show Context)
Citation Context ...ough the entire program is publicly available for inspection. More precisely, the obfuscation process is assumed to have the indistinguishability property, which is weaker than the black-box property =-=[2]-=-: Given two programs of the same size that produce the same outputs, suppose that one of them was the input to the obfuscation process; in other words, it was used to produce the obfuscated program. T... |

260 | Security proofs for signature schemes
- Pointcheval, Stern
- 1996
(Show Context)
Citation Context ...lly speaking, the security of both schemes is based on intractability of the discrete log problem in a finite field. However, the security reductions for Schnorr signatures in the random oracle model =-=[63, 64]-=- were lost in going from Schnorr to DSA. We commented that one could retain some reductionist security in DSA if instead of simply hashing the message M in the signing equation one hashes both M and a... |

256 | Foundations of Cryptography
- Goldreich
(Show Context)
Citation Context ... oracle assumption does not apply. It is because of this extension attack that prefix-MAC, THE RANDOM ORACLE MODEL: A TWENTY-YEAR RETROSPECTIVE 5 In response to [47], Goldreich wrote an opinion piece =-=[41]-=- in which he accused us of post-modernism and had especially harsh words for our defense of the random oracle model, which he likened to worship of the Bronze Serpent: Indeed, what happened with the R... |

145 | Secure Hash-and-Sign Signatures Without the Random Oracle
- Gennaro, Halevi, et al.
- 1999
(Show Context)
Citation Context ...hrase somewhere in the paper, as of June 6, 2013.) Our purpose is not to comment on 286 papers. Rather, we examine three of the most important efforts to construct replacements for ROM-protocols (see =-=[38, 14, 45]-=-) and find that all of the non-ROM constructions have potential security weaknesses that were not present in the original ROM-versions. Following [26], we also describe a remarkable fact about pairing... |

140 | Practical identity-based encryption without random oracles
- Gentry
(Show Context)
Citation Context ...es themselves rather than hashes of the pairing values. The authors of [26] found three protocols that succumb to these attacks—a public-key encryption scheme [18], an identitybased encryption scheme =-=[39]-=-, and an oblivious transfer protocol [24]. All three of those protocols had been designed specifically so as to have a security reduction that did not require the random oracle assumption. In all case... |

126 |
Log depth circuits for division and related problems
- Beame, Cook, et al.
- 1986
(Show Context)
Citation Context ...obfuscation would have a multilinearity level whose bitlength is also in the thousands. THE RANDOM ORACLE MODEL: A TWENTY-YEAR RETROSPECTIVE 15 whose circuit has greater size but much lower depth. In =-=[4]-=- Beame, Cooke, and Hoover constructed an algorithm with logarithmic-depth circuit for the iterated product problem. If m denotes the bitlength of the integers being multiplied, their circuit has depth... |

95 | An uninstantiable random-oracle-model scheme for a hybrid-encryption problem
- Bellare, Boldyreva, et al.
(Show Context)
Citation Context ...nesses of the proofs of security of well-known protocols. In addition to the construction in [25], we looked at the two other most frequently cited examples of failure of the random oracle model (see =-=[6, 42]-=-). In all three cases we found that the constructions relied in essential ways on violations of basic principles of sound cryptographic practice. For instance, a certain message triggers the release o... |

93 | Separating random oracle proofs from complexity theoretic proofs: The noncommitting encryption case
- Nielsen
(Show Context)
Citation Context ...me so that, when presented with certain pairs (xi, H(xi)), it outputs the secret key. In [47] we went further, arguing that the inability of some of the top researchers in cryptography—the authors of =-=[25, 6, 42, 58]-=-—to come up with a convincing example of any real danger in using ROM-protocols should in and of itself serve as an argument in their favor: ...if one of the world’s leading specialists in provable se... |

83 | Direct Chosen Ciphertext Security from Identity-Based Techniques
- Boyen, Mei, et al.
- 2005
(Show Context)
Citation Context ...her secret. And it must transmit the values themselves rather than hashes of the pairing values. The authors of [26] found three protocols that succumb to these attacks—a public-key encryption scheme =-=[18]-=-, an identitybased encryption scheme [39], and an oblivious transfer protocol [24]. All three of those protocols had been designed specifically so as to have a security reduction that did not require ... |

73 | Another look at “provable security
- Koblitz, Menezes
(Show Context)
Citation Context ...is informal argument might be convincing, but it is not a formal proof. A formal proof constructs an actual reduction from the problem of inverting the one-way function to the forger’s task. In §3 of =-=[47]-=- we discuss the formal proof, especially the tightness issue that arises in the reduction. Could this argument be replaced by one that does not use random oracles? In [34] Dodis, Oliveira, and Pietrza... |

71 | Security analysis of the strong diffie-hellman problem
- Cheon
- 2006
(Show Context)
Citation Context ...p model. At first it seemed that the factor √ m was not a cause for concern, and that the true difficulty of the m-SDH problem was probably √ q as in the case of CDH. However, at Eurocrypt 2006 Cheon =-=[28]-=-, using the same attack that had been described earlier in a different setting by Brown and Gallant [22, 37], showed that m-SDH can be solved—and in fact the discrete logarithm x can be found—in √ q/m... |

63 | Unique Signatures and Verifiable Random Functions from the DH-DDH Separation.
- Lysyanskaya
- 2002
(Show Context)
Citation Context ...there is a (publicly known) encoding that maps the message space2 to a code that has a certain required minimum Hamming distance between the encodings of distinct messages (see §3.4 of [36] and §5 of =-=[54]-=-); this is needed for the proof of adaptive security in [45]. We let M ′ denote the encoding of M . Alice randomly chooses a constant v prime to N and a sequence of exponents ai,b, b = 0, 1, i = 1, . ... |

62 | Unknown key-share attacks on the station-to-station (STS) protocol
- Blake-Wilson, Menezes
- 1999
(Show Context)
Citation Context ...sser–Micali–Rivest [43] security model for signatures, it easily succumbs to a certain type of attack that is outside that model. The Duplicate Signature Key Selection (DSKS) attack. In a DSKS attack =-=[13]-=- we suppose that Alice, whose public key is accompanied by a certificate, has sent Bob her signature s on a message M . A successful DSKS attacker Chris is able to produce a certified public key of hi... |

56 | Practical multilinear maps over the integers
- Coron, Lepoint, et al.
(Show Context)
Citation Context ...task of the certification authority, and the running time for verification are all prohibitively large. The most efficient way known to compute obfuscations uses the method of multilinear pairings in =-=[30]-=-. The complexity of the method grows rapidly with the “level” of the pairing. The construction uses a modulus x0, which is a product of secret primes. In §3.1.3 of [1] it is shown that the bitlength o... |

53 | On the (In)security of the Fiat-Shamir Paradigm
- Goldwasser, Tauman
(Show Context)
Citation Context ...nesses of the proofs of security of well-known protocols. In addition to the construction in [25], we looked at the two other most frequently cited examples of failure of the random oracle model (see =-=[6, 42]-=-). In all three cases we found that the constructions relied in essential ways on violations of basic principles of sound cryptographic practice. For instance, a certain message triggers the release o... |

47 | The insecurity of the elliptic curve digital signature algorithm with partially known nonces,” Des.
- Nguyen, Shparlinski
- 2003
(Show Context)
Citation Context ...eneration, but also needs a new random value k for each message that is signed. The security of ECDSA is particularly sensitive to poor implementation of pseudorandom generation of k. For example, in =-=[59]-=- it was shown that if just three bits of k are known for several hundred signatures, then it is possible to recover the static secret key K. Starting with Barwood [3] and Wigley [70], a number of peop... |

43 | High-speed high-security signatures
- Bernstein, Duif, et al.
(Show Context)
Citation Context ...70], a number of people (see [65]) have proposed replacing pseudorandom generation of k by a deterministic value k = H ′(K,M) obtained by hashing the message and the static secret key. See also §2 of =-=[11]-=- for a discussion of the rationale for this modification of ECDSA. Remark 5. An advantage of stipulating k = H ′(K,M) rather than random k is that it forces the user to change k for each message. In 2... |

39 | Optimal asymmetric encryption—how to encrypt with RSA - BELLARE, ROGAWAY - 1995 |

38 |
A Paradoxical Solution to the Signature Problem
- Goldwasser, Micali, et al.
- 1984
(Show Context)
Citation Context ...e s is th̃ mod N . Bob verifies Alice’s signature by computing h and then sh mod N , which should equal t. Unfortunately, while the GHR scheme is provably secure in the usual Goldwasser–Micali–Rivest =-=[43]-=- security model for signatures, it easily succumbs to a certain type of attack that is outside that model. The Duplicate Signature Key Selection (DSKS) attack. In a DSKS attack [13] we suppose that Al... |

35 | Simulatable adaptive oblivious transfer,”
- Camenisch, Neven, et al.
- 2007
(Show Context)
Citation Context ...airing values. The authors of [26] found three protocols that succumb to these attacks—a public-key encryption scheme [18], an identitybased encryption scheme [39], and an oblivious transfer protocol =-=[24]-=-. All three of those protocols had been designed specifically so as to have a security reduction that did not require the random oracle assumption. In all cases a crucial feature that made it possible... |

33 |
Private communication,
- Bernstein
- 2004
(Show Context)
Citation Context ...rnstein et al. [12] presented several techniques for evaluating obfuscated programs, which yield a more than 50-fold speedup in the evaluation of the obfuscation circuit for the 16-bit point function =-=[10]-=-. In practice one would need a far more elaborate function to evaluate H(·) with a 3072-bit modulus N , for instance; and one would want at least a 128-bit security level. Remark 4. In November 2014, ... |

31 | Cryptanalysis of the multilinear map over the integers. Cryptology ePrint Archive, Report 2014/906, 2014. http: //eprint.iacr.org
- Cheon, Han, et al.
(Show Context)
Citation Context ...uld need a far more elaborate function to evaluate H(·) with a 3072-bit modulus N , for instance; and one would want at least a 128-bit security level. Remark 4. In November 2014, several researchers =-=[17, 29, 40]-=- devised polynomial-time attacks on the multilinear pairing construction in [30] that recover all of the secret quantities. The authors of [17] and [40] proposed a modification to the multilinear pair... |

31 | Replacing a random oracle: Full domain hash from indistinguishability obfuscation.
- Hohenberger, Sahai, et al.
- 2014
(Show Context)
Citation Context ...hrase somewhere in the paper, as of June 6, 2013.) Our purpose is not to comment on 286 papers. Rather, we examine three of the most important efforts to construct replacements for ROM-protocols (see =-=[38, 14, 45]-=-) and find that all of the non-ROM constructions have potential security weaknesses that were not present in the original ROM-versions. Following [26], we also describe a remarkable fact about pairing... |

28 | Design Validations for Discrete Logarithm Based Signature Schemes. In Public Key Cryptography,
- Brickell, Pointcheval, et al.
- 2000
(Show Context)
Citation Context ... generating ephemeral secret keys is the same as in ECDSA. The NIST modification appears not to be sufficient for obtaining the reductionist security result we want. We also note that Brickell et al. =-=[19]-=- obtained several security results for modifications of DSA, that is, for a broad class of signature schemes based on the discrete log problem in a finite field. 10Strictly speaking, one cannot even a... |

28 | Discrete-log-based signatures may not be equivalent to discrete log
- Paillier, Vergnaud
- 2005
(Show Context)
Citation Context ...function H is preimage-resistant in certain senses (this is a weaker condition than collision-resistance). Their reduction is tight.14 There are also two negative results due to Paillier and Vergnaud =-=[61]-=-; see also [68]. Informally speaking, they showed that it is unlikely that a reduction from the DLP to unforgeability of Schnorr signatures exists under a “standard” assumption (meaning that the hash ... |

26 |
On the generic insecurity of the full domain hash.
- Dodis, Oliveira, et al.
- 2005
(Show Context)
Citation Context ... the forger’s task. In §3 of [47] we discuss the formal proof, especially the tightness issue that arises in the reduction. Could this argument be replaced by one that does not use random oracles? In =-=[34]-=- Dodis, Oliveira, and Pietrzak gave a negative answer to this question “generically.” That is, they proved that security of FDH cannot be proved without random oracles if the trapdoor permutation f is... |

22 | Immunizing multilinear maps against zeroizing attacks
- Boneh, Wu, et al.
(Show Context)
Citation Context ...uld need a far more elaborate function to evaluate H(·) with a 3072-bit modulus N , for instance; and one would want at least a 128-bit security level. Remark 4. In November 2014, several researchers =-=[17, 29, 40]-=- devised polynomial-time attacks on the multilinear pairing construction in [30] that recover all of the secret quantities. The authors of [17] and [40] proposed a modification to the multilinear pair... |

22 | The Exact Security of ECDSA.
- Brown
- 2000
(Show Context)
Citation Context ...ete guarantee given by the proof would be taken seriously. In the random oracle model the Pointcheval–Stern results for Schnorr are comparable to the corresponding results for ECDSA (Theorem II.10 of =-=[21]-=-) or ECDSA+ (our claim and informal proof in §7.3). Brown’s Theorem II.10 not only has a tightness gap of qH , but assumes intractability of an unnatural and little studied problem (semi-logarithms) t... |

20 |
The Random-Oracle Model, Revisited
- Goldreich, Halevi
- 1998
(Show Context)
Citation Context ... constructed so as to have a security reduction without random oracles. 2. The Bronze Serpent Controversy The first major assault on the validity of the random oracle model was the widely-cited paper =-=[25]-=- by Canetti, Goldreich, and Halevi, who constructed a ROM-protocol that’s insecure with any concrete hash function. By their own admission, their construction was contrived and bizarre from the standp... |

17 | Programmable hash functions in the multilinear setting
- Freire, Hofheinz, et al.
(Show Context)
Citation Context ... supposes that there is a (publicly known) encoding that maps the message space2 to a code that has a certain required minimum Hamming distance between the encodings of distinct messages (see §3.4 of =-=[36]-=- and §5 of [54]); this is needed for the proof of adaptive security in [45]. We let M ′ denote the encoding of M . Alice randomly chooses a constant v prime to N and a sequence of exponents ai,b, b = ... |

13 | Another look at generic groups.
- Koblitz, Menezes
- 2006
(Show Context)
Citation Context ...the m-SDH assumption that the authors of [14] felt the need to resort to the generic group model. Thus, in order to avoid using random oracles, they used generic groups—even though, as pointed out in =-=[49]-=-, the generic model for groups is arguably a much weaker reflection of reality than is the random oracle model for hash functions. Moreover, a more serious difficulty with the provable security result... |

11 | Another look at tightness
- Chatterjee, Menezes, et al.
(Show Context)
Citation Context ...rantee with the chosen parameters that results from the security reduction turns out to be meaningless, that should not be a cause of great concern. We discussed this issue at length in [48]—see also =-=[27]-=-—and we don’t find this argument convincing. If one believes that rigorous security reductions are of some importance as part of an evaluation of a scheme—and we accepted this premise at the beginning... |

9 |
The static Diffie–Hellman problem
- Brown, Gallant
(Show Context)
Citation Context ...y of the m-SDH problem was probably √ q as in the case of CDH. However, at Eurocrypt 2006 Cheon [28], using the same attack that had been described earlier in a different setting by Brown and Gallant =-=[22, 37]-=-, showed that m-SDH can be solved—and in fact the discrete logarithm x can be found—in √ q/m0 operations if m0 divides q−1 and m0 ≤ m, m0 < q1/3. A little later Jao and Yoshida [46] showed that the m-... |

9 | Boneh-Boyen signatures and the Strong DiffieHellman problem - Jao, Yoshida - 2009 |

9 |
Hash function requirements for schnorr signatures
- Neven, Smart, et al.
(Show Context)
Citation Context ...east b/2 pairs (α0, β) (β ∈ B) are “good.” The splitting lemma says that there are at least a/2 elements in A0. THE RANDOM ORACLE MODEL: A TWENTY-YEAR RETROSPECTIVE 25 • Neven, Smart, and Warinschi =-=[57]-=-, working in the generic group model, proved existential unforgeability under chosen-message attack if the hash function H is preimage-resistant in certain senses (this is a weaker condition than coll... |

9 |
able to foil basic safeguards of privacy on Web,
- Perloth, Larson, et al.
- 2013
(Show Context)
Citation Context ...g a defective implementation of pseudorandom number generation, resulting in a large-scale theft of Bitcoins [23], among other things. One month later the public learned from the Edward Snowden leaks =-=[62]-=- that the NSA had put a backdoor in the NIST-standardized Dual Elliptic Curve Deterministic Random Bit Generator (EC DRBG), which was included as the default in RSA’s BSAFE toolkit. These scandals hav... |

8 | Instantiating random oracles via UCEs
- Bellare, Hoang, et al.
- 2013
(Show Context)
Citation Context ...ever claimed a security result for prefix-MAC under the random oracle model. 6 NEAL KOBLITZ AND ALFRED J. MENEZES work that’s been devoted to constructing non-ROM replacements for these protocols. In =-=[7]-=- Bellare, Hoang, and Keelveedhi comment: There is a large body of work on cryptography without random oracles. (A Google Scholar search shows 286 papers with the phrase “without random oracles” in the... |

8 |
Cryptanalysis of two candidate fixes of multilinear maps over the integers. http://eprint.iacr.org/2014/975
- Coron, Lepoint, et al.
(Show Context)
Citation Context ...and [40] proposed a modification to the multilinear pairing construction in [30] that appears to resist the new attacks. However, shortly afterwards these countermeasures were shown to be ineffective =-=[31]-=-. In February 2015, Coron, Lepoint, and Tibouchi [32] proposed a variant of their multilinear pairing construction that they claim resists the new attacks. While the impact of the attacks on the secur... |

7 | Implementing cryptographic program obfuscation (video), Crypto
- Apon, Huang, et al.
- 2014
(Show Context)
Citation Context ...thod of multilinear pairings in [30]. The complexity of the method grows rapidly with the “level” of the pairing. The construction uses a modulus x0, which is a product of secret primes. In §3.1.3 of =-=[1]-=- it is shown that the bitlength of x0 is at least 4k 2λ2 log2(λ), where k is the level of the pairing and λ is the security parameter. Suppose that we want a 128-bit security level. Then the RSA modul... |

7 |
The importance of the final exponentiation in pairings when considering fault attacks,”
- Whelan, Scott
- 2007
(Show Context)
Citation Context ...re elliptic curve groups, and the pairing is computed by a series of iterations of “Miller operations” involving a linear function L(Q). If the adversary is able to cause a certain kind of sign error =-=[69]-=- or a premature termination [60], then a comparison between the correct and incorrect pairing values leads to equations that can be solved for the coordinates of Q. A necessary condition for this type... |

6 |
Zeroizing without zeroes: Cryptanalyzing multilinear maps without encodings of zero. http://eprint.iacr.org/2014/929
- Gentry, Halevi, et al.
(Show Context)
Citation Context ...uld need a far more elaborate function to evaluate H(·) with a 3072-bit modulus N , for instance; and one would want at least a 128-bit security level. Remark 4. In November 2014, several researchers =-=[17, 29, 40]-=- devised polynomial-time attacks on the multilinear pairing construction in [30] that recover all of the secret quantities. The authors of [17] and [40] proposed a modification to the multilinear pair... |

6 | Another look at security definitions
- Koblitz, Menezes
(Show Context)
Citation Context ...his own, and so we shall suppose that the certification authority demands a proof of knowledge of the corresponding private key before granting a certificate for the public key. As discussed in §2 of =-=[51]-=-, although a DSKS attack falls outside the standard Goldwasser–Micali–Rivest security model (which asks only for security against adaptive chosen-message forgers), it can have serious consequences in ... |

5 |
Generic groups, collision resistance
- Brown
(Show Context)
Citation Context ...g the interaction, cannot feasibly produce a valid forgery of any message at all that was not queried. The definitive work on provable security for ECDSA was done by Dan Brown in the early 2000s (see =-=[20]-=-). He proved that in the generic group model ECDSA is existentially unforgeable against adaptive chosen-message attack provided that certain conditions are satisfied by the hash function (collision re... |

5 |
Randomized Hashing for Digital Signatures
- Dang
- 2008
(Show Context)
Citation Context ...y replacing H(M) by H(kP,M) in the signing equation and define the signature to be (kP, s); let ECDSA+ denote the resulting scheme.11 9A somewhat similar modification of ECDSA was proposed by NIST in =-=[33]-=-. The NIST modification randomizes the message by combining it with an ECDSA signature component; however, the procedure for generating ephemeral secret keys is the same as in ECDSA. The NIST modifica... |

5 |
A fault attack on pairing-based cryptography,”
- Page, Vercauteren
- 2006
(Show Context)
Citation Context ...hic device that’s performing an operation with a secret key. The adversary uses the incorrect output, perhaps with other available data, to obtain some information about the secret key. Starting with =-=[60]-=-, a number of authors have developed fault attacks on pairing-based protocols. The purpose of the recent paper [26] is for the first time to consider which of the many pairing-based protocols in the l... |

4 | A unified approach to idealized model separations via indistinguishability obfuscation. Cryptology ePrint Archive, Report 2014/863,
- Green, Katz, et al.
- 2014
(Show Context)
Citation Context ...ight be clever and of theoretical interest, they were no cause of concern for practitioners. Remark 1. The same comment applies to recent efforts to undermine the random oracle model. For example, in =-=[44]-=- the authors show that if indistinguishability obfuscation exists, then there exists a bit-encryption protocol that is secure in the random oracle model but is insecure when the random oracle is insta... |

4 | The brave new world of bodacious assumptions in cryptography
- Koblitz, Menezes
- 2010
(Show Context)
Citation Context ...re is to employ the term standard model to refer to any set of properties and hardness assumptions that do not include random oracles. This leads to some questionable uses of the word “standard” (see =-=[50]-=-). We prefer the more neutral term “non-ROM protocol” to refer to a protocol that was constructed so as to have a security reduction without random oracles. 2. The Bronze Serpent Controversy The first... |

3 | On the exact security of schnorr-type signatures in the random oracle model
- Seurin
- 2012
(Show Context)
Citation Context ...reimage-resistant in certain senses (this is a weaker condition than collision-resistance). Their reduction is tight.14 There are also two negative results due to Paillier and Vergnaud [61]; see also =-=[68]-=-. Informally speaking, they showed that it is unlikely that a reduction from the DLP to unforgeability of Schnorr signatures exists under a “standard” assumption (meaning that the hash function cannot... |

2 |
iPhone hacker publishes secret Sony PlayStation 3 key’,
- Fildes
- 2011
(Show Context)
Citation Context ...′(K,M) rather than random k is that it forces the user to change k for each message. In 2011 Sony’s implementation of ECDSA for PlayStation 3 was completely broken because they used a constant k; see =-=[35]-=-. An adversary who has two different messages signed with the same k can easily compute the private key. 7.1. ECDSA and ECDSA*. Before discussing security of the modified version of ECDSA, we first re... |

2 |
Deterministic usage of the Digital Signature Algorithm (DSA
- Pornin
- 2013
(Show Context)
Citation Context ...shown that if just three bits of k are known for several hundred signatures, then it is possible to recover the static secret key K. Starting with Barwood [3] and Wigley [70], a number of people (see =-=[65]-=-) have proposed replacing pseudorandom generation of k by a deterministic value k = H ′(K,M) obtained by hashing the message and the static secret key. See also §2 of [11] for a discussion of the rati... |

1 |
Digital signatures using elliptic curves, http://groups.google.com/ group/sci.crypt/msg/b28aba37180dd6c6
- Barwood
- 1997
(Show Context)
Citation Context ...generation of k. For example, in [59] it was shown that if just three bits of k are known for several hundred signatures, then it is possible to recover the static secret key K. Starting with Barwood =-=[3]-=- and Wigley [70], a number of people (see [65]) have proposed replacing pseudorandom generation of k by a deterministic value k = H ′(K,M) obtained by hashing the message and the static secret key. Se... |

1 |
Caught in between theory and practice
- Bellare
(Show Context)
Citation Context ... noted that cryptographic research is characterized by a particularly sharp divide between theory and practice; for an interesting perspective on this issue, see Bellare’s invited talk at Crypto 2014 =-=[5]-=-. Reading the obfuscation literature, even those of us who are accustomed to this gap are startled when we encounter the vast chasm that separates obfuscation theory from cryptographic practice. Remar... |

1 | Bad directions in cryptographic hash functions, preprint, 2015; available at http://obviouscation.cr.yp.to/ obviouscation-20150223.pdf
- Bernstein, Hülsing, et al.
(Show Context)
Citation Context ...he 52-bit security level. Using a 32-core machine, the time for evaluating the obfuscated circuit was 3 hours, and the size of the obfuscated program was 31 gigabytes. More recently, Bernstein et al. =-=[12]-=- presented several techniques for evaluating obfuscated programs, which yield a more than 50-fold speedup in the evaluation of the obfuscation circuit for the 16-bit point function [10]. In practice o... |

1 |
Critical vulnerability found in Android wallets, http://bitcoinmagazine
- Buterin
- 2013
(Show Context)
Citation Context ...In August 2013 it was discovered that a bug in the Android operating system had been causing a defective implementation of pseudorandom number generation, resulting in a large-scale theft of Bitcoins =-=[23]-=-, among other things. One month later the public learned from the Edward Snowden leaks [62] that the NSA had put a backdoor in the NIST-standardized Dual Elliptic Curve Deterministic Random Bit Genera... |

1 | Fault attacks on pairing-based protocols revisited
- Chatterjee, Karabina, et al.
(Show Context)
Citation Context ...truct replacements for ROM-protocols (see [38, 14, 45]) and find that all of the non-ROM constructions have potential security weaknesses that were not present in the original ROM-versions. Following =-=[26]-=-, we also describe a remarkable fact about pairing-based protocols: essentially the only ones that are known to be directly vulnerable to induced-fault side-channel attacks on pairing computations are... |

1 |
New multilinear maps over the integers, available at http://eprint.iacr.org/2015/162
- Coron, Lepoint, et al.
(Show Context)
Citation Context ...airing construction in [30] that appears to resist the new attacks. However, shortly afterwards these countermeasures were shown to be ineffective [31]. In February 2015, Coron, Lepoint, and Tibouchi =-=[32]-=- proposed a variant of their multilinear pairing construction that they claim resists the new attacks. While the impact of the attacks on the security of obfuscation remains to be determined, the atta... |

1 |
The static Diffie-Hellman problem, presented at ECC 2005, available at cacr.waterloo.ca/conferences/2005/ecc2005/gallant.pdf
- Gallant
(Show Context)
Citation Context ...y of the m-SDH problem was probably √ q as in the case of CDH. However, at Eurocrypt 2006 Cheon [28], using the same attack that had been described earlier in a different setting by Brown and Gallant =-=[22, 37]-=-, showed that m-SDH can be solved—and in fact the discrete logarithm x can be found—in √ q/m0 operations if m0 divides q−1 and m0 ≤ m, m0 < q1/3. A little later Jao and Yoshida [46] showed that the m-... |

1 | Another look at security theorems for 1-key nested MACs
- Koblitz, Menezes
(Show Context)
Citation Context ...here to the viewpoint (attributed to Lars Knudsen) that “if it’s provably secure, then it probably isn’t”—have no reason to read this paper. So let’s agree to accept the premise that, as we stated in =-=[52]-=-, “security proofs are useful as a minimal type of assurance.” Once we accept this premise, it follows that whenever we replace a well-studied cryptographic protocol by an alternative version that we ... |

1 | Fully secure and fast signing from obfuscation
- Ramchen, Waters
- 2014
(Show Context)
Citation Context ...omed to this gap are startled when we encounter the vast chasm that separates obfuscation theory from cryptographic practice. Remark 2. An obfuscated program for evaluating a punctured PRF is used in =-=[66]-=- to get a signature scheme with short signatures and fast signature generation that can be proved secure without random oracles. However, signature verification is prohibitively slow, as the authors a... |

1 |
Removing need for rng in signatures, http://groups.google.com/group/ sci.cryp/msg/a6da45bcc8939a89
- Wigley
- 1997
(Show Context)
Citation Context .... For example, in [59] it was shown that if just three bits of k are known for several hundred signatures, then it is possible to recover the static secret key K. Starting with Barwood [3] and Wigley =-=[70]-=-, a number of people (see [65]) have proposed replacing pseudorandom generation of k by a deterministic value k = H ′(K,M) obtained by hashing the message and the static secret key. See also §2 of [11... |

1 |
How to obfuscate programs directly, Advances in Cryptology – Eurocrypt 2015, Part II, LNCS 9057
- Zimmerman
- 2015
(Show Context)
Citation Context ...24 exponents ai,M ′i , and finally computes v pi(M ′) mod N . The most efficient construction that satisfies the required indistinguishability obfuscation property is due to J. Zimmerman (Appendix to =-=[71]-=-). In that construction the multilinearity level k is of order 2d, and the number of ring operations modulo x0 is of order s, where d denotes the depth and s the size of the circuit that’s obfuscated.... |