talks

2024

1. End-to-End Hybrid Authenticated Key Exchanges

   National Center for Scientific Research "Demokritos" and FORTH Hellas, January 11.

   Abstract

   End-to-end authenticity in public networks plays a significant role. Namely, without authenticity, the adversary might be able to retrieve even confidential information straight away by impersonating others. Proposed solutions to establish an authenticated channel cover pre-shared key-based, password-based, and certificate-based techniques. To add confidentiality to an authenticated channel, authenticated key exchange (AKE) protocols usually have one of the three solutions built in. As an amplification, hybrid AKE (HAKE) approaches are getting more popular nowadays and were presented in several flavors to incorporate classical, post-quantum, or quantum-key-distribution components. The main benefit is redundancy, i.e., if some of the components fail, the primitive still yields a confidential and authenticated channel. However, current HAKE instantiations either rely on pre-shared keys (which yields inefficient end-to-end authenticity) or only support one or two of the three above components (resulting in reduced redundancy and flexibility). In this work, we present an extension of a modular HAKE framework due to Dowling, Brandt Hansen, and Paterson (PQCrypto’20) that does not suffer from the above constraints. While their instantiation, dubbed Muckle, requires pre-shared keys (and hence yields inefficient end-to-end authenticity), our extended instantiation called Muckle+ utilizes post-quantum digital signatures. While replacing pre-shared keys with digital signatures is rather straightforward in general, this turned out to be surprisingly non-trivial when applied to HAKE frameworks (resulting in a significant model change with adapted proof techniques).

2023

1. (Invited) QCI-CAT: Austrian Quantum-Communication Infrastructure

   5G Techritory – Embracing the Quantum Era, October 19.

   Abstract

2. Muckle+: End-to-End Hybrid Authenticated Key Exchanges

   PQCrypto 2023, August 17.

   Abstract

   End-to-end authenticity in public networks plays a significant role. Namely, without authenticity, the adversary might be able to retrieve even confidential information straight away by impersonating others. Proposed solutions to establish an authenticated channel cover pre-shared key-based, password-based, and certificate-based techniques. To add confidentiality to an authenticated channel, authenticated key exchange (AKE) protocols usually have one of the three solutions built in. As an amplification, hybrid AKE (HAKE) approaches are getting more popular nowadays and were presented in several flavors to incorporate classical, post-quantum, or quantum-key-distribution components. The main benefit is redundancy, i.e., if some of the components fail, the primitive still yields a confidential and authenticated channel. However, current HAKE instantiations either rely on pre-shared keys (which yields inefficient end-to-end authenticity) or only support one or two of the three above components (resulting in reduced redundancy and flexibility). In this work, we present an extension of a modular HAKE framework due to Dowling, Brandt Hansen, and Paterson (PQCrypto’20) that does not suffer from the above constraints. While their instantiation, dubbed Muckle, requires pre-shared keys (and hence yields inefficient end-to-end authenticity), our extended instantiation called Muckle+ utilizes post-quantum digital signatures. While replacing pre-shared keys with digital signatures is rather straightforward in general, this turned out to be surprisingly non-trivial when applied to HAKE frameworks (resulting in a significant model change with adapted proof techniques).

3. Muckle+: End-to-End Hybrid Authenticated Key Exchanges

   IEEE P193 Working Group, June 16, 2023.

   Abstract

   End-to-end authenticity in public networks plays a significant role. Namely, without authenticity, the adversary might be able to retrieve even confidential information straight away by impersonating others. Proposed solutions to establish an authenticated channel cover pre-shared key-based, password-based, and certificate-based techniques. To add confidentiality to an authenticated channel, authenticated key exchange (AKE) protocols usually have one of the three solutions built in. As an amplification, hybrid AKE (HAKE) approaches are getting more popular nowadays and were presented in several flavors to incorporate classical, post-quantum, or quantum-key-distribution components. The main benefit is redundancy, i.e., if some of the components fail, the primitive still yields a confidential and authenticated channel. However, current HAKE instantiations either rely on pre-shared keys (which yields inefficient end-to-end authenticity) or only support one or two of the three above components (resulting in reduced redundancy and flexibility). In this work, we present an extension of a modular HAKE framework due to Dowling, Brandt Hansen, and Paterson (PQCrypto’20) that does not suffer from the above constraints. While their instantiation, dubbed Muckle, requires pre-shared keys (and hence yields inefficient end-to-end authenticity), our extended instantiation called Muckle+ utilizes post-quantum digital signatures. While replacing pre-shared keys with digital signatures is rather straightforward in general, this turned out to be surprisingly non-trivial when applied to HAKE frameworks (resulting in a significant model change with adapted proof techniques).

4. (Invited) Muckle+: End-to-End Hybrid Authenticated Key Exchanges

   With Sebastian Ramacher.

   NXP Belgium, May 3, 2023.

   Abstract

   End-to-end authenticity in public networks plays a significant role. Namely, without authenticity, the adversary might be able to retrieve even confidential information straight away by impersonating others. Proposed solutions to establish an authenticated channel cover pre-shared key-based, password-based, and certificate-based techniques. To add confidentiality to an authenticated channel, authenticated key exchange (AKE) protocols usually have one of the three solutions built in. As an amplification, hybrid AKE (HAKE) approaches are getting more popular nowadays and were presented in several flavors to incorporate classical, post-quantum, or quantum-key-distribution components. The main benefit is redundancy, i.e., if some of the components fail, the primitive still yields a confidential and authenticated channel. However, current HAKE instantiations either rely on pre-shared keys (which yields inefficient end-to-end authenticity) or only support one or two of the three above components (resulting in reduced redundancy and flexibility). In this work, we present an extension of a modular HAKE framework due to Dowling, Brandt Hansen, and Paterson (PQCrypto’20) that does not suffer from the above constraints. While their instantiation, dubbed Muckle, requires pre-shared keys (and hence yields inefficient end-to-end authenticity), our extended instantiation called Muckle+ utilizes post-quantum digital signatures. While replacing pre-shared keys with digital signatures is rather straightforward in general, this turned out to be surprisingly non-trivial when applied to HAKE frameworks (resulting in a significant model change with adapted proof techniques).

5. Hybrid Authenticated Key Exchanges: Status-Quo, Novel Constructions, and Applications to Long-Range Quantum-Safe Networks

   9th ETSI/IQC Quantum Safe Cryptography Event, February 13-15, 2023.

   Abstract

   Hybrid Authenticated Key Exchange (HAKE) mechanisms use classical, post-quantum, and QKD-based key elements to establish an authenticated and confidential channel even in the event of cryptographically relevant quantum computers. Notably, such mechanisms can be fault-tolerant, meaning that even if some of the components fail or are turned off, the channel is still authenticated and confidential. HAKE schemes can come in many flavours with a variety of properties and can be adjusted to the application scenario or use case yielding a modular approach to mitigate the transition from non-quantum to quantum-safe systems. Moreover, a novel HAKE instantiation (avoiding the quadratic increase of pre-shared keys in large networks) is presented that allows end-to-end authenticity and confidentially even if two of the three components above fail or are turned off. This could be particularly interesting for upcoming long-range QKD networks such as the EuroQCI. The outline of the presentation is as follows: i) Motivation of hybrid AKE (HAKE) incorporating classical, post-quantum, and QKD mechanism, ii) Presenting the cryptographic concept with a state-of-the-art overview, iii) Enhanced HAKE protocol proposal with end-to-end authentication, and iv) Outlook.

6. (Invited) Hybrid Key Exchanges for End-to-End Security in Quantum-Safe Networks

   IDQ Europe, Workshop: Migration to Quantum-Safe, February 10, 2023.

   Abstract

   End-to-end authenticity in public networks plays a significant role. Namely, without authenticity, the adversary might be able to retrieve even confidential information straight away by impersonating others. Proposed solutions to establish an authenticated channel cover pre-shared key-based, password-based, and certificate-based techniques. To add confidentiality to an authenticated channel, authenticated key exchange (AKE) protocols usually have one of the three solutions built in. As an amplification, hybrid AKE (HAKE) approaches are getting more popular nowadays and were presented in several flavors to incorporate classical, post-quantum, or quantum-key-distribution components. The main benefit is redundancy, i.e., if some of the components fail, the primitive still yields a confidential and authenticated channel. However, current HAKE instantiations either rely on pre-shared keys (which yields inefficient end-to-end authenticity) or only support one or two of the three above components (resulting in reduced redundancy and flexibility). In this work, we present an extension of a modular HAKE framework due to Dowling, Brandt Hansen, and Paterson (PQCrypto’20) that does not suffer from the above constraints. While their instantiation, dubbed Muckle, requires pre-shared keys (and hence yields inefficient end-to-end authenticity), our extended instantiation called Muckle+ utilizes post-quantum digital signatures. While replacing pre-shared keys with digital signatures is rather straightforward in general, this turned out to be surprisingly non-trivial when applied to HAKE frameworks (resulting in a significant model change with adapted proof techniques).

2022

1. (Invited) Efficient Puncturable Encryption – From Bloom Filters to Forward Security

   Chair of Applied Cryptography, Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU), December 9, 2022. (Invited by Dominique Schröder.)

   Abstract

   This talks covers the puncturable-encryption paradigm and particularly the Bloom-filter encryption instantiation.

2. (Invited) Efficient Puncturable Encryption – From Bloom Filters to Forward Security

   Foundation of Cryptography Group, ETH Zurich, September 21, 2022. (Invited by Dennis Hofheinz.)

   Abstract

   This talks covers the puncturable-encryption paradigm and particularly the Bloom-filter encryption instantiation.

3. Puncturable Encryption - A Fine-Grained Approach to Forward Security and More

   Real World Crypto Symposium 2022, Amsterdam, April 13-15.

   Abstract Slides Video

   Forward security is an essential design goal of modern cryptographic protocols with a long body of literature in several application domains such as interactive key-establishment protocols (prominently, in TLS 1.3), digital signatures, search on encrypted data, updatable cryptography, mobile Cloud backups, decentralized contact tracing, new approaches to Tor, and even novel distributed protocols such as Dfinity’s Internet Computer, among others. The well-known benefit of forward security is the mitigation of key leakage by evolving secret keys over epochs and thereby revoking access to prior-epoch ciphertexts. Such a strong security guarantee is highly recognized by industry to be included into security products (e.g., by companies such as Google, Apple, Meta, Microsoft, and Cloudflare), particularly resulting in over 99% of Internet sites surveyed by Qualys SSL Labs (https://www.ssllabs.com/ssl-pulse) support at least some form of forward security at the time of writing. Green and Miers (S&P 2015) initiated the studies of puncturable encryption (PE) as a new cryptographic primitive towards the strong form of non-interactive forward-secure encryption (in particular, without the need of any pre-shared key material). Already several follow-up works showed the versatility of such a concept yielding a rich abstraction of forward security investigated in a variety of (data-in-transit and data-at-rest) application domains such as 0-RTT key exchange with replay protection for TLS (Eurocrypt’17, Eurocrypt’18, Asiacrypt’20, JoC’21), Google’s QUIC (Cans’20), Searchable Encryption (CCS’17, CCS’18, NDSS’21), mobile Cloud backups (OSDI’20), Content Distribution Networks (Financial Crypto’21), Tor (PoPETS’20), and Updatable Encryption (ePrint’21). Loosely speaking, PE is a promising variant of public-key encryption that allows realizing the property of fine-grained and non-interactive forward security with several useful applications. This talk provides an exhausting overview to the concept of PE with motivation, presents state-of-the-art research on PE schemes, and discusses applications (such as 0-RTT key exchange with forward security and replay protection, and forward security for Content Delivery Networks). The overall goal is to make PE more accessible to the general audience and industry in a developer-friendly way, and also presenting new insights and results. The presentation builds on an existing blog post with the same title (https://profet.at/blog/pe).

2021

1. Fine-Grained Forward Secrecy: Allow-List/Deny-List Encryption and Applications

   With Sebastian Ramacher, and Daniel Slamanig.

   Financial Cryptography and Data Security 2021, Virtual, March 1-5.

   Abstract Video

   Forward secrecy is an important feature for modern cryptographic systems and is widely used in secure messaging such as Signal and WhatsApp as well as in common Internet protocols such as TLS, IPSec or SSH. The benefits of forward secrecy is that the damage in case of key-leakage is mitigated. Forward-secret encryption schemes provides security of past ciphertexts even if secret key leaks, which is interesting in settings where cryptographic keys often reside in memory for quite a long time and could be extracted by an adversary, e.g., in cloud computing. The recent concept of puncturable encryption (PE; IEEE S&P’15) provides a versatile generalization of forward-secret encryption: it allows to puncture secret keys with respect to ciphertexts to prevent the future decryption of these ciphertexts. Thus it represents a fine-grained mechanism to restrict decryption capabilities of a secret key to reduce damage in case of key leakage. We introduce the abstraction of allow-list/deny-list encryption schemes, and classify different types of PE schemes using this abstraction. Based on our classification we identify and close a gap in existing work by introducing a novel variant of PE which we dub Dual-Form Puncturable Encryption (DFPE). DFPE significantly enhances and in particular generalizes previous variants of PE, by allowing an interleaved application of allow- and deny-list operations. We present a construction of DFPE in prime order bilinear groups based on the novel primitive of tagged hierarchical identity-based encryption (THIBE). We discuss a direct application of DPFE for enhancing security guarantees within Cloudflare’s Geo Key Manager and show its generic use to construct forward-secret IBE and forward-secret digital signatures.

2. Towards Functional Encryption in the Quantum-Safe Setting and Standardization Efforts

   European Telecommunications Standards Institute (ETSI), Quantum Safe Cryptography Technical Event 2021, Virtual, February 18-19.

   Abstract

   The talk motivates the use of Functional Encryption (FE) as a methodology for fine-grained encryption and secure computation of data. Furthermore, Identity-Based Encryption (IBE) and Attribute-Based Encryption (ABE) as special variants of FE are presented. The talk concludes with standardization efforts and quantum-safeness towards available IBE and ABE schemes.

3. (Invited) Redactable Blockchains

   With Daniel Slamanig.

   TU Vienna, January 2021, Virtual, January 14. (Invited by Matteo Maffei as a single-lecture for the course Cryptocurrencies.)

   Abstract

   The lecture motivates the problem of editing/re-writing blockchains with a focus on the advanced cryptographic tools policy-based chameleon hashing and attribute-based encryption used for redactable blockchains.

2020

1. (Invited, in German) Europäische Standards für das IoT – Security-, Safety-, und Privacy-by-Design

   With Christoph Schmittner..

   Austrian Standards, 4. IoT-Fachkongress 2020, Virtual, November 4.

   Abstract Press 1 Press 2

   The talk presents current technology and standardization work within the EU HORIZON 2020 ECSEL project SECREDAS.

2. (Invited) Attribute-Based Encryption for Strong Access Control: TS 103 532

   European Telecommunications Standards Institute (ETSI), Security Week 2020, 8-19 June 2020, online.

   Abstract Webinar

   Attribute-Based Encryption (ABE) is a cryptographic mechanism that enforces access control solely on the mathematical level with strong security guarantees. A main incentive using ABE is to provide a proper and versatile replacement for software-only access-control mechanisms that need to embed all trust into (often seen to be error-prone) software components by design. Applications of ABE in EU research projects and ETSI TS 103 532 will be presented.

3. Quantum-Safe Identity-Based Encryption: TR 103 618

   European Telecommunications Standards Institute (ETSI), Security Week 2020, 8-19 June 2020, online.

   Abstract Webinar

   As quantum computing poses a threat to the long-term security of most of the currently used encryption mechanisms, ongoing efforts in the development of quantum-safe Identity-Based Encryption (IBE), with a focus on a hierarchical IBE scheme based on structured lattices and described in ETSI TR 103 618, are presented.

4. (Invited) Advanced Public-Key Encryption

   TU Wien 2020, Vienna, Austria. January 28. (Invited by Daniel Slamanig as a single-lecture for the course Modern Cryptography.)

   Abstract Slides

   The lecture recaps advanced public-key encryption ranging from identity-based encryption to attribute-based encryption with security models and constructions.

2019

1. (Invited) Attribute-Based Encryption for Strong Access Control

   Graz Security Days for Industry 2019, Graz, Austria, September 19.

   Abstract

   The talk covers the concept of attribute-based encryption (ABE) and the ABE standardization work done at ETSI towards strong access control.

2. Fine-Grained and Controlled Rewriting in Blockchains: Chameleon-Hashing Gone Attribute-Based

   The Network and Distributed System Security Symposium (NDSS) 2019, San Diego, USA, February 24-27.

   Abstract Slides Video

   Blockchain technologies recently received a considerable amount of attention. While the initial focus was mainly on the use of blockchains in the context of cryptocurrencies such as Bitcoin, application scenarios now go far beyond this. Most blockchains have the property that once some object, e.g., a block or a transaction, has been registered to be included into the blockchain, it is persisted and there are no means to modify it again. While this is an essential feature of most blockchain scenarios, it is still often desirable—at times it may be even legally required–to allow for breaking this immutability in a controlled way. Only recently, Ateniese et al. (EuroS&P 2017) proposed an elegant solution to this problem on the block level. Thereby, the authors replace standard hash functions with so-called chameleon-hashes (Krawczyk and Rabin, NDSS 2000). While their work seems to offer a suited solution to the problem of controlled re-writing of blockchains, their approach is too coarse-grained in that it only offers an all-or-nothing solution. We revisit this idea and introduce the novel concept of policy-based chameleon-hashes (PBCH). PBCHs generalize the notion of chameleon-hashes by giving the party computing a hash the ability to associate access policies to the generated hashes. Anyone who possesses enough privileges to satisfy the policy can then find arbitrary collisions for a given hash. We then apply this concept to transaction-level rewriting within blockchains, and thus support fine-grained and controlled modifiability of blockchain objects. Besides modeling PBCHs, we present a generic construction of PBCHs (using a strengthened version of chameleon-hashes with ephemeral trapdoors which we also introduce), rigorously prove its security, and instantiate it with efficient building blocks. We report first implementation results.

3. (Invited) Advanced Public-Key Encryption

   TU Wien, Vienna, Austria, January 22, 2019. (Invited by Daniel Slamanig as a single-lecture for the course Modern Cryptography.)

   Abstract Slides

   The lecture recapped advanced public-key encryption ranging from identity-based encryption to attribute-based encryption with security models and constructions.

2018

1. Attribute-Based Encryption (ABE) for Access Control and Personal Data Protection

   With François Ambrosini..

   ETSI Webinar, 23 October, 2018.
2. (Invited) Bloom Filter Encryption and Applications to Efficient Forward-Secret 0-RTT Key Exchange

   Royal Holloway, University of London (RHUL) seminar, London, UK, October 18, 2018. (Invited by Martin R. Albrecht.)

   Abstract Slides

   Forward secrecy is considered an essential design goal of modern key establishment (KE) protocols, such as TLS 1.3, for example. Furthermore, efficiency considerations such as zero round-trip time (0-RTT), where a client is able to send cryptographically protected payload data along with the very first KE message, are motivated by the practical demand for secure low-latency communication. For a long time, it was unclear whether protocols that simultaneously achieve 0-RTT and full forward secrecy exist. Only recently, the first forward-secret 0-RTT protocol was described by Günther et al. (EUROCRYPT 2017). It is based on Puncturable Encryption. Forward secrecy is achieved by “puncturing” the secret key after each decryption operation, such that a given ciphertext can only be decrypted once (cf. also Green and Miers, S&P 2015). Unfortunately, their scheme is completely impractical, since one puncturing operation takes between 30 seconds and several minutes for reasonable security and deployment parameters, such that this solution is only a first feasibility result, but not efficient enough to be deployed in practice. In this paper, we introduce a new primitive that we term Bloom Filter Encryption (BFE), which is derived from the probabilistic Bloom filter data structure. We describe different constructions of BFE schemes, and show how these yield new puncturable encryption mechanisms with extremely efficient puncturing. Most importantly, a puncturing operation only involves a small number of very efficient computations, plus the deletion of certain parts of the secret key, which outperforms previous constructions by orders of magnitude. This gives rise to the first forward-secret 0-RTT protocols that are efficient enough to be deployed in practice. We believe that BFE will find applications beyond forward-secret 0-RTT protocols.

3. Revisiting Proxy Re-encryption: Forward Secrecy, Improved Security, and Applications

   PKC 2018, Rio de Janeiro, Brazil, March 25-29.

   Abstract

   We revisit the notion of proxy re-encryption (PRE), an enhanced public-key encryption primitive envisioned by Blaze et al. (Eurocrypt’98) and formalized by Ateniese et al. (NDSS’05) for delegating decryption rights from a delegator to a delegatee using a semi- trusted proxy. PRE notably allows to craft re-encryption keys in order to equip the proxy with the power of transforming ciphertexts under a delegator’s public key to ciphertexts under a delegatee’s public key, while not learning anything about the underlying plaintexts. We study an attractive cryptographic property for PRE, namely that of forward secrecy. In our forward-secret PRE (fs-PRE) definition, the proxy periodically evolves the re-encryption keys and permanently erases old versions while he delegator’s public key is kept constant. As a consequence, ciphertexts for old periods are no longer re-encryptable and, in particular, cannot be decrypted anymore at the delegatee’s end. Moreover, delegators evolve their secret keys too, and, thus, not even they can decrypt old ciphertexts once their key material from past periods has been deleted. This, as we will discuss, directly has application in short-term data/message-sharing scenarios. Technically, we formalize fs-PRE. Thereby, we identify a subtle but significant gap in the well-established security model for conventional PRE and close it with our formalization (which we dub fs-PRE+). We present the first provably secure and efficient constructions of fs-PRE as well as PRE (implied by the former) satisfying the strong fs-PRE+ and PRE+ notions, respectively. All our constructions are instantiable in the standard model under standard assumptions and our central build- ing block are hierarchical identity-based encryption (HIBE) schemes that only need to be selectively secure.

2015

1. Confined guessing: a reduction strategy to obtain new signatures from standard assumptions

   NTT, Tokyo, Japan, September, 2015.

   Abstract Slides

   We put forward new techniques for designing signature schemes. As a result, we present practical signature schemes based on the CDH, the RSA, and the SIS assumptions. Our schemes compare favorably with existing schemes based on these assumptions. Our core idea is the use of tag-based signatures. Concretely, each signatures contains a tag which is uniformly chosen from a suitable tag set. Intuitively, the tag provides a way to embed instances of computational problems. Indeed, carefully choosing these tag spaces provides new ways to partition the set of possible message-tag pairs into "signable" and "unsignable" pairs. In our security proof, we will thus be able to sign all adversarially requested messages, and at the same time use an adversarially generated forgery with suitably large probability

2014

1. A Generic View on Trace-and-Revoke Broadcast Encryption Schemes

   CT-RSA 2014 - The Cryptographer’s Track at the RSA Conference 2014, San Francisco, CA, USA, February 25-28.

   Abstract

   At Eurocrypt 2011, Wee presented a generalization of threshold public key encryption, threshold signatures, and revocation schemes arising from threshold extractable hash proof systems. In particular, he gave instances of his generic revocation scheme from the DDH assumption (which led to the Naor-Pinkas revocation scheme), and from the factoring assumption (which led to a new revocation scheme). We expand on Wee’s work in two directions: (a) We propose threshold extractable hash proof instantiations from the “Extended Decisional Diffie-Hellman” (EDDH) assumption due to Hemenway and Ostrovsky (PKC 2012). This in particular yields EDDH-based variants of threshold public key encryption, threshold signatures, and revocation schemes. In detail, this yields a DCR-based revocation scheme. (b) We show that our EDDH-based revocation scheme allows for a mild form of traitor tracing (and, thus, yields a new trace-and-revoke scheme). In particular, compared to Wee’s factoring-based scheme, our DCR-based scheme has the advantage that it allows to trace traitors.

2. Programmable Hash Functions in the Multilinear Setting

   Rhine Neckar Crypto Seminar, 2014.

   Abstract

   We adapt the concept of a programmable hash function (PHF, Crypto 2008) to a setting in which a multilinear map is available. This enables new PHFs with previously unachieved parameters. To demonstrate their usefulness, we show how our (standard-model) PHFs can replace random oracles in several well-known cryptographic constructions. Namely, we obtain standard-model versions of the Boneh-Franklin identity-based encryption scheme, the Boneh-Lynn-Shacham signature scheme, and the Sakai-Ohgishi-Kasahara identity-based non- interactive key exchange (ID-NIKE) scheme. The ID-NIKE scheme is the first scheme of its kind in the standard model. Our abstraction also allows to derive hierarchical versions of the above schemes in settings with multilinear maps. This in particular yields simple and efficient hierarchical generalizations of the BF, BLS, and SOK schemes. In the case of hierarchical ID-NIKE, ours is the first such scheme with full security, in either the random oracle model or the standard model. While our constructions are formulated with respect to a generic multilinear map, we also outline the necessary adaptations required for the recent “noisy” multilinear map candidate due to Garg, Gentry, and Halevi.

2013

1. Practical Signatures from Standard Assumptions

   EUROCRYPT 2013, Athens, Greece, May 29.

   Abstract

   We put forward new techniques for designing signature schemes. As a result, we present practical signature schemes based on the CDH, the RSA, and the SIS assumptions. Our schemes compare favorably with existing schemes based on these assumptions. Our core idea is the use of tag-based signatures. Concretely, each signatures contains a tag which is uniformly chosen from a suitable tag set. Intuitively, the tag provides a way to embed instances of computational problems. Indeed, carefully choosing these tag spaces provides new ways to partition the set of possible message-tag pairs into "signable" and "unsignable" pairs. In our security proof, we will thus be able to sign all adversarially requested messages, and at the same time use an adversarially generated forgery with suitably large probability.