International Association
for Cryptologic Research

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.

Bit permutation based block ciphers, like PRESENT and GIFT, are well-known for their extreme lightweightness in hardware implementation. However, designing such ciphers comes with one major challenge - to ensure strong cryptographic properties simply depending on the combination of three components, namely S-box, a bit permutation and a key addition function. Having a wrong combination of components could lead to weaknesses. In this article, we studied the interaction between these components, improved the theoretical security bound of GIFT and highlighted the potential pitfalls associated with a bit permutation based primitive design. We also conducted analysis on TRIFLE, a first-round candidate for the NIST lightweight cryptography competition, where our findings influenced the elimination of TRIFLE from second-round of the NIST competition. In particular, we showed that internal state bits of TRIFLE can be partially decrypted for a few rounds even without any knowledge of the key.

In the past decades, user authentication has been dominated by server-side password-based solutions that rely on "what users know". This approach is susceptible to breaches and phishing attacks, and poses usability challenges. As a result, the industry is gradually moving to biometric-based client-side solutions that do not store any secret information on servers. This shift necessitates the safe storage of biometric templates and private keys, which are used to generate tokens, on user devices.

We propose a new generic framework called Biometric Enabled Threshold Authentication (BETA) to protect sensitive client-side information like biometric templates and cryptographic keys. Towards this, we formally introduce the notion of Fuzzy Threshold Tokenizer (FTS) where an initiator can use a "close" biometric measurement to generate an authentication token if at least $t$ (the threshold) devices participate. We require that the devices only talk to the initiator, and not to each other, to capture the way user devices are connected in the real world. We use the universal composability (UC) framework to model the security properties of FTS, including the unforgeability of tokens and the privacy of the biometric values (template and measurement), under a malicious adversary. We construct three protocols that meet our definition.

Our first two protocols are general feasibility results that work for any distance function, any threshold $t$ and tolerate the maximal (i.e. $t-1$) amount of corruption. They are based on any two round UC-secure multi-party computation protocol in the standard model (with a CRS) and threshold fully homomorphic encryption, respectively. We show how to effectively use these primitives to build protocols in a constrained communication model with just four rounds of communication.

For the third protocol, we consider inner-product based distance metrics (cosine similarity, Euclidean distance, etc.) specifically, motivated by the recent interest in its use for face recognition. We use Paillier encryption, efficient NIZKs for specific languages, and a simple garbled circuit to build an efficient protocol for the common case of $n=3$ devices with one compromised.

Event date: 18 November to 20 November 2020
Submission deadline: 3 July 2020
Notification: 4 September 2020

Technology Innovation Institute (TII) is a publicly funded research institute, based in Abu Dhabi, United Arab Emirates. It is home to a diverse community of leading scientists, engineers, mathematicians, and researchers from across the globe, transforming problems and roadblocks into pioneering research and technology prototypes that help move society ahead. At TII, we help society to overcome its biggest hurdles through a rigorous approach to scientific discovery and inquiry, using state-of-the-art facilities and collaboration with leading international institutions

As a Symmetric Cryptography Researcher, you will:

Design and implement symmetric cryptographic algorithms on software.

Conduct research in the field of symmetric cryptography and lightweight cryptography

Perform security assessments of cryptographic primitives at theoretical and implementation level.

Work closely with the other R&D teams to build secure systems using state-of-the-art cryptographic algorithms and protocols.

Minimum qualifications:

PhD degree in one of the following: Cryptography, Applied Cryptography, Information theory, Mathematics, Computer Science or any relevant Engineering degree.

Valuable publications record in the field of Symmetric Cryptography.

Knowledge of relevant theoretical and practical cryptanalysis techniques.

Extensive experience developing in C, C++, x86 or ARM assembly, Rust or Go.

Understanding of security attacks, including: timing, cache-based and microarchitectural attacks, and the corresponding countermeasures.

Closing date for applications:

Contact: Mehdi Messaoudi - Talent Acquisition Partner

As a Lead Cryptographic Protocols Researcher, you will:

Lead the scientific watch specialized in cryptographic protocols

Guide the team members in their research and development work

Analyze project requirements and provide technical and functional recommendations

Design and implement classical, quantum-resistant and hybrid cryptographic protocols and algorithms

Conduct research and development on state-of-the-art modern protocols

Perform security assessments of cryptographic protocols at the theoretical and implementation level

Minimum Qualifications:

MSc or PhD degree in Cryptography, Applied Cryptography, Information Theory, Mathematics or Computer Science

6+ years of work experience. Previous experience heading teams is a plus

Knowledge of widely-deployed cryptographic protocols and primitives

Experience in C desired, C++, Rust or Go relevant as well

Solid engineering practices and processes, such as development and testing methodology and documentation

Prior contributions to crypto protocols and open source software collaboration preferred

Quick learner, geared towards implementation

Eager to develop new skills and willing to take ownership of projects

Closing date for applications:

Contact: Mehdi Messaoudi - Talent Acquisition Partner

More information: https://www.linkedin.com/company/tiiuae/about/

In late 2016, NIST issued a call for proposals for the standardization of cryptographic systems resistant to a quantum computer for encryption, key exchange and signature primitives (hereafter NIST PQC). The standardization process is currently ending its second phase, with only 26 candidates remaining.

Each submission comes with a software implementation, targeting standard security levels for widespread applications, such as e-commerce.

Topic 1: General improvement of post-quantum primitives

During this thesis, the successful candidate will study the NIST PQC submissions still running for standardization and will propose modifications that improve the submissions in general (e.g. tighter reductions, improved theoretical error rate analysis, etc.), or that provide specific advantages in constrained settings (e.g. soft/hard implementation simplicity, reduced bandwidth, reduced latency, etc.).

Topic 2: Hardware implementations of cryptographic schemes based on error-correcting codes and/or lattices

The software performance of NIST PQC submissions has been thoroughly studied. On the other hand, the hardware performance (e.g. energy cost or gate cost on broadly available FPGAs) of many submissions is still not very well understood. During this thesis, the successful candidate will study code-based and/or lattice-based NIST PQC submissions, and propose hardware implementations of both the original submisssions and variations designed by the candidate to improve hardware performance.

Closing date for applications:

Contact: Carlos Aguilar Melchor

As a Post-Quantum Crypto Researcher, you will:

Design and implement quantum-safe PKE/KEM and digital signature schemes.

Conduct research and development in one of the following: lattice-based cryptography, code-based cryptography, hash-based cryptography, isogeny-based cryptography

Perform security assessments of crypto-primitives and cryptosystems at the theoretical and implementation level

Minimum qualifications:

MSc or PhD degree in Cryptography, Applied Cryptography, Information Theory, Mathematics or Computer Science

Extensive experience developing in C, C++, Rust or Go

Deep understanding of cryptographic algorithms and protocols

Understanding of security attacks, including: side-channel analysis, fault injection, microarchitectural attacks, and the corresponding countermeasures

Familiarity with hardware languages is a plus

Closing date for applications:

Contact: Mehdi Messaoudi - Talent Acquisition Partner

More information: https://www.linkedin.com/company/tiiuae/about/

A ring signature (introduced by Rivest et al., Asiacrypt 2001) allows a signer to sign a message without revealing their identity by anonymizing themselves within a group of users (chosen by the signer in an ad-hoc fashion at signing time). The signature proves that one member of the group is the signer, but does not reveal which one. We consider threshold ring signatures (introduced by Bresson et al., Crypto 2002), where any $t$ signers can sign a message together while anonymizing themselves within a larger (size-$n$) group. The signature proves that $t$ members of the group signed, without revealing anything else about their identities.

Our contributions in this paper are two-fold. First, we strengthen existing definitions of threshold ring signatures in a natural way; we demand that a signer cannot be de-anonymized even by their fellow signers. This is crucial, since in applications where a signer's anonymity is important, we do not want that anonymity to be compromised by a single insider.

Second, we give the first rigorous construction of a threshold ring signature with size independent of $n$, the number of users in the larger group. Instead, our signatures have size linear in $t$, the number of signers. This is also a very important contribution; signers should not have to choose between achieving their desired degree of anonymity (possibly very large $n$) and their need for communication efficiency.

Nakamoto's famous blockchain protocol enables achieving consensus in a so-called permissionless setting--anyone can join (or leave) the protocol execution, and the protocol instructions do not depend on the identities of the players. His ingenious protocol prevents ``sybil attacks'' (where an adversary spawns any number of new players) by relying on computational puzzles (a.k.a. ``moderately hard functions'') introduced by Dwork and Naor (Crypto'92). Recent work by Garay et al (EuroCrypt'15) and Pass et al. (EuroCrypt'17) demonstrate that this protocol provably achieves consistency and liveness assuming a) honest players control a majority of the computational power in the network, b) the puzzle-difficulty is appropriately set as a function of the maximum network message delay and the total computational power of the network, and c) the computational puzzle is modeled as a random oracle.

These works, however, leave open the question of how to set the puzzle difficulty in a setting where the computational power in the network is changing. Nakamoto's protocol indeed also includes a description of a difficutly update procedure. A recent work by Garay et al. (Crypto'17) indeed shows a variant of this difficulty adjustment procedure can be used to get a sound protocol as long as the computational power does not change too fast --- however, under two restrictions: 1) their analysis assumes that the attacker cannot delays network messages, and 2) the changes in computational power in the network changes are statically set (i.e., cannot be adaptively selected by the adversary). In this work, we show the same result but without these two restrictions, demonstrating the soundness of a (slightly different) difficulty update procedure, assuming only that the computational power in the network does not change too fast (as a function of the maximum network message delays); as an additional contribution, our analysis yields a tight bound on the ``chain quality'' of the protocol.

A common approach to bootstrapping a new cryptocurrency is an airdrop, an arrangement in which existing users give away currency to entice new users to join. But current airdrops offer no recipient privacy: they leak which recipients have claimed the funds, and this information is easily linked to off-chain identities.

In this work, we address this issue by defining a private airdrop and describing concrete schemes for widely-used user credentials, such as those based on ECDSA and RSA. Our private airdrop for RSA builds upon a new zero-knowledge argument of knowledge of the factorization of a committed secret integer, which may be of independent interest. We also design a private genesis airdrop that efficiently sends private airdrops to millions of users at once. Finally, we implement and evaluate. Our fastest implementation takes 40--180 ms to generate and 3.7--10 ms to verify an RSA private airdrop signature. Signatures are 1.8--3.3 kiB depending on the security parameter.

Blockchain protocols based on variations of the longest-chain rule--whether following the proof-of-work paradigm or one of its alternatives--suffer from a fundamental latency barrier. This arises from the need to collect a sufficient number of blocks on top of a transaction-bearing block to guarantee the transaction's stability while limiting the rate at which blocks can be created in order to prevent security-threatening forks.

Our main result is a black-box security-amplifying combiner based on parallel composition of $m$ blockchains that achieves $\Theta(m)$-fold security amplification or, equivalently, $\Theta(m)$-fold reduction in latency. Our construction breaks the latency barrier to achieve, for the first time, a worst-case constant-time-settlement ledger based purely on Nakamoto longest-chain consensus: Transaction settlement can be accelerated to a constant multiple of block propagation time with negligible error.

Operationally, our construction shows how to view any family of blockchains as a unified, virtual ledger without requiring any coordination among the chains or any new protocol metadata. Users of the system have the option to inject a transaction into a single constituent blockchain or--if they desire accelerated settlement--all of the constituent blockchains. Our presentation and proofs introduce a new formalism for reasoning about blockchains, the dynamic ledger, and articulate our constructions as transformations of dynamic ledgers that amplify security. We additionally illustrate the versatility of this formalism by presenting a class of robust-combiner constructions for blockchains that can protect against complete adversarial control of a minority of a family of blockchains.

Coercion resistance is one of the most important features of a secure voting procedure. Because of the properties such as transparency, decentralization, and non-repudiation, blockchain is a fundamental technology of great interest in its own right, and it also has large potential when integrated into many other areas. Here we propose a decentralized e-voting protocol that is coercion-resistant and vote-selling resistant, while being also completely transparent and not receipt-free. We prove the security of the protocol under the standard DDH assumption.