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

9
April
2019

In this paper we present the first fully post-quantum proof of a shuffle for RLWE encryption schemes. Shuffles are commonly used to construct mixing networks (mix-nets), a key element to ensure anonymity in many applications such as electronic voting systems. They should preserve anonymity even against an attack using quantum computers in order to guarantee long-term privacy. The proof presented in this paper is built over RLWE commitments which are perfectly binding and computationally hiding under the RLWE assumption, thus achieving security in a post-quantum scenario. Furthermore we provide a new definition for a secure mixing node (mix-node) and prove that our construction satisfies this definition.

7
April
2019

ePrint Report
Ad Hoc Multi-Input Functional Encryption
Shweta Agrawal, Michael Clear, Ophir Frieder, Sanjam Garg, Adam O'Neill, Justin Thaler

Consider sources that supply sensitive data to an aggregator. Standard encryption only hides the data from eavesdroppers, but using specialized encryption one can hope to hide the data (to the extent possible) from the aggregator itself. For flexibility and security, we envision schemes that allow sources to supply encrypted data, such that at any point a dynamically chosen subset of sources can allow an agreed-upon joint function of their data to be computed by the aggregator. A primitive called multi-input functional encryption (MIFE), due to Goldwasser et al. (EUROCRYPT 2014), comes close, but has two main limitations:
– it requires trust in a third party, who is able to decrypt all the data,
and
– it requires function arity to be fixed at setup time and to be equal to the number of parties.

To drop these limitations, we introduce a new notion of ad hoc MIFE. In our setting, each source generates its own public key and issues individual, function-specific secret keys to an aggregator. For successful decryption, an aggregator must obtain a separate key from each source whose ciphertext is being computed upon. The aggregator could obtain multiple such secret keys from a user corresponding to functions of varying arity. For this primitive, we obtain the following results: – We show that standard MIFE for general functions can be bootstrapped to ad hoc MIFE for free, i.e. without making any additional assumption. – We provide a direct construction of ad hoc MIFE for the inner product functionality based on the Learning with Errors (LWE) assumption. This yields the first construction of this natural primitive based on a standard assumption.

At a technical level, our results are obtained by combining standard MIFE schemes and two-round secure multiparty computation (MPC) protocols in novel ways highlighting an interesting interplay between MIFE and two-round MPC in the construction of non interactive primitives.

To drop these limitations, we introduce a new notion of ad hoc MIFE. In our setting, each source generates its own public key and issues individual, function-specific secret keys to an aggregator. For successful decryption, an aggregator must obtain a separate key from each source whose ciphertext is being computed upon. The aggregator could obtain multiple such secret keys from a user corresponding to functions of varying arity. For this primitive, we obtain the following results: – We show that standard MIFE for general functions can be bootstrapped to ad hoc MIFE for free, i.e. without making any additional assumption. – We provide a direct construction of ad hoc MIFE for the inner product functionality based on the Learning with Errors (LWE) assumption. This yields the first construction of this natural primitive based on a standard assumption.

At a technical level, our results are obtained by combining standard MIFE schemes and two-round secure multiparty computation (MPC) protocols in novel ways highlighting an interesting interplay between MIFE and two-round MPC in the construction of non interactive primitives.

ePrint Report
To Infect Or Not To Infect: A Critical Analysis Of Infective Countermeasures In Fault Attacks
Anubhab Baksi, Dhiman Saha, Sumanta Sarkar

As fault based cryptanalysis is becoming more and more of a practical threat, it is imperative to make efforts to devise suitable countermeasures. In this regard, the so-called ``infective countermeasures'' have garnered particular attention from the community due to their ability in inhibiting differential fault attacks without explicitly detecting the fault. We observe that despite being adopted over a decade ago, a systematic study is missing from the literature. Moreover, there seems to be a lack of proper security analysis of the schemes proposed, as quite a few of them have been broken promptly. Our first contribution comes in the form of a generalization of infective schemes which aids us with a better insight into the vulnerabilities, scopes for cost reduction and possible improvements. This way, we are able to propose lightweight alternatives of two existing schemes, propose new design based on already established standards, refute a security claim made by a scheme proposed in CHES'14 and re-instantiate another scheme which is deemed broken by proposing a simple patch.

2
April
2019

ePrint Report
Benchmarking Privacy Preserving Scientific Operations
Abdelrahaman Aly, Nigel P. Smart

In this work, we examine the efficiency of protocols for secure evaluation of basic mathematical functions ($\mathtt{sqrt}, \mathtt{sin}, \mathtt{arcsin}$, amongst others), essential to various application domains. e.g., Artificial Intelligence. Furthermore, we have incorporated our code in state-of-the-art Multiparty Computation (MPC) software, so we can focus on the algorithms to be used as opposed to the underlying MPC system. We make use of practical approaches that, although, some of them, theoretically can be regarded as less efficient, can, nonetheless, be implemented in such software libraries without further adaptation. We focus on basic scientific operations, and introduce a series of data-oblivious protocols based on fixed point representation techniques. Our protocols do not reveal intermediate values and do not need special adaptations from the underlying MPC protocols. We include extensive computational experimentation under various settings and MPC protocols.

ePrint Report
A Faster Constant-time Algorithm of CSIDH keeping Two Torsion Points
Hiroshi Onuki, Yusuke Aikawa, Tsutomu Yamazaki, Tsuyoshi Takagi

At ASIACRYPT 2018, Castryck, Lange, Martindale, Panny and Renes proposed CSIDH, which is a key-exchange protocol based on isogenies between elliptic curves, and a candidate for post-quantum cryptography. However, the implementation by Castryck et al. is not constant-time. Specifically, a part of the secret key could be recovered by the side-channel Attacks. Recently, Meyer, Campos and Reith proposed a constant-time implementation of CSIDH by introducing dummy isogenies and taking secret exponents only from intervals of non-negative integers. Their non-negative intervals make the calculation cost of their implementation of CSIDH twice that of the worst case of the standard (variable-time) implementation of CSIDH. In this paper, we propose a more efficient constant-time algorithm that takes secret exponents from intervals symmetric with respect to the zero. For using these intervals, we need to keep two torsion points in an elliptic curve and calculation for these points. We evaluate the costs of our implementation and that of Meyer et al. in terms of the number of operations on a finite prime field. Our evaluation shows that our constant-time implementation of CSIDH reduces the calculation cost by 28.23% compared with the implementation by Mayer et al. We also implemented our algorithm by extending the implementation in C of Meyer et al. (originally from Castryck et al.). Then our implementation achieved 172.4 million clock cycles, which is about 27.35% faster than that of Meyer et al. and confirms the above reduction ratio in our cost evaluation.

ePrint Report
SoK: A Taxonomy for Layer-2 Scalability Related Protocols for Cryptocurrencies
Maxim Jourenko, Kanta Kurazumi, Mario Larangeira, Keisuke Tanaka

Blockchain based systems, in particular cryptocurrencies, face a serious limitation: scalability. This holds, especially, in terms of number of transactions per second.
Several alternatives are currently being pursued by both the research and practitioner communities. One venue for exploration is on protocols that do not constantly add transactions on the blockchain and therefore do not consume the blockchain's resources. This is done using off-chain transactions, i.e., protocols that minimize the interaction with the blockchain, also commonly known as Layer-2 approaches.
This work relates several existing off-chain channel methods, also known as payment and state channels, channel network constructions methods, and other components as channel and network management protocols, e.g., routing nodes. All these components are crucial to keep the usability of the channel, and are often overlooked. For the best of our knowledge, this work is the first to propose a taxonomy for all the components of the Layer-2. We provide an extensive coverage on the state-of-art protocols available. We also outline their respective approaches, and discuss their advantages and disadvantages.

Currently, the Simple Password-Based Encrypted Key Exchange (SPAKE2) protocol of Abdalla and Pointcheval (CT-RSA 2005) is being considered by the IETF for standardization and integration in TLS 1.3. Although it has been proven secure in the Find-then-Guess model of Bellare, Pointcheval and Rogaway (EUROCRYPT 2000), whether it satisfies some notion of forward secrecy remains an open question.

In this work, we prove that the SPAKE2 protocol satisfies the so-called weak forward secrecy introduced by Krawczyk (CRYPTO 2005). Furthermore, we demonstrate that the incorporation of key-confirmation codes in SPAKE2 results in a protocol that provably satisfies the stronger notion of perfect forward secrecy. As forward secrecy is an explicit requirement for cipher suites supported in the TLS handshake, we believe this work could fill the gap in the literature and facilitate the adoption of SPAKE2 in the recently approved TLS 1.3.

In this work, we prove that the SPAKE2 protocol satisfies the so-called weak forward secrecy introduced by Krawczyk (CRYPTO 2005). Furthermore, we demonstrate that the incorporation of key-confirmation codes in SPAKE2 results in a protocol that provably satisfies the stronger notion of perfect forward secrecy. As forward secrecy is an explicit requirement for cipher suites supported in the TLS handshake, we believe this work could fill the gap in the literature and facilitate the adoption of SPAKE2 in the recently approved TLS 1.3.

ePrint Report
nGraph-HE: A Graph Compiler for Deep Learning on Homomorphically Encrypted Data
Fabian Boemer, Yixing Lao, Rosario Cammarota, Casimir Wierzynski

Homomorphic encryption (HE)---the ability to perform computation on encrypted data---is an attractive remedy to increasing concerns about data privacy in deep learning (DL). However, building DL models that operate on ciphertext is currently labor-intensive and requires simultaneous expertise in DL, cryptography, and software engineering. DL frameworks and recent advances in graph compilers have greatly accelerated the training and deployment of DL models to various computing platforms. We introduce nGraph-HE, an extension of nGraph, Intel's DL graph compiler, which enables deployment of trained models with popular frameworks such as TensorFlow while simply treating HE as another hardware target. Our graph-compiler approach enables HE-aware optimizations-- implemented at compile-time, such as constant folding and HE-SIMD packing, and at run-time, such as special value plaintext bypass. Furthermore, nGraph-HE integrates with DL frameworks such as TensorFlow, enabling data scientists to benchmark DL models with minimal overhead.

ePrint Report
Spin Me Right Round: Rotational Symmetry for FPGA-specific AES
Felix Wegener, Lauren De Meyer, Amir Moradi

The effort in reducing the area of AES implementations has largely been focused on Application-Specific Integrated Circuits (ASICs) in which a tower field construction leads to a small design of the AES S-box. In contrast, a naive implementation of the AES S-box has been the status-quo on Field-Programmable Gate Arrays (FPGAs). A similar discrepancy holds for masking schemes - a well-known side-channel analysis countermeasure - which are commonly optimized to achieve minimal area in ASICs. In this paper we demonstrate a representation of the AES S-box exploiting rotational symmetry which leads to a 50% reduction of the area footprint on FPGA devices. We present new AES implementations which improve on the state of the art and explore various trade-offs between area and latency. For instance, at the cost of increasing 4.5 times the latency, one of our design variants requires 25% less look-up tables (LUTs) than the smallest known AES on Xilinx FPGAs by Sasdrich and Güneysu at ASAP 2016.
We further explore the protection of such implementations against side-channel attacks. We introduce a generic methodology for masking any n-bit Boolean functions of degree t with protection order d. The methodology is exact for first-order and heuristic for higher orders.
Its application to our new construction of the AES S-box allows us to improve previous results and introduce the smallest first-order masked AES implementation on Xilinx FPGAs, to-date.

ePrint Report
Efficient and Scalable Universal Circuits
Masaud Y. Alhassan, Daniel Günther, Ágnes Kiss, Thomas Schneider

A universal circuit (UC) can be programmed to simulate any circuit up to a given size n by specifying its program inputs. It provides elegant solutions in various application scenarios, e.g., for private function evaluation (PFE) and for improving the flexibility of attribute-based encryption (ABE) schemes. The asymptotic lower bound for the size of a UC is $\Omega(n \log n)$ and Valiant (STOC'76) provided two theoretical constructions, the so-called 2-way and 4-way UCs (i.e., recursive constructions with 2 and 4 substructures), with asymptotic sizes $5n \log_2n$ and $4.75n \log_2n$, respectively.

In this article, we present and extend our results published in (Kiss and Schneider, EUROCRYPT'16) and (Günther et al., ASIACRYPT'17). We validate the practicality of Valiant's UCs, by realizing the 2-way and 4-way UCs in our modular open-source implementations. We also provide an example implementation for PFE using these size-optimized UCs. We propose a 2/4-hybrid approach that combines the 2-way with the 4-way UC in order to minimize the size of the resulting UC. We realize that the bottleneck in universal circuit generation and programming becomes the memory consumption of the program since the whole structure of size $\mathcal{O}(n \log n)$ is handled by the algorithms in memory.

In this work, we overcome this by designing novel scalable algorithms for the UC generation and programming. We show that the generation, which involves topological ordering of the UC as well, can be designed to be performed block by block from top to bottom, while the programming can be performed subcircuit by subcircuit. Both algorithms use only $\mathcal{O}(n)$ memory at any point in time. We prove the practicality of our scalable design with a scalable proof-of-concept implementation for generating Valiant's 4-way UC. We note that this can be extended to work with optimized building blocks analogously. Moreover, we substantially improve the size of our UCs by including and implementing the recent optimization of Zhao et al. (ePrint 2018/943) that reduces the asymptotic size of the 4-way UC to $4.5n\log_2n$. Furthermore, we include their optimization in the implementation of our 2/4-hybrid UC which yields the smallest UC construction known so far.

In this article, we present and extend our results published in (Kiss and Schneider, EUROCRYPT'16) and (Günther et al., ASIACRYPT'17). We validate the practicality of Valiant's UCs, by realizing the 2-way and 4-way UCs in our modular open-source implementations. We also provide an example implementation for PFE using these size-optimized UCs. We propose a 2/4-hybrid approach that combines the 2-way with the 4-way UC in order to minimize the size of the resulting UC. We realize that the bottleneck in universal circuit generation and programming becomes the memory consumption of the program since the whole structure of size $\mathcal{O}(n \log n)$ is handled by the algorithms in memory.

In this work, we overcome this by designing novel scalable algorithms for the UC generation and programming. We show that the generation, which involves topological ordering of the UC as well, can be designed to be performed block by block from top to bottom, while the programming can be performed subcircuit by subcircuit. Both algorithms use only $\mathcal{O}(n)$ memory at any point in time. We prove the practicality of our scalable design with a scalable proof-of-concept implementation for generating Valiant's 4-way UC. We note that this can be extended to work with optimized building blocks analogously. Moreover, we substantially improve the size of our UCs by including and implementing the recent optimization of Zhao et al. (ePrint 2018/943) that reduces the asymptotic size of the 4-way UC to $4.5n\log_2n$. Furthermore, we include their optimization in the implementation of our 2/4-hybrid UC which yields the smallest UC construction known so far.

TLS 1.3 allows two parties to establish a shared session key from an out-of-band agreed
Pre Shared Key (PSK) is used to mutually authenticate the parties, under the assumption that it is not shared with others. This allows the parties to skip the certificate verification steps, saving bandwidth, communication rounds, and latency.

We identify a security vulnerability in this TLS 1.3 path, by showing a new reflection attack that we call ``Selfie''. The Selfie attack breaks the mutual authentication. It leverages the fact that TLS does not mandate explicit authentication of the server and the client in every message.

The paper explains the root cause of this TLS 1.3 vulnerability, demonstrates the Selfie attack on the TLS implementation of OpenSSL and proposes appropriate mitigation.

The attack is surprising because it breaks some assumptions and uncovers an interesting gap in the existing TLS security proofs. We explain the gap in the model assumptions and subsequently in the security proofs. We also provide an enhanced Multi-Stage Key Exchange (MSKE) model that captures the additional required assumptions of TLS 1.3 in its current state. The resulting security claims in the case of external PSKs are accordingly different.

We identify a security vulnerability in this TLS 1.3 path, by showing a new reflection attack that we call ``Selfie''. The Selfie attack breaks the mutual authentication. It leverages the fact that TLS does not mandate explicit authentication of the server and the client in every message.

The paper explains the root cause of this TLS 1.3 vulnerability, demonstrates the Selfie attack on the TLS implementation of OpenSSL and proposes appropriate mitigation.

The attack is surprising because it breaks some assumptions and uncovers an interesting gap in the existing TLS security proofs. We explain the gap in the model assumptions and subsequently in the security proofs. We also provide an enhanced Multi-Stage Key Exchange (MSKE) model that captures the additional required assumptions of TLS 1.3 in its current state. The resulting security claims in the case of external PSKs are accordingly different.

ePrint Report
Yet Another Side Channel Cryptanalysis on SM3 Hash Algorithm
Christophe Clavier, Leo Reynaud, Antoine Wurcker

SM3, the Chinese standard hash algorithm inspired from SHA2, can be
attacker by similar means than SHA2 up to an adaptation to its differences. But this
kind of attack is based on targeting point of interest of different kinds, some are end
of computation results, that are stored when others are in intermediate computational
data. The leakage effectiveness of the later could be subject to implementation choices,
device type or device type of leakage. In this paper, we propose a new approach that
targets only the first kind of intermediate data that are more susceptible to appear.
As an example, we targeted the HMAC construction using SM3, where our method
allows to recover the first half of the secret information. reducing the security of the
HMAC protocol.

Second-order analyses have shown a great interest to defeat first level of masking protections.
Their practical realization remains tedious in a lot of cases.
This is partly due to the difficulties of achieving a fine alignment of two areas that are combined together afterward.
Classical protections makes therefore use of random jitter or shuffling to make the alignment difficult or even impossible.
This paper extends Scatter attack to high-order analyses.
Processing the jointdistribution of two selection of points, it becomes possible to retrieve the secret key even when traces are not fully aligned.
The results presented in this paper are validated through practical experimentation and compared with existing window-based techniques, such as the FFT.
Scatter shows the best results when misalignment is significant.
This illustrates that Scatter offers an alternative to existing high-order attacks and can target all kinds of cryptography implementations, regardless they are executed in hardware or software.
With the ability to exploit several leakage points, it may be valuable also when applying a second-order attack on aligned traces.

ePrint Report
Cryptanalysis of Curl-P and Other Attacks on the IOTA Cryptocurrency
Ethan Heilman, Neha Narula, Garrett Tanzer, James Lovejoy, Michael Colavita, Madars Virza, Tadge Dryja

We present attacks on the cryptography formerly used in the IOTA blockchain, including under certain conditions the ability to forge signatures. We developed practical attacks on IOTA's cryptographic hash function Curl-P-27, allowing us to quickly generate short colliding messages. These collisions work even for messages of the same length. Exploiting these weaknesses in Curl-P-27, we broke the EU-CMA security of the former IOTA Signature Scheme (ISS). Finally, we show that in a chosen-message setting we could forge signatures and multi-signatures of valid spending transactions (called bundles in IOTA).

ePrint Report
Optimizations of Side-Channel Attack on AES MixColumns Using Chosen Input
Aurelien Vasselle, Antoine Wurcker

Considering AES sub-steps that can be attacked with a small guess space,
the most practicable is to target SubBytes of extremal rounds. For its contrast
between candidates (non-linearity) and that the search space is reduced to 28 -sized
blocks. But when such point of interests are not available, MixColumns may be
considered but involve search spaces of 2^32 -sized blocks. This number of attacks to
run being often considered as unrealistic to reach, published papers propose to attack
using chosen inputs in order to reduce back search space to 2^8 -sized blocks. Several
sets of chosen inputs acquisition will then be required to succeed an attack.
Our contribution consists in an optimization of usage of gained information that
allows to drastically reduce the number of set needed to realize such an attack, even
to only one set in some configurations.

ePrint Report
LightChain: A DHT-based Blockchain for Resource Constrained Environments
Yahya Hassanzadeh-Nazarabadi, Alptekin Küpçü, Öznur Özkasap

As an append-only distributed database, blockchain is utilized in a vast
variety of applications including the cryptocurrency and Internet-of-Things
(IoT). The existing blockchain solutions have downsides in communication and
storage efficiency, convergence to centralization, and consistency problems. In
this paper, we propose LightChain, which is the first blockchain architecture
that operates over a Distributed Hash Table (DHT) of participating peers.
LightChain is a permissionless blockchain that provides addressable blocks and
transactions within the network, which makes them efficiently accessible by all
the peers. Each block and transaction is replicated within the DHT of peers and
is retrieved in an on-demand manner. Hence, peers in LightChain are not
required to retrieve or keep the entire blockchain. LightChain is fair as all
of the participating peers have a uniform chance of being involved in the
consensus regardless of their influence such as hashing power or stake.
LightChain provides a deterministic fork-resolving strategy as well as a
blacklisting mechanism, and it is secure against colluding adversarial peers
attacking the availability and integrity of the system. We provide mathematical
analysis and experimental results on scenarios involving 10K nodes to
demonstrate the security and fairness of LightChain.

ePrint Report
MixEth: efficient, trustless coin mixing service for Ethereum
István András Seres, Dániel A. Nagy, Chris Buckland, Péter Burcsi

Coin mixing is a prevalent privacy-enhancing technology for cryptocurrency users. In this paper, we present MixEth, which is a trustless coin mixing service for Turing-complete blockchains. MixEth does not rely on a trusted setup and is more efficient than any proposed trustless coin tumbler. It requires only 3 on-chain transactions at most per user and 1 off-chain message. It achieves strong notions of anonymity and is able to resist denial-of-service attacks. Furthermore the underlying protocol can also be used to efficiently shuffle ballots, ciphertexts in a trustless and decentralized manner.

Concerning the side-channel attacks on Advanced Encryp-
tion Standard, it seems that majority of studies focus on the lowest size:
AES-128. Even when adaptable to higher sizes (AES-192 and AES-256),
lots of state-of-the-art attacks see their complexity substantially raised.
Indeed, it often requires to perform two consecutive dependent attacks.
The first is similar to the one applied on AES-128, but a part of the key
remains unknown and must be retrieved through a second attack directly
dependent on the success of the first.
This configuration may substantially raise the complexity for the at-
tacker, especially if new signal acquisitions with specific input, built using
the first key part recovered, must be performed. Any error/uncertainty
in the first attack raise the key recovery complexity.
Our contribution is to show that this complexity can be lowered to two
independent attacks by the mean of attacking separately first and last
round keys. We show that the information is enough to recover the main
key (or a very small list of candidates) in a negligible exploratory effort.

ePrint Report
Lightweight Authenticated Encryption Mode of Operation for Tweakable Block Ciphers
Yusuke Naito, Takeshi Sugawara

Using a small block length is a common strategy in designing lightweight block cipher. So far, many $64$-bit primitives have been proposed. However, if we use such a $64$-bit primitive for an authenticated encryption with birthday-bound security, it has only $32$-bit plaintext complexity which is subject to a practical attack. To take advantage of a short block length without losing security, we propose a lightweight AEAD mode $\mathsf{FBAE}$ that achieves beyond-birthday-bound security. For the purpose, we extend the idea of $\mathsf{iCOFB}$, originally defined with a tweakable random function, with tweakable block cipher. More specifically, we fix the tweak length which was variable in $\mathsf{iCOFB}$, and further generalize the feedback function. Moreover, we improve its security bound. We evaluate the concrete hardware performances of $\mathsf{FBAE}$. $\mathsf{FBAE}$ benefits from the small block length and shows the particularly good performances in threshold implementation.

ePrint Report
Garbled Neural Networks are Practical
Marshall Ball, Brent Carmer, Tal Malkin, Mike Rosulek, Nichole Shimanski

We show that garbled circuits are a practical choice for secure evaluation of neural network classifiers. At the protocol level, we start with the garbling scheme of Ball, Malkin & Rosulek (ACM CCS 2016) for arithmetic circuits and introduce new optimizations for modern neural network activation functions. We develop fancy-garbling, the first implementation of the BMR16 garbling scheme along with our new optimizations, as part of heavily optimized garbled-circuits tool that is driven by a TensorFlow classifier description.

We evaluate our constructions on a wide range of neural networks. We find that our approach is up to 100x more efficient than straight-forward boolean garbling (depending on the neural network). Our approach is also roughly 40% more efficient than DeepSecure (Rouhani et al., DAC 2018), the only previous garbled-circuit-based approach for secure neural network evaluation, which incorporates significant optimization techniques for boolean circuits. Furthermore, our approach is competitive with other non-garbled-circuit approaches for secure neural network evaluation.

We evaluate our constructions on a wide range of neural networks. We find that our approach is up to 100x more efficient than straight-forward boolean garbling (depending on the neural network). Our approach is also roughly 40% more efficient than DeepSecure (Rouhani et al., DAC 2018), the only previous garbled-circuit-based approach for secure neural network evaluation, which incorporates significant optimization techniques for boolean circuits. Furthermore, our approach is competitive with other non-garbled-circuit approaches for secure neural network evaluation.

ePrint Report
Anonymous Deniable Identification in Ephemeral Setup & Leakage Scenarios
Łukasz Krzywiecki, Mirosław Kutyłowski, Jakub Pezda, Marcin Słowik

In this paper we concern anonymous identification, where the verifier
can check that the user belongs to a given group of users (just like in case of
ring signatures), however a transcript of a session executed between a user and a
verifier is deniable. That is, neither the verifier nor the prover can convice a third
party that a given user has been involved in a session but also he cannot prove
that any user has been interacting with the verifier. Thereby one can achieve high
standards for protecting personal data according to the General Data Protection
Regulation – the fact that an interaction took place might be a sensitive data from
information security perspective.
We show a simple realization of this idea based on Schnorr identification scheme
arranged like for ring signatures. We show that with minor modifications one can
create a version immune to leakage of ephemeral keys.
We extend the above scenario to the case of k out of n, where the prover must
use at least k private keys corresponding to the set of n public keys. With the
most probable setting of k = 2 or 3, we are talking about the practical case of
multifactor authentication that might be necessary for applications with higher
security level.

ePrint Report
DEEP-FRI: Sampling Outside the Box Improves Soundness
Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf

Motivated by the quest for scalable and succinct zero knowledge arguments, we revisit worst-case-to-average-case reductions for linear spaces, raised by [Rothblum, Vadhan, Wigderson, STOC 2013]. The previous state of the art by [Ben-Sasson, Kopparty, Saraf, CCC 2018] showed that if some member of an affine space $U$ is $\delta$-far in relative Hamming distance from a linear code $V$ — this is the worst-case assumption — then most elements of $U$ are almost-$\delta$-far from $V$ — this is the average case. However, this result was known to hold only below the “double Johnson” function of the relative distance $\delta_V$ of the code $V$ , i.e., only when $\delta < 1 - \sqrt[4]{1 - \delta_V}$.
First, we increase the soundness-bound to the “one-and-a-half Johnson” function of $\delta_V$ and show that the average distance of $U$ from $V$ is nearly $\delta$ for any worst-case distance $\delta$ smaller than $1 - \sqrt[3]{1 - \delta_V}$. This bound is tight, which is somewhat surprising because the one-and-a-half Johnson function is unfamiliar in the literature on error correcting codes.
To improve soundness further for Reed Solomon codes we sample outside the box. We suggest a new protocol in which the verifier samples a single point $z$ outside the box $D$ on which codewords are evaluated, and asks the prover for the value at $z$ of the interpolating polynomial of a random element of $U$. Intuitively, the answer provided by the prover “forces” it to choose one codeword from a list of “pretenders” that are close to $U$. We call this technique Domain Extending for Eliminating Pretenders (DEEP).
The DEEP method improves the soundness of the worst-case-to-average-case reduction for RS codes up their list decoding radius. This radius is bounded from below by the Johnson bound, implying average distance is approximately $\delta$ for all $\delta < 1 - \sqrt{1 - \delta_V}$. Under a plausible conjecture about the list decoding radius of Reed-Solomon codes, average distance from $V$ is approximately $\delta$ for all $\delta$. The DEEP technique can be generalized to all linear codes, giving improved reductions for capacity-achieving list-decodable codes.
Finally, we use the DEEP technique to devise two new protocols:
• An Interactive Oracle Proof of Proximity (IOPP) for RS codes, called DEEP-FRI. This soundness of the protocol improves upon that of the FRI protocol of [Ben-Sasson et al., ICALP 2018] while retaining linear arithmetic proving complexity and logarithmic verifier arithmetic complexity.
• An Interactive Oracle Proof (IOP) for the Algebraic Linking IOP (ALI) protocol used to construct zero knowledge scalable transparent arguments of knowledge (ZK-STARKs) in [Ben-Sasson et al., eprint 2018]. The new protocol, called DEEP-ALI, improves soundness of this crucial step from a small constant $< 1/8$ to a constant arbitrarily close to $1$.

ePrint Report
Examining the Practical Side Channel Resilience of ARX-boxes
Yan Yan, Elisabeth Oswald

Implementations of ARX ciphers are hoped to have some intrinsic side channel resilience owing to the specific choice of cipher components: modular addition (A), rotation (R) and exclusive-or (X). Previous work has contributed to this understanding by developing theory regarding the side channel resilience of components (pioneered by the early works of Prouff) as well as some more recent practical investigations by Biryukov et al. that focused on lightweight cipher constructions. We add to this work by specifically studying ARX-boxes both mathematically as well as practically. Our results show that previous works' reliance on the simplistic assumption that intermediates independently leak (their Hamming weight) has led to the incorrect conclusion that the modular addition is necessarily the best target and that ARX constructions are therefore harder to attack in practice: we show that on an ARM M0, the best practical target is the exclusive or and attacks succeed with only tens of traces.

ePrint Report
Practically Efficient Secure Distributed Exponentiation without Bit-Decomposition
Abdelrahaman Aly, Aysajan Abidin, Svetla Nikova

Bit-decomposition is a powerful tool which can be used to design constant round protocols for bit-oriented multiparty computation (MPC) problems, such as comparison and Hamming weight computation. However, protocols that involve bit-decomposition are expensive in terms of performance. In this paper, we introduce a set of protocols for distributed exponentiation without bit-decomposition. We build upon the current state-of-the-art by Ning and Xu [ASIACRYPT 2010 & ASIACRYPT 2011], in terms of round and multiplicative complexity.
We consider different cases where the inputs are either private or public and present privacy-preserving protocols for each case. Our protocols offer perfect security against passive and active adversaries and have constant multiplicative and round complexity, for any fixed number of parties. Furthermore, we showcase how these primitives can be used, for instance, to perform secure distributed decryption for some public key schemes, that are based on modular exponentiation.

There are several new efficient approaches to decrease the trust in the CRS creators in the case of non-interactive zero knowledge (NIZK) in the CRS model. Recently, Groth et al. (CRYPTO 2018) defined the notion of NIZK with updatable CRS (updatable NIZK) and described an updatable SNARK. We consider the same problem in the case of QA-NIZKs.
While doing it, we define an important new property: we require that after updating the CRS, one should be able to update a previously generated argument to a new argument that is valid with the new CRS. We propose a general definitional framework for key-and-argument-updatable QA-NIZKs. After that, we describe a key-and-argument-updatable version of the most efficient known QA-NIZK for linear subspaces by Kiltz and Wee. Importantly, for obtaining soundness it suffices to update a universal public key that just consists of a matrix drawn from a KerMDH-hard distribution and thus can be shared by any pairing-based application that relies on the same hardness assumption. After specializing the universal public key to concrete language parameter, one can use the proposed key-and-argument updating algorithms to continue updating to strengthen the soundness guarantee.

ePrint Report
Efficient Private Comparison Queries over Encrypted Databases using Fully Homomorphic Encryption with Finite Fields
Benjamin Hong Meng Tan, Hyung Tae Lee, Huaxiong Wang, Shu Qin Ren, Khin Mi Mi Aung

To achieve security and privacy for data stored on the cloud, we need the ability to secure data in compute. Equality comparisons, ``$x=y, x\neq y$'', have been widely studied with many proposals but there is much room for improvement for order comparisons, ``$x < y,~x \leq y, x > y$ and $x \geq y$''. Most protocols for order comparisons have some limitation, either leaking some information about the data or requiring several rounds of communication between client and server. In addition, little work has been done on retrieving with compound conditions, mixing several equality and order comparisons. Fully homomorphic encryption (FHE) promises the ability to compute arbitrary functions on encrypted data without sacrificing privacy and without communication, but its potential has yet to be fulfilled. Particularly, private comparisons for database queries using FHE are expensive to compute.

In this work, we design efficient private database query (PDQ) protocols which support order comparisons and compound conditions. To this end, we first present a private comparison algorithm on encrypted integers using FHE, which scales efficiently for the length of input integers, by applying techniques from finite field theory. Then, we consider two scenarios for PDQ protocols, the first for retrieving data based on one order comparison and the second based on a conjunction of one order and four equality conditions. The proposed algorithm and protocols are implemented and tested to determine their performance in practice. The proposed comparison algorithm takes about 20.155 seconds to compare 697 pairs of 64-bit integers using Brakerski-Gentry-Vaikuntanathan's leveled FHE scheme with single instruction multiple data (SIMD) techniques at more than 110 bits of security. This yields an amortized rate of just 29 milliseconds per comparison. On top of that, we show that our techniques achieve an efficient PDQ protocol for one order and four equality comparisons, achieving an amortized time and communication cost of 36 milliseconds and 154 bytes per database element.

In this work, we design efficient private database query (PDQ) protocols which support order comparisons and compound conditions. To this end, we first present a private comparison algorithm on encrypted integers using FHE, which scales efficiently for the length of input integers, by applying techniques from finite field theory. Then, we consider two scenarios for PDQ protocols, the first for retrieving data based on one order comparison and the second based on a conjunction of one order and four equality conditions. The proposed algorithm and protocols are implemented and tested to determine their performance in practice. The proposed comparison algorithm takes about 20.155 seconds to compare 697 pairs of 64-bit integers using Brakerski-Gentry-Vaikuntanathan's leveled FHE scheme with single instruction multiple data (SIMD) techniques at more than 110 bits of security. This yields an amortized rate of just 29 milliseconds per comparison. On top of that, we show that our techniques achieve an efficient PDQ protocol for one order and four equality comparisons, achieving an amortized time and communication cost of 36 milliseconds and 154 bytes per database element.

ePrint Report
Optimized Supersingular Isogeny Key Encapsulation on ARMv8 Processors
Amir Jalali, Reza Azarderakhsh, Mehran Mozaffari Kermani, Matthew Campagna, David Jao

In this work, we present highly-optimized constant-time software libraries for Supersingular Isogeny Key Encapsulation (SIKE) protocol on ARMv8 processors. Our optimized hand-crafted assembly libraries provide the most efficient timing results on 64-bit ARM-powered devices. Moreover, the presented libraries can be integrated into any other cryptography primitives targeting the same finite field size. We design a new mixed implementation of field arithmetic on 64-bit ARM processors by exploiting the A64 and Advanced SIMD processing units working in parallel. Using these techniques, we are able to improve the performance of the entire protocol by the factor of 5 times compared to optimized C implementations on 64-bit ARM high-performance cores, providing 83-, 124-, and 159-bit quantum-security levels. Furthermore, we compare the performance of our proposed library with the previous highly-optimized ARMv8 assembly library available in the literature. The implementation results illustrate the overall 10% performance improvement in comparison with previous work, highlighting the benefit of using mixed implementation over relatively-large finite field size.

ePrint Report
Practical Supersingular Isogeny Group Key Agreement
Reza Azarderakhsh, Amir Jalali, David Jao, Vladimir Soukharev

We present the first quantum-resistant $n$-party key agreement scheme based on supersingular elliptic curve isogenies. We show that the scheme is secure against quantum adversaries, by providing a security reduction to an intractable isogeny problem. We describe the communication and computational steps required for $n$ parties to establish a common shared secret key. Our scheme is the first non-generic quantum-resistant group key agreement protocol, and is more efficient than generic protocols, with near-optimal communication overhead. In addition, our scheme is contributory, which in some settings is a desirable security property: each party applies a function of their own private key to every further transmission. We implement the proposed protocol in portable C for the special case where three parties establish a shared secret. Moreover, we benchmark our software on two generations of Intel processors, highlighting the feasibility and efficiency of using the proposed scheme in practical settings. The proposed software computes the entire group key agreement in 994 and 1,374 millions of clock cycles on Intel Core i7-6500 Skylake and Core i7-2609 Sandy Bridge processors, respectively.

30
March
2019

ePrint Report
Publicly Verifiable Proofs of Sequential Work
Mohammad Mahmoody, Tal Moran, Salil Vadhan

We construct a publicly verifiable protocol for proving computational work based on collision-resistant hash functions and a new plausible complexity assumption regarding the existence of "inherently sequential" hash functions. Our protocol is based on a novel construction of time-lock puzzles. Given a sampled "puzzle" $P \gets D_n$, where $n$ is the security parameter and $D_n$ is the distribution of the puzzles, a corresponding "solution" can be generated using $N$ evaluations of the sequential hash function, where $N>n$ is another parameter, while any feasible adversarial strategy for generating valid solutions must take at least as much time as $\Omega(N)$ *sequential* evaluations of the hash function after receiving $P$. Thus, valid solutions constitute a "proof" that $\Omega(N)$ parallel time elapsed since $P$ was received. Solutions can be publicly and efficiently verified in time $\poly(n) \cdot \polylog(N)$. Applications of these "time-lock puzzles" include noninteractive timestamping of documents (when the distribution over the possible documents corresponds to the puzzle distribution $D_n$) and universally verifiable CPU benchmarks.

Our construction is secure in the standard model under complexity assumptions (collision-resistant hash functions and inherently sequential hash functions), and makes black-box use of the underlying primitives. Consequently, the corresponding construction in the random oracle model is secure unconditionally. Moreover, as it is a public-coin protocol, it can be made non-interactive in the random oracle model using the Fiat-Shamir Heuristic.

Our construction makes a novel use of ``depth-robust'' directed acyclic graphs---ones whose depth remains large even after removing a constant fraction of vertices---which were previously studied for the purpose of complexity lower bounds. The construction bypasses a recent negative result of Mahmoody, Moran, and Vadhan (CRYPTO `11) for time-lock puzzles in the random oracle model, which showed that it is impossible to have time-lock puzzles like ours in the random oracle model if the puzzle generator also computes a solution together with the puzzle.

Our construction is secure in the standard model under complexity assumptions (collision-resistant hash functions and inherently sequential hash functions), and makes black-box use of the underlying primitives. Consequently, the corresponding construction in the random oracle model is secure unconditionally. Moreover, as it is a public-coin protocol, it can be made non-interactive in the random oracle model using the Fiat-Shamir Heuristic.

Our construction makes a novel use of ``depth-robust'' directed acyclic graphs---ones whose depth remains large even after removing a constant fraction of vertices---which were previously studied for the purpose of complexity lower bounds. The construction bypasses a recent negative result of Mahmoody, Moran, and Vadhan (CRYPTO `11) for time-lock puzzles in the random oracle model, which showed that it is impossible to have time-lock puzzles like ours in the random oracle model if the puzzle generator also computes a solution together with the puzzle.

We show that every construction of one-time signature schemes from a random oracle achieves black-box security at most
$2^{(1+o(1))q}$, where $q$ is the total number of oracle queries asked by the key generation, signing, and verification
algorithms. That is, any such scheme can be broken with probability close to $1$ by a (computationally unbounded)
adversary making $2^{(1+o(1))q}$ queries to the oracle. This is tight up to a constant factor in the number of queries, since a
simple modification of Lamport's one-time signatures (Lamport'79) achieves $2^{(0.812-o(1))q}$ black-box security using $q$ queries to the oracle.

Our result extends (with a loss of a constant factor in the number of queries) also to the random permutation and ideal-cipher oracles. Since the symmetric primitives (e.g. block ciphers, hash functions, and message authentication codes) can be constructed by a constant number of queries to the mentioned oracles, as corollary we get lower bounds on the efficiency of signature schemes from symmetric primitives when the construction is black-box. This can be taken as evidence of an inherent efficiency gap between signature schemes and symmetric primitives.

Our result extends (with a loss of a constant factor in the number of queries) also to the random permutation and ideal-cipher oracles. Since the symmetric primitives (e.g. block ciphers, hash functions, and message authentication codes) can be constructed by a constant number of queries to the mentioned oracles, as corollary we get lower bounds on the efficiency of signature schemes from symmetric primitives when the construction is black-box. This can be taken as evidence of an inherent efficiency gap between signature schemes and symmetric primitives.