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

12
October
2018

Event Calendar
SACMAT 2019: 24th ACM Symposium on Access Control Models and Technologies
Toronto, Canada, 4 June - 6 June 2019

Event date: 4 June to 6 June 2019

Submission deadline: 10 February 2019

Notification: 8 April 2019

Submission deadline: 10 February 2019

Notification: 8 April 2019

9
October
2018

A key-dependent message (KDM) secure encryption scheme is secure even if an adversary obtains encryptions of messages that depend on the secret key. Such key-dependent encryptions naturally occur in scenarios such as harddisk encryption, formal cryptography, or in specific protocols. However, there are not many provably secure constructions of KDM-secure encryption schemes. Moreover, only one construction, due to Camenisch, Chandran, and Shoup (Eurocrypt 2009) is known to be secure against active (i.e., CCA) attacks.

In this work, we construct the first public-key encryption scheme that is KDM-secure against active adversaries and has compact ciphertexts. As usual, we allow only circular key dependencies, meaning that encryptions of arbitrary *entire* secret keys under arbitrary public keys are considered in a multi-user setting.

Technically, we follow the approach of Boneh, Halevi, Hamburg, and Ostrovsky (Crypto 2008) to KDM security, which however only achieves security against passive adversaries. We explain an inherent problem in adapting their techniques to active security, and resolve this problem using a new technical tool called ``lossy algebraic filters'' (LAFs). We stress that we significantly deviate from the approach of Camenisch, Chandran, and Shoup to obtain KDM security against active adversaries. This allows us to develop a scheme with compact ciphertexts that consist only of a constant number of group elements.

In this work, we construct the first public-key encryption scheme that is KDM-secure against active adversaries and has compact ciphertexts. As usual, we allow only circular key dependencies, meaning that encryptions of arbitrary *entire* secret keys under arbitrary public keys are considered in a multi-user setting.

Technically, we follow the approach of Boneh, Halevi, Hamburg, and Ostrovsky (Crypto 2008) to KDM security, which however only achieves security against passive adversaries. We explain an inherent problem in adapting their techniques to active security, and resolve this problem using a new technical tool called ``lossy algebraic filters'' (LAFs). We stress that we significantly deviate from the approach of Camenisch, Chandran, and Shoup to obtain KDM security against active adversaries. This allows us to develop a scheme with compact ciphertexts that consist only of a constant number of group elements.

ePrint Report
On Tightly Secure Primitives in the Multi-Instance Setting
Dennis Hofheinz, Ngoc Khanh Nguyen

We initiate the study of general tight reductions in cryptography. There already exist a variety of works that offer tight reductions for a number of cryptographic tasks, ranging from encryption and signature schemes to proof systems. However, our work is the first to provide a universal definition of a tight reduction (for arbitrary primitives), along with several observations and results concerning primitives for which tight reductions have not been known.

Technically, we start from the general notion of reductions due to Reingold, Trevisan, and Vadhan (TCC 2004), and equip it with a quantification of the respective reduction loss, and a canonical multi-instance extension to primitives. We then revisit several standard reductions whose tight security has not yet been considered. For instance, we revisit a generic construction of signature schemes from one-way functions, and show how to tighten the corresponding reduction by assuming collision-resistance from the used one-way function. We also obtain tightly secure pseudorandom generators (by using suitable rerandomisable hard-core predicates), and tightly secure lossy trapdoor functions.

Technically, we start from the general notion of reductions due to Reingold, Trevisan, and Vadhan (TCC 2004), and equip it with a quantification of the respective reduction loss, and a canonical multi-instance extension to primitives. We then revisit several standard reductions whose tight security has not yet been considered. For instance, we revisit a generic construction of signature schemes from one-way functions, and show how to tighten the corresponding reduction by assuming collision-resistance from the used one-way function. We also obtain tightly secure pseudorandom generators (by using suitable rerandomisable hard-core predicates), and tightly secure lossy trapdoor functions.

An obfuscated program reveals nothing about its design other than its
input/output behavior. A digital locker is an obfuscated program that outputs
a stored cryptographic key if and only if a user enters a previously stored
password. A digital locker is private if it provides an adversary with no
information with high probability. An ideal digital locker would also prevent an
adversary from mauling an obfuscation on one password and key into a new
program that obfuscates a related password or key. There are no known
constructions of non-malleable digital lockers (in the standard model).

Komargodski and Yogev (Eurocrypt, 2018) constructed a simpler primitive: a non-malleable keyless digital locker. For this functionality, a user can only confirm if their point is correct. This primitive is known as non-malleable point obfuscation. Their construction prevents an adversary from transforming an obfuscation into an obfuscation on a related password.

This work proposes two new composable and nonmalleable digital lockers for short keys, one for a single bit key and a second for a logarithmic length keys. Using these construction we construct the first two non-malleable digital lockers. Our full design combines a digital locker for short keys, non-malleable codes, and universal hashing. Our constructions require a common reference string.

Komargodski and Yogev (Eurocrypt, 2018) constructed a simpler primitive: a non-malleable keyless digital locker. For this functionality, a user can only confirm if their point is correct. This primitive is known as non-malleable point obfuscation. Their construction prevents an adversary from transforming an obfuscation into an obfuscation on a related password.

This work proposes two new composable and nonmalleable digital lockers for short keys, one for a single bit key and a second for a logarithmic length keys. Using these construction we construct the first two non-malleable digital lockers. Our full design combines a digital locker for short keys, non-malleable codes, and universal hashing. Our constructions require a common reference string.

ePrint Report
Key-Insulated and Privacy-Preserving Signature Scheme with Publicly Derived Public Key
Zhen Liu, Guomin Yang, Duncan S. Wong, Khoa Nguyen, Huaxiong Wang

Since the introduction of Bitcoin in 2008, cryptocurrency has been undergoing a quick and explosive development. At the same time, privacy protection, one of the key merits of cryptocurrency, has attracted much attention by the community.
In this paper, we identify a security vulnerability of the privacy-preserving key derivation algorithm of Monero, which is one of the most popular privacy-centric cryptocurrencies.
To provide a formal treatment for the problem, we introduce and formalize a new signature variant, called Key-Insulated and Privacy-Preserving Signature Scheme with Publicly Derived Public Key (PDPKS), which forms a convenient and robust cryptographic tool for building privacy-preserving cryptocurrencies.
Specifically, PDPKS allows anyone to derive new signature verification keys for a user, say Alice, based on her long-term public-key, while only Alice can derive the signing keys corresponding to those verification keys.
In terms of privacy, given a derived verification key and valid signatures with respect to it, an adversary is not able to link them to the underlying long-term public key;
and given two verification keys and corresponding valid signatures, an adversary cannot tell whether the verification keys are derived from the same long-term public key.
A distinguishing security feature of PDPKS, with the above functionality and privacy features, is that the derived keys are independent/insulated from each other, namely, compromising the signing key associated with a verification key does not allow an adversary to forge a valid signature for another verification key, even if both verification keys are derived from the same long-term public key.

We formalize the notion of PDPKS and propose a practical and proven secure construction, which fixes the identified security vulnerability in Monero and provides a more robust solution for implementing the so-called stealth addresses for cryptocurrencies. Also, our PDPKS scheme can be used to fix the similar vulnerability in the deterministic wallet algorithm for Bitcoin.

We formalize the notion of PDPKS and propose a practical and proven secure construction, which fixes the identified security vulnerability in Monero and provides a more robust solution for implementing the so-called stealth addresses for cryptocurrencies. Also, our PDPKS scheme can be used to fix the similar vulnerability in the deterministic wallet algorithm for Bitcoin.

A Sparse Merkle tree is based on the idea of a complete Merkle tree of an intractable size. The assumption here is that as the size of the tree is intractable, there would only be a few leaf nodes with valid data blocks relative to the tree size, rendering the tree as sparse. We present a novel approach called Minimum distance path algorithm to simulate this Merkle tree of intractable size which gives us eﬃcient space-time trade-oﬀs. We provide the algorithms for insertion, deletion and (non -) membership proof for a leaf in this Compact Sparse Merkle tree.

ePrint Report
Efficient Ratcheting: Almost-Optimal Guarantees for Secure Messaging
Daniel Jost, Ueli Maurer, Marta Mularczyk

In the era of mass surveillance and information breaches, privacy of Internet communication, and messaging in particular, is a growing concern. As secure messaging protocols are executed on the not-so-secure end-user devices, and because their sessions are long-lived, they aim to guarantee strong security even if secret states and local randomness can be exposed.

The most basic security properties, including forward secrecy, can be achieved using standard techniques such as authenticated encryption. Modern protocols, such as Signal, go one step further and additionally provide the so-called backward secrecy, or healing from state exposures. These additional guarantees come at the price of a slight efficiency loss (they require public-key primitives).

On the opposite side of the spectrum is the work by Jaeger and Stepanovs and by Poettering and Roesler, which characterizes the optimal security a secure-messaging scheme can achieve. However, their proof-of-concept constructions suffer from an extreme efficiency loss compared to Signal. Moreover, this caveat seems inherent.

In this paper, we explore the area in between. That is, our starting point are the basic, efficient constructions. We then ask the question: how far can we go towards the optimal security without losing too much efficiency? We present a construction with guarantees much stronger than those achieved by Signal, and slightly weaker than optimal, yet its efficiency is closer to that of Signal (we only use standard public-key cryptography).

On a technical level, achieving optimal guarantees inherently requires key-updating public-key primitives, where the update information is allowed to be public. We consider secret update information instead. Since a state exposure temporally breaks confidentiality, we carefully design such secretly-updatable primitives whose security degrades gracefully if the supposedly secret update information leaks.

The most basic security properties, including forward secrecy, can be achieved using standard techniques such as authenticated encryption. Modern protocols, such as Signal, go one step further and additionally provide the so-called backward secrecy, or healing from state exposures. These additional guarantees come at the price of a slight efficiency loss (they require public-key primitives).

On the opposite side of the spectrum is the work by Jaeger and Stepanovs and by Poettering and Roesler, which characterizes the optimal security a secure-messaging scheme can achieve. However, their proof-of-concept constructions suffer from an extreme efficiency loss compared to Signal. Moreover, this caveat seems inherent.

In this paper, we explore the area in between. That is, our starting point are the basic, efficient constructions. We then ask the question: how far can we go towards the optimal security without losing too much efficiency? We present a construction with guarantees much stronger than those achieved by Signal, and slightly weaker than optimal, yet its efficiency is closer to that of Signal (we only use standard public-key cryptography).

On a technical level, achieving optimal guarantees inherently requires key-updating public-key primitives, where the update information is allowed to be public. We consider secret update information instead. Since a state exposure temporally breaks confidentiality, we carefully design such secretly-updatable primitives whose security degrades gracefully if the supposedly secret update information leaks.

ePrint Report
A Comparative Evaluation of Order-Preserving and Order-Revealing Schemes and Protocols
Dmytro Bogatov, George Kollios, Leo Reyzin

Database query evaluation over encrypted data has received a lot of attention recently.
Order Preserving Encryption (OPE) and Order Revealing Encryption (ORE) are two important encryption schemes that have been proposed in this area.
These schemes can provide very efficient query execution but at the same time may leak some information to adversaries.
In this paper, we present the first comprehensive comparison among a number of important OPE and ORE schemes using a framework that we developed.
We evaluate protocols that are based on these schemes as well.
We analyze and compare them both theoretically and experimentally and measure their performance over database indexing and query evaluation techniques using not only execution time but also {\IO} performance and usage of cryptographic primitive operations.
Our comparison reveals some interesting insights concerning the relative security and performance of these approaches in database settings.
Furthermore, we propose a number of improvements for some of these scheme and protocols.
Finally, we provide a number of suggestions and recommendations that can be valuable to database researchers and users.

ePrint Report
Approximate Homomorphic Encryption over the Conjugate-invariant Ring
Duhyeong Kim, Yongsoo Song

The Ring Learning with Errors (RLWE) problem over a cyclotomic ring has been the most widely used hardness assumption for the construction of practical homomorphic encryption schemes. However, this restricted choice of a base ring may cause a waste in terms of plaintext space usage. For example, the approximate homomorphic encryption scheme of Cheon et al. (ASIACRYPT'17) is able to store a complex number in each of the plaintext slots since its canonical embedding of a cyclotomic field has a complex image. The imaginary part of a plaintext is not underutilized at all when the computation is performed over the real numbers, which is required in most of the real-world applications such as machine learning.

In this paper, we propose a new approximate homomorphic encryption scheme which is optimized in the computation over real numbers. Our scheme is based on RLWE over a special subring of a cyclotomic ring, which is no easier than a standard lattice problem over ideal lattices by the reduction of Peikert et al. (STOC'17). Our scheme allows real numbers to be packed in a ciphertext without any waste of a plaintext space and consequently we can encrypt twice as many plaintext slots as the previous scheme while maintaining the same security level, storage, and computational costs.

In this paper, we propose a new approximate homomorphic encryption scheme which is optimized in the computation over real numbers. Our scheme is based on RLWE over a special subring of a cyclotomic ring, which is no easier than a standard lattice problem over ideal lattices by the reduction of Peikert et al. (STOC'17). Our scheme allows real numbers to be packed in a ciphertext without any waste of a plaintext space and consequently we can encrypt twice as many plaintext slots as the previous scheme while maintaining the same security level, storage, and computational costs.

In the area of card-based cryptography one devises small and easy to perform protocols for secure multiparty computation using a deck of physical playing cards with indistinguishable backs, which can be run if no trusted computer is available, or in classroom settings to illustrate privacy notions and secure computations.

Initiated by the “Five-Card Trick” of den Boer (EUROCRYPT 1989) for computing the AND of two players' bits, and the work of Crépeau and Kilian (CRYPTO 1993) introducing committed format protocols which can be used as building blocks in larger computations, this is a field with a growing number of simple protocols. This paper devises two new AND protocols which are card-minimal w.r.t. specific requirements, and shows the card-minimality of the COPY protocol (necessary in arbitrary circuits, due to the physical nature of card-encoded bits) of Mizuki and Sone (FAW 2009) and the AND protocol of Abe et al. (APKC 2018). By this, we completely determine the landscape of card-minimal protocols with respect to runtime requirements (finite runtime or Las Vegas behavior with/without restarts) and practicality demands on the shuffling operations.

Moreover, we systematize and extend techniques for proving lower bounds on the number of cards, which we believe is of independent interest.

Initiated by the “Five-Card Trick” of den Boer (EUROCRYPT 1989) for computing the AND of two players' bits, and the work of Crépeau and Kilian (CRYPTO 1993) introducing committed format protocols which can be used as building blocks in larger computations, this is a field with a growing number of simple protocols. This paper devises two new AND protocols which are card-minimal w.r.t. specific requirements, and shows the card-minimality of the COPY protocol (necessary in arbitrary circuits, due to the physical nature of card-encoded bits) of Mizuki and Sone (FAW 2009) and the AND protocol of Abe et al. (APKC 2018). By this, we completely determine the landscape of card-minimal protocols with respect to runtime requirements (finite runtime or Las Vegas behavior with/without restarts) and practicality demands on the shuffling operations.

Moreover, we systematize and extend techniques for proving lower bounds on the number of cards, which we believe is of independent interest.

ePrint Report
Security bound for CTR-ACPKM internally re-keyed encryption mode
Liliya R. Akhmetzyanova, Evgeny K. Alekseev, Stanislav V. Smyshlyaev

In 2018 the CTR-ACPKM internally re-keyed block cipher mode was adopted in Russian Standardization System and must pass through the last formal standardization stages in IETF. The main distinctive feature of this mode is that during each message processing, the key, used for data blocks transformation, is periodically changed. In the current paper we obtained the security bound for this mode in the standard IND-CPNA security model.

ePrint Report
Constructing TI-friendly Substitution Boxes using Shift-Invariant Permutations
Si Gao, Arnab Roy, Elisabeth Oswald

The threat posed by side channels requires ciphers that can be efficiently protected in both software and hardware against such attacks. In this paper, we proposed a novel Sbox construction based on iterations of shift-invariant quadratic permutations and linear diffusions. Owing to the selected quadratic permutations, all of our Sboxes enable uniform 3-share threshold implementations, which provide first order SCA protections without any fresh randomness. More importantly, because of the "shift-invariant" property, there are ample implementation trade-offs available, in software as well as hardware. We provide implementation results (software and hardware) for a four-bit and an eight-bit Sbox, which confirm that our constructions are competitive and can be easily adapted to various platforms as claimed. We have successfully verified their resistance to first order attacks based on real acquisitions. Because there are very few studies focusing on software-based threshold implementations, our software implementations might be of independent interest in this regard.

ePrint Report
MILP-Based Automatic Differential Searches for LEA and HIGHT
Elnaz Bagherzadeh, Zahra Ahmadian

In this paper we use MILP technique for automatic search for differential characteristics of ARX ciphers LEA and HIGHT. We show
that the MILP model of the differential property of modular addition with one constant input can be represented with a much less number of linear inequalities compared to the general case. Benefiting from this new developed model for HIGHT block cipher, we can achieve a reduction of 112r out of 480r in the total number of linear constraints for MILP model of r-round of HIGHT. This saving accelerates the searching process of HIGHT about twice as fast.
We enjoy the MILP model to investigate the differential effect of these ciphers and provide a more accurate estimation for the differential probability, as well. Our observations show that despite HIGHT, LEA exhibits a strong differential effect. The details of differential effects are reflected in a more compact manner using the newly defined notion of probability polynomial. The results gained by this method improve or extend the previous results as follows. For LEA block cipher, we found more efficient 12 and 13-round differentials whose probabilities are better than
the best previous 12 and 13-round differentials for a factor of about 2^6 and 2^7, respectively. In the case of HIGHT block cipher, we found two new 12 and 13-round differentials, though with the same best reported probabilities.

Circulant UOV and Circulant Rainbow are new variants of UOV (unbalanced oil and vinegar signature scheme) and Rainbow respectively. In this short report, we study the security of these new variants Circulant UOV and Circulant Rainbow.

ePrint Report
Building an Efficient Lattice Gadget Toolkit: Subgaussian Sampling and More
Nicholas Genise, Daniele Micciancio, Yuriy Polyakov

Many advanced lattice cryptography applications require efficient algorithms for inverting the so-called "gadget" matrices, which are used to formally describe a digit decomposition problem that produces an output with specific (statistical) properties. The common gadget inversion problems are the classical (often binary) digit decomposition, subgaussian decomposition, Learning with Errors (LWE) decoding, and discrete Gaussian sampling. In this work, we build and implement an efficient lattice gadget toolkit that provides a general treatment of gadget matrices and algorithms for their inversion/sampling. The main contribution of our work is a set of new gadget matrices and algorithms for efficient subgaussian sampling that have a number of major theoretical and practical advantages over previously known algorithms. Another contribution deals with efficient algorithms for LWE decoding and discrete Gaussian sampling in the Residue Number System (RNS) representation.

We implement the gadget toolkit in PALISADE and evaluate the performance of our algorithms both in terms of runtime and noise growth. We illustrate the improvements due to our algorithms by implementing a concrete complex application, key-policy attribute-based encryption (KP-ABE), which was previously considered impractical for CPU systems (except for a very small number of attributes). Our runtime improvements for the main bottleneck operation based on subgaussian sampling range from 18x (for 2 attributes) to 289x (for 16 attributes; the maximum number supported by a previous implementation). Our results are applicable to a wide range of other advanced applications in lattice cryptography, such as GSW-based homomorphic encryption schemes, leveled fully homomorphic signatures, key-hiding PRFs and other forms of ABE, some program obfuscation constructions, and more.

We implement the gadget toolkit in PALISADE and evaluate the performance of our algorithms both in terms of runtime and noise growth. We illustrate the improvements due to our algorithms by implementing a concrete complex application, key-policy attribute-based encryption (KP-ABE), which was previously considered impractical for CPU systems (except for a very small number of attributes). Our runtime improvements for the main bottleneck operation based on subgaussian sampling range from 18x (for 2 attributes) to 289x (for 16 attributes; the maximum number supported by a previous implementation). Our results are applicable to a wide range of other advanced applications in lattice cryptography, such as GSW-based homomorphic encryption schemes, leveled fully homomorphic signatures, key-hiding PRFs and other forms of ABE, some program obfuscation constructions, and more.

ePrint Report
On the Inner Product Predicate and a Generalization of Matching Vector Families
Balthazar Bauer, Jevgēnijs Vihrovs, Hoeteck Wee

Motivated by cryptographic applications such as predicate encryption, we consider the problem of representing an arbitrary predicate as the inner product predicate on two vectors. Concretely, fix a Boolean function $P$ and some modulus $q$. We are interested in encoding $x$ to $\vec x$ and $y$ to $\vec y$ so that $$P(x,y) = 1 \Longleftrightarrow \langle\vec x,\vec y\rangle= 0 \bmod q,$$ where the vectors should be as short as possible. This problem can also be viewed as a generalization of matching vector families, which corresponds to the equality predicate. Matching vector families have been used in the constructions of Ramsey graphs, private information retrieval (PIR) protocols, and more recently, secret sharing.

Our main result is a simple lower bound that allows us to show that known encodings for many predicates considered in the cryptographic literature such as greater than and threshold are essentially optimal for prime modulus $q$. Using this approach, we also prove lower bounds on encodings for composite $q$, and then show tight upper bounds for such predicates as greater than, index and disjointness.

Our main result is a simple lower bound that allows us to show that known encodings for many predicates considered in the cryptographic literature such as greater than and threshold are essentially optimal for prime modulus $q$. Using this approach, we also prove lower bounds on encodings for composite $q$, and then show tight upper bounds for such predicates as greater than, index and disjointness.

Event Calendar
IWSEC 2019: The 14th International Workshop on Security
Tokyo, Japan, 28 August - 30 August 2019

Event date: 28 August to 30 August 2019

Submission deadline: 15 March 2019

Notification: 15 May 2019

Submission deadline: 15 March 2019

Notification: 15 May 2019

7
October
2018

Event Calendar
PQCrypto 2019: The Tenth International Conference on Post-Quantum Cryptography
Chongqing, China, 8 May - 10 May 2019

Event date: 8 May to 10 May 2019

Submission deadline: 24 November 2018

Notification: 12 January 2019

Submission deadline: 24 November 2018

Notification: 12 January 2019

5
October
2018

ePrint Report
Data-Independent Memory Hard Functions: New Attacks and Stronger Constructions
Jeremiah Blocki, Ben Harsha, Siteng Kang, Seunghoon Lee, Lu Xing, Samson Zhou

Data-Independent Memory-hard functions (iMHFs) are a key cryptographic primitive underlying the design of moderately expensive password hashing algorithms and egalitarian proofs of work that are resistant to side-channel attacks. Several goals for MHFs have been proposed including bandwidth hardness, space-time (ST) complexity, amortized area-time (aAT) complexity and sustained space complexity. An iMHF can be specified using a directed acyclic graph (DAG) $G$ with $N=2^n$ nodes and low indegree, and the cost (aAT, ST etc...) to evaluate the iMHF can be analyzed using pebbling games. In particular, given a parameter $N$ (e.g., maximum acceptable running time) we would like to design the DAG $G$ to have maximum possible pebbling cost i.e., to ensure that the iMHF is as expensive as possible for an attacker to compute. Recently, Alwen et al. (CCS'17) gave a randomized DAG construction called DRSample and proved that the aAT cost to pebble the graph was $\Omega\left( N^2/\log N\right)$. In an asymptotic sense the DRSample outperformed all prior constructions including Argon2i, the winner of the password hashing competition, which can be pebbled with aAT cost at most $\mathcal{O}\left(N^{1.767}\right)$. In this work we first prove a matching upper bound on the pebbling cost of DRSample by analyzing the greedy pebbling attack of Boneh et al. (ASIACRYPT'16). This sequential attack on DRSample is simple, easy to implement and has good concrete performance. In fact, our results show that, for practical values of $N\leq 2^{24}$, Argon2i provides stronger resistance to known pebbling attacks than DRSample reversing a finding of Alwen et al. (CCS'17). We then develop a new iMHF candidate by extending DRSample with the bit-reversal graph, and show that the iMHF resists all known attacks in practice and has optimal asymptotic performance under every MHF metric. In particular, we prove that (1) any (nearly) sequential pebbling attack (including the greedy pebbling attack) has aAT cost $\Omega\left( N^2\right)$, (2) any parallel attacker has aAT cost at least $\Omega\left(N^2/\log N\right)$ and at least $\Omega\left(N^2 \log \log N/\log N\right)$ unless one can find new depth-reducing attacks against DRSample which significantly improve upon the state of the art, (3) the graph has high bandwidth-complexity, and (4) any pebbling either has aAT cost $\omega(N^2)$ or requires at least $\Omega(N)$ steps with $\Omega(N/\log N)$ pebbles on the DAG. This makes our construction the first practical iMHF with strong guarantees on the sustained space-complexity. We also observe that the Argon2i round function can (trivially) be evaluated in parallel, which would allow an attacker to reduce aAT costs by (nearly) an order of magnitude, and we develop an inherently sequential version of the Argon2i round function that prevents this attack. We implement our new iMHF candidate (with and without the sequential round function) and show that evaluation speed is nearly identical to Argon2i. Finally, we provide a pebbling reduction which proves that in the parallel random oracle model (PROM) the cost of evaluating an iMHF like Argon2i or DRSample+BRG is given by the pebbling cost of the underlying DAG.

ePrint Report
Valiant's Universal Circuits Revisited: an Overall Improvement and a Lower Bound
Shuoyao Zhao, Yu Yu, Jiang Zhang, Hanlin Liu

A universal circuit (UC) is a general-purpose circuit that can simulate arbitrary circuits (up to a certain size $n$). At STOC 1976 Valiant presented a graph theoretic approach to the construction of UCs, where a UC is represented by an edge universal graph (EUG) and is recursively constructed using a dedicated graph object (referred to as supernode). As a main end result, Valiant constructed a 4-way supernode of size 19 and an EUG of size $4.75n\log n$ (omitting smaller terms), which remained the most size-efficient even to this day (after more than 4 decades).

Motivated by the emerging applications of UCs in various privacy preserving computation scenarios, we revisit Valiant's universal circuits, and propose a size-optimal 4-way supernode of size 18, and an EUG of size $4.5n\log n$. As a practical consequence, we reduce the size of universal circuits (and the number of AND gates) by more than 5\% in general (rather than just for small-size circuits in particular), and thus improve upon the efficiency of UC-based cryptographic applications accordingly. Our approach to the design of optimal supernodes is computer aided (rather than by hand as in previous works), which might be of independent interests. As a complement, we give lower bounds on the size of EUGs and UCs in Valiant's framework, which significantly improves upon the generic lower bound on UC size and therefore reduces the gap between theory and practice of universal circuits.

Motivated by the emerging applications of UCs in various privacy preserving computation scenarios, we revisit Valiant's universal circuits, and propose a size-optimal 4-way supernode of size 18, and an EUG of size $4.5n\log n$. As a practical consequence, we reduce the size of universal circuits (and the number of AND gates) by more than 5\% in general (rather than just for small-size circuits in particular), and thus improve upon the efficiency of UC-based cryptographic applications accordingly. Our approach to the design of optimal supernodes is computer aided (rather than by hand as in previous works), which might be of independent interests. As a complement, we give lower bounds on the size of EUGs and UCs in Valiant's framework, which significantly improves upon the generic lower bound on UC size and therefore reduces the gap between theory and practice of universal circuits.

ePrint Report
Insured MPC: Efficient Secure Multiparty Computation with Punishable Abort
Carsten Baum, Bernardo David, Rafael Dowsley

Fairness in Secure Multiparty Computation (MPC) is known to be impossible to achieve in the presence of a dishonest majority. Previous works have proposed combining MPC protocols with Cryptocurrencies in order to financially punish aborting adversaries, providing an incentive for parties to honestly follow the protocol. This approach also yields privacy-preserving Smart Contracts, where private inputs can be processed with MPC in order to determine the distribution of funds given to the contract. Unfortunately, the focus of existing work is on proving that this approach is possible and they present monolithic and mostly inefficient constructions. In this work, we put forth the first modular construction of ``Insured MPC'', where the result of the private computation of parties either yields an output describing how to distribute funds or a proof that a set of parties has misbehaved, allowing for financial punishments. Moreover, both the output and the proof of cheating are publicly verifiable, allowing third parties to independently validate an execution.

We present a highly efficient protocol which allows public verification of cheating behavior during the output stage. This scheme is constructed using a publicly verifiable homomorphic commitment scheme, for which we propose an efficient construction. Furthermore, we construct a compiler that uses any such scheme together with a Smart Contract to implement Insured MPC. This compiler requires a standard (non-private) Smart Contract. Our results are proven in the Universal Composability framework using a Global Random Oracle as the setup assumption. From a theoretical perspective, our general results provide the first characterization of sufficient properties that MPC protocols must achieve in order to be efficiently combined with Cryptocurrencies, as well as insights on publicly verifiable protocols. On the other hand, all our constructions and protocols are highly efficient and allow for a fast implementation.

We present a highly efficient protocol which allows public verification of cheating behavior during the output stage. This scheme is constructed using a publicly verifiable homomorphic commitment scheme, for which we propose an efficient construction. Furthermore, we construct a compiler that uses any such scheme together with a Smart Contract to implement Insured MPC. This compiler requires a standard (non-private) Smart Contract. Our results are proven in the Universal Composability framework using a Global Random Oracle as the setup assumption. From a theoretical perspective, our general results provide the first characterization of sufficient properties that MPC protocols must achieve in order to be efficiently combined with Cryptocurrencies, as well as insights on publicly verifiable protocols. On the other hand, all our constructions and protocols are highly efficient and allow for a fast implementation.

This tutorial demonstrates how cryptographic security notions, constructions, and game-based security proofs can be formalized using the CryptHOL framework. As a running example, we formalize a variant of the hash-based ElGamal encryption scheme and its IND-CPA security in the random oracle model. This tutorial assumes familiarity with Isabelle/HOL basics and standard cryptographic terminology.

ePrint Report
Reusable Non-Interactive Secure Computation
Melissa Chase, Yevgeniy Dodis, Yuval Ishai, Daniel Kraschewski, Tianren Liu, Rafail Ostrovsky, Vinod Vaikuntanathan

We consider the problem of Non-Interactive Secure Computation (NISC), a 2-message ``Sender-Receiver'' secure computation protocol that retains its security even when both parties can be malicious. While such protocols are easy to construct using garbled circuits and general non-interactive zero-knowledge proofs, this approach inherently makes a non-black-box use of the underlying cryptographic primitives and is infeasible in practice.

Ishai et al. (Eurocrypt 2011) showed how to construct NISC protocols that only use parallel calls to an ideal oblivious transfer (OT) oracle, and additionally make only a black-box use of any pseudorandom generator. Combined with the efficient 2-message OT protocol of Peikert et al. (Crypto 2008), this leads to a practical approach to NISC that has been implemented in subsequent works. However, a major limitation of all known OT-based NISC protocols is that they are subject to selective failure attacks that allows a malicious sender to entirely compromise the security of the protocol when the receiver's first message is reused.

Motivated by the failure of the OT-based approach, we consider the problem of basing \emph{reusable} NISC on parallel invocations of a standard arithmetic generalization of OT known as oblivious linear-function evaluation (OLE). We obtain the following results:

- We construct an information-theoretically secure reusable NISC protocol for arithmetic branching programs and general zero-knowledge functionalities in the OLE-hybrid model. Our zero-knowledge protocol only makes an absolute constant number of OLE calls per gate in an arithmetic circuit whose satisfiability is being proved. As a corollary, we get reusable NISC/OLE for general Boolean circuits using any one-way function. - We complement this by a negative result, showing that reusable NISC/OT is impossible to achieve, and a more restricted negative result for the case of the zero-knowledge functionality. This provides a formal justification for the need to replace OT by OLE. - We build a universally composable 2-message OLE protocol in the CRS model that can be based on the security of Paillier encryption and requires only a constant number of modular exponentiations. This provides the first arithmetic analogue of the 2-message OT protocols of Peikert et al. (Crypto 2008). - By combining our NISC/OLE protocol and the 2-message OLE protocol, we get protocols with new attractive asymptotic and concrete efficiency features. In particular, we get the first (designated-verifier) NIZK protocols where following a statement-independent preprocessing, both proving and verifying are entirely ``non-cryptographic'' and involve only a constant computational overhead.

Ishai et al. (Eurocrypt 2011) showed how to construct NISC protocols that only use parallel calls to an ideal oblivious transfer (OT) oracle, and additionally make only a black-box use of any pseudorandom generator. Combined with the efficient 2-message OT protocol of Peikert et al. (Crypto 2008), this leads to a practical approach to NISC that has been implemented in subsequent works. However, a major limitation of all known OT-based NISC protocols is that they are subject to selective failure attacks that allows a malicious sender to entirely compromise the security of the protocol when the receiver's first message is reused.

Motivated by the failure of the OT-based approach, we consider the problem of basing \emph{reusable} NISC on parallel invocations of a standard arithmetic generalization of OT known as oblivious linear-function evaluation (OLE). We obtain the following results:

- We construct an information-theoretically secure reusable NISC protocol for arithmetic branching programs and general zero-knowledge functionalities in the OLE-hybrid model. Our zero-knowledge protocol only makes an absolute constant number of OLE calls per gate in an arithmetic circuit whose satisfiability is being proved. As a corollary, we get reusable NISC/OLE for general Boolean circuits using any one-way function. - We complement this by a negative result, showing that reusable NISC/OT is impossible to achieve, and a more restricted negative result for the case of the zero-knowledge functionality. This provides a formal justification for the need to replace OT by OLE. - We build a universally composable 2-message OLE protocol in the CRS model that can be based on the security of Paillier encryption and requires only a constant number of modular exponentiations. This provides the first arithmetic analogue of the 2-message OT protocols of Peikert et al. (Crypto 2008). - By combining our NISC/OLE protocol and the 2-message OLE protocol, we get protocols with new attractive asymptotic and concrete efficiency features. In particular, we get the first (designated-verifier) NIZK protocols where following a statement-independent preprocessing, both proving and verifying are entirely ``non-cryptographic'' and involve only a constant computational overhead.

ePrint Report
The Proof is in the Pudding: Proofs of Work for Solving Discrete Logarithms
Marcella Hastings, Nadia Heninger, Eric Wustrow

We propose a proof of work protocol that computes the discrete logarithm of an element in a cyclic group. Individual provers generating proofs of work perform a distributed version of the Pollard rho algorithm. Such a protocol could capture the computational power expended to construct proof-of-work-based blockchains for a more useful purpose, as well as incentivize advances in hardware, software, or algorithms for an important cryptographic problem. We describe our proposed construction and elaborate on challenges and potential trade-offs that arise in designing a practical proof of work.

ePrint Report
Private Message Franking with After Opening Privacy
Iraklis Leontiadis, Serge Vaudenay

Recently Grubbs et al. [GLR17] initiated the formal study of message franking protocols. This new type of service launched by Facebook, allows the receiver in a secure messaging application to verifiably report to a third party an abusive message some sender has sent. A novel cryptographic primitive: committing AEAD has been initiated, whose functionality apart from confidentiality and authenticity asks for a compact commitment over the message, which is delivered to the receiver as part of the ciphertext. A new construction CEP (Committing Encrypt and PRF) has then been proposed, which is multi-opening secure and reduces the computational costs for the sender and the receiver.

Despite the merits of the message franking protocols [GLR17], our observation which launched this work, is that all the designs be it compositional or the CEP construction, leak too much when the receiver needs to open the abusive message to the third party. Namely, the receiver opens the entire message along with the opening key to the third party, thus confidentiality of the message is entirely broken. Moreover, the opening of the entire message increases the communication cost of the protocol and in cases of big messages being exchanged (attachments, videos, multimedia files, etc.) it might be unnecessary. We provide to the best of our knowledge the first formal treatment of message franking protocols with minimum leakage whereby only the abusive blocks are opened, while the rest non-abusive blocks of the message remain private.

First we give a new definition for multi-opening indistinguishability with partial opening (MO-IND-PO), which forces an adversary to distinguish encryptions of abusive blocks. We then design and analyze two protocols CEP-AOP1 (Committing Encrypt and PRF with After Opening Privacy) and CEP-AOP2, which adhere to the new privacy definition. As a side contribution we show a multi-opening secure CEP-AOP2 construction using only one PRF evaluation over the message, in a weaker but meaningful security model, relying only on standard assumptions of the underlying symmetric primitives.

Despite the merits of the message franking protocols [GLR17], our observation which launched this work, is that all the designs be it compositional or the CEP construction, leak too much when the receiver needs to open the abusive message to the third party. Namely, the receiver opens the entire message along with the opening key to the third party, thus confidentiality of the message is entirely broken. Moreover, the opening of the entire message increases the communication cost of the protocol and in cases of big messages being exchanged (attachments, videos, multimedia files, etc.) it might be unnecessary. We provide to the best of our knowledge the first formal treatment of message franking protocols with minimum leakage whereby only the abusive blocks are opened, while the rest non-abusive blocks of the message remain private.

First we give a new definition for multi-opening indistinguishability with partial opening (MO-IND-PO), which forces an adversary to distinguish encryptions of abusive blocks. We then design and analyze two protocols CEP-AOP1 (Committing Encrypt and PRF with After Opening Privacy) and CEP-AOP2, which adhere to the new privacy definition. As a side contribution we show a multi-opening secure CEP-AOP2 construction using only one PRF evaluation over the message, in a weaker but meaningful security model, relying only on standard assumptions of the underlying symmetric primitives.

ePrint Report
Improved Brute-Force Search Strategies for Single-Trace and Few-Traces Template Attacks on the DES Round Keys
Mathias Wagner, Stefan Heyse

We present an improved search strategy for a template attack on the secret DES key of a widely-used smart card, which is based on a Common-Criteria certified chip. We use the logarithm of the probability function as returned by the template attack itself, averaged over all 28 template positions along the rings representing the C and D Registers of the DES key schedule, as the sorting criteria for the key candidates. For weak keys - which in this attack model have a minimal rest entropy of only two bits - we find that on average only 37.75 bits need to be recovered by brute force when using only a single trace in the Exploitation Phase. This effort goes down to just a few bits for a single DES key when using only a few traces in Exploitation Phase.

4
October
2018

Event Calendar
Call for Workshop Proposals (IEEE EuroS&P 2019)
Stockholm, Sweden, 16 June - 20 June 2018

Event date: 16 June to 20 June 2018

Submission deadline: 11 November 2018

Notification: 3 December 2018

Submission deadline: 11 November 2018

Notification: 3 December 2018

Event Calendar
ISDF2018: International Conference on Information Security and Digital Forensics
Thessaloniki, Greece, 7 December - 9 December 2018

Event date: 7 December to 9 December 2018

Submission deadline: 1 November 2018

Submission deadline: 1 November 2018

3
October
2018

As a Senior Cryptography Engineer - Cloud Engineer, you will:

Design, implement and deploy cryptographic algorithms tailored for a cloud environment.

Conduct research and development in differential privacy, secret sharing, multi-party secure computation and fully homomorphic encryption.

Perform security assessments of crypto-primitives, cryptosystems and cloud security solutions at the theoretical and implementation level.

Work closely with the other teams in the organization to design and deploy safe cloud-based solutions .

Be involved in the integration of developed cryptosystems within DarkMatter products.

Enjoy all the cultural, educational and travel opportunities Abu Dhabi offers

To bring your dream to life, you’ll need:

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

Extensive experience developing in various programming languages.

A desire to innovate in the UAE

**Closing date for applications:** 3 March 2019

**Contact:** Sheila Morjaria

Mehdi Messaoudi

**More information:** https://grnh.se/d694fd601

As a Cryptography Embedded Systems Engineer, you will:

• Design, implement and deploy cryptographic algorithms tailored for resource-constrained devices.

• Conduct research and development in lightweight cryptography.

• Perform security assessments of crypto-primitives and cryptosystems suitable for resource-constrained devices at the theoretical and implementation level.

• Work closely with the other teams in the organization to deploy secure embedded systems.

• Be involved in the integration of developed cryptosystems within DarkMatter products.

• Enjoy all the cultural, educational and travel opportunities Abu Dhabi offers.

To bring your dream to life, you’ll need:

• MS or PhD degree in Computer Science, Computer Engineering, Electrical Engineering, Cryptography or related field.

• Development experience within embedded systems, RFID and sensor networks.

• Knowledge of Unix/Linux environments and kernel development.

• Knowledge of one or more of the following: Microcontrollers, SoC, TrustZone, ARM processors, performance optimization, bootloading, firmware, x86 assembly, system BIOS or hardware/software integration.

• Knowledge of side-channel attacks and countermeasures.

• Experience coding in C/C++.

• A desire to innovate in the UAE

**Closing date for applications:** 3 April 2019

**Contact:** Sheila Morjaria

Mehdi Messaoudi

**More information:** https://grnh.se/fb5c073f1