International Association
for Cryptologic Research

Event date: 17 September to 18 September 2020
Submission deadline: 10 July 2020
Notification: 20 August 2020

In this work, we exhibit a hierarchy of polynomial time algorithms solving approximate variants of the Closest Vector Problem (CVP). Our first contribution is a heuristic algorithm achieving the same distance tradeoff as HSVP algorithms, namely $\approx \beta^{\frac{n}{2\beta}}\textrm{covol}(\Lambda)^{\frac{1}{n}}$ for a random lattice $\Lambda$ of rank $n$. Compared to the so-called Kannan's embedding technique, our algorithm allows using precomputations and can be used for efficient batch CVP~instances. This implies that some attacks on lattice-based signatures lead to very cheap forgeries, after a precomputation. Our second contribution is a \emph{proven} reduction from approximating the closest vector with a factor $\approx n^{\frac32}\beta^{\frac{3n}{2\beta}}$ to the Shortest Vector Problem (SVP) in dimension $\beta$.

In function inversion, we are given a function $f: [N] \mapsto [N]$, and want to prepare some advice of size $S$, such that we can efficiently invert any image in time $T$. This is a well studied problem with profound connections to cryptography, data structures, communication complexity, and circuit lower bounds. Investigation of this problem in the quantum setting was initiated by Nayebi, Aaronson, Belovs, and Trevisan (2015), who proved a lower bound of $ST^2 = \tilde\Omega(N)$ for random permutations against classical advice, leaving open an intriguing possibility that Grover's search can be sped up to time $\tilde O(\sqrt{N/S})$. Recent works by Hhan, Xagawa, and Yamakawa (2019), and Chung, Liao, and Qian (2019) extended the argument for random functions and quantum advice, but the lower bound remains $ST^2 = \tilde\Omega(N)$.

In this work, we prove that even with quantum advice, $ST + T^2 = \tilde\Omega(N)$ is required for an algorithm to invert random functions. This demonstrates that Grover's search is optimal for $S = \tilde O(\sqrt{N})$, ruling out any substantial speed-up for Grover's search even with quantum advice. Further improvements to our bounds would imply a breakthrough in circuit lower bounds, as shown by Corrigan-Gibbs and Kogan (2019).

To prove this result, we develop a general framework for establishing quantum time-space lower bounds. We further demonstrate the power of our framework by proving the following results.

* Yao's box problem: We prove a tight quantum time-space lower bound for classical advice. For quantum advice, we prove a first time-space lower bound using shadow tomography. These results resolve two open problems posted by Nayebi, Aaronson, Belovs, and Trevisan (2015).

* Salted cryptography: We show that “salting generically provably defeats preprocessing,” a result shown by Coretti, Dodis, Guo, and Steinberger (2018), also holds in the quantum setting. In particular, we prove quantum time-space lower bounds for a wide class of salted cryptographic primitives in the quantum random oracle model. This yields a first quantum time-space lower bound for salted collision-finding, which in turn implies that $\mathsf{PWPP}^{\mathcal O} \not\subseteq \mathsf{FBQP}^{\mathcal O}\mathsf{/qpoly}$ relative to a random oracle $\mathcal O$.

Masking is one of the most popular countermeasures to protect cryptographic implementations against side-channel analysis since it is provably secure and can be deployed at the algorithm level. To strengthen the original Boolean masking scheme, several works have suggested using schemes with high algebraic complexity. The Inner Product Masking (IPM) is one of those. In this paper, we propose a unified framework to quantitatively assess the side-channel security of the IPM in a coding-theoretic approach. Specifically, starting from the expression of IPM in a coded form, we use two defining parameters of the code to characterize its side-channel resistance. In order to validate the framework, we then connect it to two leakage metrics (namely signal-to-noise ratio and mutual information, from an information-theoretic aspect) and one typical attack metric (success rate, from a practical aspect) to build a firm foundation for our framework.

As an application, our results provide ultimate explanations on the observations made by Balasch et al. at EUROCRYPT'15 and at ASIACRYPT'17, Wang et al. at CARDIS'16 and Poussier et al. at CARDIS'17 regarding the parameter effects in IPM, like higher security order in bounded moment model. Furthermore, we show how to systematically choose optimal codes (in the sense of a concrete security level) to optimize IPM by using this framework. Eventually, we present a simple but effective algorithm for choosing optimal codes for IPM, which is of special interest for designers when selecting optimal parameters for IPM.

In this paper we present the concept of linear secret-sharing homomorphisms, which are linear transformations between different secret-sharing schemes defined over vector spaces over a field $\mathbb{F}$ and allow for efficient multiparty conversion from one secret-sharing scheme to the other. This concept generalizes the observation from (Smart and Talibi, IMACC 2019) and (Dalskov et al., EPRINT 2019) that moving from a secret-sharing scheme over $\mathbb{F}$ to a secret sharing over an elliptic curve group $\mathbb{G}$ of order $p$ can be done very efficiently with no communication by raising the generator of $\mathbb{G}$ to each share over $\mathbb{F}$. We then show how to securely evaluate arbitrary bilinear maps, which can be instantiated in particular with pairings over elliptic curves.

We illustrate the benefits of being able to efficiently perform secure computation over elliptic curves by providing several applications and use-cases. First, we show methods for securely encoding and decoding field elements into elliptic curve points, which enable applications that require computation back and forth between fields and elliptic curves. Then, we show how to use use the secure pairing evaluation to sign and verify Pointcheval-Sanders signatures (D. Pointcheval and O. Sanders, CT-RSA 2016) in MPC, which enable multiple applications in which some authenticity property is required on secret-shared data. We consider some of these applications in our work, namely Dynamic Proactive Secret Sharing, on which a shared secret is intended to be transferred from one set of parties to another, and Input Certification, on which the "validity'' of the input provided by some party to some MPC protocol can be verified.

Secret sharing-based distributed storage systems are one approach to provide long-term protection of data even against quantum computing. Confidentiality is provided because the shares of data are renewed periodically while integrity is provided by commitment schemes. However, this solution is prohibitively costly and impractical: share renewal requires an information-theoretically secure channel between any two nodes and long-term confidential commitment schemes are computationally impractical for large files. In this paper, we present SAFE, a secret sharing-based long-term secure distributed storage system that leverages a Trusted Execution Environment (TEE) to overcome the above limitations. Share generation and renewal are performed inside the TEE and the shares are securely distributed to the storage servers. We prototype SAFE protocols using a TEE instantiation, and show their efficiency, even for large files, compared to existing schemes.

Skinny is a lightweight tweakable block cipher which received a great deal of cryptanalytic attention following its elegant structure and efficiency. Inspired by the Skinny competitions, multiple attacks on it were reported in different settings (e.g. single vs. related-tweakey) using different techniques (impossible differentials, meet-in-the-middle, etc.). In this paper we revisit some of these attacks, identify issues with several of them, and offer a series of improved attacks which were experimentally verified. Our best attack can attack up to 18 rounds using $2^{60}$ chosen ciphertexts data, $2^{116}$ time, and $2^{112}$ memory.

In this paper we introduce a novel method for constructing an efficient linkable ring signature without a trusted setup in a group where decisional Diffie-Hellman problem is hard and no bilinear pairings exist. Our linkable ring signature is logarithmic in the size of the signer anonymity set, its verification complexity is linear in the anonymity set size and logarithmic in the signer threshold. A range of the recently proposed setup-free logarithmic size signatures is based on the commitment-to-zero proving system by Groth and Kohlweiss or on the Bulletproofs inner-product compression method by Bünz et al. In contrast, we construct our signature from scratch using the Lin2-Xor and Lin2-Selector lemmas that we formulate and prove here. With these lemmas we construct an n-move public coin special honest verifier zero-knowledge membership proof protocol and instantiate the protocol in the form of a general-purpose setup-free signer-ambiguous linkable ring signature in the random oracle model.

We study time/memory tradeoffs of function inversion: an algorithm, i.e. an inverter, equipped with an $s$-bit advice for a randomly chosen function $f:[n]\to [n]$ and using $q$ oracle queries to $f$, tries to invert a randomly chosen output $y$ of $f$ (i.e. to find $x$ such that $f(x)=y$). Much progress was done regarding adaptive function inversion - the inverter is allowed to make adaptive oracle queries. Hellman80 [IEEE transactions on Information Theory '80] presented an adaptive inverter that inverts with high probability a random $f$. Fiat and Naor [SICOMP '00] proved that for any $s,q$ with $s^2 q = n^2$ (ignoring low-order  terms), an $s$-advice, $q$-query variant of Hellman's algorithm inverts a constant fraction of the image points of any function. Yao [STOC '90] proved a lower bound of $sq \ge n$ for this problem. Closing the gap between the above lower and upper bounds is a long-standing open question.

Very little is known for the non-adaptive variant of the question - the inverter chooses its queries in advance. The only known upper bounds, i.e. inverters, are the trivial ones (with $s+q=n$), and the only lower bound is the above bound of Yao. In a recent work, Corrigan-Gibbs and Kogan [TCC '19] partially justified the difficulty of finding lower bounds on non-adaptive inverters, showing that a lower bound on the time/memory tradeoff of non-adaptive inverters implies a lower bound on low-depth Boolean circuits. Bounds that for a strong enough choice of parameters, are notoriously hard to prove.

We make progress on the above intriguing question, both for the adaptive and the non-adaptive case, proving the following lower bounds on restricted families of inverters:

- Linear-advice (adaptive inverter). If the advice string is a linear function of f (e.g. $A\cdot f$, viewing $f$ as a vector in $[n]^n$), then $s+q = \Omega(n)$.

- Affine non-adaptive decoders. If the non-adaptive inverter has an affine decoder - it  outputs a linear function, determined by the advice string and the element to invert, of the query answers - then $s = \Omega(n)$ (regardless of $q$).

- Affine non-adaptive decision trees. If the non-adaptive inversion algorithm is a $d$-depth affine decision tree - it outputs the evaluation of a decision tree whose nodes compute a linear function of the answers to the queries - and $q < cn$ for some universal $c>0$, then $s = \Omega(n/d log n)$.

The Internet of Things (IoT) based services are getting a widespread expansion in all the directions and dimensions of the 21st century. The IoT based deployment involves an internet-connected sensor, mobiles, laptops, and other networking and computing de- vices. In most IoT based applications, the sensor collects the data and communicates it to the end-user via gateway device or fog device over a precarious internet channel. The attacker can use this open channel to capture the sensing device or the gateway device to collect the IoT data or control the IoT system. For a long time, numerous researchers are working towards designing the authentication mechanism for the sen- sor network to achieve reliable and computationally feasible security. For the resource constraint environment of the IoT, it is essential to design reliable, ecient, and secure authentication protocol. In this paper, we propose a novel approach of authentication in the IoT paradigm called a Level-Dependent Authentication(LDA). In the LDA protocol, we propose a security reliable and resource ecient key sharing mechanism in which users at level li can communicate with the sensor at level lj if and only if the level of user in the organizational hierarchy is lower or equal to the level of sensor deployment. We pro- vide a security analysis for the proposed LDA protocol using random oracle based games & widely accepted AVISPA tools. We prove mutual authentication for the proposed protocol using BAN logic. In this paper, we also discuss a comparative analysis of the proposed protocol with other existing IoT authentication systems based on communica- tion cost, computation cost, and security index. We provide an implementation for the proposed protocol using a globally adopted IoT protocol called MQTT protocol. Finally, we present the collected data related to the networking parameters like throughput and round trip delay.

Oblivious linear evaluation (OLE) is a fundamental building block in multi-party computation protocols. In OLE, a sender holds a description of an affine function $f_{\alpha,\beta}(z)=\alpha z+\beta$, the receiver holds an input $x$, and gets $\alpha x+\beta$ (where all computations are done over some field, or more generally, a ring). Vector OLE (VOLE) is a generalization where the sender has many affine functions and the receiver learns the evaluation of all of these functions on a single point $x$.

The state-of-the-art semi-honest VOLE protocols generally fall into two groups. The first group relies on standard assumptions to achieve security but lacks in concrete efficiency. These constructions are mostly based on additively homomorphic encryption (AHE) and are classified as ``folklore". The second group relies on less standard assumptions, usually properties of sparse, random linear codes, but they manage to achieve concrete practical efficiency.

In this work, we present a conceptually simple VOLE protocol that derives its security from a standard assumption, namely Ring Learning with Errors (RLWE), while still achieving concrete efficiency comparable to the fastest VOLE protocols from non-standard coding assumptions. Furthermore, our protocol admits a natural extension to batch OLE (BOLE), which is yet another variant of OLE that computes many OLEs in parallel.

How to balance user privacy with a law enforcement agency's need to view their communications during investigations has always been a delicate and hard to formalize problem. In the age of analog communication, interception was as simple as "wiretapping" a telephone line. Due to technological advances, this is now mandated, at least in the context of mobile communications, by laws and standards pertaining to lawful interception. We introduce a new primitive, called Lawful Interception Key-Exchange (or LIKE), that guarantees key-security (up to a collision of n-1) authorities, as well as a series of novel properties, such as non-frameability and honest operator. Our approach is generic enough to be adapted to a number of use cases, is more privacy preserving than existing implementations and strikes the right balance between security and exceptional access.

Ring signatures are a cryptographic primitive that allow a signer to anonymously sign messages on behalf of an ad-hoc group of $N$ potential signers (the so-called ring). This primitive has attracted significant research since its introduction by Rivest et al. (ASIACRYPT'01), but until recently, no construction was known that was both (i) compact, i.e., the signature size is sub-linear in $N$, and (ii) in the plain model, i.e., secure under standard hardness assumptions without requiring heuristic or setup assumptions. The first construction in this most desirable setting, where reducing trust in external parties is the primary goal, was only recently presented by Backes et al. (EUROCRYPT'19). An interesting generalization of ring signatures are $t$-out-of-$N$ ring signatures for $t\geq 1$, also known as threshold ring (thring) signatures (Bresson et al., CRYPTO'02). For threshold ring signatures, non-linkable sub-linear-size constructions are not even known under heuristic or setup assumptions.

In this work, we propose the first sub-linear thring signatures and prove them secure in the plain model. While our constructions are inspired by the template underlying the Backes et al. construction, they require novel ideas and techniques. Our scheme is non-interactive, and has strong inter-signer anonymity, meaning that signers do not need to know the other signers that participate in a threshold signing. We then present a linkable counterpart to our non-linkable construction. Our thring signatures can easily be adapted to achieve the recently introduced notions of flexibility (Okamoto et al., EPRINT'18) as well as claimability and repudiability (Park and Sealfon, CRYPTO'19).

(Th)Ring signatures and, in particular, their linkable versions have recently drawn significant attention in the field of privacy-friendly cryptocurrencies. We discuss applications that are enabled by our strong inter-signer anonymity, demonstrating that thring signatures are interesting from a practical perspective also.

A Diophantine equation is a multi-variate polynomial equation with integer coefficients, and it is satisfiable if it has a solution with all unknowns taking integer values. Davis, Putnam, Robinson and Matiyasevich showed that the general Diophantine satisfiability problem is undecidable (giving a negative answer to Hilbert’s tenth problem) but it is nevertheless possible to argue in zero-knowledge the knowledge of a solution, if a solution is known to a prover. We provide the first succinct honest-verifier zero-knowledge argument for the satisfiability of Diophantine equations with a communication complexity and a round complexity that grows logarithmically in the size of the polynomial equation. The security of our argument relies on standard assumptions on hidden-order groups. As the argument requires to commit to integers, we introduce a new integer-commitment scheme that has much smaller parameters than Damga&#778;rd and Fujisaki’s scheme. We finally show how to succinctly argue knowledge of solutions to several NP-complete problems and cryptographic problems by encoding them as Diophantine equations.

This report deals with the problem of identifying the potential correlations between the observable power consumption of a digital circuit and its inputs, when the operating conditions of the circuit involve a logic hazard (also known as glitch). This problem is of utmost importance when the circuit is a cryptographic primitive that must ensure that secret input data (e.g., keys) does not leak. We present a universal algebra construction that allows to derive a set of artefacts from a digital circuit among which a conservative estimate of the Boolean expression that the circuit might leak as well as the extended input/output correlation matrix [1]. This allows the evaluation of the robustness against side channel attacks through a set of constructions that fall under the umbrella of robust probing security [2]. We believe that such a formalisation is well suited for CAD synthesis tools to help the design of more robust cryptographic primitives.