International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News

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

email icon
via email
RSS symbol icon
via RSS feed

27 April 2019

Abdelrahaman Aly, Tomer Ashur, Eli Ben-Sasson, Siemen Dhooghe, Alan Szepieniec
ePrint Report ePrint Report
While common symmetric primitives like the AES and SHA3 are optimized for efficient hardware and software implementations, a range of emerging applications using advanced cryptographic protocols such as multi-party computation and zero-knowledge proofs require optimization with respect to a different metric: arithmetic complexity. We propose two families of symmetric primitives --- Vision and Rescue --- designed specifically to have a compact algebraic description optimizing the advanced cryptographic protocols that employ them. Vision operates on a small number of binary field elements and adopts the overall design strategy, and thus the security rationale, of the AES: it is a substitution permutation network whose nonlinear layer composes finite field inversion with an affine transform. To make the same security rationale work for prime fields, the nonlinear layer of Rescue consists of a low-degree power map in even steps and its high-degree inverse in odd ones. The algebraic simplicity of the proposed ciphers raises the need for careful cryptanalysis, with a particular focus on algebraic attacks. After providing an elaborate security analysis, we proceed to evaluate the performance of our ciphers with respect to three use cases: the ZK-STARK proof system, proof systems based on Rank-One Constraint Satisfaction (R1CS) systems; and Multi-Party Computation (MPC) with masked operations.
Expand
Flavio Bergamaschi, Shai Halevi, Tzipora T. Halevi, Hamish Hunt
ePrint Report ePrint Report
In this work, we demonstrate the use the CKKS homomorphic encryption scheme to train a large number of logistic regression models simultaneously, as needed to run a genome-wide association study (GWAS) on encrypted data. Our implementation can train more than 30,000 models (each with four features) in about 20 minutes. To that end, we rely on a similar iterative Nesterov procedure to what was used by Kim, Song, Kim, Lee, and Cheon to train a single model [KSKLC18].

We adapt this method to train many models simultaneously using the SIMD capabilities of the CKKS scheme. We also performed a thorough validation of this iterative method and evaluated its suitability both as a generic method for computing logistic regression models, and specifically for GWAS.
Expand
Raghvendra Rohit
ePrint Report ePrint Report
KNOT is a Round 1 submission of the ongoing NIST lightweight cryptography project. In this short note, we show that the preimage security of KNOT-Hash instances with squeezing rate half the state size is lower than the claimed security. Our attack exploits the non-randomness properties of the KNOT Sbox which reduce the preimage complexities.

In particular, if $2n$ is the squeezing rate then the preimage security is approximately $(\text{log\textsubscript{2}}(\frac{3}{4}))^{-n} \times 2^{\frac{3n}{4}} \times (\text{log\textsubscript{2}}(3))^{\frac{n}{2}}$. For $n = 64$, 96 and 128, the former bound translates to $2^{125.28}$, $2^{187.92}$ and $2^{250.57}$, respectively.
Expand
Peter T. Breuer
ePrint Report ePrint Report
An `obfuscation' for the encrypted computing context is quantified exactly here, leading to an argument that security against polynomial-time attacks has been achieved for user data, with or without encryption. Encrypted computing is the emerging science and technology of processors that take encrypted inputs to encrypted outputs via encrypted intermediate values (at nearly conventional speeds). The aim is to make user data in general-purpose computing secure against the operator and operating system as potential adversaries. A stumbling block has always been that memory addresses are data and good encryption means the encrypted value varies randomly,and that makes hitting any target in memory problematic without address decryption, but decryption anywhere on the memory path would open up many easily exploitable vulnerabilities. This paper `solves compilation' for processors without address decryption, covering all of ANSI C while satisfying the required security properties and opening up encrypted computing for the standard software tool-chain and infrastructure. The new understanding produces the argument referred to above.
Expand
Alexander Moch, Eik List
ePrint Report ePrint Report
The combination of universal hashing and encryption is a fundamental paradigm for the construction of symmetric-key MACs, dating back to the seminal works by Wegman and Carter, Shoup, and Bernstein. While fully sufficient for many practical applications, the Wegman-Carter construction, however, is well-known to break if nonces are ever repeated, and provides only birthday-bound security if instantiated with a permutation. Those limitations inspired the community to several recent proposals that addressed them, initiated by Cogliati et al.'s Encrypted Wegman-Carter Davies-Meyer (EWCDM) construction. This work extends this line of research by studying two constructions based on the sum of PRPs: (1) a stateless deterministic scheme that uses two hash functions, and (2) a nonce-based scheme with one hash-function call and a nonce. We show up to 2n/3-bit security for both of them if the hash function is universal. Compared to the EWCDM construction, our proposals avoid the fact that a single reuse of a nonce can lead to a break.
Expand
Liliya Akhmetzyanova, Evgeny Alekseev, Ekaterina Smyshlyaeva, Alexandr Sokolov
ePrint Report ePrint Report
The TLS protocol is the main cryptographic protocol of the Internet. The work on its current version, TLS 1.3, was completed in 2018. This version differs from the previous ones and has been developed taking into account all modern principles of constructing cryptographic protocols. At the same time, even when there are security proofs in some fairly strong security model, it is important to study the possibility of extending this model and then clarifying the security limits of the protocol.

In this paper, we consider in detail the restriction on the usage of post-handshake authentication in connections established on external PSK. We clarify that the certain vulnerability appears only in the case of psk_ke mode if more than a single pair of entities can possess a single PSK. We provide several practical scenarios where this condition can be easily achieved. Also we propose appropriate mitigation.
Expand
Prasanna Ravi, Sourav Sen Gupta, Anupam Chattopadhyay, Shivam Bhasin
ePrint Report ePrint Report
In this short note, we propose an optimization to improve the signing speed of Dilithium's signing procedure. Our optimization works by reducing the number of computations in the rejected iterations through Early-Evaluation of the rejection condition. We would like to note that this straightforward algorithmic optimization only reduces the computational overhead in every rejected iteration, without having any effect on the rejection rate. We perform experimental validation of our optimization through software implementation on an Intel(R) Core(TM) i5-4460 CPU and observe observe a speed up of about 7-8% of Dilithium's signing procedure for recommended parameter sets of Dilithium. Moreover, this optimization is also implementation agnostic and hence can be ported to all implementation platforms.
Expand

24 April 2019

Martin R. Albrecht, Carlos Cid, Lorenzo Grassi, Dmitry Khovratovich, Reinhard Lüftenegger, Christian Rechberger, Markus Schofnegger
ePrint Report ePrint Report
The block cipher Jarvis and the hash function Friday, both members of the MARVELlous family of cryptographic primitives, were recently proposed as custom designs aimed at addressing bottlenecks involving practical applications of STARKs. In the proposal several types of algebraic attacks were ruled out, and security arguments from Rijndael/AES were used to inform the choice for the number of rounds, with extra security margin added. In this work we describe new algebraic attacks on Jarvis and Friday using Gröbner bases, showing that the proposed number of rounds is not sufficient to provide security. In Jarvis, the round function is obtained by combining a finite field inversion S-box with a full-degree linearised permutation polynomial. However, we show that even though the high degree of this polynomial should prevent some algebraic attacks (as claimed by the designers), their particular algebraic properties make the designs vulnerable to Gröbner basis attacks. Our analysis illustrates that block cipher designs for algebraic platforms such as STARKs, FHE or MPC may be particularly vulnerable to algebraic attacks. Finally, we argue that MiMC -- a cipher similar in structure to Jarvis -- is resistant against our proposed attack strategy.
Expand
S. Sharmila Deva Selvi, Arinjita Paul, Siva Dirisala, Saswata Basu, C. Pandu Rangan
ePrint Report ePrint Report
Recently, blockchain technology has attracted much attention of the research community in several domains requiring transparency of data accountability, due to the removal of intermediate trust assumptions from third parties. One such application is enabling file sharing in blockchain enabled distributed cloud storage. Proxy re-encryption is a cryptographic primitive that allows such file sharing by re-encrypting ciphertexts towards legitimate users via semi-trusted proxies, without them learning any information about the underlying message. To facilitate secure data sharing in the distributed cloud, it is essential to construct efficient proxy re-encryption protocols. In this paper, we introduce the notion of proxy self re-encryption (SE-PRE) that is highly efficient, as compared to the existing PRE schemes in the literature. We show that our self encryption scheme is provably CCA secure based on the DLP assumption and our proxy re-encryption scheme with self encryption is CCA secure under the hardness of the Computational Diffie Hellman (CDH) and Discrete Logarithm (DLP) assumption. Our novel encryption scheme, called self encryption, has no exponentiation or costly pairing operation. Even the re-encryption in SE-PRE does not have such operations and this facilitates the service provider with efficiency gain.
Expand
Jung Hee Cheon, Dongwoo Kim, Duhyeong Kim, Hun Hee Lee, Keewoo Lee
ePrint Report ePrint Report
We propose a new method to compare numbers which are encrypted by Homomorphic Encryption (HE). Previously, comparison and min/max functions were evaluated using Boolean functions where input numbers are encrypted bit-wisely. However, the bit-wise encryption methods require relatively expensive computation of basic arithmetic operations such as addition and multiplication.

In this paper, we introduce iterative algorithms that approximately compute the min/max and comparison operations of several numbers which are encrypted word-wisely. From the concrete error analyses, we show that our min/max and comparison algorithms have $\Theta(\alpha)$ and $\Theta(\alpha\log\alpha)$ computational complexity to obtain approximate values within an error rate $2^{-\alpha}$, while the previous minimax polynomial approximation method requires the exponential complexity $\Theta(2^{\alpha/2})$ and $\Theta(\sqrt{\alpha}\cdot 2^{\alpha/2})$, respectively. We also show the (sub-)optimality of our min/max and comparison algorithms in terms of asymptotic computational complexity among polynomial evaluations to obtain approximate min/max and comparison results. Our comparison algorithm is extended to several applications such as computing the top-$k$ elements and counting numbers over the threshold in encrypted state.

Our new method enables word-wise HEs to enjoy comparable performance in practice with bit-wise HEs for comparison operations while showing much better performance on polynomial operations. Computing an approximate maximum value of any two $\ell$-bit integers encrypted by HEAAN, up to error $2^{\ell-10}$, takes only $1.14$ milliseconds in amortized running time, which is comparable to the result based on bit-wise HEs.
Expand
Evangelos Georgiadis
ePrint Report ePrint Report
Transactions are arguably the most important part in the bitcoin mechanism, with everything else facilitating the proper creation, propagation and validation; culminating with their addition to the public ledger – the blockchain. One crucial measure inevitably intertwined with transactions is, throughput, the number of transactions confirmed (or added to the blockchain) per second, or simply, tps. Understanding throughput capacity from different angles remains of paramount importance for gaining insights into the underlying infrastructure. We compute the exact upper bound for the maximal transaction throughput of the bitcoin protocol and obtain 27 tps. The previous best known bound for the average transaction throughput is 7 tps. All results are based on legacy infrastructure, i.e., pre-SegWit era.
Expand
Ryuya Nakamura, Takayuki Jimba, Dominik Harz
ePrint Report ePrint Report
Decentralised ledgers are a prime application case for consensus protocols. Changing sets of validators have to agree on a set of transactions in an asynchronous network and in the presence of Byzantine behaviour. Major research efforts focus on creating consensus protocols under such conditions, with proof-of-stake (PoS) representing a promising candidate for decentralised ledgers. PoS aims to reduce the waste of energy inherent to proof-of-work (PoW) consensus protocols. However, a significant challenge is to get PoS protocols "right", i.e. ensure that they are secure w.r.t. safety and liveness. Security proofs are provided using pen-and-paper approaches including the "Correct-by-Construction" (CBC) Casper proposed by the Ethereum project. CBC Casper's design philosophy deviates from traditional consensus protocols as it is an abstract framework to define consensus protocols and aims to prove its correctness without loss of abstractness. Each member of the CBC Casper family of protocols is defined by five parameters. CBC Casper models the protocol by a state of each validator and messages sent by validators. Each validator can transition its state using messages by other validators that include their current consensus value and a justification (i.e. their previous messages). We extend CBC Casper in three ways. First, we summarise the research of CBC Casper and extend the definitions of safety and liveness properties. To this end, we discuss an instance of CBC Casper called Casper The Friendly GHOST (TFG), a consensus protocol using a variant of the GHOST fork-choice rule. Second, we refine the properties of messages and states in CBC Casper and give a definition of blockchain safety for Casper TFG. Third, we formally verify CBC Casper together with our additional properties in the Isabelle/HOL proof assistant.
Expand

23 April 2019

Xi'an, China, 15 November - 17 November 2019
Event Calendar Event Calendar
Event date: 15 November to 17 November 2019
Submission deadline: 10 June 2019
Notification: 20 April 2019
Expand
TU Darmstadt
Job Posting Job Posting
We are looking for outstanding Post doctoral researchers working on topics related to cryptography and IT Security.

Current topics of interest include (but are not limited to):

- Secure cryptographic implementations

- Leakage/tamper resilient cryptography

- Blockchains and cryptocurrencies

- Distributed cryptography

The application must include a curriculum vitae, a short research statement, and names of 2 contacts that can provide reference about the applicant and her/his work. The candidate shall be able to show solid expertise in cryptography/IT Security illustrated in form of publications at major crypto/security venues such as CRYPTO, EUROCRYPT, ASIACRYPT, TCC, PKC, CHES, FC, ACM CCS, IEEE S&P, USENIX Security, NDSS etc.

The position can be partially funded by the Ethereum Foundation and hence offers an internationally competitive salary including social benefits, and the opportunity for close collaboration with one of the leading cryptocurrencies.

TU Darmstadt offers excellent working environment and has a strong institute for research on IT security with more than 300 researchers working on all aspects of cybersecurity.

Review of applications starts immediately until the position is filled.

Closing date for applications: 14 June 2019

Contact: Prof. Sebastian Faust, Contact: sebastian.faust(at)cs(dot)tu-darmstadt(dot)de

Expand
The University of Sheffield, Department of Computer Science
Job Posting Job Posting
This is an exciting opportunity for a Lecturer/Senior Lecturer in Cybersecurity at the University of Sheffield, a world top 100 University.

The Department of Computer Science (https://www.sheffield.ac.uk/dcs) is embarking on an ambitious growth strategy following our strong performance in the Research Excellence Framework (REF) 2014, in which we were ranked 5th out of 89 computer science departments in the UK. The Department is part of the Faculty of Engineering, ranked 84th globally by the recent Times Higher Education (THE) World University Rankings, and holds a Silver Athena SWAN award, in recognition of our commitment to equality and diversity.

We are seeking candidates with an outstanding record of scholarship in cybersecurity. Suitable areas of expertise include (but are not limited to): security policies, threat modelling, authentication, access control, malware and malware detection, network security, secure protocols, secure software, security testing, and human factors and security. Candidates whose expertise includes elements of ‘security by design’ (primarily focused on software based systems) are particularly encouraged to apply.

You will hold a PhD in Computer Science or a relevant discipline (or have equivalent experience), and you will be able to conduct research to the highest standards. You will secure research funding, publish in high impact journals, supervise research students and manage research projects. As a teacher, you will play a key role in maintaining our reputation for high-quality teaching by designing, delivering and assessing undergraduate and postgraduate-level courses in cybersecurity and other core topics in computer science.

We’re one of the best not-for-profit organisations to work for in the UK. The University’s Total Reward Package includes a competitive salary, a generous Pension Scheme and annual leave entitlement, as well as access to a range of learning and development courses to support your personal and professional development.

Closing date for applications: 21 May 2019

Contact: Prof John Clark, Security of Advanced Systems Research Group Lead. An initial contact via email (john.clark (at) sheffield.ac.uk) is encouraged.

More information: https://www.jobs.ac.uk/job/BRR743/lecturer-senior-lecturer-in-cybersecurity

Expand

22 April 2019

Nico Dottling, Sanjam Garg, Mohammad Hajiabadi, Daniel Masny, Daniel Wichs
ePrint Report ePrint Report
We show a new general approach for constructing maliciously secure two-round oblivious transfer (OT). Specifically, we provide a generic sequence of transformations to upgrade a very basic notion of two-round OT, which we call elementary OT, to UC-secure OT. We then give simple constructions of elementary OT under the Computational Diffie-Hellman (CDH) assumption or the Learning Parity with Noise (LPN) assumption, yielding the first constructions of malicious (UC-secure) two-round OT under these assumptions. Since two-round OT is complete for two-round 2-party and multi-party computation in the malicious setting, we also achieve the first constructions of the latter under these assumptions.
Expand
Itai Dinur
ePrint Report ePrint Report
An adversary with $S$ bits of memory obtains a stream of $Q$ elements that are uniformly drawn from the set $\{1,2,\ldots,N\}$, either with or without replacement. This corresponds to sampling $Q$ elements using either a random function or a random permutation. The adversary's goal is to distinguish between these two cases.

This problem was first considered by Jaeger and Tessaro (EUROCRYPT 2019), which proved that the adversary's advantage is upper bounded by $\sqrt{Q \cdot S/N}$. Jaeger and Tessaro used this bound as a streaming switching lemma which allowed proving that known time-memory tradeoff attacks on several modes of operation (such as counter-mode) are optimal up to a factor of $O(\log N)$ if $Q \cdot S \approx N$. However, if $Q \cdot S \ll N$ there is a gap between the upper bound of $\sqrt{Q \cdot S/N}$ and the $Q \cdot S/N$ advantage obtained by known attacks. Moreover, the bound's proof assumed an unproven combinatorial conjecture.

In this paper, we prove a tight upper bound (up to poly-logarithmic factors) of $O(\log Q \cdot Q \cdot S/N)$ on the adversary's advantage in the streaming distinguishing problem. The proof does not require a conjecture and is based on a reduction from communication complexity to streaming.
Expand
Eliane KOUSSA, Gilles MACARIO-RAT, Jacques PATARIN
ePrint Report ePrint Report
In this document, we investigate the complexity of an old-time combinatorial problem - namely Permuted Kernel Problem (PKP) - about which no new breakthrough were reported for a while. PKP is an NP-complete algebraic problem that consists of finding a kernel vector with particular entries for a publicly known matrix. It’s simple, and needs only basic linear algebra. Hence, this problem was used to develop the first Identification Scheme (IDS) which has an efficient implementation on low-cost smart cards. The Permuted Kernel Problem has been extensively studied. We present a summary of previously known algorithms devoted to solve this problem and give an update to their complexity. Contrary to what is shown in JOUX-JAULMES's article, and after a thorough analysis of the State-of-the-art attacks of PKP, we claim that the most efficient algorithm for solving PKP is still the one introduced by J. PATARIN and P. CHAUVAUD. We have been able to specify a theoretical bound on the complexity of PKP which allows us to identify hard instances of this latter. Among all the attacks, the problem PKP is in spite of the research effort, still exponential.
Expand
Tong Cao, Jiangshan Yu, Jérémie Decouchant, Xiapu Luo, Paulo Verissimo
ePrint Report ePrint Report
As of 12th January 2019, Monero is ranked as the first privacy-preserving cryptocurrency by market capitalization, and the 14th among all cryptocurrencies. This paper aims at improving the understanding of the Monero peer-to-peer network. We develop a tool set to explore the Monero peer-to-peer network, including its network size, distribution, and connectivity. In addition, we set up four Monero nodes that run our tools: two in the U.S., one in Asia, and one in Europe. We show that through a short time (one week) data collection, our tool is already able to discover 68.7% more daily active peers (in average) compared to a Monero mining pool, called Monerohash, that also provides data on the Monero node distribution. Overall, we discovered 21,678 peer IP addresses in the Monero network. Our results show that only 4,329 (about 20%) peers are active. We also show that the nodes in the Monero network follow the power law distribution concerning the number of connections they maintain. In particular, only 0.7% of the active maintain more than 250 outgoing connections simultaneously, and a large proportion (86.8%) of the nodes maintain less than 8 outgoing connections. These 86.8% nodes only maintain 17.14% of the overall connections in the network, whereas the remaining 13.2% nodes maintain 82.86% of the overall connections. We also show that our tool is able to dynamically infer the complete outgoing connections of 99.3% nodes in the network, and infer 250 outgoing connections of the remaining 0.7% nodes.
Expand
Kai Samelin, Daniel Slamanig
ePrint Report ePrint Report
Sanitizable signatures allow a single, and signer-defined, sanitizer to modify signed messages in a controlled way without invalidating the respective signature. They turned out to be a fascinating primitive, proven by different variants and extensions, e.g., allowing multiple sanitizers or adding new sanitizers one-by-one. Still, existing constructions are very limited regarding their flexibility in specifying potential sanitizers. In this paper, we propose a different and more powerful approach: Instead of using the sanitizers' public keys directly, we assign attributes to them. Sanitizing is then based on policies, i.e., access structures defined over attributes. A sanitizer can sanitize, if, and only if, it holds a secret key to attributes satisfying the policy associated to a signature, while offering full-scale accountability.
Expand
◄ Previous Next ►