International Association
for Cryptologic Research

We consider the theoretically-sound selection of cryptographic parameters, such as the size of algebraic groups or RSA keys, for TLS 1.3 in practice. While prior works gave security proofs for TLS 1.3, their security loss is quadratic in the total number of sessions across all users, which due to the pervasive use of TLS is huge. Therefore, in order to deploy TLS 1.3 in a theoretically-sound way, it would be necessary to compensate this loss with unreasonably large parameters that would be infeasible for practical use at large scale. Hence, while these previous works show that in principle the design of TLS 1.3 is secure in an asymptotic sense, they do not yet provide any useful concrete security guarantees for real-world parameters used in practice. In this work, we provide a new security proof for the cryptographic core of TLS 1.3, which reduces the security of TLS 1.3 tightly (that is, with constant security loss) to the (multi-user) security of its building blocks. For some building blocks, such as the symmetric record layer encryption scheme, we can then rely on prior work to establish tight security. For others, such as the RSA-PSS digital signature scheme currently used in TLS 1.3, we obtain at least a linear loss in the number of users, independent of the number of sessions, which is much easier to compensate with reasonable parameters. Our work also shows that by replacing the RSA-PSS scheme with a tightly-secure scheme (e. g., in a future TLS version), one can obtain the first fully tightly-secure TLS protocol. Our results enable a theoretically-sound selection of parameters for TLS 1.3, even in large-scale settings with many users and sessions per user.

Secret sharing enables a dealer to split a secret into a set of shares, in such a way that certain authorized subsets of share holders can reconstruct the secret, whereas all unauthorized subsets cannot. Non-malleable secret sharing (Goyal and Kumar, STOC 2018) additionally requires that, even if the shares have been tampered with, the reconstructed secret is either the original or a completely unrelated one.

In this work, we construct non-malleable secret sharing tolerating p-time joint-tampering attacks in the plain model (in the computational setting), where the latter means that, for any p>0 fixed {\em a priori}, the attacker can tamper with the same target secret sharing up to p times. In particular, assuming one-to-one one-way functions, we obtain:

- A secret sharing scheme for threshold access structures which tolerates joint p-time tampering with subsets of the shares of maximal size ({\em i.e.}, matching the privacy threshold of the scheme). This holds in a model where the attacker commits to a partition of the shares into non-overlapping subsets, and keeps tampering jointly with the shares within such a partition (so-called {\em selective partitioning}).

- A secret sharing scheme for general access structures which tolerates joint p-time tampering with subsets of the shares of size $O(\sqrt{\log n})$, where n is the number of parties. This holds in a stronger model where the attacker is allowed to adaptively change the partition within each tampering query (so-called {\em adaptive partitioning}).

At the heart of our result for selective partitioning lies a new technique showing that every one-time {\em statistically} non-malleable secret sharing against joint tampering is in fact {\em leakage-resilient} non-malleable ({\em i.e.},\ the attacker can leak jointly from the shares prior to tampering). We believe this may be of independent interest, and in fact we show it implies lower bounds on the share size and randomness complexity of statistically non-malleable secret sharing against {\em independent} tampering.

Accumulators provide compact representations of large sets and enjoy compact membership witnesses. Besides constant-size witnesses, public-key accumulators provide efficient updates of both the accumulator itself and the witness; however, they come with two drawbacks: they require a trusted setup and -- without knowledge of the secret trapdoors -- their performance is not practical for real-world applications with large sets. Recent improvements in the area of secure multi-party computation allow us to replace the trusted setup with a distributed generation of the public parameters.

In this paper, we introduce multi-party public-key accumulators dubbed dynamic linear secret-shared accumulators. We present versions of dynamic public-key accumulators in bilinear groups giving access to more efficient witness generation and update algorithms that utilize the shares of the secret trapdoors sampled by the parties generating the public parameters.Specifically, for the $t$-SDH-based accumulators, we provide a maliciously-secure variant sped up by a secure multi-party computation (MPC) protocol (IMACC'19) built on top of SPDZ. For this scheme, a performant proof-of-concept implementation is provided, which substantiates the practicability of public-key accumulators in this setting. With our implementation in two MPC frameworks, MP-SPDZ and FRESCO, we obtain more efficient accumulators for both medium-sized ($2^{10}$) and large ($2^{14}$ and above) accumulated sets.

Finally, we explore applications of dynamic linear secret-shared accumulators to revocations schemes of group signatures and credentials system. In particular, we consider it as part of Sovrin's system for anonymous credentials where credentials are issued by the a foundation of trusted nodes. Hence, our accumulators naturally fit this setting.

Pedersen commitments have been adopted by several cryptocurrencies for hiding transaction amounts. While Pedersen commitments are perfectly hiding in isolation, the cryptocurrency transaction rules can reveal relationships between the amounts hidden in the commitments involved in the transaction. Such relationships can be combined with the public coin creation schedule to provide upper bounds on the number of coins in a commitment. In this paper, we consider the Grin cryptocurrency and derive upper bounds on the number of coins which can be present in regular transaction outputs. In a March 2020 snapshot of the Grin blockchain, we find that out of the 110,149 unspent regular transaction outputs 983 of them have less than 1800 grin (number of coins typically minted in half an hour) stored in them. On the other hand, 95% of the unspent regular transaction outputs in the snapshot have an upper bound which is at least 90% of the total Grin supply at their respective block heights. We conclude that while our method does not violate the confidentiality of the amounts in most of the outputs on the Grin blockchain, the amounts in some outputs can be estimated to be in a narrow range.

This paper exposes a new vulnerability and introducesa corresponding attack, the NoneXistent Name ServerAttack (NXNSAttack), that disrupts and may paralyzethe DNS system making it difficult or impossible for In-ternet users to access websites, web e-mail, online videochats, or any other online resource. The NXNSAttackgenerates a storm of packets between DNS resolvers andDNS authoritative name servers. The storm is producedby the response of resolvers to unrestricted referral re-sponse messages of authoritative name servers. Theattack is significantly more destructive than NXDomainattacks (e.g., the Mirai attack): i) It reaches an am-plification factor of more than 1620x on the numberof packets exchanged by the recursive resolver. ii) Inaddition to the negative cache, the attack also satu-rates the ‘NS’ resolver caches. To mitigate the attackimpact, we propose an enhancement to the recursiveresolver algorithm, MaxFetch(k), that prevents unnec-essary proactive fetches. We implemented MaxFetch(1)mitigation enhancement on a BIND resolver and testedit on real-world DNS query datasets. Our results showthat MaxFetch(1) degrades neither the recursive resolverthroughput nor its latency. Following the discovery of theattack, a responsible disclosure procedure was carriedout, and several DNS vendors and public providers haveissued a CVE and patched their systems.

Privacy-preserving machine learning (PPML) has many applications, from medical image evaluation and anomaly detection to financial analysis. nGraph-HE (Boemer et al., Computing Frontiers'19) enables data scientists to perform private inference of deep learning (DL) models trained using popular frameworks such as TensorFlow. nGraph-HE computes linear layers using the CKKS homomorphic encryption (HE) scheme (Cheon et al., ASIACRYPT'17), and relies on a client-aided model to compute non-polynomial activation functions, such as MaxPool and ReLU, where intermediate feature maps are sent to the data owner to compute activation functions in the clear. This approach leaks the feature maps, from which it may be possible to deduce the DL model weights. As a result, the client-aided model may not be suitable for deployment when the DL model is intellectual property. In this work, we present MP2ML, a machine learning framework which integrates nGraph-HE and the secure two-party computation framework ABY (Demmler et al., NDSS'15), to overcome the limitations of the client-aided model. We introduce a novel scheme for the conversion between CKKS and secure multi-party computation (MPC) to execute DL inference while maintaining the privacy of both the input data and model weights. MP2ML is compatible with popular DL frameworks such as TensorFlow that can infer pre-trained neural networks with native ReLU activations. We benchmark MP2ML on the CryptoNets network with ReLU activations, on which it achieves a throughput of 33.3 images/s and an accuracy of 98.6%. This throughput matches the previous state-of-the-art for hybrid HE-MPC networks from GAZELLE (Juvekar et al., USENIX'18), even though our protocol is more accurate and scalable than GAZELLE.

Nowadays, the resistance against algebraic attacks and fast algebraic attacks are considered as an important cryptographic property for Boolean functions used in stream ciphers. Both attacks are very powerful analysis concepts and can be applied to symmetric cryptographic algorithms used in stream ciphers. The notion of algebraic immunity has received wide attention since it is a powerful tool to measure the resistance of a Boolean function to standard algebraic attacks. Nevertheless, an algebraic tool to handle the resistance to fast algebraic attacks is not clearly identified in the literature. In the current paper, we propose a new parameter to measure the resistance of a Boolean function to fast algebraic attack. We also introduce the notion of fast immunity profile and show that it informs both on the resistance to standard and fast algebraic attacks. Further, we evaluate our parameter for two secondary constructions of Boolean functions. Moreover, A coding-theory approach to the characterization of perfect algebraic immune functions is presented. Via this characterization, infinite families of binary linear complementary dual codes (or LCD codes for short) are obtained from perfect algebraic immune functions. The binary LCD codes presented in this paper have applications in armoring implementations against so-called side-channel attacks (SCA) and fault non-invasive attacks, in addition to their applications in communication and data storage systems.

Secret sharing is a very useful way to maintain secrecy of private data when stored in a distributed way among several nodes. Two significant questions in this area are 1. how to accommodate new nodes and assign shares to the new nodes, the problem becomes harder if the number of joining nodes or the access structure is not known in advance and can be (potentially) unbounded and 2. to reduce the computational complexity of secret sharing schemes. In this paper we propose two new constructions of such secret sharing schemes based on different combinatorial structures. The first construction is based on generalized paths joining the opposite vertices of a hypercube which has been divided into smaller hypercubes. The second construction is a forest- based construction utilizing a dynamic data structure technique known as fractional cascading. The generalized path we call a pavement is new to this paper. Both our constructions use a new secret redistribution scheme to assign and re-assign shares to nodes. Towards the second question we show that allowing certain trade-offs, the constructions are implementable by $AC^0$ circuits which is the lowest complexity class in which secret sharing and reconstruction is possible. To the best of the knowledge of the authors, none of the similar existing schemes (evolving or dynamic) are $AC^0$ computable and this paper for the first time combines the idea of hypercubes and dynamic data structures with secret sharing for preserving long-term confidentiality of secret data.

The common approach in secure channel protocols is to rely on ciphertexts arriving in-order and to close the connection upon any rogue ciphertext. Cryptographic security models for channels generally reflect such design. This is reasonable when running atop lower-level transport protocols like TCP ensuring in-order delivery, as for example is the case with TLS or SSH. However, channels such as QUIC or DTLS which run over a non-reliable transport protocol like UDP, do not---and in fact cannot---close the connection if packets are lost or arrive in a different order. Those protocols instead have to carefully catch effects arising naturally in unreliable networks, usually by using a sliding-window technique where ciphertexts can be decrypted correctly as long as they are not misplaced too far.

To accommodate such handling of unreliable network messages, we introduce a generalized notion of robustness of cryptographic channels. This property can capture unreliable network behavior and guarantees that adversarial tampering cannot hinder ciphertexts that can be decrypted correctly from being accepted. We show that robustness is orthogonal to the common notion of integrity for channels, but together with integrity and chosen-plaintext security it provides a robust analogue of chosen-ciphertext security of channels. We then discuss two particularly interesting targets, namely the packet encryption in the record layer protocols of QUIC and of DTLS 1.3. We show that both protocols achieve the intended level of robust chosen-ciphertext security based on certain properties of their sliding-window techniques and on the underlying AEAD schemes. Notably, the robustness needed in handling unreliable network messages require both record layer protocols to tolerate repeated adversarial forgery attempts, which means we can only establish non-tight security bounds (in terms of AEAD integrity). Our bounds have led the responsible IETF working groups to introduce concrete forgery limits for both protocol drafts.

As the fault based analysis techniques are becoming more and more powerful, there is a need to streamline the existing tools for better accuracy and ease of use. In this regard, we propose a machine learning assisted tool that can be used in the context of a differential fault analysis. In particular, finding the exact fault location by analyzing the XORed output of a stream cipher/ stream cipher based design is somewhat non-trivial. Traditionally, Pearson's correlation coefficient is used for this purpose. We show that a machine learning method is more powerful than the existing correlation coefficient, aside from being simpler to implement. As a proof of concept, we take two variants of Grain-128a (namely a stream cipher, and a stream cipher with authentication), and demonstrate that machine learning can outperform correlation with the same training/testing data. Our analysis shows that the machine learning can be considered as a replacement for the correlation in the future research works.

Physically unclonable function (PUF) is a technology to generate a device-unique identifier using process variation. PUF enables a cryptographic key that appears only when the chip is active, providing an efficient countermeasure against reverse-engineering attacks. In this paper, we explore the data conversion that digitizes a physical quantity representing PUF’s uniqueness into a numerical value as a new attack surface. We focus on time-to-digital converter (TDC) that converts time duration into a numerical value. We show the first signal injection attack on a TDC by manipulating its clock, and verify it through experiments on an off-the-shelf TDC chip. Then, we show how to leverage the attack to reveal a secret key protected by a PUF that uses a TDC for digitization.

In this short trivial note we argue that, assuming Generalized Continuum Hypothesis to be true, it is impractical to use encryption with $Key \in \{ 0, 1 \}^K$ and $Message \in \{ 0, 1 \}^M$ such that $\aleph_0 \leqslant \mathrm{card}\,K < \mathrm{card}\,M$, because "complexity" of the known-plaintext bruteforce attack equals "complexity" of a single $En/Decrypt(Key, Message)$ "computation" then.

We define and study a new cryptographic primitive, named One-One Constrained Pseudorandom Functions. In this model there are two parties, Alice and Bob, that hold a common random string $K$, where Alice in addition holds a predicate $f:[N] \rightarrow \{ 0,1 \}$ and Bob in addition holds an input $x \in [N]$. We then let Alice generate a key $K_f$ based on $f$ and $K$, and let Bob evaluate a value $K_x$ based on $x$ and $K$. We consider a third party that sees the values $(x,f,K_f)$ and the goal is to allow her to reconstruct $K_x$ whenever $f(x)=1$, while keeping $K_x$ pseudorandom whenever $f(x)=0$. This primitive can be viewed as a relaxation of constrained PRFs, such that there is only a single key query and a single evaluation query.

We focus on the information-theoretic setting, where the one-one cPRF has perfect correctness and perfect security. Our main results are as follows.

1. A Lower Bound. We show that in the information-theoretic setting, any one-one cPRF for punctured predicates is of exponential complexity (and thus the lower bound meets the upper bound that is given by a trivial construction). This stands in contrast with the well known GGM-based punctured PRF from OWF, which is in particular a one-one cPRF. This also implies a similar lower bound for all NC1.

2. New Constructions. On the positive side, we present efficient information-theoretic constructions of one-one cPRFs for a few other predicate families, such as equality predicates, inner-product predicates, and subset predicates. We also show a generic AND composition lemma that preserves complexity.

3. An Amplification to standard cPRF. We show that all of our one-one cPRF constructions can be amplified to a standard (single-key) cPRF via any key-homomorphic PRF that supports linear computations. More generally, we suggest a new framework that we call the double-key model which allows to construct constrained PRFs via key-homomorphic PRFs.

4. Relation to CDS. We show that one-one constrained PRFs imply conditional disclosure of secrets (CDS) protocols.

We believe that this simple model can be used to better understand constrained PRFs and related cryptographic primitives, and that further applications of one-one constrained PRFs and our double-key model will be found in the future, in addition to those we show in this paper.

Proxy re-encryption (PRE), formalized by Blaze et al. in 1998, allows a proxy entity to delegate the decryption right of a ciphertext from one party to another without obtaining the information of the plaintext. In recent years, many studies have explored how to construct PRE schemes that support fine-grained access control for complex application scenarios, such as identity-based PRE and attribute-based PRE. Besides, in order to achieve more flexible access control, the predicate proxy re-encryption (PPRE) is further studied. However, existing PPRE is restricted with the inner product predicate function. Therefore, how to realize the PPRE of arbitrary predicate function is still a problem to be solved. In this manuscript, we propose a secure generic construction of predicate proxy key re-encapsulation mechanism built from a ``linear'' predicate key encapsulation mechanism. Since the secure key encapsulation mechanism can be used as a building block to construct public key encryption, we can obtain a PPRE from our construction. As a result, the results open up new avenues for building more flexible and fine-grained PPRE.

We develop two variants of Cocks' identity-based encryption. One variant has faster encryption which is as efficient as RSA encryption. The other variant makes the first variant anonymous under suitable complexity assumptions, while its decryption efficiency is about twice lower than the first one. Both the variants have ciphertext expansion twice larger than the original Cocks' identity-based encryption.

Auditing a secure multiparty computation (MPC) protocol entails the validation of the protocol transcript by a third party that is otherwise untrusted. In this work we introduce the concept of end-to-end verifiable MPC (VMPC), that requires the validation to provide a correctness guarantee even in the setting that all servers, trusted setup primitives and all the client systems utilized by the input-providing users of the MPC protocol are subverted by an adversary. To instantiate VMPC, we introduce a new concept in the setting of zero-knowlegde protocols that we term crowd verifiable zero-knowledge (CVZK). A CVZK protocol enables a prover to convince a set of verifiers about a certain statement, even though each one individually contributes a small amount of entropy for verification and some of them are adversarially controlled. Given CVZK, we present a VMPC protocol that is based on discrete-logarithm related assumptions. At the high level of adversity that VMPC is meant to withstand, it is infeasible to ensure perfect correctness, thus we investigate the classes of functions and verifiability relations that are feasible in our framework, and present a number of possible applications the underlying functions of which can be implemented via VMPC.

We study the rational behaviors of participants in committee-based blockchains. Committee-based blockchains rely on specific blockchain consensus that must be guaranteed in presence of rational participants. We consider a simplified blockchain consensus algorithm based on existing or proposed committee-based blockchains that encapsulates the main actions of the participants: voting for a block, and checking its validity. Knowing that those actions have costs, and achieving the consensus gives rewards to committee members, we study using game theory how strategic players behave while trying to maximizing their gains. We consider different reward schemes, and found that in each setting, there exist equilibria where blockchain consensus is guaranteed; in some settings however, there can be coordination failures hindering consensus. Moreover, we study equilibria with trembling participants, which is a novelty in the context of committee-based blockchains. Trembling participants are rational that can do unintended actions with a low probability. We found that in presence of trembling participants, there exist equilibria where blockchain consensus is guaranteed; however, when only voters are rewarded, there also exist equilibria where validity can be violated.

Token-curated registries (TCRs) are a mechanism by which a set of users are able to jointly curate a reputable list about real-world information. Entries in the registry may have any form, so this primitive has been proposed for use -- and deployed -- in a variety of decentralized applications, ranging from the simple joint creation of lists to helping to prevent the spread of misinformation online. Despite this interest, the security of this primitive is not well understood, and indeed existing constructions do not achieve strong or provable notions of security or privacy. In this paper, we provide a formal cryptographic treatment of TCRs as well as a construction that provably hides the votes cast by individual curators. Along the way, we provide a model and proof of security for an underlying voting scheme, which may be of independent interest.

Recent studies have suggested various side-channel attacks for eavesdropping sound by analyzing the side effects of sound waves on nearby objects (e.g., a bag of chips and window) and devices (e.g., motion sensors). These methods pose a great threat to privacy, however they are limited in one of the following ways: they (1) cannot be applied in real time (e.g., Visual Microphone), (2) are not external, requiring the attacker to compromise a device with malware (e.g., Gyrophone), or (3) are not passive, requiring the attacker to direct a laser beam at an object (e.g., laser microphone). In this paper, we introduce "Lamphone," a novel side-channel attack for eavesdropping sound; this attack is performed by using a remote electro-optical sensor to analyze a hanging light bulb’s frequency response to sound. We show how fluctuations in the air pressure on the surface of the hanging bulb (in response to sound), which cause the bulb to vibrate very slightly (a millidegree vibration), can be exploited by eavesdroppers to recover speech and singing, passively, externally, and in real time. We analyze a hanging bulb’s response to sound via an electro-optical sensor and learn how to isolate the audio signal from the optical signal. Based on our analysis, we develop an algorithm to recover sound from the optical measurements obtained from the vibrations of a light bulb and captured by the electro-optical sensor. We evaluate Lamphone’s performance in a realistic setup and show that Lamphone can be used by eavesdroppers to recover human speech (which can be accurately identified by the Google Cloud Speech API) and singing (which can be accurately identified by Shazam and SoundHound) from a bridge located 25 meters away from the target room containing the hanging light bulb.

We give a lattice reduction algorithm that achieves root Hermite factor $k^{1/(2k)}$ in time $k^{k/8 + o(k)}$ and polynomial memory. This improves on the previously best known enumeration-based algorithms which achieve the same quality, but in time $k^{k/(2e) + o(k)}$. A cost of $k^{k/8 + o(k)}$ was previously mentioned as potentially achievable (Hanrot-Stehlé'10) or as a heuristic lower bound (Nguyen'10) for enumeration algorithms. We prove the complexity and quality of our algorithm under a heuristic assumption and provide empirical evidence from simulation and implementation experiments attesting to its performance for practical and cryptographic parameter sizes. Our work also suggests potential avenues for achieving costs below $k^{k/8 + o(k)}$ for the same root Hermite factor, based on the geometry of SDBKZ-reduced bases.