International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News

If you have a news item you wish to distribute, they should be sent to the communications secretary. See also the events database for conference announcements.

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

09 June 2020

Wei Cheng, Sylvain Guilley, Claude Carlet, Sihem Mesnager, Jean-Luc Danger
ePrint Report ePrint Report
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.
Expand
Diego Aranha, Anders Dalskov, Daniel Escudero, Claudio Orlandi
ePrint Report ePrint Report
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.
Expand
Johannes Buchmann, Ghada Dessouky, Tommaso Frassetto, Ágnes Kiss, Ahmad-Reza Sadeghi, Thomas Schneider, Giulia Traverso, Shaza Zeitouni
ePrint Report ePrint Report
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.
Expand
Orr Dunkelman, Senyang Huang, Eran Lambooij, Stav Perle
ePrint Report ePrint Report
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.
Expand
Anton A. Sokolov
ePrint Report ePrint Report
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.
Expand
Dror Chawin, Iftach Haitner, Noam Mazor
ePrint Report ePrint Report
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)$.
Expand
Chintan Patel, Nishant Doshi
ePrint Report ePrint Report
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.
Expand
Leo de Castro, Chiraag Juvekar, Vinod Vaikuntanathan
ePrint Report ePrint Report
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.
Expand
Ghada Arfaoui, Olivier Blazy, Xavier Bultel, Pierre-Alain Fouque, Adina Nedelcu, Cristina Onete
ePrint Report ePrint Report
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.
Expand
Abida Haque, Stephan Krenn, Daniel Slamanig, Christoph Striecks
ePrint Report ePrint Report
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.
Expand
Patrick Towa, Damien Vergnaud
ePrint Report ePrint Report
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.
Expand

08 June 2020

Vittorio Zaccaria
ePrint Report ePrint Report
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.
Expand
Sumanta Sarkar, Yu Sasaki, Siang Meng Sim
ePrint Report ePrint Report
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.
Expand
Shashank Agrawal, Saikrishna Badrinarayanan, Payman Mohassel, Pratyay Mukherjee, Sikhar Patranabis
ePrint Report ePrint Report
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.
Expand
Lübeck, Duitsland, 18 November - 20 November 2020
Event Calendar Event Calendar
Event date: 18 November to 20 November 2020
Submission deadline: 3 July 2020
Notification: 4 September 2020
Expand
Technology Innovation Institute - Abu Dhabi, UAE
Job Posting Job Posting

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

  • Expand
    Technology Innovation Institute - Abu Dhabi, UAE
    Job Posting Job Posting
    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/

  • Expand
    ISAE SUPAERO, Toulouse, France
    Job Posting Job Posting

    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

    Expand
    Technology Innovation Institute - Abu Dhabi, UAE
    Job Posting Job Posting

    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/

  • Expand

    07 June 2020

    Alexander Munch-Hansen, Claudio Orlandi, Sophia Yakoubov
    ePrint Report ePrint Report
    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.
    Expand
    ◄ Previous Next ►