International Association
for Cryptologic Research

Protocols for secure Multi-Party Computation (MPC) can be classified according to the underlying communication model. Two prominent communication models considered in the literature are the synchronous and asynchronous models, which considerably differ in terms of the achievable security guarantees. Synchronous MPC protocols can achieve the optimal corruption threshold $n/2$ and allow every party to give input, but become completely insecure when synchrony assumptions are violated. On the other hand, asynchronous MPC protocols remain secure under arbitrary network conditions, but can tolerate only $n/3$ corruptions and parties with slow connections unavoidably cannot give input.

A natural question is whether there exists a protocol for MPC that can tolerate up to $t_s < n/2$ corruptions under a synchronous network and $t_a < n/3$ corruptions even when the network is asynchronous. We answer this question by showing tight feasibility and impossibility results. More specifically, we show that such a protocol exists if and only if $t_a + 2t_s < n$ and the number of inputs taken into account under an asynchronous network is at most $n-t_s$.

Timed-release encryption (TRE) makes it possible to send information ``into the future'' such that a pre-determined amount of time needs to pass before the information can be decrypted, which has found numerous applications. The most prominent construction is based on sequential squaring in RSA groups, proposed by Rivest et al. in 1996. Malavolta and Thyagarajan (CRYPTO'19) recently proposed an interesting variant of TRE called homomorphic time-lock puzzles (HTLPs). Here one considers multiple puzzles which can be independently generated by different entities. One can homomorphically evaluate a circuit over these puzzles to obtain a new puzzle. Solving this new puzzle yields the output of a circuit evaluated on all solutions of the original puzzles. While this is an interesting concept and enables various new applications, for constructions under standard assumptions one has to rely on sequential squaring.

We observe that viewing HTLPs as homomorphic TRE gives rise to a simple generic construction that avoids the homomorphic evaluation on the puzzles and thus the restriction of relying on sequential squaring. It can be instantiated based on any TLP, such as those based on one-way functions and the LWE assumption (via randomized encodings), while providing essentially the same functionality for applications. Moreover, it overcomes the limitation of the approach of Malavolta and Thyagarajan that, despite the homomorphism, one puzzle needs to be solved per decrypted ciphertext. Hence, we obtain a ``solve one, get many for free'' property for an arbitrary amount of encrypted data, as we only need to solve a single puzzle independent of the number of ciphertexts. In addition, we introduce the notion of incremental TLPs as a particularly useful generalization of TLPs, which yields particularly practical (homomorphic) TRE schemes. Finally, we demonstrate various applications by firstly showcasing their cryptographic application to construct dual variants of timed-release functional encryption and also show that we can instantiate previous applications of HTLPs in a simpler and more efficient way.

In this article, we propose GIFT-COFB, an Authenticated Encryption with Associated Data (AEAD) scheme, based on the GIFT lightweight block cipher and the COFB lightweight AEAD operating mode. We explain how these two primitives can fit together and the various design adjustments possible for performance and security improvements. We show that our design provides excellent performances in all constrained scenarios, hardware or software, while being based on a provably-secure mode and a well analysed block cipher.

Today's most compact zero-knowledge arguments are based on the hardness of the discrete logarithm problem and related classical assumptions. If one is interested in quantum-safe solutions, then all of the known techniques stem from the PCP-based framework of Kilian (STOC 92) which can be instantiated based on the hardness of any collision-resistant hash function. Both approaches produce asymptotically logarithmic sized arguments but, by exploiting extra algebraic structure, the discrete logarithm arguments are a few orders of magnitude more compact in practice than the generic constructions.

In this work, we present the first (poly)-logarithmic, potentially post-quantum zero-knowledge arguments that deviate from the PCP approach. At the core of succinct zero-knowledge proofs are succinct commitment schemes (in which the commitment and the opening proof are sub-linear in the message size), and we propose two such constructions based on the hardness of the (Ring)-Short Integer Solution (Ring-SIS) problem, each having certain trade-offs. For commitments to $N$ secret values, the communication complexity of our first scheme is $\tilde{O}(N^{1/c})$ for any positive integer $c$, and $O(\log^2 N)$ for the second. Both of these are a significant theoretical improvement over the previously best lattice construction by Bootle et al. (CRYPTO 2018) which gave $O(\sqrt{N})$-sized proofs.

In the setting of continual-leakage (CL) --- Brakerski \emph{et al.}, Dodis \emph{et al.}, FOCS 2010 --- the secret key of a cryptographic scheme evolves according to time periods; the adversary gets some bounded leakage function of its choice applied to the current secret key in each time period. This model necessitates a \emph{randomized} key update procedure, as otherwise the adversary can leak a future secret key bit by bit over time. Unfortunately, this is a major source of difficulty, for example in handling leakage on updates. On the other hand, the above reason why a randomized key update procedure is required is arguably unsatisfying, since in practice a leakage function will not continually compute the update procedure and leak a future key in whole.

Our goal is to provide a general security model for continual leakage with deterministic key updates, and constructions that improve in various respects on prior work. In fact, as described below we incorporate forward security into our model as well. For our basic security model we take an \emph{entropy-based} approach, leading to a model we call \emph{entropic continual leakage} (ECL). In the ECL model, the adversary is allowed to make a limited total number of leakage queries that, as in CL, can depend arbitrarily on other keys (in particular, we do not completely bar the leakage function from ``computing the update procedure''), but an \emph{unlimited} total number of what we call ``local'' leakage queries. The latter does not decrease computational entropy of other keys. Hence, in some sense, the local leakage queries do not compute the key update procedure. Another major benefit of allowing deterministic key updates is that we can more readily incorporate forward security (FS) in our constructions, recently pointed out by Bellare \emph{et al.} (CANS 2017) to be an important security hedge in this context. This is because techniques for achieving FS often require deterministic updates. Accordingly, we also introduce the FS+ECL model (which is in fact incomparable to the CL model). We target this enhanced model for our constructions and provide constructions of public-key encryption (based on non-interactive key exchange) and digital signatures (based on identification schemes) that improve over the assumptions or leakage rates of the FS+CL schemes of Bellare \emph{et al.}. These results demonstrate the feasibility of improved constructions in our more realistic model. Finally, as a result of independent interest, we present a public-key encryption scheme in the FS+CL model (with randomized update) that improves on both the assumptions and leakage rates compared to the scheme of Bellare \emph{et al}.

We present a new short zero-knowledge argument for the range proof and the arithmetic circuits without a trusted setup. In particular, the proof size of our protocol is the shortest of the category of proof systems with a trustless setup. More concretely, when proving a committed value is a positive integer less than 64 bits, except for negligible error in the $128$-bit security parameter, the proof size is $576$ byte long, which is of $85.7\%$ size of the previous shortest one due to B\"unz et al.~(Bulletproofs, IEEE Security and Privacy 2018), while computational overheads in both proof generation and verification are comparable with those of Bulletproofs, respectively. Bulletproofs is established as one of important privacy enhancing technologies for distributed ledger, due to its trustless feature and short proof size. In particular, it has been implemented and optimized in various programming languages for practical usages by independent entities since it proposed. The essence of Bulletproofs is based on the logarithmic inner product argument with no zero-knowledge. In this paper, we revisit Bulletproofs from the viewpoint of the first sublinear zero-knowledge argument for linear algebra due to Groth~(CRYPTO 2009) and then propose Bulletproofs+, an improved variety of Bulletproofs. The main ingredient of our proposal is the zero-knowledge weighted inner product argument (zk-WIP) to which we reduce both the range proof and the arithmetic circuit proof. The benefit of reducing to the zk-WIP is a minimal transmission cost during the reduction process. Note the zk-WIP has all nice features of the inner product argument such as an aggregating range proof and batch verification.

We provide a simple and complete proof of the famous Pi&#8853;Pj Theorem in the particular case where &#958;max=2. This Theorem gives a lower bound for the number of solutions of simple linear systems of equations in the case where all the variables have to be pairwise distinct. Such systems often occur in cryptographic proofs of security, and this particular Theorem can be used to prove that the function x&#8614;P(0||x)&#8853;P(1||x) is an optimally secure pseudorandom function when P is a uniformly random permutation.

Event date: 14 June to 17 June 2021
Submission deadline: 5 February 2021
Notification: 5 April 2021

About be-ys

Be-ys creates and monitors digital solutions for sensitive data processing in demanding business sectors such as healthcare and banking.
We are the national leader in data security, which is expanding internationally and deploying its solutions using state-of-the-art technologies.
We are now looking for new talents to strengthen our leading position and continue bringing innovation to the market.

Job Description

Our Be ys Pay subsidiary has created worldwide payment solutions. Our aim is to develop disruptive technologies for bank payment systems with smart card, mobile device and Blockchain. As part of its development, we are looking for a Software Developer for Payment Systems.
As part of an expert team dedicated to the payment technology, smart card, blockchain, cryptography and cryptography business sectors, your main tasks will be to develop products in C, C++, Java and NodeJS languages for smart card personalization, payment transaction authorization, token generation/validation and wallets for mobile devices.
You will be responsible for the development and implementation of algorithms, protocols and applications for PC or mobile devices for smart card issuance, as well as the development of solutions for the validation and generation of tokens for banking payment systems.

Profile description

• You have a 5-year degree in engineering, development and/or crypto
• You have an excellent knowledge of C, C++, Java and cryptography.
• Knowledge of payment technology with EMV standard and Blockchain would be a plus.
• You enjoy working as part of a team and working collaboratively in an agile mode.
• You are autonomous, proactive and have an interest in experimenting.
• You like innovation and enjoy working in a constantly changing environment.
• You must be fluent in English (written and spoken).

Closing date for applications:

Contact: Above all, we are looking for potential. We believe that passion for the job and skills are the key to a successful employee.
We transform your energy into talent.
To apply, please send your resume to: recrutement@almerys.com

Securing components for the IoT market, as well as critical cyberphysical infrastructures, requires analyzing their vulnerabilities and defining hardware and software countermeasures at the fair cost. The increasing complexity of the processors and the applications they run means that the software fault models (such as instruction skips, or instruction replacement) usually used to analyze the vulnerability of their code are no longer sufficient to express the diversity of faulty behaviors in modern architectures [1]. Indeed, architecture designers have progressively added many complex hardware blocks (such as pipeline, cache memory, branch prediction, or speculative execution) to processors in order to optimize program execution. At the same time, fault injection techniques are constantly progressing (e.g., localized ElectroMagnetic or laser attacks, glitch injection attacks) allowing today higher-order injections (both multi-temporal and multi-spatial). Faced with these attacks, designers must implement countermeasures to detect or mask the effects of injected faults. These countermeasures can be implemented at the hardware level (e.g., duplication of elements, error correcting codes, isolation mechanisms) or at the software level (e.g., duplication of instructions or algorithms, insertion of security tests, signature verification). The design and validation of these countermeasures requires a realistic representation of the effects of faulty attacks (fault model) at the hardware and/or software level. The difficulties encountered are then: (1) the relevance of the fault models: do these fault models correctly represent the effects that an attacker can generate on a target processor? (2) the adequacy of countermeasures: do the countermeasures effectively protect the system, are they oversized and therefore too costly? (3) the link between software and hardware countermeasures: how to combine software and hardware countermeasures efficiently and at the fair cost, how to link the different levels for fault modeling? The CLAM project and the thesis that we propose aim to answer these questions by associating 3 French laboratories with complementary specialties.

Closing date for applications:

Contact: vincent.beroulle(at)lcis.grenoble-inp.fr; paolo.maistri(at)univ-grenoble-alpes.fr

More information: https://lcis.grenoble-inp.fr/medias/fichier/clam-thesis-subject-lcis-valence-en-_1592239520450-pdf?ID_FICHE=559219&INLIN

The Department of Information Technology at Uppsala University invites applications for an Associate Professor in Computer Science with specialization in Cybersecurity The department hosts many successful research efforts on different aspects of cybersecurity, which have attracted a significant amount of external funding. We are now in the process to establish cybersecurity as a strong and visible area in research and teaching. The holder of the position is expected to develop a teaching and research profile in cybersecurity, as well as to take leadership responsibilities in cybersecurity activities within the department. Application Deadline: June 22.

Closing date for applications:

Contact: Christian Rohner (christian.rohner@it.uu.se)

More information: https://uu.se/en/about-uu/join-us/details/?positionId=325568

The new-age processor is going to require hardware-oriented solutions as a primary design criterion for the security against threats. Alternative computational architectures proposed in recent years drive this idea by the inclusion of multi-value logic operations. The realization of multi-value logic gates and testing the advantages of polymorphic inputs and outputs of a circuit, however, remains elusive due to the existing technology gap. In this project, we put forward a new logic-locking framework that will allow us to incorporate multi-value and multi-layer logic with existing CMOS-based logic-locking architectures. Enabling future-generation processors with BioNanoLock is the prime target of the project with small (10-100 logic gates) to medium-sized (100-10000 logic gates) circuits as an intermediate goal. We also envision developing heterogeneous integrated systems for secure information processing in the long-term. In BioNanoLock, an encoded DNA sequence acts as a secret ‘biological activation-key’. This key is molecularly recognized as a unique and secret pattern of key-gates (called biological key-gates) or activates them. This, in turn, enables the CMOS-based key-gates in the logic-locked circuit with the appropriate key value. Different voltage-levels in the multi-valued logic define the “on” or “off” state of the key-gates, thereby adding another level of ambiguity for an attacker and making it harder for the attacker to unlock the circuit. Moving away from the classical CMOS-based techniques for logic locking, the BioNanoLock project enables the researchers to delve into novel logic locking techniques. The project also provides opportunities to map the new logic locking paradigms and attack methodologies to a different class of problems in the complexity theory. As novel simulation methodologies are unexplored in the interdisciplinary domain, the project provides ample opportunities for research and innovation.

Closing date for applications:

Contact: Dr. Farhad Merchant (farhad.merchant@ice.rwth-aachen.de)

More information: https://www.ice.rwth-aachen.de/institute/jobs/job-offer-research-assistant-phd-student-for-bionanolock-project-1/

The candidates for the NIST Post-Quantum Cryptography standardization have undergone extensive studies on efficiency and theoretical security, but research on their side-channel security is largely lacking. This remains a considerable obstacle for their real-world deployment, where side-channel security can be a critical requirement. This work describes a side-channel resistant instance of Saber, one of the lattice-based candidates, using masking as a countermeasure. Saber proves to be very efficient to mask due to two specific design choices: power-of-two moduli, and limited noise sampling of learning with rounding. A major challenge in masking lattice-based cryptosystems is the integration of bit-wise operations with arithmetic masking, requiring algorithms to securely convert between masked representations. The described design includes a novel primitive for masked logical shifting on arithmetic shares, as well as adapts an existing masked binomial sampler for Saber. An implementation is provided for an ARM Cortex-M4 microcontroller, and its side-channel resistance is experimentally demonstrated. The masked implementation features a 2.5x overhead factor, significantly lower than the 5.7x previously reported for a masked variant of NewHope. Masked key decapsulation requires less than 3,000,000 cycles on the Cortex-M4 and consumes less than 12kB of dynamic memory, making it suitable for deployment in embedded platforms.

Database management systems (DBMS) are one of cloud services with great interests in industry and business. In such services, since there is no trust in the cloud servers, the databases are encrypted prior to outsourcing. One of the most challenging issues in designing these services is supporting SQL join queries on the encrypted database. The multi-adjustable join scheme (M-Adjoin) [Khazaei-Rafiee 2019], an extension of Adjoin [Popa-Zeldovich 2012 and Mironov-Segev-Shahaf 2017], is a symmetric-key primitive that supports the join queries for a list of column labels on an encrypted database. In previous works, the following security notions were introduced for Adjoin and M-Adjoin schemes: 3Partition, M3Partition and M3P k , for every integer k . Additionally, simulation-based and indistinguishability-based security notions have been defined by Mironov et al. for Adjoin scheme. In this paper, we extend their results to M-Adjoin and study the relations between all security notions for M-Adjoin. Some non-trivial relations are proved which resolve some open problems raised by [Mironov-Segev-Shahaf 2017].

PMAC is a rate-1, parallelizable, block-cipher-based message authentication code (MAC), proposed by Black and Rogaway (EUROCRYPT 2002). Improving the security bound is a main research topic for PMAC. In particular, showing a tight bound is the primary goal of the research, since Luykx et al.'s paper (EUROCRYPT 2016). Regarding the pseudo-random-function (PRF) security of PMAC, a collision of the hash function, or the difference between a random permutation and a random function offers the lower bound $\Omega(q^2/2^n)$ for $q$ queries and the block cipher size $n$. Regarding the MAC security (unforgeability), a hash collision for MAC queries, or guessing a tag offers the lower bound $\Omega(q_m^2/2^n + q_v/2^n)$ for $q_m$ MAC queries and $q_v$ verification queries (forgery attempts). The tight upper bound of the PRF-security $O(q^2/2^n)$ of PMAC was given by Ga\v{z} et el. (ToSC 2017, Issue 1), but their proof requires a 4-wise independent masking scheme that uses 4 $n$-bit random values. Open problems from their work are: (1) find a masking scheme with three or less random values with which PMAC has the tight upper bound for PRF-security; (2) find a masking scheme with which PMAC has the tight upper bound for MAC-security.

In this paper, we consider PMAC with three powering-up masks that uses three random values for the masking scheme. We show that the PMAC has the tight upper bound $O(q^2/2^n)$ for PRF-security, which answers the open problem (1), and the tight upper bound $O(q_m^2/2^n + q_v/2^n)$ for MAC-security, which answers the open problem (2). Note that these results deal with two-key PMAC, thus showing tight upper bounds of PMACs with single-key and/or with two (or one) powering-up masks are open problems.

Time-locked puzzles---problems whose solution requires some amount of (inherently) sequential effort---have seen a recent increase in popularity (e.g., in the context of verifiable delay functions). Most constructions rely on the conjecture that, given a random~$x$, computing $x^{2^T} \bmod N$ requires at least $T$ (sequential) steps. We study the security of time-locked primitives from two perspectives:

We give the first hardness result about the sequential squaring conjecture. Namely, we show that even in (a quantitative version of) the algebraic group model, any speed up of sequential squaring is as hard as factoring~$N$.

We then focus on \emph{timed commitments}, one of the most important primitives that can be obtained from time-locked puzzles. We extend existing security definitions to settings that may arise when using timed commitments in higher-level protocols. We then give the first construction of \emph{non-malleable} timed commitments. As a building block of independent interest, we also define (and give constructions for) a new primitive called \emph{time-released public-key encryption}.

We present a new protocol for two-party private set intersection (PSI) with semi-honest security in the plain model and one-sided malicious security in the random oracle model. Our protocol achieves a better balance between computation and communication than existing PSI protocols. Specifically, our protocol is the fastest in networks with moderate bandwidth (e.g., $30 - 100$ Mbps). Considering the monetary cost (proposed by Pinkas et al. in CRYPTO 2019) to run the protocol on a cloud computing service, our protocol also compares favorably.

Underlying our PSI protocol is a new lightweight multi-point oblivious pesudorandom function (OPRF) protocol based on oblivious transfer (OT) extension. We believe this new protocol may be of independent interest.

We present our discovery of a group of side-channel vulnerabilities in implementations of the ECDSA signature algorithm in a widely used Atmel AT90SC FIPS 140-2 certified smartcard chip and five cryptographic libraries (libgcrypt, wolfSSL, MatrixSSL, SunEC/OpenJDK/Oracle JDK, Crypto++). Vulnerable implementations leak the bit-length of the scalar used in scalar multiplication via timing. Using leaked bit-length, we mount a lattice attack on a 256-bit curve, after observing enough signing operations. We propose two new methods to recover the full private key requiring just 500 signatures for simulated leakage data, 1200 for real cryptographic library data, and 2100 for smartcard data.

The number of signatures needed for a successful attack depends on the chosen method and its parameters as well as on the noise profile, influenced by the type of leakage and used computation platform. We use the set of vulnerabilities reported in this paper, together with the recently published TPM-FAIL vulnerability as a basis for real-world benchmark datasets to systematically compare our newly proposed methods and all previously published applicable lattice-based key recovery methods. The resulting exhaustive comparison highlights the methods' sensitivity to its proper parametrization and demonstrates that our methods are more efficient in most cases. For the TPM-FAIL dataset, we decreased the number of required signatures from approximately 40 000 to mere 900.

An increasing number of lightweight cryptographic primitives have been published recently. Some of these proposals are ARX primitives, which have shown a great performance in software. Rotational-XOR cryptanalysis is a statistical technique to attack ARX primitives. In this paper, a computer tool to speed up and make easier the security evaluation of ARX block ciphers against rotational-XOR cryptanalysis is shown. Our tool takes a Python implementation of an ARX block cipher and automatically finds an optimal rotational-XOR characteristic. Compared to most of the automated tools, which only support a small set of primitives, our tool supports any ARX block cipher and it is executed with a simple shell command.

We consider the theoretically-sound selection of cryptographic parameters, such as the size of algebraic groups or RSA keys, for TLS 1.3 in practice. While prior works gave security proofs for TLS 1.3, their security loss is quadratic in the total number of sessions across all users, which due to the pervasive use of TLS is huge. Therefore, in order to deploy TLS 1.3 in a theoretically-sound way, it would be necessary to compensate this loss with unreasonably large parameters that would be infeasible for practical use at large scale. Hence, while these previous works show that in principle the design of TLS 1.3 is secure in an asymptotic sense, they do not yet provide any useful concrete security guarantees for real-world parameters used in practice. In this work, we provide a new security proof for the cryptographic core of TLS 1.3, which reduces the security of TLS 1.3 tightly (that is, with constant security loss) to the (multi-user) security of its building blocks. For some building blocks, such as the symmetric record layer encryption scheme, we can then rely on prior work to establish tight security. For others, such as the RSA-PSS digital signature scheme currently used in TLS 1.3, we obtain at least a linear loss in the number of users, independent of the number of sessions, which is much easier to compensate with reasonable parameters. Our work also shows that by replacing the RSA-PSS scheme with a tightly-secure scheme (e. g., in a future TLS version), one can obtain the first fully tightly-secure TLS protocol. Our results enable a theoretically-sound selection of parameters for TLS 1.3, even in large-scale settings with many users and sessions per user.