## Publications

**M. Bellare, E. Crites, C. Komlo, M. Maller, S. Tessaro and C. Zhu**

Better than Advertised Security for Non-Interactive Threshold Signatures

Advances in Cryptology - Crypto 2022 Proceedings, Lecture Notes in Computer Science Vol. , Y. Dodis and T. Shrimpton eds, Springer, 2022.Elizabeth and Chenzhi's talk.

**Note:**This Crypto 2022 paper was a merger of two submissions. The full versions are separate, and our group's is below.**M. Bellare, S. Tessaro and C. Zhu**

Stronger Security for Non-Interactive Threshold Signatures: BLS and FROST

Cryptology ePrint Archive, Paper 2022/833, June 2022.

**Note:**Full version of our part of the above Crypto 2022 paper.**M. Bellare and V. T. Hoang**

Efficient Schemes for Committing Authenticated Encryption

Advances in Cryptology - Eurocrypt 2022 Proceedings, Lecture Notes in Computer Science Vol. 13276, O. Dunkelman and S. Dziembowski eds, Springer, 2022.**M. Bellare and W. Dai**

Chain Reductions for Multi-Signatures and the HBMS Scheme

Advances in Cryptology - Asiacrypt 2021 Proceedings, Lecture Notes in Computer Science Vol. 13093, M. Tibouchi and H. Wang eds, Springer, 2021.

Wei's talk.**M. Bellare, W. Dai and P. Rogaway**

Reimagining Secret Sharing: Creating a Safer and More Versatile Primitive by Adding Authenticity, Correcting Errors, and Reducing Randomness Requirements

Proceedings on Privacy Enhancing Technologies, Vol. 2020, No. 1, 2020.

Phil's talk.**V. Arte, M. Bellare and L. Khati**

Incremental Cryptography Revisited: PRFs, Nonces and Modular Design

Progress in Cryptology - Indocrypt 2020 Proceedings, Lecture Notes in Computer Science Vol. 12578, K. Bhargavan, E. Oswald and M. Prabhakaran eds, Springer, 2020.

Vivek's talk.**V. Arte and M. Bellare**

Dual-Mode NIZKs: Possibility and Impossibility Results for Property Transfer

Progress in Cryptology - Indocrypt 2020 Proceedings, Lecture Notes in Computer Science Vol. 12578, K. Bhargavan, E. Oswald and M. Prabhakaran eds, Springer, 2020.

Vivek's talk.**M. Bellare and W. Dai**

The Multi-Base Discrete Logarithm Problem: Tight Reductions and Non-Rewinding Proofs for Schnorr Identification and Signatures

Progress in Cryptology - Indocrypt 2020 Proceedings, Lecture Notes in Computer Science Vol. 12578, K. Bhargavan, E. Oswald and M. Prabhakaran eds, Springer, 2020.

Wei's talk.**M. Bellare, H. Davis and F. Günther**

Separate Your Domains: NIST PQC KEMs, Oracle Cloning and Read-Only Indifferentiability

Advances in Cryptology - Eurocrypt 2020 Proceedings, Lecture Notes in Computer Science Vol. 12107, A. Canteaut and Y. Ishai eds, Springer, 2020.

Hannah's talk.**M. Bellare and I. Stepanovs**

Security under Message-Derived Keys: Signcryption in iMessage

Advances in Cryptology - Eurocrypt 2020 Proceedings, Lecture Notes in Computer Science Vol. 12107, A. Canteaut and Y. Ishai eds, Springer, 2020.

Igors' talk.**M. Bellare, W. Dai and L. Li**

The Local Forking Lemma and its Application to Deterministic Encryption

Advances in Cryptology - Asiacrypt 2019 Proceedings, Lecture Notes in Computer Science Vol. 11923, S. Galbraith and S. Moriai eds, Springer, 2019.**M. Bellare, R. Ng and B. Tackmann**

Nonces are Noticed: AEAD Revisited

Advances in Cryptology - Crypto 2019 Proceedings, Lecture Notes in Computer Science Vol. 11692, A. Boldyreva and D. Micciancio eds, Springer, 2019.

Ruth's talk.**M. Backendal, M. Bellare, J. Sorrell and J. Sun**

The Fiat-Shamir Zoo: Relating the Security of Different Signature Variants

Secure IT Systems - 23rd Nordic Conference, NordSec 2018, Lecture Notes in Computer Science 11252, Springer 2018.-
**B. Auerbach, M. Bellare and E. Kiltz.**

Public-Key Encryption Resistant to Parameter Subversion and its Realization from Efficiently-Embeddable Groups.

Public Key Cryptography - PKC 2018, Proceedings, Lecture Notes in Computer Science Vol. , M. Abdalla ed, Springer-Verlag, 2018. -
**M. Bellare and W. Dai.**

Defending Against Key Exfiltration: Efficiency Improvements for Big-Key Cryptography via Large-Alphabet Subkey Prediction.

Proceedings of the 24th ACM Conference on Computer and Communications Security (CCS), ACM, 2017. -
**M. Bellare, J. Jaeger and J. Len.**

Better Than Advertised: Improved Collision-Resistance Guarantees for MD-Based Hash Functions.

Proceedings of the 24th ACM Conference on Computer and Communications Security (CCS), ACM, 2017.

Julia's talk. -
**M. Bellare and V. T. Hoang.**

Identity-based Format-Preserving Encryption.

Proceedings of the 24th ACM Conference on Computer and Communications Security (CCS), ACM, 2017.

Tung's talk. -
**M. Bellare, A. C. Singh, J. Jaeger, M. Nyayapati and I. Stepanovs.**

Ratcheted encryption and key exchange: The security of messaging.

Advances in Cryptology - Crypto 2017 Proceedings, Lecture Notes in Computer Science Vol. 10402, J. Katz and H. Shacham eds, Springer, 2017.

Joseph's talk. -
**M. Bellare, A. O'Neill and I. Stepanovs.**

Forward-Security under Continual Leakage.

Cryptology and Network Security (CANS) - 16th International Conference, Proceedings, Lecture Notes in Computer Science Vol. , S. Capkun and S. Chow eds, Springer 2017. -
**M. Bellare, B. Poettering and D. Stebila.**

Deterring certificate subversion: efficient double-authentication-preventing signatures.

Public Key Cryptography - PKC 2016, Proceedings, Lecture Notes in Computer Science Vol. 10175, S. Fehr ed, Springer-Verlag, 2016. -
**M. Bellare, V. T. Hoang and S. Tessaro.**

Message-recovery attacks on feistel-based format preserving encryption.

Proceedings of the 23rd ACM Conference on Computer and Communications Security (CCS), ACM, 2016.

Stefano's talk. -
**M. Bellare and B. Tackmann.**

The multi-user security of authenticated encryption: AES-GCM in TLS 1.3.

Advances in Cryptology - Crypto 2016 Proceedings, Lecture Notes in Computer Science Vol. 9814, M. Robshaw and J. Katz eds, Springer, 2016.

Bjorn's talk. -
**M. Bellare, D. Kane and P. Rogaway.**

Big-key symmetric encryption: resisting key exfiltration.

Advances in Cryptology - Crypto 2016 Proceedings, Lecture Notes in Computer Science Vol. 9814, M. Robshaw and J. Katz eds, Springer, 2016.

Mihir's talk. -
**M. Bellare and B. Tackmann.**

Nonce-based cryptography: Retaining security when randomness fails.

Advances in Cryptology - Eurocrypt 2016 Proceedings, Lecture Notes in Computer Science Vol. 9665, M. Fischlin and J. Coron eds, Springer, 2016. -
**M. Bellare, D. Bernstein and S. Tessaro.**

Hash-function based PRFs: AMAC and its multi-user security.

Advances in Cryptology - Eurocrypt 2016 Proceedings, Lecture Notes in Computer Science Vol. 9665, M. Fischlin and J. Coron eds, Springer, 2016. -
**M. Bellare, I. Stepanovs and B. Waters.**

New negative results on differing-inputs obfuscation.

Advances in Cryptology - Eurocrypt 2016 Proceedings, Lecture Notes in Computer Science Vol. 9666, M. Fischlin and J. Coron eds, Springer, 2016.

Igors' talk. -
**M. Bellare and I. Stepanovs.**

Point-function obfuscation: a framework and generic constructions.

Proceedings of the 13th Theory of Cryptography Conference (TCC 2016-A), Lecture Notes in Computer Science Vol. 9563, E. Kushilevitz and T. Malkin eds, Springer, 2016. -
**M. Bellare, I. Stepanovs and S. Tessaro.**

Contention in cryptoland: obfuscation, leakage and UCE.

Proceedings of the 13th Theory of Cryptography Conference (TCC 2016-A), Lecture Notes in Computer Science Vol. 9563, E. Kushilevitz and T. Malkin eds, Springer, 2016.

Stefano's talk. -
**M. Bellare, G. Fuchsbauer and A. Scafuro.**

NIZKs with an untrusted CRS: Security in the face of parameter subversion.

Advances in Cryptology - Asiacrypt 2016 Proceedings, Lecture Notes in Computer Science Vol. 10032, J. H. Cheon and T. Takagi eds, Springer-Verlag, 2016.

Georg's talk. -
**M. Bellare, B. Poettering and D. Stebila.**

From Identification to Signatures, Tightly: A Framework and Generic Transforms.

Advances in Cryptology - Asiacrypt 2016 Proceedings, Lecture Notes in Computer Science Vol. 10032, J. H. Cheon and T. Takagi eds, Springer-Verlag, 2016.

Bertram's talk. -
**M. Bellare and A. Lysyanskaya.**

Symmetric and Dual PRFs from Standard Assumptions: A Generic Validation of an HMAC Assumption.

IACR Cryptology ePrint Archive Report 1198, 2015. -
**M. Bellare and V. T. Hoang.**

Resisting Randomness Subversion: Fast Deterministic and Hedged Public-Key Encryption in the Standard Model.

Advances in Cryptology - Eurocrypt 2015 Proceedings, Lecture Notes in Computer Science Vol. 9057, E. Oswald and M. Fischlin eds, Springer, 2015. -
**M. Bellare, J. Jaeger and D. Kane.**

Mass-surveillance without the state: Strongly undetectable algorithm-substitution attacks.

Proceedings of the 22nd ACM Conference on Computer and Communications Security (CCS), ACM, 2015. -
**M. Bellare and S. Keelveedhi.**

Interactive message-locked encryption and secure deduplication.

Public Key Cryptography - PKC 2015, Proceedings, Lecture Notes in Computer Science Vol. 9020, J. Katz ed, Springer-Verlag, 2015. -
**M. Bellare and V. T. Hoang.**

Adaptive witness encryption and asymmetric password-based cryptography.

Public Key Cryptography - PKC 2015, Proceedings, Lecture Notes in Computer Science Vol. 9020, J. Katz ed, Springer-Verlag, 2015. -
**M. Bellare, R. Dowsley and S. Keelveedhi.**

How Secure is Deterministic Encryption?

Public Key Cryptography - PKC 2015, Proceedings, Lecture Notes in Computer Science Vol. 9020, J. Katz ed, Springer-Verlag, 2015. -
**M. Bellare, D. Hofheinz and E. Kiltz.**

Subtleties in the definition of IND-CCA: When and how should challenge decryption be disallowed?

Journal of Cryptology Vol. 28, No. 1, 2015. -
**M. Bellare, I. Stepanovs and S. Tessaro.**

Poly-many hardcore bits for any one-way function and a framework for differing-inputs obfuscation.

Advances in Cryptology - Asiacrypt 2014 Proceedings, Lecture Notes in Computer Science Vol. 8874, P. Sarkar and T. Iwata eds, Springer-Verlag, 2014. -
**M. Bellare, V. T. Hoang and S. Keelveedhi.**

Cryptography from compression functions: The UCE bridge to the ROM.

Advances in Cryptology - Crypto 2014 Proceedings, Lecture Notes in Computer Science Vol. 8616, J. Garay and R. Gennaro eds, Springer, 2014.

Tung's talk. -
**M. Bellare, K. Paterson and P. Rogaway.**

Security of symmetric encryption against mass surveillance.

Advances in Cryptology - Crypto 2014 Proceedings, Lecture Notes in Computer Science Vol. 8616, J. Garay and R. Gennaro eds, Springer, 2014.

Phil's talk. -
**J. Vance and M. Bellare.**

An Extension of the FF2 FPE Scheme.

NIST, Modes Development, Proposed Modes, 2014. -
**M. Bellare, S. Meiklejohn and S. Thomson.**

Key-versatile signatures and applications: RKA, KDM and Joint Enc/Sig.

Advances in Cryptology - Eurocrypt 2014 Proceedings, Lecture Notes in Computer Science Vol. 8441, P. Nguyen and E. Oswald eds, Springer, 2014. -
**M. Bellare and G. Fuchsbauer.**

Policy-Based Signatures.

Public Key Cryptography - PKC 2014, Proceedings, Lecture Notes in Computer Science Vol. 8383, H. Krawczyk ed, Springer-Verlag, 2014. -
**M. Bellare, V. T. Hoang and S. Keelveedhi.**

Instantiating random oracles via UCEs.

Advances in Cryptology - Crypto 2013 Proceedings, Lecture Notes in Computer Science Vol. 8043, R. Canetti and J. Garay eds, Springer, 2013.

Sriram's talk. -
**M. Bellare, S. Keelveedhi and T. Ristenpart.**

DupLESS: Server-aided encryption for deduplicated storage.

22nd Usenix Security Symposium Proceedings, Usenix 2013. -
**M. Bellare, V. T. Hoang, S. Keelveedhi and P. Rogaway.**

Efficient Garbling from a Fixed-Key Blockcipher.

IEEE Symposium on Security and Privacy (Oakland 2013). -
**M. Bellare, S. Keelveedhi and T. Ristenpart.**

Message-Locked Encryption and Secure Deduplication.

Advances in Cryptology - Eurocrypt 2013 Proceedings, Lecture Notes in Computer Science Vol. 7881, T. Johansson and P. Nguyen eds, Springer, 2013. -
**M. Bellare and A. O'Neill.**

Semantically-Secure Functional Encryption: Possibility Results, Impossibility Results and the Quest for a General Definition. Cryptology and Network Security (CANS) - 12th International Conference, Proceedings, Lecture Notes in Computer Science Vol. 8257, M. Abdalla, C. Nita-Rotaru and R. Dahab eds, Springer 2013. -
**M. Bellare, V. T. Hoang and P. Rogaway.**

Adaptively Secure Garbling with Applications to One-Time Programs and Secure Outsourcing.

Advances in Cryptology - Asiacrypt 2012 Proceedings, Lecture Notes in Computer Science Vol. 7658, X. Wang and K. Sako eds, Springer-Verlag, 2012. -
**M. Bellare, K. Paterson and S. Thomson.**

RKA Security beyond the Linear Barrier: IBE, Encryption and Signatures.

Advances in Cryptology - Asiacrypt 2012 Proceedings, Lecture Notes in Computer Science Vol. 7658, X. Wang and K. Sako eds, Springer-Verlag, 2012. -
**M. Bellare, V. T. Hoang and P. Rogaway.**

Foundations of garbled circuits.

Proceedings of the 19th ACM Conference on Computer and Communications Security (CCS), ACM, 2012. -
**M. Bellare, S. Tessaro and A. Vardy.**

Semantic Security for the Wiretap Channel.

Advances in Cryptology - Crypto 2012 Proceedings, Lecture Notes in Computer Science Vol. 7417, R. Safavi-Naini and R. Canetti eds, Springer, 2012.

Stefano's talk. -
**M. Bellare, S. Tessaro and A. Vardy.**

A Cryptographic Treatment of the Wiretap Channel.

IACR Cryptology ePrint Archive Vol. 2012/015. -
**M. Bellare and S. Tessaro.**

Polynomial-Time, Semantically-Secure Encryption Achieving the Secrecy Capacity.

IACR Cryptology ePrint Archive Vol. 2012/022. -
**M. Bellare, T. Ristenpart and S. Tessaro.**

Multi-instance Security and Its Application to Password-Based Cryptography.

Advances in Cryptology - Crypto 2012 Proceedings, Lecture Notes in Computer Science Vol. 7417, R. Safavi-Naini and R. Canetti eds, Springer, 2012.

Stefano's talk. -
**M. Bellare, E. Kiltz, C. Peikert and B. Waters.**

Identity-Based (Lossy) Trapdoor Functions and Applications.

Advances in Cryptology - Eurocrypt 2012 Proceedings, Lecture Notes in Computer Science Vol. 6110, D. Pointcheval and T. Johansson eds, Springer, 2012.

Eike's talk. -
**M. Bellare, R. Dowsley, B. Waters and S. Yilek.**

Standard Security Does Not Imply Security against Selective-Opening.

Advances in Cryptology - Eurocrypt 2012 Proceedings, Lecture Notes in Computer Science Vol. 6110, D. Pointcheval and T. Johansson eds, Springer, 2012.

Rafael's talk. -
**M. Bellare, O. Goldreich.**

On Probabilistic versus Deterministic Provers in the Definition of Proofs of Knowledge.

Studies in Complexity and Cryptography 2011. -
**M. Bellare, D. Cash and R. Miller.**

Cryptography Secure against Related-Key Attacks and Tampering.

Advances in Cryptology - Asiacrypt 2011 Proceedings, Lecture Notes in Computer Science Vol. 7073, D. H. Lee and X. Wang eds, Springer-Verlag, 2011. -
**M. Bellare, D. Cash and S. Keelveedhi.**

Ciphers that securely encipher their own keys.

Proceedings of the 18th ACM Conference on Computer and Communications Security (CCS), ACM, 2011. -
**M. Bellare and S. Keelveedhi.**

Authenticated and Misuse-Resistant Encryption of Key-Dependent Data.

Advances in Cryptology - Crypto 2011 Proceedings, Lecture Notes in Computer Science Vol. 6841, P. Rogaway ed, Springer, 2011.

Sriram's talk. -
**M. Bellare, B. Waters and S. Yilek.**

Identity-Based Encryption Secure against Selective Opening Attack.

Proceedings of the 8th Theory of Cryptography Conference (TCC 2011), Lecture Notes in Computer Science Vol. 6597, Y. Ishai ed, Springer, 2011. -
**M. Bellare and D. Cash.**

Pseudorandom Functions and Permutations Provably Secure against Related-Key Attacks.

Advances in Cryptology - Crypto 2010 Proceedings, Lecture Notes in Computer Science Vol. 6223, T. Rabin ed, Springer, 2010. -
**T. Acar, M. Belenkiy, M. Bellare and D. Cash.**

Cryptographic Agility and Its Relation to Circular Encryption.

Advances in Cryptology - Eurocrypt 2010 Proceedings, Lecture Notes in Computer Science Vol. 6110, H. Gilbert ed, Springer, 2010. -
**M. Abdalla, M. Bellare and G. Neven.**

Robust Encryption.

Proceedings of the 7th Theory of Cryptography Conference (TCC 2010), Lecture Notes in Computer Science Vol. 5978, D. Micciancio ed, Springer, 2010. -
**M. Bellare and S. Duan.**

Partial Signatures and their Applications.

IACR Cryptology ePrint Archive Vol. 2009/336. -
**M. Bellare, Z. Brakerski, M. Naor, T. Ristenpart, G. Segev, H. Shacham and S. Yilek.**

Hedged Public-Key Encryption: How to Protect against Bad Randomness.

Advances in Cryptology - Asiacrypt 2009 Proceedings, Lecture Notes in Computer Science Vol. 5912, M. Matsui ed, Springer-Verlag, 2009. -
**M. Bellare, S. Duan and A. Palacio.**

Key Insulation and Intrusion Resilience over a Public Channel.

Topics in Cryptology - CT-RSA 09, Lecture Notes in Computer Science Vol. 5473, M. Fischlin ed, Springer-Verlag, 2009. -
**M. Bellare and S. Yilek.**

Encryption Schemes Secure under Selective Opening Attack.

IACR Cryptology ePrint Archive Vol. 2009/101.

Full version of our part of the following. -
**M. Bellare, D. Hofheinz and S. Yilek.**

Possibility and Impossibility Results for Encryption and Commitment Secure under Selective Opening.

Advances in Cryptology - Eurocrypt 2009 Proceedings, Lecture Notes in Computer Science Vol. 5479, A. Joux ed, Springer-Verlag, 2009. -
**M. Bellare and T. Ristenpart.**

Simulation without the Artificial Abort: Simplified Proof and Improved Concrete Security for Waters' IBE Scheme.

Advances in Cryptology - Eurocrypt 2009 Proceedings, Lecture Notes in Computer Science Vol. 5479, A. Joux ed, Springer-Verlag, 2009. -
**M. Bellare, T. Ristenpart, P. Rogaway and T. Stegers.**

Format-Preserving Encryption.

Proceedings of the 16th Workshop on Selected Areas in Cryptography (SAC 2009), Lecture Notes in Computer Science Vol. 5867, M. Jacobson, V. Rijmen, R. Safavi-Naini eds, Springer-Verlag, 2009. -
**M. Bellare and T. Ristov.**

A characterization of chameleon hash functions and new, efficient designs.

Journal of Cryptology Vol. 27, No. 4, 2014. Earlier version, titled Hash Functions from Sigma Protocols and Improvements to VSH, in Advances in Cryptology - Asiacrypt 2008 Proceedings, Lecture Notes in Computer Science Vol. 5350, J. Pieprzyk ed, Springer-Verlag, 2008. -
**M. Bellare, M. Fischlin, A. O'Neill and T. Ristenpart.**

Deterministic Encryption: Definitional Equivalences and Constructions without Random Oracles.

Advances in Cryptology - Crypto 2008 Proceedings, Lecture Notes in Computer Science Vol. 5157, D. Wagner ed, Springer-Verlag, 2008. -
**M. Bellare and P. Rogaway.**

Robust computational secret sharing and a unified account of classical secret-sharing goals.

Proceedings of the 14th ACM Conference on Computer and Communications Security (CCS), ACM, 2007. -
**M. Bellare, A. Boldyreva and A. O'Neill.**

Deterministic and efficiently searchable encryption.

Advances in Cryptology - Crypto 2007 Proceedings, Lecture Notes in Computer Science Vol. 4622, A. Menezes ed, Springer-Verlag, 2007.

Sasha's broad talk on deterministic encryption. -
**M. Bellare and G. Neven.**

Identity-Based Multi-signatures from RSA.

Topics in Cryptology - CT-RSA 2007 Proceedings, Lecture Notes in Computer Science Vol. 4377, M. Abe ed, Springer-Verlag, 2007. -
**M. Bellare and T. Ristenpart.**

Hash Functions in the Dedicated-Key Setting: Design Choices and MPP Transforms.

Automata, Languages and Programming, 34th International Colloquium, ICALP 2007 Proceedings, Lecture Notes in Computer Science Vol. 4596, C. Cachin ed, Springer-Verlag, 2007. -
**M. Bellare, C. Namprempre and G. Neven.**

Unrestricted Aggregate Signatures.

Automata, Languages and Programming, 34th International Colloquium, ICALP 2007 Proceedings, Lecture Notes in Computer Science Vol. 4596, C. Cachin ed, Springer-Verlag, 2007. -
**M. Bellare and S. Shoup.**

Two-Tier Signatures, Strongly Unforgeable Signatures, and Fiat-Shamir without Random Oracles.

Public Key Cryptography - PKC 2007, Proceedings, Lecture Notes in Computer Science Vol. 4450, T. Okamoto, X. Wang eds, Springer-Verlag, 2007. -
**M. Bellare and T. Ristenpart.**

Multi-Property-Preserving Hash Domain Extension and the EMD Transform.

Advances in Cryptology - Asiacrypt 2006 Proceedings, Lecture Notes in Computer Science Vol. 4284, X. Lai and K. Chen eds, Springer-Verlag, 2006. -
**M. Bellare, T. Kohno and V. Shoup.**

Stateful Public-Key Cryptosystems: How to Encrypt with One 160-bit Exponentiation.

Proceedings of the 13th ACM Conference on Computer and Communications Security (CCS), ACM, 2006. -
**M. Bellare and G. Neven.**

Multisignatures in the Plain Public-Key Model and a General Forking Lemma.

Proceedings of the 13th ACM Conference on Computer and Communications Security (CCS), ACM, 2006. -
**M. Bellare.**

New Proofs for NMAC and HMAC: Security without Collision-Resistance.

Journal of Cryptology Vol. 28 No. 4, 2015. Earlier version in Advances in Cryptology - Crypto 2006 Proceedings, Lecture Notes in Computer Science Vol. 4117, C. Dwork ed, Springer-Verlag, 2006. -
**M. Bellare and P. Rogaway.**

Code-Based Game-Playing Proofs and the Security of Triple Encryption.

Advances in Cryptology - Eurocrypt 2006 Proceedings, Lecture Notes in Computer Science Vol. 4004, S. Vaudenay ed, Springer-Verlag, 2006. -
**M. Abdalla, M. Bellare, D. Catalano, E. Kiltz, T. Kohno, T. Lange, J. Malone-Lee, G. Neven, P. Paillier and H. Shi.**

Searchable Encryption Revisited: Consistency Properties, Relation to Anonymous IBE, and Extensions.

Advances in Cryptology - Crypto 2005 Proceedings, Lecture Notes in Computer Science Vol. 3621, V. Shoup ed, Springer-Verlag, 2005. -
**M. Bellare, K. Pietrzak and P. Rogaway.**

Improved Security Analyses for CBC MACs.

Advances in Cryptology - Crypto 2005 Proceedings, Lecture Notes in Computer Science Vol. 3621, V. Shoup ed, Springer-Verlag, 2005. -
**M. Bellare, H. Shi and C. Zhang.**

Foundations of Group Signatures: The Case of Dynamic Groups.

Topics in Cryptology - CT-RSA 2005 Proceedings, Lecture Notes in Computer Science Vol. 3376, A. Menezes ed, Springer-Verlag, 2005. -
**M. Bellare and A. Palacio.**

Towards Plaintext-Aware Public-Key Encryption without Random Oracles.

Advances in Cryptology - Asiacrypt 2004 Proceedings, Lecture Notes in Computer Science Vol. 3329, P. J. Lee ed, Springer-Verlag, 2004. -
**M. Bellare and A. Palacio.**

The knowledge-of-exponent assumptions and 3-round zero-knowledge protocols.

Advances in Cryptology - Crypto 2004 Proceedings, Lecture Notes in Computer Science Vol. 3152, M. Franklin ed, Springer-Verlag, 2004. -
**M. Bellare and T. Kohno.**

Hash function balance and its impact on birthday attacks.

Advances in Cryptology - Eurocrypt 2004 Proceedings, Lecture Notes in Computer Science Vol. 3027, C. Cachin and J. Camenisch eds, Springer-Verlag, 2004. -
**M. Bellare, C. Namprempre and G. Neven.**

Security Proofs for Identity-Based Identification and Signature Schemes

Advances in Cryptology - Eurocrypt 2004 Proceedings, Lecture Notes in Computer Science Vol. 3027, C. Cachin and J. Camenisch eds, Springer-Verlag, 2004. -
**M. Bellare, A. Boldyreva and A. Palacio.**

An Uninstantiable Random-Oracle-Model Scheme for a Hybrid-Encryption Problem.

Advances in Cryptology - Eurocrypt 2004 Proceedings, Lecture Notes in Computer Science Vol. 3027, C. Cachin and J. Camenisch eds, Springer-Verlag, 2004. -
**M. Bellare, P. Rogaway and D. Wagner.**

The EAX Mode of Operation.

Proceedings of the 11th Workshop on Fast Software Encryption (FSE 2004), Lecture Notes in Computer Science Vol. 3017, R. Bimal and W. Meier eds, Springer-Verlag, 2004. -
**M. Bellare, D. Micciancio and B. Warinschi.**

Foundations of Group Signatures: Formal Definitions, Simplified Requirements, and a Construction Based on General Assumptions.

Advances in Cryptology - Eurocrypt 2003 Proceedings, Lecture Notes in Computer Science Vol. 2656, E. Biham ed, Springer-Verlag, 2003. -
**M. Bellare and T. Kohno.**

A Theoretical Treatment of Related-Key Attacks: RKA-PRPs, RKA-PRFs, and Applications.

Advances in Cryptology - Eurocrypt 2003 Proceedings, Lecture Notes in Computer Science Vol. 2656, E. Biham ed, Springer-Verlag, 2003. -
**M. Bellare, A. Boldyreva, K. Kurosawa and J. Staddon.**

Multi-Recipient Encryption Schemes: How to Save on Bandwidth and Computation without Sacrificing Security.

IEEE Transactions on Information Theory, Volume 53, Number 11, pp. 3927-3943, November 2007. -
**M. Bellare, A. Boldyreva and J. Staddon.**

Multi-Recipient Encryption Schemes: Security Notions and Randomness Re-Use.

The preliminary version of this paper was titled*Randomness reuse in multi-recipient encryption schemes*, and appeared in the proceedings of Public Key Cryptography -- PKC 2003, Lecture Notes in Computer Science Vol. 2567, Y. Desmedt ed, Springer-Verlag, 2003. -
**M. Bellare and B. Yee.**

Forward-Security in Private-Key Cryptography.

Topics in Cryptology - CT-RSA 03, Lecture Notes in Computer Science Vol. 2612, M. Joye ed, Springer-Verlag, 2003. -
**M. Bellare, T. Kohno and C. Namprempre.**

Breaking and provably repairing the SSH authenticated encryption scheme: A case study of the Encode-then-Encrypt-and-MAC paradigm.

ACM Transactions on Information and System Security (TISSEC), Vol. 7, Iss. 2, May 2004, pp. 206--241.

The preliminary version of this paper was titled*Authenticated Encryption in SSH: Provably Fixing the SSH Binary Packet Protocol*, and appeared in the Proceedings of the 9th ACM conference on Computer and Communications Security (CCS), ACM, 2002. -
**M. Bellare and G. Neven.**

Transitive Signatures: New Schemes and Proofs.

IEEE Transactions on Information Theory, Vol. 51, No. 6, June 2005, pp. 2133-2151.

The preliminary version of this paper was titled*Transitive Signatures based on Factoring and RSA*and appeared in Advances in Cryptology - Asiacrypt 2002 Proceedings, Lecture Notes in Computer Science Vol. 2501, Y. Zheng ed, Springer-Verlag, 2002. -
**M. Bellare and A. Palacio.**

GQ and Schnorr Identification Schemes: Proofs of Security against Impersonation under Active and Concurrent Attacks.

Advances in Cryptology - Crypto 2002 Proceedings, Lecture Notes in Computer Science Vol. 2442, M. Yung ed, Springer-Verlag, 2002. -
**M. Abdalla, J. An, M. Bellare and C. Namprempre.**

From Identification to Signatures via the Fiat-Shamir Transform: Minimizing Assumptions for Security and Forward-Security.

Advances in Cryptology - Eurocrypt 2002 Proceedings, Lecture Notes in Computer Science Vol. 2332 , L. Knudsen ed, Springer-Verlag, 2002. -
**M. Bellare, A. Boldyreva, A. Desai and D. Pointcheval.**

Key-privacy in public-key encryption.

Advances in Cryptology - Asiacrypt 2001 Proceedings, Lecture Notes in Computer Science Vol. 2248, C. Boyd ed, Springer-Verlag, 2001. -
**P. Rogaway, M. Bellare, J. Black and T. Krovetz.**

OCB: A block-cipher mode of operation for efficient authenticated encryption.

Proceedings of the 8th ACM Conference on Computer and Communications Security (CCS), ACM, 2001. -
**M. Bellare, A. Boldyreva, L. Knudsen and C. Namprempre.**

On-Line Ciphers and the Hash-CBC Constructions.

Journal of Cryptology Vol. 25, No. 4, 2012. Preliminary version in Advances in Cryptology - Crypto 2001 Proceedings, Lecture Notes in Computer Science Vol. 2139 , J. Kilian ed, Springer-Verlag, 2001. -
**M. Bellare and R. Sandhu.**

The security of practical two-party RSA signature schemes. -
**J. An and M. Bellare.**

Does encryption with redundancy provide authenticity?

Advances in Cryptology - Eurocrypt 2001 Proceedings, Lecture Notes in Computer Science Vol. 2045 , B. Pfitzmann ed, Springer-Verlag, 2001. -
**M. Bellare, M. Fischlin, S. Goldwasser and S. Micali.**

Identification protocols secure against reset attacks.

Advances in Cryptology - Eurocrypt 2001 Proceedings, Lecture Notes in Computer Science Vol. 2045, B. Pfitzmann ed, Springer-Verlag, 2001. -
**M. Abdalla, M. Bellare and P. Rogaway.**

DHIES: An encryption scheme based on the Diffie-Hellman Problem

Extended abstract, titled The Oracle Diffie-Hellman Assumptions and an Analysis of DHIES, was in Topics in Cryptology - CT-RSA 01, Lecture Notes in Computer Science Vol. 2020, D. Naccache ed, Springer-Verlag, 2001. -
**M. Bellare, C. Namprempre, D. Pointcheval and M. Semanko.**

The One-More-RSA-Inversion Problems and the security of Chaum's Blind Signature Scheme.

Journal of Cryptology, Vol. 16, No. 3, 2003, pp. 185-215.

The preliminary version of this paper was titled*The Power of RSA Inversion Oracles and the Security of Chaum's RSA-Based Blind Signature Scheme*and appeared in Financial Cryptography 01, Lecture Notes in Computer Science Vol. 2339, P. Syverson ed, Springer-Verlag, 2001. -
**M. Abdalla and M. Bellare.**

Increasing the lifetime of a key: A comparitive analysis of the security of rekeying techniques.

Advances in Cryptology - Asiacrypt 2000 Proceedings, Lecture Notes in Computer Science Vol. 1976, T. Okamoto ed, Springer-Verlag, 2000. -
**M. Bellare and A. Boldyreva.**

The Security of Chaffing and Winnowing.

Advances in Cryptology - Asiacrypt 2000 Proceedings, Lecture Notes in Computer Science Vol. 1976, T. Okamoto ed, Springer-Verlag, 2000. -
**M. Bellare and C. Namprempre.**

Authenticated Encryption: Relations among notions and analysis of the generic composition paradigm.

Advances in Cryptology - Asiacrypt 2000 Proceedings, Lecture Notes in Computer Science Vol. 1976, T. Okamoto ed, Springer-Verlag, 2000. -
**M. Bellare and P. Rogaway.**

Encode-then-encipher encryption: How to exploit nonces or redundancy in plaintexts for efficient cryptography.

Advances in Cryptology - Asiacrypt 2000 Proceedings, Lecture Notes in Computer Science Vol. 1976, T. Okamoto ed, Springer-Verlag, 2000. -
**M. Bellare, D. Pointcheval and P. Rogaway.**

Authenticated Key Exchange Secure Against Dictionary Attacks.

Advances in Cryptology - Eurocrypt 2000 Proceedings, Lecture Notes in Computer Science Vol. 1807, B. Preneel ed, Springer-Verlag, 2000. -
**M. Bellare, A. Boldyreva and S. Micali.**

Public-key Encryption in a Multi-User Setting: Security Proofs and Improvements.

Advances in Cryptology - Eurocrypt 2000 Proceedings, Lecture Notes in Computer Science Vol. 1807, B. Preneel ed, Springer-Verlag, 2000. -
**M. Bellare, O. Goldreich and E. Petrank.**

Uniform Generation of NP-witnesses using an NP-oracle.

Information and Computation, Vol. 163, 2000, pp. 510--526. -
**M. Bellare and A. Sahai.**

Non-Malleable Encryption: Equivalence between Two Notions, and an Indistinguishability-Based Characterization.

Advances in Cryptology - Crypto 99 Proceedings, Lecture Notes in Computer Science Vol. 1666, M. Wiener ed, Springer-Verlag, 1999. -
**M. Bellare and S. Miner.**

A forward-secure digital signature scheme.

Advances in Cryptology - Crypto 99 Proceedings, Lecture Notes in Computer Science Vol. 1666, M. Wiener ed, Springer-Verlag, 1999. -
**M. Bellare, O. Goldreich and H. Krawczyk.**

Stateless evaluation of pseudorandom functions: Security beyond the birthday barrier.

Advances in Cryptology - Crypto 99 Proceedings, Lecture Notes in Computer Science Vol. 1666, M. Wiener ed, Springer-Verlag, 1999. -
**J. An and M. Bellare .**

Constructing VIL-MACs from FIL-MACs: Message authentication under weakened assumptions.

Advances in Cryptology - Crypto 99 Proceedings, Lecture Notes in Computer Science Vol. 1666, M. Wiener ed, Springer-Verlag, 1999. -
**M. Bellare and P. Rogaway.**

On the construction of variable-input-length ciphers.

Proceedings of the 6th Workshop on Fast Software Encryption, Lecture Notes in Computer Science Vol. 1636, Ed. L. Knudsen, Springer-Verlag, 1999. -
**M. Bellare, J. Garay, C. Jutla and M. Yung.**

VarietyCash: A Multi-purpose Electronic Payment System.

Proceedings of the 3rd Usenix Workshop on Electronic Commerce, Usenix, 1998. -
**M. Bellare, S. Halevi, A. Sahai and S. Vadhan.**

Many-to-one trapdoor functions and their relation to public-key cryptosystems

. Advances in Cryptology- Crypto 98 Proceedings, Lecture Notes in Computer Science Vol. 1462, H. Krawczyk ed, Springer-Verlag, 1998. -
**M. Bellare, A. Desai, D. Pointcheval and P. Rogaway.**

Relations among notions of security for public-key encryption schemes.

Advances in Cryptology- Crypto 98 Proceedings, Lecture Notes in Computer Science Vol. 1462, H. Krawczyk ed, Springer-Verlag, 1998. -
**W. Aiello, M. Bellare, G. Di Crescenzo and R. Venkatesan.**

Security amplification by composition: The case of doubly-iterated, ideal ciphers.

Advances in Cryptology- Crypto 98 Proceedings, Lecture Notes in Computer Science Vol. 1462, H. Krawczyk ed, Springer-Verlag, 1998. -
**M. Bellare, R. Canetti, and H. Krawczyk.**

A modular approach to the design and analysis of authentication and key exchange protocols.

Proceedings of 30th Annual Symposium on the Theory of Computing, ACM, 1998. -
**M. Bellare, T. Krovetz and P. Rogaway.**

Luby-Rackoff backwards: Increasing security by making block ciphers non-invertible.

Advances in Cryptology- Eurocrypt 98 Proceedings, Lecture Notes in Computer Science Vol. 1403, K. Nyberg ed, Springer-Verlag, 1998. -
**M. Bellare, J. Garay and T. Rabin.**

Fast batch verification for modular exponentiation and digital signatures.

Advances in Cryptology- Eurocrypt 98 Proceedings, Lecture Notes in Computer Science Vol. 1403, K. Nyberg ed, Springer-Verlag, 1998. -
**A. Bar-Noy, M. Bellare, M. Halldorsson, H. Shachnai and T. Tamir.**

On chromatic sums and distributed resource allocation.

Information and Computation, Vol. 140, No. 2, February 1998, pp. 183--202. -
**M. Bellare, O. Goldreich and M. Sudan.**

Free bits, PCPs and non-approximability.

SIAM J. on Computing, Vol. 27, No. 3, 1998, pp. 804-915. -
**M. Bellare, A. Desai, E. Jokipii and P. Rogaway.**

A Concrete Security Treatment of Symmetric Encryption: Analysis of the DES Modes of Operation.

The preliminary version of this paper was titled*A Concrete Security Treatment of Symmetric Encryption*and appeared in the Proceedings of 38th Annual Symposium on Foundations of Computer Science, IEEE, 1997. -
**M. Bellare, R. Impagliazzo, and M. Naor.**

Does Parallel Repetition Lower the Error in Computationally Sound Protocols?

Proceedings of 38th Annual Symposium on Foundations of Computer Science, IEEE, 1997. -
**M. Bellare and P. Rogaway.**

Collision-Resistant Hashing: Towards Making UOWHFs Practical.

Advances in Cryptology- Crypto 97 Proceedings, Lecture Notes in Computer Science Vol. 1294, B. Kaliski ed, Springer-Verlag, 1997. -
**M. Bellare, S. Goldwasser and D. Micciancio.**

``Pseudo-Random'' Number Generation within Cryptographic Algorithms: the DSS Case.

Advances in Cryptology- Crypto 97 Proceedings, Lecture Notes in Computer Science Vol. 1294, B. Kaliski ed, Springer-Verlag, 1997. -
**M. Bellare.**

A Note on Negligible Functions.

Journal of Cryptology Vol. 15, No. 4, 2002, pp. 271--284.

Earlier version: Technical Report CS97-529, Department of Computer Science and Engineering, UCSD, March 1997. -
**M. Bellare and D. Micciancio.**

A New Paradigm for collision-free hashing: Incrementality at reduced cost.

Advances in Cryptology- Eurocrypt 97 Proceedings, Lecture Notes in Computer Science Vol. 1233, W. Fumy ed, Springer-Verlag, 1997. -
**M. Bellare, M. Jakobsson and M. Yung.**

Round-optimal zero-knowledge arguments based on any one-way function.

Advances in Cryptology- Eurocrypt 97 Proceedings, Lecture Notes in Computer Science Vol. 1233, W. Fumy ed, Springer-Verlag, 1997. -
**M. Bellare and S. Goldwasser.**

Verifiable partial key escrow.

Proceedings 4th ACM Conference on Computer and Communications Security, April 1997. Earlier version was Technical Report CS95-447, Department of Computer Science and Engineering, UCSD, October 1995. -
**M. Bellare, R. Canetti, and H. Krawczyk.**

Pseudorandom functions revisited: The cascade construction and its concrete security.

Proceedings 37th Annual Symposium on the Foundations of Computer Science, IEEE, 1996. -
**M. Bellare, R. Canetti, and H. Krawczyk.**

Keying hash functions for message authentication.

Advances in Cryptology - Crypto 96 Proceedings, Lecture Notes in Computer Science Vol. 1109, N. Koblitz ed, Springer-Verlag, 1996. -
**M. Bellare and P. Rogaway.**

The exact security of digital signatures: How to sign with RSA and Rabin.

Advances in Cryptology - Eurocrypt 96 Proceedings, Lecture Notes in Computer Science Vol. 1070, U. Maurer ed, Springer-Verlag, 1996. -
**M. Bellare and R. Rivest.**

Translucent cryptography -- An alternative to key escrow, and its implementation via fractional oblivious transfer.

Journal of Cryptology, Vol. 12, No. 2, 1999, pp. 117--140. Early version was MIT Laboratory for Computer Science Technical Memo No. 683, February 1996. -
**M. Bellare, J. Garay and T. Rabin.**

Distributed pseudo-random bit generators-- A new way to speed-up shared coin tossing.

Proceedings of the 15th ACM Symposium on Principles of Distributed Computing, ACM, 1996. -
**M. Bellare, D. Coppersmith, J. Hastad, M. Kiwi and M. Sudan.**

Linearity testing in characteristic two.

IEEE Transactions on Information Theory, Vol. 42, No. 6, pp. 1781--1795, November 1996. -
**M. Bellare, R. Guerin and P. Rogaway.**

XOR MACs: New methods for message authentication using finite pseudorandom functions.

Advances in Cryptology - Crypto 95 Proceedings, Lecture Notes in Computer Science Vol. 963, D. Coppersmith ed, Springer-Verlag, 1995. -
**M. Bellare, J. Garay, R. Hauser, A. Herzberg, H. Krawczyk, M. Steiner, G. Tsudik, E. Van Herreveghen and M. Waidner.**

Design, implementation, and deployment of the iKP secure electronic payment system.

IEEE Journal on Selected Areas in Communications, 2000, Vol. 18, No. 4, pp. 611-627. -
**M. Bellare and P. Rogaway.**

Provably secure session key distribution: the three party case.

Proceedings 27th Annual Symposium on the Theory of Computing, ACM, 1995. -
**M. Bellare, O. Goldreich and S. Goldwasser.**

Incremental cryptography with application to virus protection.

Proceedings 27th Annual Symposium on the Theory of Computing, ACM, 1995. -
**W. Aiello, M. Bellare and R. Venkatesan.**

Knowledge on the average: perfect, statistical and logarithmic.

Proceedings 27th Annual Symposium on the Theory of Computing, ACM, 1995. -
**M. Bellare, U. Feige and J. Kilian.**

On the role of shared randomness in two prover proof systems.

Proceedings 3rd Israel Symposium on Theory and Computing Systems, IEEE, 1995. -
**M. Bellare, J. Kilian and P. Rogaway.**

The security of the cipher block chaining message authentication code.

Journal of Computer and System Sciences, Vol. 61, No. 3, Dec 2000, pp. 362--399. Earlier version in Advances in Cryptology - Crypto 94 Proceedings, Lecture Notes in Computer Science Vol. 839, Y. Desmedt ed, Springer-Verlag, 1994. -
**M. Bellare, O. Goldreich and S. Goldwasser.**

Incremental cryptography: the case of hashing and signing.

Advances in Cryptology - Crypto 94 Proceedings, Lecture Notes in Computer Science Vol. 839, Y. Desmedt ed, Springer-Verlag, 1994. -
**E. Basturk, M. Bellare, C. S. Chow, and R. Guerin.**

Secure transport protocols for high-speed networks.

IBM Research Report 19981, March, 1994. -
**M. Bellare and P. Rogaway.**

Optimal asymmetric encryption -- How to encrypt with RSA.

Advances in Cryptology - Eurocrypt 94 Proceedings, Lecture Notes in Computer Science Vol. 950, A. De Santis ed, Springer-Verlag, 1995. -
**M. Bellare and J. Rompel.**

Randomness-efficient oblivious sampling.

Proceedings 35th Annual Symposium on the Foundations of Computer Science, IEEE, 1994. -
**M. Bellare and M. Sudan.**

Improved non-approximability results.

Proceedings 26th Annual Symposium on the Theory of Computing, ACM, 1994. -
**M. Bellare and S. Goldwasser.**

The complexity of decision versus search.

SIAM J. on Computing, Vol. 23, No. 1, February 1994. -
**M. Bellare and P. Rogaway.**

Random oracles are practical: A paradigm for designing efficient protocols.

Proceedings First Annual Conference on Computer and Communications Security, ACM, 1993. -
**M. Bellare and P. Rogaway.**

Entity Authentication and key distribution

Advances in Cryptology - Crypto 93 Proceedings, Lecture Notes in Computer Science Vol. 773, D. Stinson ed, Springer-Verlag, 1994. -
**M. Bellare and O. Goldreich.**

On defining proofs of knowledge.

Advances in Cryptology - Crypto 92 Proceedings, Lecture Notes in Computer Science Vol. 740, E. Brickell ed, Springer-Verlag, 1993. -
**M. Bellare and P. Rogaway.**

The complexity of approximating a nonlinear program.

Journal of Mathematical Programming B, Vol. 69, No. 3, pp. 429-441, September 1995. Also in Complexity of Numerical Optimization, ed. P. M. Pardalos, World Scientific, 1993. -
**M. Bellare.**

Interactive proofs and approximation: reductions from two provers in one round.

Proceedings 2nd Israel Symposium on Theory and Computing Systems, IEEE, 1993. -
**M. Bellare, S. Goldwasser, C. Lund and A. Russell.**

Efficient probabilistically checkable poofs and applications to approximation.

Proceedings 25th Annual Symposium on the Theory of Computing, ACM, 1993. -
**M. Bellare, O. Goldreich and S. Goldwasser.**

Randomness in interactive proofs.

Computational Complexity, Vol. 3, No. 4, 1993, pp. 319--354. -
**M. Bellare and O. Goldreich.**

Proving computational ability.

Manuscript, August 1992. Published in Studies in Complexity and Cryptography, 2011. -
**M. Bellare and M. Yung.**

Certifying permutations: Non-interactive zero-knowledge based on any trapdoor permutation.

Journal of Cryptology Vol. 9, No. 1, pp. 149--166, 1996. -
**M. Bellare.**

A technique for upper bounding the spectral norm, with applications to learning.

Proceedings of the Fifth Annual Workshop on Computational Learning Theory, ACM, 1992. -
**M. Bellare and E. Petrank.**

Making zero-knowledge provers efficient.

Proceedings 24th Annual Symposium on the Theory of Computing, ACM, 1992. **M. Bellare, L. Cowen and S. Goldwasser.**

On the Structure of Secret Key Exchange Protocols.

Distributed Computing and Cryptography, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 2, ACM, 1991.-
**M. Bellare, S. Micali and R. Ostrovsky.**

Perfect Zero-Knowledge in Constant Rounds.

Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990. -
**M. Bellare, S. Micali and R. Ostrovsky.**

The (True) Complexity of Statistical Zero Knowledge.

Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990. **M. Bellare and S. Goldwasser.**

New Paradigms for Digital Signatures and Message Authentication Based on Non-Interative Zero Knowledge Proofs.

Advances in Cryptology - Crypto 89 Proceedings, Lecture Notes in Computer Science Vol. 435, G. Brassard ed, Springer-Verlag, 1989.**M. Bellare and S. Micali.**

Non-Interactive Oblivious Transfer and Spplications.

Advances in Cryptology - Crypto 89 Proceedings, Lecture Notes in Computer Science Vol. 435, G. Brassard ed, Springer-Verlag, 1989.-
**M. Bellare and S. Micali.**

How to sign given any trapdoor permutation.

Journal of the ACM, Vol. 39, No. 1, January 1992, pp. 214--233. The preliminary version of this paper was titled*How to sign given any trapdoor function*, and appeared in the Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988.