Skip to main content
Top

2021 | Book

Public-Key Cryptography – PKC 2021

24th IACR International Conference on Practice and Theory of Public Key Cryptography, Virtual Event, May 10–13, 2021, Proceedings, Part I

insite
SEARCH

About this book

The two-volume proceedings set LNCS 12710 and 12711 constitutes the proceedings of the 24th IACR International Conference on Practice and Theory of Public Key Cryptography, PKC 2021, which was held online during May 10-13, 2021. The conference was originally planned to take place in Edinburgh, UK, but had to change to an online format due to the COVID-19 pandemic.

The 52 papers included in these proceedings were carefully reviewed and selected from 156 submissions. They focus on all aspects of public-key cryptography, covering theory, implementations and applications. This year, post-quantum cryptography, PQC constructions and cryptanalysis received special attention.

Table of Contents

Frontmatter

Post-Quantum Constructions and Cryptanalysis

Frontmatter
QCCA-Secure Generic Key Encapsulation Mechanism with Tighter Security in the Quantum Random Oracle Model
Abstract
Xagawa and Yamakawa (PQCrypto 2019) proved the transformation \(\mathsf {SXY}\) can tightly turn \(\mathsf {DS}\) secure \(\mathsf {PKE}\)s into \(\mathsf {IND}\text {-}\mathsf{qCCA}\) secure \(\mathsf {KEM}\)s in the quantum random oracle model (QROM). But transformations such as \(\mathsf {KC,\ TPunc}\) that turn PKEs with standard security (\(\mathsf {OW}\text {-}\mathsf{CPA}\) or \(\mathsf {IND}\text {-}\mathsf{CPA}\)) into \(\mathsf {DS}\) secure \(\mathsf {PKE}\)s still suffer from quadratic security loss in the QROM. In this paper, we give a tighter security reduction for the transformation \(\mathsf {KC}\) that turns \(\mathsf {OW}\text {-}\mathsf{CPA}\) secure deterministic \(\mathsf {PKE}\)s into modified \(\mathsf {DS}\) secure \(\mathsf {PKE}\)s in the QROM. We use the Measure-Rewind-Measure One-Way to Hiding Lemma recently introduced by Kuchta et al. (EUROCRYPT 2020) to avoid the square-root advantage loss. Moreover, we extend it to the case that underlying \(\mathsf {PKE}\)s are not perfectly correct. Combining with other transformations, we finally obtain a generic \(\mathsf {KEM}\) from any \(\mathsf {IND}\text {-}\mathsf{CPA}\) secure \(\mathsf {PKE}\). Our security reduction has roughly the same tightness as the result of Kuchta et al. without any other assumptions and we achieve the stronger \(\mathsf {IND}\text {-}\mathsf{qCCA}\) security. We also give a similar result for another \(\mathsf {KEM}\) transformation achieving the same security notion from any \(\mathsf {OW}\text {-}\mathsf{CPA}\) secure deterministic \(\mathsf {PKE}\).
Xu Liu, Mingqiang Wang
An Alternative Approach for SIDH Arithmetic
Abstract
In this paper, we present new algorithms for the field arithmetic layers of supersingular isogeny Diffie-Hellman; one of the fifteen remaining candidates in the NIST post-quantum standardization process. Our approach uses a polynomial representation of the field elements together with mechanisms to keep the coefficients within bounds during the arithmetic operations. We present timings and comparisons for SIKEp503 and suggest a novel 736-bit prime that offers a \(1.17\times \) speedup compared to SIKEp751 for a similar level of security.
Cyril Bouvier, Laurent Imbert
The Convergence of Slide-Type Reductions
Abstract
In this work, we apply the dynamical systems analysis of Hanrot et al. (CRYPTO’11) to a class of lattice block reduction algorithms that includes (natural variants of) slide reduction and block-Rankin reduction. This implies sharper bounds on the polynomial running times (in the query model) for these algorithms and opens the door to faster practical variants of slide reduction. We give heuristic arguments showing that such variants can indeed speed up slide reduction significantly in practice. This is confirmed by experimental evidence, which also shows that our variants are competitive with state-of-the-art reduction algorithms.
Michael Walter
On the Success Probability of Solving Unique SVP via BKZ
Abstract
As lattice-based key encapsulation, digital signature, and fully homomorphic encryption schemes near standardisation, ever more focus is being directed to the precise estimation of the security of these schemes. The primal attack reduces key recovery against such schemes to instances of the unique Shortest Vector Problem (uSVP). Dachman-Soled et al. (Crypto 2020) recently proposed a new approach for fine-grained estimation of the cost of the primal attack when using Progressive BKZ for lattice reduction. In this paper we review and extend their technique to BKZ 2.0 and provide extensive experimental evidence of its accuracy. Using this technique we also explain results from previous primal attack experiments by Albrecht et al. (Asiacrypt 2017) where attacks succeeded with smaller than expected block sizes. Finally, we use our simulators to reestimate the cost of attacking the three lattice KEM finalists of the NIST Post Quantum Standardisation Process.
Eamonn W. Postlethwaite, Fernando Virdia
Two-Round n-out-of-n and Multi-signatures and Trapdoor Commitment from Lattices
Abstract
Although they have been studied for a long time, distributed signature protocols have garnered renewed interest in recent years in view of novel applications to topics like blockchains. Most recent works have focused on distributed versions of ECDSA or variants of Schnorr signatures, however, and in particular, little attention has been given to constructions based on post-quantum secure assumptions like the hardness of lattice problems. A few lattice-based threshold signature and multi-signatureschemes have been proposed in the literature, but they either rely on hash-and-sign lattice signatures (which tend to be comparatively inefficient), use expensive generic transformations, or only come with incomplete security proofs.
In this paper, we construct several lattice-based distributed signing protocols with low round complexity followingthe Fiat–Shamir with Aborts (FSwA) paradigm of Lyubashevsky (Asiacrypt 2009). Our protocols can be seen as distributed variants of the fast Dilithium-G signature scheme and the full security proof can be made assuming the hardness of module SIS and LWE problems. A key step to achieving security (unexplained in some earlier papers) is to prevent the leakage that can occur when parties abort after their first message—which can inevitably happen in the Fiat–Shamir with Aborts setting. We manage to do so using homomorphic commitments.
Exploiting the similarities between FSwA and Schnorr-style signatures, our approach makes the most of observations from recent advancements in the discrete log setting, such as Drijvers et al.’s seminal work on two-round multi-signatures (S&P 2019). In particular, we observe that the use of commitment not only resolves the subtle issue with aborts, but also makes it possible to realize secure two-round n-out-of-n distributed signing and multi-signature in the plain public key model, by equipping the commitment with a trapdoor feature. The construction of suitable trapdoor commitment from lattices is a side contribution of this paper.
Ivan Damgård, Claudio Orlandi, Akira Takahashi, Mehdi Tibouchi
Isogeny-Based Key Compression Without Pairings
Abstract
SIDH/SIKE-style protocols benefit from key compression to minimize their bandwidth requirements, but proposed key compression mechanisms rely on computing bilinear pairings. Pairing computation is a notoriously expensive operation, and, unsurprisingly, it is typically one of the main efficiency bottlenecks in SIDH key compression, incurring processing time penalties that are only mitigated at the cost of trade-offs with precomputed tables. We address this issue by describing how to compress isogeny-based keys without pairings. As a bonus, we also substantially reduce the storage requirements of other operations involved in key compression.
Geovandro C. C. F. Pereira, Paulo S. L. M. Barreto
Analysis of Multivariate Encryption Schemes: Application to Dob
Abstract
In this paper, we study the effect of two modifications to multivariate public key encryption schemes: internal perturbation (ip), and \(Q_+\). Focusing on the Dob encryption scheme, a construction utilising these modifications, we accurately predict the number of degree fall polynomials produced in a Gröbner basis attack, up to and including degree five. The predictions remain accurate even when fixing variables. Based on this new theory we design a novel attack on the Dob encryption scheme, which breaks Dob using the parameters suggested by its designers.
While our work primarily focuses on the Dob encryption scheme, we also believe that the presented techniques will be of particular interest to the analysis of other big–field schemes.
Morten Øygarden, Patrick Felke, Håvard Raddum
On the Integer Polynomial Learning with Errors Problem
Abstract
Several recent proposals of efficient public-key encryption are based on variants of the polynomial learning with errors problem (PLWE\(^f\)) in which the underlying polynomial ring \(\mathbb {Z}_q[x]/f\) is replaced with the (related) modular integer ring \(\mathbb {Z}_{f(q)}\); the corresponding problem is known as Integer Polynomial Learning with Errors (I-PLWE\(^f\)). Cryptosystems based on I-PLWE\(^f\) and its variants can exploit optimised big-integer arithmetic to achieve good practical performance, as exhibited by the ThreeBears cryptosystem. Unfortunately, the average-case hardness of I-PLWE\(^f\) and its relation to more established lattice problems have to date remained unclear.
We describe the first polynomial-time average-case reductions for the search variant of I-PLWE\(^f\), proving its computational equivalence with the search variant of its counterpart problem PLWE\(^f\). Our reductions apply to a large class of defining polynomials f. To obtain our results, we employ a careful adaptation of Rényi divergence analysis techniques to bound the impact of the integer ring arithmetic carries on the error distributions. As an application, we present a deterministic public-key cryptosystem over integer rings. Our cryptosystem, which resembles ThreeBears, enjoys one-way (OW-CPA) security provably based on the search variant of I-PLWE\(^f\).
Julien Devevey, Amin Sakzad, Damien Stehlé, Ron Steinfeld
Shorter Lattice-Based Zero-Knowledge Proofs via One-Time Commitments
Abstract
There has been a lot of recent progress in constructing efficient zero-knowledge proofs for showing knowledge of an \(\vec {\varvec{s}}\) with small coefficients satisfying \(\varvec{A}\vec {\varvec{s}}=\vec {\varvec{t}}\). For typical parameters, the proof sizes have gone down from several megabytes to a bit under 50KB (Esgin et al., Asiacrypt 2020). These are now within an order of magnitude of the sizes of lattice-based signatures, which themselves constitute proof systems which demonstrate knowledge of something weaker than the aforementioned equation. One can therefore see that this line of research is approaching optimality. In this paper, we modify a key component of these proofs, as well as apply several other tweaks, to achieve a further reduction of around \(30\%\) in the proof output size. We also show that this savings propagates itself when these proofs are used in a general framework to construct more complex protocols.
Vadim Lyubashevsky, Ngoc Khanh Nguyen, Gregor Seiler
Multivariate Public Key Cryptosystem from Sidon Spaces
Abstract
A Sidon space is a subspace of an extension field over a base field in which the product of any two elements can be factored uniquely, up to constants. This paper proposes a new a public-key cryptosystem of the multivariate type which is based on Sidon spaces, and has the potential to remain secure even if quantum supremacy is attained. This system, whose security relies on the hardness of the well-known MinRank problem, is shown to be resilient to several straightforward algebraic attacks. In particular, it is proved that the two popular attacks on the MinRank problem, the kernel attack and the minor attack, succeed only with exponentially small probability. The system is implemented in software, and its hardness is demonstrated experimentally.
Netanel Raviv, Ben Langton, Itzhak Tamo
Banquet: Short and Fast Signatures from AES
Abstract
This work introduces Banquet, a digital signature scheme with post-quantum security, constructed using only symmetric-key primitives. The design is based on the MPC-in-head paradigm also used by Picnic (CCS 2017) and BBQ (SAC 2019). Like BBQ, Banquet uses only standardized primitives, namely AES and SHA-3, but signatures are more than 50% shorter, making them competitive with Picnic (which uses a non-standard block cipher to improve performance). The MPC protocol in Banquet uses a new technique to verify correctness of the AES S-box computations, which is efficient because the cost is amortized with a batch verification strategy. Our implementation and benchmarks also show that both signing and verification can be done in under 10ms on a current x64 CPU. We also explore the parameter space to show the range of trade-offs that are possible with the Banquet design, and show that Banquet can nearly match the signature sizes possible with Picnic (albeit with slower, but still practical run times) or have speed within a factor of two of Picnic (at the cost of larger signatures).
Carsten Baum, Cyprien Delpech de Saint Guilhem, Daniel Kales, Emmanuela Orsini, Peter Scholl, Greg Zaverucha

Cryptographic Primitives and Schemes

Frontmatter
Improving Revocation for Group Signature with Redactable Signature
Abstract
Group signature is a major cryptographic tool allowing anonymous access to a service. However, in practice, access to a service is usually granted for some periods of time, which implies that the signing rights must be deactivated the rest of the time. This requirement thus calls for complex forms of revocation, reminiscent of the concept of time-bound keys. However, schemes implementing this concept are rare and only allow revocation with limited granularity. That is, signing keys are associated with an expiry time and become definitively useless once the latter has passed.
In this paper, we revisit the notion of group signatures with time-bound keys with several contributions. Firstly, we extend this notion to allow high granularity revocation: a member’s signing key can in particular be deactivated at some moments and then be automatically reinstated. Secondly, we show that this complex property is actually simple to achieve using redactable signature. In particular, we consider in this context a recent redactable signature scheme from PKC 20 that we improve by dramatically reducing the size of the public key. The resulting construction is of independent interest.
Olivier Sanders
Bootstrapping Fully Homomorphic Encryption over the Integers in Less than One Second
Abstract
One can bootstrap LWE-based fully homomorphic encryption (FHE) schemes in less than one second, but bootstrapping AGCD-based FHE schemes, also known as FHE over the integers, is still very slow. In this work we propose a fast bootstrapping method for FHE over the integers, closing thus this gap between these two types of schemes. We use a variant of the AGCD problem to construct a new GSW-like scheme that can natively encrypt polynomials, then, we show how the single-gate bootstrapping method proposed by Ducas and Micciancio (EUROCRYPT 2015) can be adapted to FHE over the integers using our scheme, and we implement a bootstrapping that, using around 400 MB of key material, runs in less than one second in a common personal computer.
Hilder Vitor Lima Pereira
Group Signatures with User-Controlled and Sequential Linkability
Abstract
Group signatures allow users to create signatures on behalf of a group while remaining anonymous. Such signatures are a powerful tool to realize privacy-preserving data collections, where e.g., sensors, wearables or vehicles can upload authenticated measurements into a data lake. The anonymity protects the user’s privacy yet enables basic data processing of the uploaded unlinkable information. For many applications, full anonymity is often neither desired nor useful though, and selected parts of the data must eventually be correlated after being uploaded. Current solutions of group signatures do not provide such functionality in a satisfactory way: they either rely on a trusted party to perform opening or linking of signatures, which clearly conflicts with the core privacy goal of group signatures; or require the user to decide upon the linkability of signatures before they are generated.
In this paper we propose a new variant of group signatures that provides linkability in a flexible and user-centric manner. Users – and only they – can decide before and after signature creation whether they should remain linkable or be correlated. To prevent attacks where a user omits certain signatures when a sequence of events in a certain section (e.g., time frame), should be linked, we further extend this new primitive to allow for sequential link proofs. Such proofs guarantee that the provided sequence of data is not only originating from the same signer, but also occurred in that exact order and contains all of the user’s signatures within the time frame. We formally define the desired security and privacy properties, propose a provably secure construction based on DL-related assumptions and report on a prototypical implementation of our scheme.
Jesus Diaz, Anja Lehmann
Impossibility on Tamper-Resilient Cryptography with Uniqueness Properties
Abstract
In this work, we show negative results on the tamper-resilience of a wide class of cryptographic primitives with uniqueness properties, such as unique signatures, verifiable random functions, signatures with unique keys, injective one-way functions, and encryption schemes with a property we call unique-message property. Concretely, we prove that for these primitives, it is impossible to derive their (even extremely weak) tamper-resilience from any common assumption, via black-box reductions. Our proofs exploit the simulatable attack paradigm proposed by Wichs (ITCS ’13), and the tampering model we treat is the plain model, where there is no trusted setup.
Yuyu Wang, Takahiro Matsuda, Goichiro Hanaoka, Keisuke Tanaka
Rate-1 Key-Dependent Message Security via Reusable Homomorphic Extractor Against Correlated-Source Attacks
Abstract
In this work, we first present general methods to construct information rate-1 PKE that is \(\mathsf {KDM}^{(n)}\)-secure with respect to block-affine functions for any unbounded polynomial n. To achieve this, we propose a new notion of extractor that satisfies reusability, homomorphic, and security against correlated-source attacks, and show how to use this extractor to improve the information rate of the \(\mathsf {KDM}\)-secure PKE of Brakerski et al. (Eurocrypt 18). Then, we show how to amplify \(\mathsf {KDM}\) security from block-affine function class into general bounded size circuits via a variant of the technique of Applebaum (Eurocrypt 11), achieving better efficiency. Furthermore, we show how to generalize these approaches to the IBE setting.
Additionally, our PKE and IBE schemes are also leakage resilient, with leakage rates \(1-o(1)\) against a slightly smaller yet still general class – block leakage functions. We can instantiate the required building blocks from \(\mathsf {LWE}\) or \(\mathsf {DDH}\).
Qiqi Lai, Feng-Hao Liu, Zhedong Wang
Two-Party Adaptor Signatures from Identification Schemes
Abstract
Adaptor signatures are a novel cryptographic primitive with important applications for cryptocurrencies. They have been used to construct second layer solutions such as payment channels or cross-currency swaps. The basic idea of an adaptor signature scheme is to tie the signing process to the revelation of a secret value in the sense that, much like a regular signature scheme, an adaptor signature scheme can authenticate messages, but simultaneously leaks a secret to certain parties. Recently, Aumayr et al. provide the first formalization of adaptor signature schemes, and present provably secure constructions from ECDSA and Schnorr signatures. Unfortunately, the formalization and constructions given in this work have two limitations: (1) current schemes are limited to ECDSA and Schnorr signatures, and no generic transformation for constructing adaptor signatures is known; (2) they do not offer support for aggregated two-party signing, which can significantly reduce the blockchain footprint in applications of adaptor signatures.
In this work, we address these two shortcomings. First, we show that signature schemes that are constructed from identification (ID) schemes, which additionally satisfy certain homomorphic properties, can generically be transformed into adaptor signature schemes. We further provide an impossibility result which proves that unique signature schemes (e.g., the BLS scheme) cannot be transformed into an adaptor signature scheme. In addition, we define two-party adaptor signature schemes with aggregatable public keys and show how to instantiate them via a generic transformation from ID-based signature schemes. Finally, we give instantiations of our generic transformations for the Schnorr, Katz-Wang and Guillou-Quisquater signature schemes.
Andreas Erwig, Sebastian Faust, Kristina Hostáková, Monosij Maitra, Siavash Riahi
Compact Zero-Knowledge Proofs for Threshold ECDSA with Trustless Setup
Abstract
Threshold ECDSA signatures provide a higher level of security to a crypto wallet since it requires more than t parties out of n parties to sign a transaction. The state-of-the-art bandwidth efficient threshold ECDSA used the additive homomorphic Castagnos and Laguillaumie (CL) encryption based on an unknown order group G, together with a number of zero-knowledge proofs in G. In this paper, we propose compact zero-knowledge proofs for threshold ECDSA to lower the communication bandwidth, as well as the computation cost. The proposed zero-knowledge proofs include the discrete-logarithm relation in G and the well-formedness of a CL ciphertext.
When applied to two-party ECDSA, we can lower the bandwidth of the key generation algorithm by 47%, and the running time for the key generation and signing algorithms are boosted by about 35% and 104% respectively. When applied to threshold ECDSA, our first scheme is more optimized for the key generation algorithm (about 70% lower bandwidth and 85% faster computation in key generation, at a cost of 20% larger bandwidth in signing), while our second scheme has an all-rounded performance improvement (about 60% lower bandwidth, 46% faster computation in key generation without additional cost in signing).
Tsz Hon Yuen, Handong Cui, Xiang Xie
Universal Proxy Re-Encryption
Abstract
We put forward the notion of universal proxy re-encryption (UPRE). A UPRE scheme enables a proxy to convert a ciphertext under a (delegator) public key of any existing public-key encryption (PKE) scheme into another ciphertext under a (delegatee) public key of any existing PKE scheme (possibly different from the delegator one). The proxy has a re-encryption key generated from the delegator’s secret key and the delegatee public key. Thus UPRE generalizes proxy re-encryption by supporting arbitrary PKE schemes and allowing to convert ciphertexts into ones of possibly different PKE schemes. In this work, we
  • provide syntax and definitions for both UPRE and a variant we call relaxed UPRE. The relaxed variant means that decryption algorithms for re-encrypted ciphertexts are slightly modified but still only use the original delegatee secret keys for decryption.
  • construct a UPRE based on probabilistic indistinguishability obfuscation (PIO). It allows us to re-encrypt ciphertexts polynomially many times.
  • construct relaxed UPRE from garbled circuits (GCs). We provide two variants of this construction, one which allows us to re-encrypt ciphertexts polynomially many times, and a second one which satisfies a stronger security requirement but only allows us to re-encrypt ciphertexts a constant number of times.
Nico Döttling, Ryo Nishimaki
Master-Key KDM-Secure ABE via Predicate Encoding
Abstract
In this paper, we propose the first generic framework for attribute-based encryptions (ABE) with master-secret-key-dependent-message security (mKDM security) for affine functions via predicate encodings by Chen, Gay and Wee [Eurocrypt 2015]. The construction is adaptively secure under standard k-Lin assumption in prime-order bilinear groups. By this, we obtain a set of new mKDM-secure ABE schemes with high expressiveness that have never been reached before: we get the first hierarchical IBE (HIBE) scheme and the first ABE scheme for arithmetic branching program (ABP) with mKDM security for affine functions. Thanks to the expressiveness (more concretely, delegability like HIBE), we can obtain mKDM-secure ABE against chosen-ciphertext attack (i.e., CCA security) via a classical CPA-to-CCA transformation that works well in the context of mKDM.
Shengyuan Feng, Junqing Gong, Jie Chen
Exact Lattice Sampling from Non-Gaussian Distributions
Abstract
We propose a new framework for (trapdoor) sampling over lattices. Our framework can be instantiated in a number of ways. It allows for example to sample from uniform, affine and “product affine” distributions. Another salient point of our framework is that the output distributions of our samplers are perfectly indistinguishable from ideal ones, in contrast with classical samplers that are statistically indistinguishable. One caveat of our framework is that all our current instantiations entail a rather large standard deviation.
Maxime Plançon, Thomas Prest
Efficient Adaptively-Secure IB-KEMs and VRFs via Near-Collision Resistance
Abstract
We construct more efficient cryptosystems with provable security against adaptive attacks, based on simple and natural hardness assumptions in the standard model. Concretely, we describe:
  • An adaptively-secure variant of the efficient, selectively-secure LWE-based identity-based encryption (IBE) scheme of Agrawal, Boneh, and Boyen (EUROCRYPT 2010). In comparison to the previously most efficient such scheme by Yamada (CRYPTO 2017) we achieve smaller lattice parameters and shorter public keys of size \(\mathcal {O} (\log \lambda )\), where \(\lambda \) is the security parameter.
  • Adaptively-secure variants of two efficient selectively-secure pairing-based IBEs of Boneh and Boyen (EUROCRYPT 2004). One is based on the DBDH assumption, has the same ciphertext size as the corresponding BB04 scheme, and achieves full adaptive security with public parameters of size only \(\mathcal {O} (\log \lambda )\). The other is based on a \(q \)-type assumption and has public key size \(\mathcal {O} (\lambda )\), but a ciphertext is only a single group element and the security reduction is quadratically tighter than the corresponding scheme by Jager and Kurek (ASIACRYPT 2018).
  • A very efficient adaptively-secure verifiable random function where proofs, public keys, and secret keys have size \(\mathcal {O} (\log \lambda )\).
As a technical contribution we introduce blockwise partitioning, which leverages the assumption that a cryptographic hash function is weak near-collision resistant to prove full adaptive security of cryptosystems.
Tibor Jager, Rafael Kurek, David Niehues
Subversion-Resilient Public Key Encryption with Practical Watchdogs
Abstract
Restoring the security of maliciously implemented cryptosystems has been widely considered challenging due to the fact that the subverted implementation could arbitrarily deviate from the official specification. Achieving security against adversaries that can arbitrarily subvert implementations seems to inherently require trusted component assumptions and/or architectural properties. At ASIACRYPT 2016, Russell et al. proposed an attractive model where a watchdog is used to test and approve individual components of an implementation before or during deployment. Such a detection-based strategy has been useful for designing various cryptographic schemes that are provably resilient to subversion.
We consider Russell et al.’s watchdog model from a practical perspective regarding watchdog efficiency. We find that the asymptotic definitional framework, while permitting strong positive theoretical results, does not yet guarantee practical watchdogs, due to the fact that the running time of a watchdog is only bounded by an abstract polynomial. Hence, in the worst case, the running time of the watchdog might exceed the running time of the adversary, which seems impractical for most applications. We adopt Russell et al.’s watchdog model to the concrete security setting and design the first subversion-resilient public-key encryption scheme which allows for extremely efficient watchdogs with only linear running time.
At the core of our construction is a new variant of a combiner for key encapsulation mechanisms (KEMs) by Giacon et al. (PKC’18). We combine this construction with a new subversion-resilient randomness generator that also can be checked by an efficient watchdog, even in constant time, which could be of independent interest for the design of other subversion-resilient cryptographic schemes. Our work thus shows how to apply Russell et al.’s watchdog model to design subversion-resilient cryptography with efficient watchdogs. We insist that this work does not intend to show that the watchdog model outperforms other defense approaches, but to demonstrate that practical watchdogs are practically achievable.
Pascal Bemmann, Rongmao Chen, Tibor Jager
Non-interactive CCA2-Secure Threshold Cryptosystems: Achieving Adaptive Security in the Standard Model Without Pairings
Abstract
We consider threshold public-key encryption, where the decryption servers distributively hold the private key shares, and we need a threshold of these servers to decrypt the message (while the system remains secure when less than the threshold is corrupt). We investigate the notion of chosen-ciphertext secure threshold systems which has been historically hard to achieve. We further require the systems to be, both, adaptively secure (i.e., secure against a strong adversary making corruption decisions dynamically during the protocol), and non-interactive (i.e., where decryption servers do not interact amongst themselves but rather efficiently contribute, each, a single message). To date, only pairing-based implementations were known to achieve security in the standard security model without relaxation (i.e., without assuming the random oracle idealization) under the above stringent requirements. Here, we investigate how to achieve the above using other assumptions (in order to understand what other algebraic building blocks and mathematical assumptions are needed to extend the domain of encryption methods achieving the above). Specifically, we show realizations under the Decision Composite Residuosity (\(\mathsf {DCR}\)) and Learning-With-Errors (\(\mathsf {LWE}_{}\)) assumptions.
Julien Devevey, Benoît Libert, Khoa Nguyen, Thomas Peters, Moti Yung
Updatable Signatures and Message Authentication Codes
Abstract
Cryptographic objects with updating capabilities have been proposed by Bellare, Goldreich and Goldwasser (CRYPTO’94) under the umbrella of incremental cryptography. They have recently seen increased interest, motivated by theoretical questions (Ananth et al., EC’17) as well as concrete practical motivations (Lehmann et al., EC’18; Groth et al. CRYPTO’18; Klooß et al., EC’19). In this work, the form of updatability we are particularly interested in is that primitives are key-updatable and allow to update “old” cryptographic objects, e.g., signatures or message authentication codes, from the “old” key to the updated key at the same time without requiring full access to the new key (i.e., only via a so-called update token).
Inspired by the rigorous study of updatable encryption by Lehmann and Tackmann (EC’18) and Boyd et al. (CRYPTO’20), we introduce a definitional framework for updatable signatures (USs) and message authentication codes (UMACs). We discuss several applications demonstrating that such primitives can be useful in practical applications, especially around key rotation in various domains, as well as serve as building blocks in other cryptographic schemes. We then turn to constructions and our focus there is on ones that are secure and practically efficient. In particular, we provide generic constructions from key-homomorphic primitives (signatures and PRFs) as well as direct constructions. This allows us to instantiate these primitives from various assumptions such as DDH or CDH (latter in bilinear groups), or the (R)LWE and the SIS assumptions. As an example, we obtain highly practical US schemes from BLS signatures or UMAC schemes from the Naor-Pinkas-Reingold PRF.
Valerio Cini, Sebastian Ramacher, Daniel Slamanig, Christoph Striecks, Erkan Tairi
Multi-Client Functional Encryption for Separable Functions
Abstract
In this work, we provide a compiler that transforms a single-input functional encryption scheme for the class of polynomially bounded circuits into a multi-client functional encryption (MCFE) scheme for the class of separable functions. An n-input function f is called separable if it can be described as a list of polynomially bounded circuits \(f^1, \dots , f^n\) s.t. \(f(x_1, \dots , x_n)= f^1(x_1)+ \dots + f^n(x_n)\) for all \(x_1,\dots , x_n\). Our compiler extends the works of Brakerski et al. [Eurocrypt 2016] and of Komargodski et al. [Eurocrypt 2017] in which a generic compiler is proposed to obtain multi-input functional encryption (MIFE) from single-input functional encryption. Our construction achieves the stronger notion of MCFE but for the less generic class of separable functions. Prior to our work, a long line of results has been proposed in the setting of MCFE for the inner-product functionality, which is a special case of a separable function. We also propose a modified version of the notion of decentralized MCFE introduced by Chotard et al. [Asiacrypt 2018] that we call outsourceable mulit-client functional encryption (OMCFE). Intuitively, the notion of OMCFE makes it possible to distribute the load of the decryption procedure among at most n different entities, which will return decryption shares that can be combined (e.g., additively) thus obtaining the output of the computation. This notion is especially useful in the case of a very resource consuming decryption procedure, while the combine algorithm is non-time consuming. We also show how to extend the presented MCFE protocol to obtain an OMCFE scheme for the same functionality class.
Michele Ciampi, Luisa Siniscalchi, Hendrik Waldner
Backmatter
Metadata
Title
Public-Key Cryptography – PKC 2021
Editor
Prof. Juan A. Garay
Copyright Year
2021
Electronic ISBN
978-3-030-75245-3
Print ISBN
978-3-030-75244-6
DOI
https://doi.org/10.1007/978-3-030-75245-3

Premium Partner