International Association
for Cryptologic Research

Functional Encryption (FE) has been widely studied in the last decade, as it provides a very useful tool for restricted access to sensitive data: from a ciphertext, it allows specific users to learn a function of the underlying plaintext. In practice, many users may be interested in the same function on the data, say the mean value of the inputs, for example. The conventional definition of FE associates each function to a secret decryption functional key and therefore all the users get the same secret key for the same function. This induces an important problem: if one of these users (called a traitor) leaks or sells the decryption functional key to be included in a pirate decryption tool, then there is no way to trace back its identity. Our objective is to solve this issue by introducing a new primitive, called Traceable Functional Encryption: the functional decryption key will not only be specific to a function, but to a user too, in such a way that if some users collude to produce a pirate decoder that successfully evaluates a function on the plaintext, from the ciphertext only, one can trace back at least one of them.

We propose a concrete solution for Inner Product Functional Encryption (IPFE). We first remark that the ElGamal-based IPFE from Abdalla et. al. in PKC '15 shares many similarities with the Boneh-Franklin traitor tracing from CRYPTO '99. Then, we can combine these two schemes in a very efficient way, with the help of pairings, to obtain a Traceable IPFE with black-box confirmation.

The Legendre PRF relies on the conjectured pseudorandomness properties of the Legendre symbol with a hidden shift. Originally proposed as a PRG by Damgård at CRYPTO 1988, it was recently suggested as an efficient PRF for multiparty computation purposes by Grassi et al. at CCS 2016. Moreover, the Legendre PRF is being considered for usage in the Ethereum 2.0 blockchain.

This paper improves previous attacks on the Legendre PRF and its higher-degree variant due to Khovratovich by reducing the time complexity from $\mathcal{O}(p\log{p}/M)$ to $\mathcal{O}(p\log^2{p}/M^2)$ Legendre symbol evaluations when $M \le \sqrt[4]{p}$ queries are available. The practical relevance of our improved attack is demonstrated by breaking two concrete instances of the PRF proposed by the Ethereum foundation. Furthermore, we generalize our attack in a nontrivial way to the higher-degree variant of the Legendre PRF and we point out a large class of weak keys for this construction.

Lastly, we provide the first security analysis of two additional generalizations of the Legendre PRF originally proposed by Damgård in the PRG setting, namely the Jacobi PRF and the power residue PRF.

Modern key exchange protocols are usually based on the Diffie–Hellman (DH) primitive. The beauty of this primitive, among other things, is its potential reusage of key shares: DH shares can be either used once as an ephemeral key or used in multiple runs as a (semi-)static key. Since DH-based protocols are insecure against quantum adversaries, alternative solutions have to be found when moving to the post-quantum setting. However, most post-quantum candidates, including schemes based on lattices and even supersingular isogeny DH, are not known to be secure under key reuse. In particular, this means that they cannot be necessarily deployed as an immediate DH substitute in protocols.

In this paper, we introduce the notion of a split key encapsulation mechanism (split KEM) to translate the desired properties of a DH-based protocol, namely contributiveness and key-reusability, to a KEM-based protocol flow. We provide the relevant security notions of split KEMs and show that the formalism lends itself to lift Signal’s X3DH to the post-quantum KEM setting. While the proposed framework conceptually solves the raised issues, we did not succeed in providing a strongly-secure, post- quantum instantiation of a split KEM yet. The intention of this paper hence is to raise further awareness of the challenges arising when moving to KEM-based key exchange protocols with contributiveness and key-resusability, and to enable others to start investigating potential solutions.

We introduce a new technique for building multivariate encryption schemes based on random linear codes. The construction is versatile, naturally admitting multiple modifications. Among these modifications is an interesting embedding modifier--- any efficiently invertible multivariate system can be embedded and used as part of the inversion process. In particular, even small scale secure multivariate signature schemes can be embedded producing reasonably efficient encryption schemes. Thus this technique offers a bridge between multivariate signatures, many of which have remained stable and functional for many years, and multivariate encryption, a historically more troubling area.

The disruptive blockchain technology is expected to have broad applications in many areas due to its advantages of transparency, fault tolerance, and decentralization, but the open nature of blockchain also introduces severe privacy issues. Since anyone can deduce private information about relevant accounts, different privacy-preserving techniques have been proposed for cryptocurrencies under the UTXO model, e.g., Zerocash and Monero. However, it is more challenging to protect privacy for account-model blockchains (e.g., Ethereum) since it is much easier to link accounts in the account-model blockchain. In this paper, we propose BlockMaze, an efficient privacy-preserving account-model blockchain based on zk-SNARKs. Along with dual-balance model, BlockMaze achieves strong privacy guaran- tees by hiding account balances, transaction amounts, and linkage between senders and recipients. Moreover, we provide formal security definitions and prove the security of BlockMaze. Finally, we implement a prototype of BlockMaze based on Libsnark and Go-Ethereum, and conduct extensive experiments to evaluate its performance. The experiment results demonstrate BlockMaze has high efficiency in computation and transaction throughput.

In a Conditional Disclosure of Secrets (CDS) a verifier V wants to reveal a message m to a prover P conditioned on the fact that x is an accepting instance of some NP-language L. An honest prover (holding the corresponding witness w) always obtains the message m at the end of the interaction. On the other hand, if x is not in L we require that no PPT P* can learn the message m. We introduce laconic CDS, a two round CDS protocol with optimal computational cost for the verifier V and optimal communication cost. More specifically, the verifier's computation and overall communication grows with poly(|x|,\lambda,log(T)), where \lambda is the security parameter and T is the verification time for checking that x is in L (given w). We obtain constructions of laconic CDS under standard assumptions, such as CDH or LWE. Laconic CDS serves as a powerful tool for "maliciousifying" semi-honest protocols while preserving their computational and communication complexities. To substantiate this claim, we consider the setting of non-interactive secure computation: Alice wants to publish a short digest corresponding to a private large input x on her web page such that (possibly many) Bob, with a private input y, can send a short message to Alice allowing her to learn C(x,y) (where C is a public circuit). The protocol must be reusable in the sense that Bob can engage in arbitrarily many executions on the same digest. In this context we obtain the following new implications.

(1) UC Secure Bob-optimized 2PC: We obtain a UC secure protocol where Bob's computational cost and the communication cost of the protocol grows with poly(|x|,|y|,\lambda, d), where d is the depth of the computed circuit C.

(2) Malicious Laconic Function Evaluation: Next, we move on to the setting where Alice's input x is large. For this case, UC secure protocols must have communication cost growing with x. Thus, with the goal of achieving better efficiency, we consider a weaker notion of malicious security. For this setting, we obtain a protocol for which Bob's computational cost and the communication cost of the protocol grows with poly(|y|,\lambda, d), where d is the depth of the computed circuit C.

In this paper we develop a number of generic techniques and algorithms in spectral analysis of large linear approximations for use in cryptanalysis. We apply the developed tools for cryptanalysis of ZUC-256 and give a distinguishing attack with complexity around $2^{236}$. Although the attack is only $2^{20}$ times faster than exhaustive key search, the result indicates that ZUC-256 does not provide a source with full 256-bit entropy in the generated keystream, which would be expected from a 256-bit key. To the best of our knowledge, this is the first known academic attack on full ZUC-256 with a computational complexity that is below exhaustive key search.

Particular instantiations of the Offset Merkle Damgaard authenticated encryption scheme (OMD) represent highly secure alternatives for AES-GCM. It is already a fact that OMD can be efficiently implemented in software. Given this, in our paper we focus on speeding-up OMD in hardware, more precisely on FPGA platforms. Thus, we propose a new OMD instantiation based on the compression function of BLAKE2b. Moreover, to the best of our knowledge, we present the first FPGA implementation results for the SHA-512 instantiation of OMD as well as the first architecture of an online authenticated encryption system based on OMD.

Secure distance measurement and therefore secure Time-of-Arrival (ToA) measurement is critical for applications such as contactless payments, passive-keyless entry and start systems, and navigation systems. This paper initiates the study of Message Time of Arrival Codes (MTACs) and their security. MTACs represent a core primitive in the construction of systems for secure ToA measurement. By surfacing MTACs in this way, we are able for the first time to formally define the security requirements of physical-layer measures that protect ToA measurement systems against attacks. Our viewpoint also enables us to provide a unified presentation of existing MTACs (such as those proposed in distance-bounding protocols and in a secure distance measurement standard) and to propose basic principles for protecting ToA measurement systems against attacks that remain unaddressed by existing mechanisms. We also use our perspective to systematically explore the tradeoffs between security and performance that apply to all signal modulation techniques enabling ToA measurements.

Mobile autonomous systems, robots, and cyber-physical systems rely on accurate positioning information. To conduct distance-measurement, two devices exchange signals and, knowing these signals propagate at the speed of light, the time of arrival is used for distance estimations. Existing distance- measurement techniques are incapable of protecting against adversarial distance enlargement—a highly devastating tactic in which the adversary reissues a delayed version of the signals transmitted between devices, after distorting the authentic signal to prevent the receiver from identifying it. The adversary need not break crypto, nor compromise any upper- layer security protocols for mounting this attack. No known solution currently exists to protect against distance enlargement. We present Ultra-Wideband Enlargement Detection (UWB-ED), a new modulation technique to detect distance enlargement attacks, and securely verify distances between two mutually trusted devices. We analyze UWB-ED under an adversary that injects signals to block/modify authentic signals. We show how UWB-ED is a good candidate for 802.15.4z Low Rate Pulse and the 5G standard.

Event date: 3 December to 7 December 2019
Submission deadline: 10 July 2019
Notification: 7 August 2019

Event date: 2 December to 4 December 2019

Event date: 30 June to 4 July 2020
Submission deadline: 25 February 2020
Notification: 27 April 2020

In blockchain space, there are elaborate proof-of-stake based protocols with some assumptions related to clock synchronization, i.e.~that all of them know the current time of the protocol. However, this assumption is satisfied by relying on the security of centralized systems such as Network Time Protocol (NTP) or Global Positioning System (GPS). Clearly, any attack on these systems (which happened in the past) can cause corruption of blockchains that rely on the clock that they provide. To solve this problem in the nature of the decentralized network, we first define a general universally composable (GUC) model that captures the notion of consensus on a clock. Simply, a consensus clock is a clock that is agreed upon by honest parties by considering the clocks of all parties. In the end, we give a simple but useful protocol relying on a blockchain network. Our protocol is secure according to our new model. It can be used by full nodes of a blockchain who need to have a common time notion to preserve the correctness and the security of the blockchain protocol. One advantage of our protocol is that it does not cause any extra communication overhead on the underlying blockchain protocol.

This work studies message authentication code (MAC) schemes supporting variable tag lengths. We provide a formalisation of such a scheme. Several variants of the classical Wegman-Carter MAC scheme are considered. Most of these are shown to be insecure by pointing out detailed attacks. One of these schemes is highlighted and proved to be secure. We further build on this scheme to obtain single-key nonce-based variable tag length MAC schemes utilising either a stream cipher or a short-output pseudo-random function. These schemes can be efficiently instantiated using practical well known primitives. We further consider the problem of building variable tag length MAC schemes without nonces. Again, efficient constructions of such schemes are described along with their proofs of security.

With the proliferation of data and emerging data-driven applications, how to perform data analytical operations while respecting privacy concerns has become a very interesting research topic. With the advancement of communication and computing technologies, e.g. the FoG computing concept and its associated Edge computing technologies, it is now appealing to deploy decentralized data-driven applications. Following this trend, in this paper, we investigate privacy-preserving singular value decomposition (SVD) solutions tailored for these new computing environments. We first analyse a privacy-preserving SVD solution by Chen et al., which is based on the Paillier encryption scheme and some heuristic randomization method. We show that (1) their solution leaks statistical information to an individual player in the system; (2) their solution leaks much more information when more than one players collude. Based on the analysis, we present a new solution, which distributes the SVD results into two different players in a privacy-preserving manner. In comparison, our solution minimizes the information leakage to both individual player and colluded ones, via randomization and threshold homomorphic encryption techniques.

The cloud changed the way we manage and store data. Today, cloud storage services offer clients an infrastructure that allows them a convenient source to store, replicate, and secure data online. However, with these new capabilities also come limitations, such as lack of transparency, limited decentralization, and challenges with privacy and security. And, as the need for more agile, private and secure data solutions continues to grow exponentially, rethinking the current structure of cloud storage is mission-critical for enterprises. By leveraging and building upon blockchain’s unique attributes, including immutability, security to the data element level, distributed (no single point of failure), we have developed a solution prototype that allows data to be reliably stored while simultaneously being secured, with tamper-evident auditability, via blockchain. The result, Audita, is a flexible solution that assures data protection and solves for challenges such as scalability and privacy. Audita works via an augmented blockchain network of participants that include storage-nodes and block-creators. In addition, it provides an automatic and fair challenge system to assure that data is distributed and reliably and provably stored. While the prototype is built on Quorum, the solution framework can be used with any blockchain platform. The benefit is a system that is built to grow along with the data needs of enterprises, while continuing to build the network via incentives and solving for issues such as auditing, outsourcing and malicious users.

In the setting of secure multiparty computation (MPC), a set of mutually distrusting parties wish to jointly compute a function, while guaranteeing the privacy of their inputs and the correctness of the output. An MPC protocol is called fully secure if no adversary can prevent the honest parties from obtaining their outputs. A protocol is called fair if an adversary can prematurely abort the computation, however, only before learning any new information.

We present highly efficient transformations from fair computations to fully secure computations, assuming the fraction of honest parties is constant (e.g., 1% of the parties are honest). Compared to previous transformations that require linear invocations (in the number of parties) of the fair computation, our transformations require super-logarithmic, and sometimes even super-constant, such invocations. The main idea is to delegate the computation to chosen random committees that invoke the fair computation. Apart from the benefit of uplifting security, the reduction in the number of parties is also useful, since only committee members are required to work, whereas the remaining parties simply "listen" to the computation over a broadcast channel.

One application of these transformations is a new $\delta$-bias coin-flipping protocol, whose round complexity has a super-logarithmic dependency on the number of parties, improving over the protocol of Beimel, Omri, and Orlov (Crypto 2010) that has a linear dependency. A second application is a new fully secure protocol for computing the Boolean OR function, with a super-constant round complexity, improving over the protocol of Gordon and Katz (TCC 2009) whose round complexity is linear in the number of parties.

Finally, we show that our positive results are in a sense optimal, by proving that for some functionalities, a super-constant number of (sequential) invocations of the fair computation is necessary for computing the functionality in a fully secure manner.

Kyber is a KEM based their security on the Modular Learning with Errors problem and was selected in the second round of NIST Post-quantum standardization process. Before we put Kyber into practical application, it is very important to assess its security in hard practical conditions especially when the Fujisaki-Okamoto transformations are neglected. In this paper, we propose an efficient key mismatch attacks on Kyber, which can recover one participant's secret key if the public key is reused. We first define the oracles in which the adversary is able to launch the attacks. Then, we show that by accessing the oracle multiple times, the adversary is able to recover the coefficients in the secret key. Furthermore, we propose two strategies to reduce the queries and time in recovering the secret key. It turns out that it is actually much easier to use key mismatch attacks to break Kyber than NewHope, another NIST second round candidate, due to their different design structures. Our implementations have demonstrated the efficiency of the proposed attacks and verified our findings. Another interesting observation from the attack is that in the most powerful Kyber-1024, it is easier to recover each coefficient compared with that in Kyber-512 and Kyber-768. Specifically, for Kyber-512 on average we recover each coefficient with $2.7$ queries, while in Kyber-1024 and 768, we only need $2.4$ queries. This demonstrates further that implementations of LWE based schemes in practice is very delicate.

Wildcard identity-based encryption (WIBE) allows a sender to simultaneously encrypt messages to a group of users matching a certain pattern, defined as a sequence of identifiers and wildcards. We propose a novel scalable wildcarded identity-based encryption, called SWIBE, which reduces the ciphertext size to be constant. To the best of our knowledge, SWIBE is the first wildcard identity-based encryption scheme that generates a constant size ciphertext regardless of the depth of the identities with fast decryption. The proposed scheme improves the decryption time. According to our experiment results, decryption of the SWIBE scheme is 3, 10, and 650 times faster than existing WIBE, WW-IBE, and CCP-ABE schemes. The SWIBE scheme also subsumes the generalized key derivation naturally by allowing wildcards in the key delegation process. We prove CPA security of the proposed scheme and extend it to be CCA secure.