International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News

Updates on the COVID-19 situation are on the Announcement channel.

Here you can see all recent updates to the IACR webpage. These updates are also available:

email icon
via email
RSS symbol icon
via RSS feed
Twitter bird icon
via Twitter
Weibo icon
via Weibo
Facebook icon
via Facebook

28 May 2020

Jason H. M. Ying, Shuwei Cao, Geong Sen Poh, Jia Xu, Hoon Wei Lim
ePrint Report ePrint Report
Private Set Intersection (PSI) enables two parties, each holding a private set to securely compute their intersection without revealing other information. This paper considers settings of secure statistical computations over PSI, where both parties hold sets containing identifiers with one of the parties having an additional positive integer value associated with each of the identifiers in her set. The main objective is to securely compute some desired statistics of the associated values for which its corresponding identifiers occur in the intersection of the two sets. This is achieved without revealing the identifiers of the set intersection. This has many useful business applications, for examples in measuring effectiveness of advertising campaigns. In many cases, the parties wish to know various statistical information with regards to the set intersection and the associated integer values. For instance, information relating to arithmetic mean, geometric mean, harmonic mean, standard deviation, minimum, maximum, range or an approximate distribution of the sum composition. A potential use case is for a credit card company to provide the percentage of high spending to a shopping mall based on their common customers. Therefore, in this paper we introduce various mechanisms to enable secure computation of statistical functions, which we collectively termed PSI-Stats. The proposed protocols maintain strong privacy guarantee, that is computations are performed without revealing the identifiers of the set intersection to both parties. Implementations of our constructions are also carried out based on a simulated dataset as well as on actual datasets in the business use cases that we defined, in order to demonstrate practicality of our solution. To the best of our knowledge, our work is the first non-circuit-based type which enables parties to learn more about the set intersection via secure computations over a wide variety of statistical functions, without requiring the machinery of fully homomorphic encryption.
Expand
Yao Jiang
ePrint Report ePrint Report
Updatable encryption schemes allow for key rotation on ciphertexts. A client outsourcing storage of encrypted data to a cloud server can change its encryption key. The cloud server can update the stored ciphertexts to the new key using only a token provided by the client.

This paper solves two open problems in updatable encryption, that of uni-directional vs. bi-directional updates, and post-quantum security.

The main result in this paper is to analyze the security notions based on uni- and bi-directional updates. Surprisingly, we prove that uni- and bi-directional variants of each security notion are equivalent.

The second result in this paper is to provide a new and highly efficient updatable encryption scheme based on the Decisional Learning with Error assumption. This gives us post-quantum security. Our scheme is bi-directional, but because of our main result, this is sufficient.
Expand

27 May 2020

University of Stuttgart, Germany
Job Posting Job Posting
The Institute for Computer Architecture and Computer Engineering (ITI) at the University of Stuttgart seeks applications for a research position for the recently approved DFG project MEMCRYPTO in the field of memristor-based cryptography. The objective of the project is to explore novel memristive devices and architectures on their basis for construction of secure cryptographic hardware blocks, such as block ciphers. The project, which is part of DFG’s new Priority Program “Nano Security” (SPP 2253), will involve a tight collaboration with a research group in material science at TU Chemnitz capable of manufacturing and testing memristive devices and circuits. The position is suitable for PhD candidates, yet interested candidates who already hold a PhD degree can be employed as well. Located in Stuttgart, one of Europe’s main economic hubs, the Institute offers you an inspiring working atmosphere in a successful international team. The remuneration is according to the German public-service salary grade TV-L E13. Part-time employment, or a combination with a teaching-assistant position associated with a teaching load, are possible. To qualify for this position, you need an above-average Master’s degree in Computer Science, Electrical Engineering or a related discipline. Moreover, we expect proven skills or experiences in at least one of the three areas listed below (and credible interest in the other two): 1. Design of digital circuits, including their specification in Verilog or VHDL, synthesis for ASIC or FPGA, simulation on different levels of abstraction. 2. Cryptography, ideally with a focus on resilience of cryptographic implementations against physical attacks (side-channel analysis, fault-injections). 3. Memristive technologies, e.g., modeling or simulation of memristive behavior, synthesis of circuits in memristive logic families. To apply, please send, by email, your cover letter (explicitly explaining your interest in the topic and pointing out which of the three above-mentioned areas you feel competent in), CV and scans of your Master’s and Bachelor’s degree certificates including the transcripts with all grades.

Closing date for applications:

Contact: Ilia Polian

More information: https://spp-nanosecurity.uni-stuttgart.de/projects/

Expand

26 May 2020

Junbin Fang, Dominique Unruh, Jian Weng, Jun Yan, Dehua Zhou
ePrint Report ePrint Report
The concept of quantum bit commitment was introduced in the early 1980s for the purpose of basing bit commitment solely on principles of quantum theory. Unfortunately, such unconditional quantum bit commitment still turns out to be impossible. As a compromise like in classical cryptography, Dumais, Mayers and Salvail [DMS00] introduce and realize the conditional quantum bit commitment that additionally relies on complexity assumptions. However, in contrast to the classical bit commitment which is widely used in classical cryptography, up until now there is relatively little work towards studying the application of quantum bit commitment in quantum cryptography. This may be partly due to the well-known weakness of the quantum binding, making it unclear whether quantum bit commitment could be used as a primitive (like its classical counterpart) in quantum cryptography.

As the first step towards studying the possible application of quantum bit commitment in quantum cryptography, in this work we consider replacing the classical bit commitment used in some well-known constructions with a perfectly/statistically-binding quantum bit commitment. We show that (quantum) security can still be fulfilled in particular with respect to zero-knowledge, oblivious transfer, and proofs-of-knowledge. In spite of this, we stress that the corresponding security analyses are by no means a trivial adaptation of their classical counterparts. New techniques are needed to handle possible superposition attacks by the cheating sender of the quantum bit commitments.

Since non-interactive quantum bit commitment schemes can be constructed from general quantum-secure one-way functions, we hope to use quantum bit commitment (rather than the classical one that is still quantum-secure) in cryptographic construction to reduce the round complexity and weaken the complexity assumption simultaneously.
Expand
Ben Kreuter, Sarvar Patel, Ben Terner
ePrint Report ePrint Report
Private set intersection and related functionalities are among the most prominent real-world applications of secure multiparty computation. While such protocols have attracted significant attention from the research community, other functionalities are often required to support a PSI application in practice. For example, in order for two parties to run a PSI over the unique users contained in their databases, they might first invoke on a support functionality to agree on the primary keys to represent their users. This paper studies a secure approach to agreeing on primary keys. We introduce and realize a functionality that computes a common set of identifiers based on incomplete information held by two parties, which we refer to as private identity agreement. We explain the subtleties in designing such a functionality that arise from privacy requirements when intending to compose securely with PSI protocols. We also argue that the cost of invoking this functionality can be amortized over a large number of PSI sessions, and that for applications that require many repeated PSI executions, this represents an improvement over a PSI protocol that directly uses incomplete or fuzzy matches.
Expand
Viet Tung Hoang, Yaobin Shen
ePrint Report ePrint Report
We study the security of $\mathsf{CTR\text{-}DRBG}$, one of NIST's recommended Pseudorandom Number Generator (PRNG) designs. Recently, Woodage and Shumow (Eurocrypt' 19), and then Cohney et al. (S&P' 20) point out some potential vulnerabilities in both NIST specification and common implementations of $\mathsf{CTR\text{-}DRBG}$. While these researchers do suggest counter-measures, the security of the patched $\mathsf{CTR\text{-}DRBG}$ is still questionable. Our work fills this gap, proving that $\mathsf{CTR\text{-}DRBG}$ satisfies the robustness notion of Dodis et al. (CCS'13), the standard security goal for PRNGs.
Expand
Ivan Damgård, Sophia Yakoubov
ePrint Report ePrint Report
Threshold encryption is encryption to a group of n intended recipients in such a way that any t+1 out of the n recipients together can decrypt, but t or fewer learn nothing about the message. Ad hoc threshold encryption (ATE) is threshold encryption with no trusted setup beyond a PKI (that is, all keys are generated independently). The techniques known in the ad hoc setting suffer either from ciphertexts linear in (n-t) (Daza et. al), or from reliance on cumbersome primitives like indistinguishability obfuscation (Reyzin et. al).

In this paper, we set out to determine whether we can get ATE with short ciphertexts from standard primitives. We therefore work in a model where we limit reliance on computational assumptions. We do this by demanding information theoretic security given black-box access to limited cryptographic tools such as non-interactive key exchange and pseudorandom generators.

We show that, with access only to idealized two-party key exchange, any secure ATE scheme must produce ciphertexts of size at least (n-t-1)l (where l is the length of the message). If access is additionally given to an idealized PRG, the lower bound on ciphertext size becomes k(n-t)/2 + l (where k is the length of the input to the PRG).

If idealized q-party key exchange for q > 2 is availabe, then we can achieve a constant-size ciphertext, at the cost of invoking the key exchange an exponential number of times. We also prove that, if the size of the ciphertext is optimal (that is, equal to the size of the message), the exponential overhead is unavoidable. Finally, we give some alternative constructions demonstrating that the overhead can be reduced at the cost of slightly larger ciphertext size.
Expand
Rachit Garg, George Lu, Brent Waters
ePrint Report ePrint Report
A proof of replication system is a cryptographic primitive that allows a server (or group of servers) to prove to a client that it is dedicated to storing multiple copies or replicas of a file. Until recently, all such protocols required fined-grained timing assumptions on the amount of time it takes for a server to produce such replicas.

Damg{\aa}rd, Ganesh, and Orlandi (CRYPTO' 19) proposed a novel notion that we will call proof of replication with client setup. Here, a client first operates with secret coins to generate the replicas for a file. Such systems do not inherently have to require fine-grained timing assumptions. At the core of their solution to building proofs of replication with client setup is an abstraction called replica encodings. Briefly, these comprise a private coin scheme where a client algorithm given a file $m$ can produce an encoding $\sigma$. The encodings have the property that, given any encoding $\sigma$, one can decode and retrieve the original file $m$. Secondly, if a server has significantly less than $n \cdot |m|$ bit of storage, it cannot reproduce $n$ encodings. The authors give a construction of encodings from ideal permutations and trapdoor functions.

In this work, we make three central contributions: 1) Our first contribution is that we discover and demonstrate that the security argument put forth by DGO19 is fundamentally flawed. Briefly, the security argument makes assumptions on the attacker's storage behavior that does not capture general attacker strategies. We demonstrate this issue by constructing a trapdoor permutation which is secure assuming indistinguishability obfuscation, serves as a counterexample to their claim (for the parameterization stated). 2) In our second contribution we show that the DGO19 construction is actually secure in the ideal permutation model from any trapdoor permutation when parameterized correctly. In particular, when the number of rounds in the construction is equal to $\lambda \cdot n \cdot b$ where $\lambda$ is the security parameter, $n$ is the number of replicas and $b$ is the number of blocks. To do so we build up a proof approach from the ground up that accounts for general attacker storage behavior where we create an analysis technique that we call ``sequence-then-switch''. 3) Finally, we show a new construction that is provably secure in the random oracle (or random function) model. Thus requiring less structure on the ideal function.
Expand

25 May 2020

Sanjam Garg, Romain Gay, Mohammad Hajiabadi
ePrint Report ePrint Report
Identity-based encryption (IBE) is a generalization of public-key encryption (PKE) by allowing encryptions to be made to user identities. In this work, we seek to obtain IBE schemes that achieve key-dependent-message (KDM) security with respect to messages that depend on the master secret key. Previous KDM-secure schemes only achieved KDM security in simpler settings, in which messages may only depend on user secret keys. An important motivation behind studying master-KDM security is the application of this notion in obtaining generic constructions of KDM-CCA secure PKE, a primitive notoriously difficult to realize. We give the first IBE that achieves master-KDM security from standard assumptions in pairing groups. Our construction is modular and combines techniques from KDM-secure PKE based from hash-proof systems, together with IBE that admits a tight security proof in the multi-challenge setting, which happens to be unexpectedly relevant in the context of KDM security. In fact, to the best of our knowledge, this is the first setting where techniques developed in the context of realizing tightly secure cryptosystems have led to a new feasibility result. As a byproduct, our KDM-secure IBE, and thus the resulting KDM-CCA-secure PKE both enjoy a tight security reduction, independent of the number of challenge ciphertexts, which was not achieved before.
Expand
Diego F. Aranha, Felipe Rodrigues Novaes, Akira Takahashi, Mehdi Tibouchi, Yuval Yarom
ePrint Report ePrint Report
Although it is one of the most popular signature schemes today, ECDSA presents a number of implementation pitfalls, in particular due to the very sensitive nature of the random value (known as the nonce) generated as part of the signing algorithm. It is known that any small amount of nonce exposure or nonce bias can in principle lead to a full key recovery: the key recovery is then a particular instance of Boneh and Venkatesan's hidden number problem (HNP). That observation has been practically exploited in many attacks in the literature, taking advantage of implementation defects or side-channel vulnerabilities in various concrete ECDSA implementations. However, most of the attacks so far have relied on at least 2 bits of nonce bias (except for the special case of curves at the $80$-bit security level, for which attacks against $1$-bit biases are known, albeit with a very high number of required signatures).

In this paper, we uncover LadderLeak, a novel class of side-channel vulnerabilities in implementations of the Montgomery ladder used in ECDSA scalar multiplication. The vulnerability is in particular present in several recent versions of OpenSSL. However, it leaks less than $1$ bit of information about the nonce, in the sense that it reveals the most significant bit of the nonce, but with probability $<1$. Exploiting such a mild leakage would be intractable using techniques present in the literature so far. However, we present a number of theoretical improvements of the Fourier analysis approach to solving the HNP (an approach originally due to Bleichenbacher), and this lets us practically break LadderLeak-vulnerable ECDSA implementations instantiated over the sect163r1 and NIST P-192 elliptic curves. In so doing, we achieve several significant computational records in practical attacks against the HNP.
Expand
Amit Deo, Benoit Libert, Khoa Nguyen, Olivier Sanders
ePrint Report ePrint Report
Electronic cash (e-cash) was introduced 40 years ago as the digital analogue of traditional cash. It allows users to withdraw electronic coins that can be spent anonymously with merchants. As advocated by Camenisch et al. (Eurocrypt 2005), it should be possible to store the withdrawn coins compactly (i.e., with logarithmic cost in the total number of coins), which has led to the notion of compact e-cash. Many solutions were proposed for this problem but the security proofs of most of them were invalidated by a very recent paper by Bourse et al. (Asiacrypt 2019). The same paper describes a generic way of fixing existing constructions/proofs but concrete instantiations of this patch are currently unknown in some settings. In particular, compact e-cash is no longer known to exist under quantum-safe assumptions. In this work, we resolve this problem by proposing the first secure compact e-cash system based on lattices following the result from Bourse et al. Contrarily to the latter work, our construction is not only generic, but we describe two concrete instantiations. We depart from previous frameworks of e-cash systems by leveraging lossy trapdoor functions to construct our coins. The indistinguishability of lossy and injective keys allows us to avoid the very strong requirements on the involved pseudo-random functions that were necessary to instantiate the generic patch proposed by Bourse et al.
Expand
Tomoki Moriya, Hiroshi Onuki, Tsuyoshi Takagi
ePrint Report ePrint Report
We propose two new supersingular isogeny-based public key encryptions: SiGamal and C-SiGamal. These public key encryptions are developed by giving an additional point of the order $2^r$ to CSIDH. SiGamal seems similar to ElGamal encryption, while C-SiGamal is a compressed version of SiGamal. We prove that SiGamal and C-SiGamal obtain IND-CPA security without using hash functions under a new assumption: the P-CSSDDH assumption. This assumption comes from the expectation that no efficient algorithm can distinguish between a random point and a point that is the image of a public point under a hidden isogeny.

Next, we propose a Naor-Reingold type pseudo random function based on SiGamal. If the P-CSSDDH assumption and the CSSDDH$^*$ assumption, which guarantees the security of CSIDH that uses a prime $p$ in the setting of SiGamal, hold, then our proposed function is a pseudo random function. Moreover, we estimate computational costs of group actions to compute our proposed PRF are about $\sqrt{\frac{8T}{3\pi}}$ times than that of the group action in CSIDH, where $T$ is the Hamming weight of input of the PRF.

Finally, we experimented group actions in SiGamal and C-SiGamal. In our experimentation, the computational costs of group actions in SiGamal-512 with a $256$-bit plaintext message space are about $2.62$ times that of a group action in CSIDH-512.
Expand
Jeroen Pijnenburg, Bertram Poettering
ePrint Report ePrint Report
A popular cryptographic option to implement Hierarchical Access Control in organizations is to combine a key assignment scheme with a symmetric encryption scheme. In brief, key assignment associates with each object in the hierarchy a unique symmetric key, and provides all higher-ranked authorized subjects with a method to recover it. This setup allows for encrypting the payloads associated with the objects so that they can be accessed by the authorized and remain inaccessible for the unauthorized. Both key assignment and symmetric encryption have been researched for roughly four decades now, and a plethora of efficient constructions have been the result. Surprisingly, a treatment of the joint primitive (key assignment combined with encryption, as used in practice) in the framework of provable security was conducted only very recently, leading to a publication in ToSC 2018(4). We first carefully revisit this publication. We then argue that there are actually two standard use cases for the combined primitive, which also require individual treatment. We correspondingly propose a fresh set of security models and provably secure constructions for each of them. Perhaps surprisingly, the two constructions call for different symmetric encryption primitives: While standard AEAD is the right tool for the one, we identify a less common tool called Encryptment as best fitting the other.
Expand
Rami Elkhatib, Reza Azarderakhsh, Mehran Mozaffari-Kermani
ePrint Report ePrint Report
New primes were proposed for Supersingular Isogeny Key Encapsulation (SIKE) in NIST standardization process of Round 2 after further cryptanalysis research showed that the security levels of the initial primes chosen were over-estimated. In this paper, we develop a highly optimized $\mathbb{F}_{p}$ Montgomery multiplication algorithm and architecture that further utilizes the special form of SIKE prime compared to previous implementations available in the literature. We then implement SIKE for all Round 2 NIST security levels (SIKEp434 for NIST security level 1, SIKEp503 for NIST security level 2, SIKEp610 for NIST security level 3, and SIKEp751 for NIST security level 5) on Xilinx Virtex 7 using the proposed multiplier. Our best implementation (NIST security level 1) runs 29\% faster and occupies 30\% less hardware resources in comparison to the leading counterpart available in the literature and implementations for other security levels achieved similar improvement.
Expand
Navid Alamati, Hart Montgomery, Sikhar Patranabis
ePrint Report ePrint Report
We show how to construct new multilinear maps from subexponentially secure indistinguishability obfuscation (iO) and (relatively) standard assumptions. In particular, we show how to construct multilinear maps with arbitrary predetermined degree of multilinearity where each of the following assumptions hold: SXDH, joint-SXDH, exponent-DDH and all other assumptions implied by them (including k-party-DDH, k-Lin and its variants). Our constructions achieve the full functionality of the “dream version” definition of multilinear maps as defined in the initial work of Garg et al. (Eurocrypt’13). Our work substantially extends a previous line of works including that of Albrecht et al. (TCC’16) and Farshim et al. (PKC’18), which showed how to build multilinear maps endowed with weaker assumptions (such as multilinear DDH and other related assumptions) from iO.

A number of recent works have shown how to build iO from multilinear maps endowed with plausible assumptions; one example would be the work of Lin and Tessaro (Crypto’17) which shows how to construct iO from subexponentially secure SXDH-hard multilinear maps and some (subexponentially secure) plausible assumptions. Coupled with any one of these constructions, our results here can be seen as formally proving the equivalence of iO and multilinear maps/graded encodings (modulo subexponential reductions and other plausible assumptions) for the first time.
Expand
Behnaz Rezvani, Thomas Conroy, Luke Beckwith, Matthew Bozzay, Trevor Laffoon, David McFeeters, Yijia Shi, Minh Vu, William Diehl
ePrint Report ePrint Report
Cryptographic protections are ubiquitous in information technology, including the emerging Internet of Things (IoT). As a result of technology migration to a resource-challenged landscape and new threats to cryptographic security, governments and industry are exploring new cryptographic algorithms. While new standards will emerge, however, old standards will not disappear for the time being. It is therefore important to explore platforms where multiple cryptographic deployments can be dynamically interchanged and even share resources. In this research we build on the Development Package for the Applications Programming Interface for Hardware Implementations of Lightweight Cryptography (DP API HW LWC). In this construct, developers design hardware implementations of authenticated encryption with associated data (AEAD) inside a cryptographic core (CryptoCore) encapsulated by input/output utilities. While CryptoCore is intended for single register-transfer level (RTL) implementations, we install a custom-designed soft core microprocessor inside CryptoCore to run underlying block ciphers, along with a shell to facilitate AEAD processing. Through dynamic loading and execution of block ciphers on the core, we demonstrate a single LWC deployment on an Artix-7 FPGA, capable of executing 3 NIST LWC Standardization Process Round 2 AEAD candidates (COMET-AES, COMET-CHAM and GIFT-COFB) using only 55% of the combined area of separate RTL implementations of the same ciphers.
Expand
Fatih Balli, Andrea Caforio, Subhadeep Banik
ePrint Report ePrint Report
The bit-sliding work of Jean et al. (CHES 2017) showed that the smallest-size circuit for SPN based blockciphers such as AES, SKINNY and, PRESENT can be achieved via bit-serial implementations. Their technique decreases the bitsize of the datapath, and it naturally leads to significant loss in latency (as well as the maximum throughput). Their designs complete a single round of the encryption in 168, 168 (for 128-bit blocks), 68 clock cycles (for 64-bit block) respectively. A follow-up work by Banik et al. (FSE 2020) introduced the swap-and-rotate technique that both eliminates this loss in latency and achieves even smaller footprint.

In the paper, we extend these results on bit-serial implementations all the way to three authenticated encryption schemes from NIST LWC. Our first focus is to decrease latency and improve throughput with the use of swap-and-rotate technique. Our blockcipher implementations have the most efficient round operations in the sense that a round function of a $n$-bit blockcipher is computed in exactly $n$ clock cycles. This leads to implementations that are similar in size to the state-of-the-art, but have much lower latency (savings up to 20 percent).

Though these results are promising, blockciphers themselves are not end-user primitives, as they need to used together with a mode of operation. Hence, in the second part of the paper, we use our blockciphers in bit-serial implementations for three active NIST authenticated encryption candidates: SUNDAE-GIFT, Romulus and SAEAES. We provide the smallest blockcipher-based authenticated encryption circuits known in the literature so far.
Expand
Andrea Caforio, Fatih Balli, Subhadeep Banik
ePrint Report ePrint Report
The selection criteria for NIST's Lightweight Crypto Standardization (LWC) have been slowly shifting towards the lightweight efficiency of designs, given that a large number of candidates already establish their security claims on conservative, well-studied paradigms. The research community has accumulated a decent level of experience on authenticated encryption primitives, thanks mostly to the recently completed CAESAR competition, with the advent of the NIST LWC, the de facto focus is now on evaluating efficiency of the designs with respect to hardware metrics like area, throughput, power and energy.

In this paper, we focus on a less investigated metric under the umbrella term lightweight, i.e. energy consumption. Quantitatively speaking, energy is the sum total electrical work done by a voltage source and thus is a critical metric of lightweight efficiency. Among the thirty-two second round candidates, we give a detailed evaluation of the ten that only make use of a lightweight or semi-lightweight block cipher at their core. We use this pool of candidates to investigate a list of generic implementation choices that have considerable effect on both the size and the energy consumption of modes of operation circuit, which function as an authenticated encryption primitive. Besides providing energy and circuit size metrics of these candidates, our results provide useful insights for designers who wish to understand what particular choices incur significant energy consumption in AEAD schemes. In the second part of the paper we shift our focus to threshold implementations that offer protection against first order power analysis attacks. There has been no study focusing on energy efficiency of such protected implementations and as such the optimizations involved in such circuits are not well established. We explore the simplest possible protected circuit: the one in which only the state path of the underlying block cipher is shared, and we explore how design choices like number of shares, implementation of the masked s-box and the circuit structure of the AEAD scheme affect the energy consumption.
Expand
Navid Alamati, Hart Montgomery, Sikhar Patranabis
ePrint Report ePrint Report
A weak pseudorandom function $F: K \times X \to Y$ is said to be ring key-homomorphic if, given $F(k_1, x)$ and $F(k_2, x)$, there are efficient algorithms to compute $F(k_1 \oplus k_2, x)$ and $F(k_1 \otimes k_2, x)$ where $\oplus$ and $\otimes$ are the addition and multiplication operations in the ring $K$, respectively. In this work, we initiate the study of ring key-homomorphic weak PRFs (RKHwPRFs). In particular, we show that the following primitives can be constructed from any RKHwPRF:

- Multiparty non-interactive key exchange (NIKE) for an arbitrary number of parties.

- Indistinguishability obfuscation for all circuits in NC_1.

Our proofs are in the standard model, and the proof for our iO scheme is program-independent. Our iO scheme can also be bootstrapped to all polynomial-size circuits using standard techniques. We also consider restricted versions of RKHwPRFs that are structurally weaker than a classic RKHwPRF but suffice for all our constructions. We show how to instantiate these restricted RKHwPRFs from various multilinear maps and associated assumptions. Our framework gives several new results, such as:

- The first iO scheme that relies only on SXDH over any asymmetric multilinear map without additional assumptions.

- The first iO scheme that relies only on DLIN (or more generally Matrix-DDH) over any (even symmetric) multilinear map without additional assumptions.

- The first iO scheme that relies on SXDH over the multilinear map presented by Ma and Zhandry (TCC'18) (the authors only presented a NIKE protocol in their paper). To our knowledge, this candidate multilinear map has not been successfully cryptanalyzed, and the SXDH assumption plausibly holds over it.

Our analysis of RKHwPRFs in a sense completes the work initiated by Alamati et al. (EUROCRYPT'19) on building cryptosystems from generic Minicrypt primitives with structure. With our results, almost all of the major known cryptosystems can be built from a weak PRF with either a group or ring homomorphism over either the input space or the key space. Thus, a major contribution of this work is advancing the study of the relationship between structure and cryptography.
Expand
Artur Mariano
ePrint Report ePrint Report
This paper introduces LUSA - the Lattice Unified Set of Algorithms library - a C++ library that comprises many high performance, parallel implementations of lattice algorithms, with particular focus on lattice-based cryptanalysis. Currently, LUSA offers algorithms for lattice reduction and the SVP. % and the CVP.

LUSA was designed to be 1) simple to install and use, 2) have no other dependencies, 3) be designed specifically for lattice-based cryptanalysis, including the majority of the most relevant algorithms in this field and 4) offer efficient, parallel and scalable methods for those algorithms.

LUSA explores paralellism mainly at the thread level, being based on OpenMP. However the code is also written to be efficient at the cache and operation level, taking advantage of carefully sorted data structures and data level parallelism.

This paper shows that LUSA delivers these promises, by being simple to use while consistently outperforming its counterparts, such as NTL, plll and fplll, and offering scalable, parallel implementations of the most relevant algorithms to date, which are currently not available in other libraries.
Expand
Next ►