International Association for Cryptologic Research

IACR News Central

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

Now viewing news items related to:

10 December 2018
ePrint Report Cryptanalysis of 2-round KECCAK-384 Rajendra Kumar, Nikhil Mittal, Shashank Singh
In this paper, we present a cryptanalysis of round reduced Keccak-384 for 2 rounds. The best known preimage attack for this variant of Keccak has the time complexity $2^{129}$. In our analysis, we find a preimage in the time complexity of $2^{89}$ and almost same memory is required.
In a recent work, Katz et al. (CANS'17) generalized the notion of Broadcast Encryption to define Subset Predicate Encryption (SPE) that emulates \emph{subset containment} predicate in the encrypted domain. They proposed two selective secure constructions of SPE in the small universe settings. Their first construction is based on $q$-type assumption while the second one is based on DBDH. % which can be converted to large universe using random oracle. Both achieve constant size secret key while the ciphertext size depends on the size of the privileged set. They also showed some black-box transformation of SPE to well-known primitives like WIBE and ABE to establish the richness of the SPE structure.

This work investigates the question of large universe realization of SPE scheme based on static assumption without random oracle. We propose two constructions both of which achieve constant size secret key. First construction $\mathsf{SPE}_1$, instantiated in composite order bilinear groups, achieves constant size ciphertext and is proven secure in a restricted version of selective security model under the subgroup decision assumption (SDP). Our main construction $\mathsf{SPE}_2$ is adaptive secure in the prime order bilinear group under the symmetric external Diffie-Hellman assumption (SXDH). Thus $\mathsf{SPE}_2$ is the first large universe instantiation of SPE to achieve adaptive security without random oracle. Both our constructions have efficient decryption function suggesting their practical applicability. Thus the primitives like WIBE and ABE resulting through black-box transformation of our constructions become more practical.
ePrint Report The Role of the Adversary Model in Applied Security Research Quang Do, Ben Martini, Kim-Kwang Raymond Choo
Adversary models have been integral to the design of provably-secure cryptographic schemes or protocols. However, their use in other computer science research disciplines is relatively limited, particularly in the case of applied security research (e.g., mobile app and vulnerability studies). In this study, we conduct a survey of prominent adversary models used in the seminal field of cryptography, and more recent mobile and Internet of Things (IoT) research. Motivated by the findings from the cryptography survey, we propose a classification scheme for common app-based adversaries used in mobile security research, and classify key papers using the proposed scheme. Finally, we discuss recent work involving adversary models in the contemporary research field of IoT. We contribute recommendations to aid researchers working in applied (IoT) security based upon our findings from the mobile and cryptography literature. The key recommendation is for authors to clearly define adversary goals, assumptions and capabilities.
We present batching techniques for cryptographic accumulators and vector commitments in groups of unknown order. Our techniques are tailored for decentralized settings where no trusted accumulator manager exists and updates to the accumulator are processed in batches. We develop techniques for non-interactively aggregating membership proofs that can be verified with a constant number of group operations. We also provide a constant sized batch non-membership proof for a large number of elements. These proofs can be used to build a positional vector commitment with constant sized openings and constant sized public parameters. As a core building block for our batching techniques we develop several succinct proofs for groups of unknown order. These include a proof that an exponentiation was done correctly and a zero-knowledge proof of knowledge of an integer discrete logarithm between two group elements. We use these new constructions to design a stateless blockchain, where nodes only need a constant storage. Further we show that our vector commitment can be used to significantly reduce the size of IOP instantiations, such as STARKs.
The division property proposed at Eurocrypt'15 is a novel technique to find integral distinguishers, which has been applied to most kinds of symmetric ciphers such as block ciphers, stream ciphers, and authenticated encryption,~\textit{etc}. The original division property is word-oriented, and later the bit-based one was proposed at FSE'16 to get better integral property, which is composed of conventional bit-based division property (two-subset division property) and bit-based division property using three subsets (three-subset division property). Three-subset division property has more potential to achieve better integral distinguishers compared with the two-subset division property. The bit-based division property could not be to apply to ciphers with large block sizes due to its unpractical complexity. At Asiacrypt'16, the two-subset division property was modeled using Mixed Integral Linear Programming (MILP) technique, and the limits of block sizes were eliminated. However, there is still no efficient method searching for three-subset division property. The propagation rule of the \texttt{XOR} operation for $\mathbb{L}$ \footnote{The definition of $\mathbb{L}$ and $\mathbb{K}$ is introduced in Section 2.}, which is a set used in the three-set division property but not in two-set one, requires to remove some specific vectors, and new vectors generated from $\mathbb{L}$ should be appended to $\mathbb{K}$ when \texttt{Key-XOR} operation is applied, both of which are difficult for common automatic tools such as MILP, SMT or CP. In this paper, we overcome one of the two challenges, concretely, we address the problem to add new vectors into $\mathbb{K}$ from $\mathbb{L}$ in an automatic search model. Moreover, we present a new model automatically searching for a variant three-subset division property (VTDP) with STP solver. The variant is weaker than the original three-subset division property (OTDP) but it is still powerful in some ciphers. Most importantly, this model has no constraints on the block size of target ciphers, which can also be applied to ARX and S-box based ciphers. As illustrations, some improved integral distinguishers have been achieved for SIMON32, SIMON32/48/64(102), SPECK32 and KATAN/KTANTAN32/48/64 according to the number of rounds or number of even/odd-parity bits.
Division property is a generalized integral property proposed by Todo at EUROCRYPT 2015, and then conventional bit-based division property (CBDP) and bit-based division property using three subsets (BDPT) were proposed by Todo and Morii at FSE 2016. The huge time and memory complexity that once restricted the applications of CBDP have been solved by Xiang et al. at ASIACRYPT 2016. They extended Mixed Integer Linear Programming (MILP) method to search integral distinguishers based on CBDP. BDPT can find more accurate integral distinguishers than CBDP, but it can not be modeled efficiently. Thus it cannot be applied to block ciphers with block size larger than 32 bits. In this paper, we focus on the feasibility of applying MILP-aided method to search integral distinguishers based on BDPT. We firstly study how to get the BDPT propagation rules of an S-box. Based on that we can efficiently describe the BDPT propagation of cipher which has S-box. Moreover, we propose a technique called ``fast propagation", which can translate BDPT into CBDP, then the balanced bits based on BDPT can be presented. Together with the propagation properties of BDPT, we can use MILP method based on CBDP to search integral distinguishers based on BDPT. In order to prove the efficiency of our method, we search integral distinguishers on SIMON, SIMECK, PRESENT, RECTANGLE, LBlock, and TWINE. For SIMON64, PRESENT, and RECTANGLE, we find more balanced bits than the previous longest distinguishers. For LBlock, we find a 17-round integral distinguisher which is one more round than the previous longest integral distinguisher, and a better 16-round integral distinguisher with less active bits can be obtain. For other ciphers, our results are in accordance with the previous longest distinguishers.
ePrint Report On Quantum Chosen-Ciphertext Attacks and Learning with Errors Gorjan Alagic, Stacey Jeffery, Maris Ozols, Alexander Poremba
Large-scale quantum computing is a significant threat to classical public-key cryptography. In strong “quantum access” security models, numerous symmetric-key cryptosystems are also vulnerable. We consider classical encryption in a model which grants the adversary quantum oracle access to encryption and decryption, but where the latter is restricted to non-adaptive (i.e., pre-challenge) queries only. We define this model formally using appropriate notions of ciphertext indistinguishability and semantic security (which are equivalent by standard arguments) and call it QCCA1 in analogy to the classical CCA1 security model. Using a bound on quantum random-access codes, we show that the standard PRF- and PRP-based encryption schemes are QCCA1-secure when instantiated with quantum-secure primitives.

We then revisit standard IND-CPA-secure Learning with Errors (LWE) encryption and show that leaking just one quantum decryption query (and no other queries or leakage of any kind) allows the adversary to recover the full secret key with constant success probability. In the classical setting, by contrast, recovering the key uses a linear number of decryption queries, and this is optimal. The algorithm at the core of our attack is a (large-modulus version of) the well-known Bernstein-Vazirani algorithm. We emphasize that our results should not be interpreted as a weakness of these cryptosystems in their stated security setting (i.e., post-quantum chosen-plaintext secrecy). Rather, our results mean that, if these cryptosystems are exposed to chosen-ciphertext attacks (e.g., as a result of deployment in an inappropriate real-world setting) then quantum attacks are even more devastating than classical ones.
The blockchain technology represents a new paradigm to realize persistent distributed ledgers globally. While the blockchain technology is promising in a great number of fields, it can be abused to covertly store and disseminate potentially harmful digital content. Consequently, using blockchains as uncensored decentralized networks for arbitrary data distribution poses a serious regulatory issue. In this work, we show the severity of the problem by demonstrating a new technique that can be exploited to use the blockchain as a covert bulletin board to secretly store and distribute objectionable content. More speci cally, all major blockchain systems use randomized cryptographic primitives, such as digital signatures and non-interactive zero-knowledge proofs, and we illustrate how the uncontrolled randomness in such primitives can be maliciously manipulated to enable covert communication and hidden persistent storage. We also demonstrate how the same technique can be extended to launch subversion attacks on the wallets of most top-ranked cryptocurrencies, such as Bitcoin, Ethereum, Monero, etc. To clarify the potential risk of uncontrolled randomness, we design, implement and evaluate our technique against the widely-used ECDSA signature scheme, the CryptoNote's ring signature scheme, and Monero's ring con dential transactions. Note that the signi cance of the demonstrated attacks stems from their undetectability, their adverse effect on the future of decentralized blockchains, and their serious repercussions on users' privacy and crypto funds. Finally, besides presenting the attacks, we provide a discussion of current countermeasures and suggest some countermeasures to mitigate the threat of such attacks.
5 December 2018
ePrint Report Lossy Trapdoor Permutations with Improved Lossiness Benedikt Auerbach, Eike Kiltz, Bertram Poettering, Stefan Schoenen
Lossy trapdoor functions (Peikert and Waters, STOC 2008 and SIAM J. Computing 2011) imply, via black-box transformations, a number of interesting cryptographic primitives, including chosen-ciphertext secure public-key encryption. Kiltz, O'Neill, and Smith (CRYPTO 2010) showed that the RSA trapdoor permutation is lossy under the Phi-hiding assumption, but syntactically it is not a lossy trapdoor function since it acts on Z_N and not on strings. Using a domain extension technique by Freeman et al. (PKC 2010 and J. Cryptology 2013) it can be extended to a lossy trapdoor permutation, but with considerably reduced lossiness.

In this work we give new constructions of lossy trapdoor permutations from the Phi-hiding assumption, the quadratic residuosity assumption, and the decisional composite residuosity assumption, all with improved lossiness. Furthermore, we propose the first all-but-one lossy trapdoor permutation from the Phi-hiding assumption. A technical vehicle used for achieving this is a novel transform that converts trapdoor functions with index-dependent domain into trapdoor functions with fixed domain.
With the fast development of quantum computation, code based cryptography arises public concern as a candidate of post quantum cryptography. However, the large key-size becomes a main drawback such that the code-based schemes seldom become practical although they performed pretty well on the speed of both encryption and decryption algorithm. Algebraic geometry codes was considered to be a good solution to reduce the size of keys, but because of its special construction, there have lots of attacks against them. In this paper, we propose a public key encryption scheme based on elliptic codes which can resist the known attacks. By using automorphism on the rational points of the elliptic curve, we construct quasi-cyclic elliptic codes, which reduce the key size further. We apply the list-decoding algorithm to decryption thus more errors beyond half of the minimum distance of the code could be correct, which is the key point to resist the known attacks for AG codes based cryptosystem.
ePrint Report Horizontal DEMA Attack as the Criterion to Select the Best Suitable EM Probe Christian Wittke, Ievgen Kabin, Dan Klann, Zoya Dyka, Anton Datsuk, Peter Langendoerfer
Implementing cryptographic algorithms in a tamper resistant way is an extremely complex task as the algorithm used and the target platform have a significant impact on the potential leakage of the implementation. In addition the quality of the tools used for the attacks is of importance. In order to evaluate the resistance of a certain design against electromagnetic emanation attacks – as a highly relevant type of attacks – we discuss the quality of different electromagnetic (EM) probes as attack tools. In this paper we propose to use the results of horizontal attacks for comparison of measurement setup and for determining the best suitable instruments for measurements. We performed horizontal differential electromagnetic analysis (DEMA) attacks against our ECC design that is an im-plementation of the Montgomery kP algorithm for the NIST elliptic curve B-233. We experimented with 7 different EM probes under same conditions: attacked FPGA, design, inputs, measurement point and measurement equipment were the same, excepting EM probes. The used EM probe influences the success rate of performed attack significantly. We used this fact for the comparison of probes and for determining the best suitable one.
ePrint Report Lattice-Based Signature from Key Consensus Leixiao Cheng, Boru Gong, Yunlei Zhao
In this work, we present generalization and optimization of Dilithium, which is one of the promising lattice-based signature candidates for NIST postquantum cryptography (PQC) standardization. This is enabled by new insights in interpreting the design of Dilithium, in terms of key consensus presented in the KCL key encapsulation mechanism (KEM) proposal to NIST PQC standardization. Based on OKCN developed in KCL, we present a generic and modular construction of lattice-based signature, and make analysis as it is deployed in reality. We thoroughly search and test a large set of parameters in order to achieve better trade-offs among security, efficiency, and bandwidth. On the recommended parameters for about 128-bit quantum security, compared with Dilithium, our scheme is more efficient both in computation and in bandwidth. This work also further justifies and highlights the desirability of OKCN as the same routine can be used for both KEM and signatures, which is useful to simplify system complexity of lattice-based cryptography. Of independent interest is a new estimation of the security against key recovery attacks in reality.
ePrint Report Elliptic Curves in Generalized Huff's Model Ronal Pranil Chand, Maheswara Rao Valluri
This paper introduces elliptic curves in generalized Huff's model. These curves endowed with addition are shown to be a group over a finite field. We present formulae for point addition and doubling point on the curves and evaluate computational cost of point addition and doubling point using projective, Jacobian and Lopez-Dahab coordinates. It is noted that the computational cost for point addition and doubling on the curves is lower on the projective coordinates than the other mentioned above coordinates.
2 December 2018
Let $\Omega$ be a finite set of operation symbols. We initiate the study of (weakly) pseudo-free families of computational $\Omega$-algebras in arbitrary varieties of $\Omega$-algebras. Most of our results concern (weak) pseudo-freeness in the variety $\mathfrak O$ of all $\Omega$-algebras. A family $(H_d)_{d\in D}$ of computational $\Omega$-algebras (where $D\subseteq\{0,1\}^*$) is called polynomially bounded (resp., having exponential size) if there exists a polynomial $\eta$ such that for all $d\in D$, the length of any representation of every $h\in H_d$ is at most $\eta(\lvert d\rvert)$ (resp., $\lvert H_d\rvert\le2^{\eta(\lvert d\rvert)}$). First, we prove the following trichotomy: (i) if $\Omega$ consists of nullary operation symbols only, then there exists a polynomially bounded pseudo-free family in $\mathfrak O$; (ii) if $\Omega=\Omega_0\cup\{\omega\}$, where $\Omega_0$ consists of nullary operation symbols and the arity of $\omega$ is $1$, then there exist an exponential-size pseudo-free family and a polynomially bounded weakly pseudo-free family (both in $\mathfrak O$); (iii) in all other cases, the existence of polynomially bounded weakly pseudo-free families in $\mathfrak O$ implies the existence of collision-resistant families of hash functions. Second, assuming the existence of collision-resistant families of hash functions, we construct a polynomially bounded weakly pseudo-free family and an exponential-size pseudo-free family of computational $m$-ary groupoids (both in $\mathfrak O$), where $m\ge1$. In particular, for arbitrary $m\ge2$, polynomially bounded weakly pseudo-free families of computational $m$-ary groupoids in $\mathfrak O$ exist if and only if collision-resistant families of hash functions exist. Moreover, we present some simple constructions of cryptographic primitives from pseudo-free families satisfying certain additional conditions. These constructions demonstrate the potential of pseudo-free families.
ePrint Report Excalibur Key-Generation Protocols For DAG Hierarchic Decryption Louis Goubin, Geraldine Monsalve, Juan Reutter, Francisco Vial Prado
Public-key cryptography applications often require structuring decryption rights according to some hierarchy. This is typically addressed with re-encryption procedures or relying on trusted parties, in order to avoid secret-key transfers and leakages. Using a novel approach, Goubin and Vial-Prado (2016) take advantage of the Multikey FHE-NTRU encryption scheme to establish decryption rights at key-generation time, thus preventing leakage of all secrets involved (even by powerful key-holders). Their algorithms are intended for two parties, and can be composed to form chains of users with inherited decryption rights. In this article, we provide new protocols for generating Excalibur keys under any DAG-like hierarchy, and present formal proofs of security against semi-honest adversaries. Our protocols are compatible with the homomorphic properties of FHE-NTRU, and the base case of our security proofs may be regarded as a more formal, simulation-based proof of said work.
ePrint Report Downgradable Identity-based Encryption and Applications Olivier Blazy, Paul Germouty, Duong Hieu Phan
In Identity-based cryptography, in order to generalize one receiver encryption to multi-receiver encryption, wildcards were introduced: WIBE enables wildcard in receivers' pattern and Wicked-IBE allows one to generate a key for identities with wildcard. However, the use of wildcard makes the construction of WIBE, Wicked-IBE more complicated and significantly less efficient than the underlying IBE. The main reason is that the conventional identity's binary alphabet is extended to a ternary alphabet $\{0,1,*\}$ and the wildcard $*$ is always treated in a convoluted way in encryption or in key generation. In this paper, we show that when dealing with multi-receiver setting, wildcard is not necessary. We introduce a new downgradable property for IBE scheme and show that any IBE with this property, called DIBE, can be efficiently transformed into WIBE or Wicked-IBE.

While WIBE and Wicked-IBE have been used to construct Broadcast encryption, we go a step further by employing DIBE to construct Attribute-based Encryption of which the access policy is expressed as a boolean formula in the disjunctive normal form.
ePrint Report New Privacy Threat on 3G, 4G, and Upcoming 5G AKA Protocols Ravi Borgaonkar, Lucca Hirschi, Shinjo Park, Altaf Shaik
Mobile communications are used by more than two thirds of the world population who expect security and privacy guarantees. The 3rd Generation Partnership Project (3GPP) responsible for the worldwide standardization of mobile communication has designed and mandated the use of the AKA protocol to protect the subscribers' mobile services. Even though privacy was a requirement, numerous subscriber location attacks have been demonstrated against AKA, some of which have been fixed or mitigated in the enhanced AKA protocol designed for 5G.

In this paper, we reveal a new privacy attack against all variants of the AKA protocol, including 5G AKA, that breaches subscriber privacy more severely than known location privacy attacks do. Our attack exploits a new logical vulnerability we uncovered that would require dedicated fixes. We demonstrate the practical feasibility of our attack using low cost and widely available setups. Finally we conduct a security analysis of the vulnerability and discuss countermeasures to remedy our attack.
We analyze the size vs. security trade-offs that are available when selecting parameters for perfectly correct key encapsulation mechanisms based on NTRU.
ePrint Report The 9 Lives of Bleichenbacher's CAT: New Cache ATtacks on TLS Implementations Eyal Ronen, Robert Gillham, Daniel Genkin, Adi Shamir, David Wong, Yuval Yarom
At CRYPTO’98, Bleichenbacher published his seminal paper which described a padding oracle attack against RSA implementations that follow the PKCS #1 v1.5 standard.

Over the last twenty years researchers and implementors had spent a huge amount of effort in developing and deploying numerous mitigation techniques which were supposed to plug all the possible sources of Bleichenbacher-like leakages. However, as we show in this paper most implementations are still vulnerable to several novel types of attack based on leakage from various microarchitectural side channels: Out of nine popular implementations of TLS that we tested, we were able to break the security of seven implementations with practical proof-of-concept attacks. We demonstrate the feasibility of using those Cache-like ATacks (CATs) to perform a downgrade attack against any TLS connection to a vulnerable server, using a BEAST-like Man in the Browser attack.

The main difficulty we face is how to perform the thousands of oracle queries required before the browser’s imposed timeout (which is 30 seconds for almost all browsers, with the exception of Firefox which can be tricked into extending this period). The attack seems to be inherently sequential (due to its use of adaptive chosen ciphertext queries), but we describe a new way to parallelize Bleichenbacher-like padding attacks by exploiting any available number of TLS servers that share the same public key certificate.

With this improvement, we could demonstrate the feasibility of a downgrade attack which could recover all the 2048 bits of the RSA plaintext (including the premaster secret value, which suffices to establish a secure connection) from five available TLS servers in under 30 seconds. This sequential-to-parallel transformation of such attacks can be of independent interest, speeding up and facilitating other side channel attacks on RSA implementations.
ePrint Report The impact of error dependencies on Ring/Mod-LWE/LWR based schemes Jan-Pieter D'Anvers, Frederik Vercauteren, Ingrid Verbauwhede
Current estimation techniques for the probability of decryption failures in Ring/Mod-LWE/LWR based schemes assume independence of the failures in individual bits of the transmitted message to calculate the full failure rate of the scheme. In this paper we disprove this assumption both theoretically and practically for schemes based on Ring/Mod-Learning with Errors/Rounding. We provide a method to estimate the decryption failure probability, taking into account the bit failure dependency. We show that the independence assumption is suitable for schemes without error correction, but that it might lead to underestimating the failure probability of algorithms using error correcting codes. In the worst case, for LAC-128, the failure rate is $2^{48}$ times bigger than estimated under the assumption of independence. This higher-than-expected failure rate could lead to more efficient cryptanalysis of the scheme through decryption failure attacks.
ePrint Report PwoP: Intrusion-Tolerant and Privacy-Preserving Sensor Fusion Chenglu Jin, Marten van Dijk, Michael Reiter, Haibin Zhang
We design and implement, PwoP, an efficient and scalable system for intrusion-tolerant and privacy-preserving multi-sensor fusion. PwoP develops and unifies techniques from dependable distributed systems and modern cryptography, and in contrast to prior works, can 1) provably defend against pollution attacks where some malicious sensors lie about their values to sway the final result, and 2) perform within the computation and bandwidth limitations of cyber-physical systems.

PwoP is flexible and extensible, covering a variety of application scenarios. We demonstrate the practicality of our system using Raspberry Pi Zero W, and we show that PwoP is efficient in both failure-free and failure scenarios.
ePrint Report Towards RSA-OAEP without Random Oracles Nairen Cao, Adam O'Neill, Mohammad Zaheri
We give the first positive results about instantiability of the widely implemented and standardized RSA-OAEP encryption scheme of Bellare and Rogaway (EUROCRYPT 1994) and variants under chosen-ciphertext attack. Recall that RSA-OAEP adds redundancy and randomness to a message before composing two rounds of an underlying Feistel transform, whose round functions are modeled as random oracles (ROs), with RSA. First, we show that either of the two oracles (while still modeling the other as a RO) can be instantiated in RSA-OAEP under IND-CCA2 using mild standard model assumptions. Ours are the first ``partial instantiation'' results for RSA-OAEP. We obtain them by exploiting (generalizations of) algebraic properties of RSA proven by Barthe, Pointcheval, and Baguelin (CCS 2012). Second, we show that both oracles can be instantiated simultaneously for two variants of RSA-OAEP, called ``$t$-clear'' and ``$s$-clear'' RSA-OAEP. In particular, we are the first show positive results for $s$-clear RSA-OAEP, and our results for it yield the most efficient RSA-based IND-CCA2 secure scheme (under plausible assumptions) in the standard model to date. We obtain it by leveraging a new hierarchy of extractability-style assumptions in the sense of Canetti and Dakdouk (TCC 2010) on the round functions, as well as novel yet plausible ``XOR-type'' assumptions on RSA. Notably, our full instantiation results avoid impossibility results of Shoup (J. Cryptology 2002), Kiltz and Pietrzak (EUROCRYPT 2009), and Bitansky et al.` (STOC 2014).
In the Conditional Disclosure of Secrets (CDS) problem (Gertner et al., J. Comput. Syst. Sci., 2000) Alice and Bob, who hold $n$-bit inputs $x$ and $y$ respectively, wish to release a common secret $z$ to Carol (who knows both $x$ and $y$) if and only if the input $(x,y)$ satisfies some predefined predicate $f$. Alice and Bob are allowed to send a single message to Carol which may depend on their inputs and some shared randomness, and the goal is to minimize the communication complexity while providing information-theoretic security.

Despite the growing interest in this model, very few lower-bounds are known. In this paper, we relate the CDS complexity of a predicate $f$ to its communication complexity under various communication games. For several basic predicates our results yield tight, or almost tight, lower-bounds of $\Omega(n)$ or $\Omega(n^{1-\epsilon})$, providing an exponential improvement over previous logarithmic lower-bounds.

We also define new communication complexity classes that correspond to different variants of the CDS model and study the relations between them and their complements. Notably, we show that allowing for imperfect correctness can significantly reduce communication -- a seemingly new phenomenon in the context of information-theoretic cryptography. Finally, our results show that proving explicit super-logarithmic lower-bounds for imperfect CDS protocols is a necessary step towards proving explicit lower-bounds against the class AM, or even $\text{AM}\cap \text{co-AM}$ -- a well known open problem in the theory of communication complexity. Thus imperfect CDS forms a new minimal class which is placed just beyond the boundaries of the ``civilized'' part of the communication complexity world for which explicit lower-bounds are known.
ePrint Report Result Pattern Hiding Searchable Encryption for Conjunctive Queries Shangqi Lai, Sikhar Patranabis, Amin Sakzad, Joseph K. Liu, Debdeep Mukhopadhyay, Ron Steinfeld, Shi-Feng Sun, Dongxi Liu, Cong Zuo
The recently proposed Oblivious Cross-Tags (OXT) protocol (CRYPTO 2013) has broken new ground in designing efficient searchable symmetric encryption (SSE) protocol with support for conjunctive keyword search in a single-writer single-reader framework. While the OXT protocol offers high performance by adopting a number of specialised data-structures, it also trades-off security by leaking ‘partial’ database information to the server. Recent attacks have exploited similar partial information leakage to breach database confidentiality. Consequently, it is an open problem to design SSE protocols that plug such leakages while retaining similar efficiency. In this paper, we propose a new SSE protocol, called Hidden Cross-Tags (HXT), that removes ‘Keyword Pair Result Pattern’ (KPRP) leakage for conjunctive keyword search. We avoid this leakage by adopting two additional cryptographic primitives - Hidden Vector Encryption (HVE) and probabilistic (Bloom filter) indexing into the HXT protocol. We propose a ‘lightweight’ HVE scheme that only uses efficient symmetric-key building blocks, and entirely avoids elliptic curve-based operations. At the same time, it affords selective simulation-security against an unbounded number of secret-key queries. Adopting this efficient HVE scheme, the overall practical storage and computational overheads of HXT over OXT are relatively small (no more than 10% for two keywords query, and 21% for six keywords query), while providing a higher level of security.
ePrint Report On the Price of Proactivizing Round-Optimal Perfectly Secret Message Transmission Ravi Kishore, Ashutosh Kumar, Chiranjeevi Vanarasa, Kannan Srinathan
In a network of $n$ nodes (modelled as a digraph), the goal of a perfectly secret message transmission (PSMT) protocol is to replicate sender's message $m$ at the receiver's end without revealing any information about $m$ to a computationally unbounded adversary that eavesdrops on any $t$ nodes. The adversary may be mobile too -- that is, it may eavesdrop on a different set of $t$ nodes in different rounds. We prove a necessary and sufficient condition on the synchronous network for the existence of $r$-round PSMT protocols, for any given $r > 0$; further, we show that round-optimality is achieved without trading-off the communication complexity; specifically, our protocols have an overall communication complexity of $O(n)$ elements of a finite field to perfectly transmit one field element. Apart from optimality/scalability, two interesting implications of our results are: (a) adversarial mobility does not affect its tolerability: PSMT tolerating a static $t$-adversary is possible if and only if PSMT tolerating mobile $t$-adversary is possible; and (b) mobility does not affect the round optimality: the fastest PSMT protocol tolerating a static $t$-adversary is not faster than the one tolerating a mobile $t$-adversary.
ePrint Report Keeping Time-Release Secrets through Smart Contracts Jianting Ning, Hung Dang, Ruomu Hou, Ee-Chien Chang
A time-release protocol enables one to send secrets into a future release time. The main technical challenge lies in incorporating timing control into the protocol, especially in the absence of a central trusted party. To leverage on the regular heartbeats emitted from decen- tralized blockchains, in this paper, we advocate an incentive-based approach that combines threshold secret sharing and blockchain based smart contract. In particular, the secret is split into shares and distributed to a set of incentivized participants, with the payment settlement contractualized and enforced by the autonomous smart contract. We highlight that such ap- proach needs to achieve two goals: to reward honest participants who release their shares honestly after the release date (the “carrots”), and to punish premature leakage of the shares (the “sticks”). While it is not difficult to contractualize a carrot mechanism for punctual releases, it is not clear how to realise the stick. In the first place, it is not clear how to identify premature leakage. Our main idea is to encourage public vigilantism by incorporating an informer-bounty mechanism that pays bounty to any informer who can provide evidence of the leakage. The possibility of being punished constitute a deterrent to the misbehaviour of premature releases. Since various entities, including the owner, participants and the in- formers, might act maliciously for their own interests, there are many security requirements. In particular, to prevent a malicious owner from acting as the informer, the protocol must ensure that the owner does not know the distributed shares, which is counter-intuitive and not addressed by known techniques. We investigate various attack scenarios, and propose a secure and efficient protocol based on a combination of cryptographic primitives. Our technique could be of independent interest to other applications of threshold secret sharing in deterring sharing.
Identity concealment and zero-round trip time (0-RTT) connection are two of current research focuses in the design and analysis of secure transport protocols, like TLS1.3 and Google's QUIC, in the client-server setting. In this work, we introduce a new primitive for identity-concealed authenticated encryption in the public-key setting, referred to as {higncryption, which can be viewed as a novel monolithic integration of public-key encryption, digital signature, and identity concealment. We present the security definitional framework for higncryption, and a conceptually simple (yet carefully designed) protocol construction.

As a new primitive, higncryption can have many applications. In this work, we focus on its applications to 0-RTT authentication, showing higncryption is well suitable to and compatible with QUIC and OPTLS, and on its applications to identity-concealed authenticated key exchange (CAKE) and unilateral CAKE (UCAKE). In particular, we make a systematic study on applying and incorporating higncryption to TLS. Of independent interest is a new concise security definitional framework for CAKE and UCAKE proposed in this work, which unifies the traditional BR and (post-ID) frameworks, enjoys composability, and ensures very strong security guarantee. Along the way, we make a systematically comparative study with related protocols and mechanisms including Zheng's signcryption, one-pass HMQV, QUIC, TLS1.3 and OPTLS, most of which are widely standardized or in use.
ePrint Report Can you sign a quantum state Gorjan Alagic, Tommaso Gagliardoni, Christian Majenz
Cryptography with quantum states exhibits a number of surprising and counterintuitive features. In a 2002 work, Barnum et al. argued informally that these strange features should imply that digital signatures for quantum states are impossible (Barnum et al., FOCS 2002). In this work, we perform the first rigorous study of the problem of signing quantum states. We first show that the intuition of Barnum et al. was correct, by proving an impossibility result which rules out even very weak forms of signing quantum states. Essentially, we show that any non-trivial combination of correctness and security requirements results in negligible security. This rules out all quantum signature schemes except those which simply measure the state and then sign the outcome using a classical scheme. In other words, only classical signature schemes exist. We then show a positive result: it is possible to sign quantum states, provided that they are also encrypted with the public key of the intended recipient. Following classical nomenclature, we call this notion quantum signcryption. Classically, signcryption is only interesting if it provides superior efficiency to simultaneous encryption and signing. Our results imply that, quantumly, it is far more interesting: by the laws of quantum mechanics, it is the only signing method available. We develop security definitions for quantum signcryption, ranging from a simple one-time two-user setting, to a chosen-ciphertext-secure many-time multi-user setting. We also give secure constructions based on post-quantum public-key primitives. Along the way, we show that a natural hybrid method of combining classical and quantum schemes can be used to "upgrade" a secure classical scheme to the fully-quantum setting, in a wide range of cryptographic settings including signcryption, authenticated encryption, and chosen-ciphertext security.
This text can be thought of an “external appendix” to the paper Sliding right into disaster: Left-to-right sliding windows leak by Daniel J. Bernstein, Joachim Breitner, Daniel Genkin, Leon Groot Bruinderink, Nadia Heninger, Tanja Lange, Christine van Vredendaal and Yuval Yarom [1, 2], and goes into the details of an alternative way to find the knowable bits of the secret exponent, which is complete and can (in rare corner cases) find more bits than the rewrite rules in Section 3.1 of [1], an algorithm to calculate the collision entropy H that is used in Theorem 3 of [1], and a proof of Theorem 3.
ePrint Report On the Concrete Security of Goldreich's Pseudorandom Generator Geoffroy Couteau, Aurélien Dupin, Pierrick Méaux, Mélissa Rossi, Yann Rotella
Local pseudorandom generators allow to expand a short random string into a long pseudo-random string, such that each output bit depends on a constant number d of input bits. Due to its extreme efficiency features, this intriguing primitive enjoys a wide variety of applications in cryptography and complexity. In the polynomial regime, where the seed is of size n and the output of size n^s for s > 1, the only known solution, commonly known as Goldreich's PRG, proceeds by applying a simple d-ary predicate to public random size-d subsets of the bits of the seed. While the security of Goldreich's PRG has been thoroughly investigated, with a variety of results deriving provable security guarantees against class of attacks in some parameter regimes and necessary criteria to be satisfied by the underlying predicate, little is known about its concrete security and efficiency. Motivated by its numerous theoretical applications and the hope of getting practical instantiations for some of them, we initiate a study of the concrete security of Goldreich's PRG, and evaluate its resistance to cryptanalytic attacks. Along the way, we develop a new guess-and-determine-style attack, and identify new criteria which refine existing criteria and capture the security guarantees of candidate local PRGs in a more fine-grained way.

  older items