### How to build time-lock encryption

IACR Eprint - Thu, 06/14/2018 - 06:49
Time-lock encryption is a method to encrypt a message such that it can only be decrypted after a certain deadline has passed. We propose a novel time-lock encryption scheme, whose main advantage over prior constructions is that even receivers with relatively weak computational resources should immediately be able to decrypt after the deadline, without any interaction with the sender, other receivers, or a trusted third party. We build our time-lock encryption on top of the new concept of computational reference clocks and an extractable witness encryption scheme. We explain how to construct a computational reference clock based on Bitcoin. We show how to achieve constant level of multilinearity for witness encryption by using SNARKs. We propose a new construction of a witness encryption scheme which is of independent interest: our scheme, based on Subset-Sum, achieves extractable security without relying on obfuscation. The scheme employs multilinear maps of arbitrary order and is independent of the implementations of multilinear maps.

### Reusing Tamper-Proof Hardware in UC-Secure Protocols

IACR Eprint - Thu, 06/14/2018 - 05:36
Universally composable protocols provide security even in highly complex environments like the Internet. Without setup assumptions, however, UC-secure realizations of cryptographic tasks are impossible. Tamper-proof hardware tokens, e.g. smart cards and USB tokens, can be used for this purpose. Apart from the fact that they are widely available, they are also cheap to manufacture and well understood. Currently considered protocols, however, suffer from two major drawbacks that impede their practical realization: - The functionality of the tokens is protocol-specific, i.e. each protocol requires a token functionality tailored to its need. - Different protocols cannot reuse the same token even if they require the same functionality from the token, because this would render the protocols insecure in current models of tamper-proof hardware. In this paper we address these problems. First and foremost, we propose formalizations of tamper-proof hardware as an untrusted and global setup assumption. Modeling the token as a global setup naturally allows to reuse the tokens for arbitrary protocols. Concerning a versatile token functionality we choose a simple signature functionality, i.e. the tokens can be instantiated with currently available signature cards. Based on this we present solutions for a large class of cryptographic tasks.

### Function-Hiding Inner Product Encryption is Practical

IACR Eprint - Wed, 06/13/2018 - 17:47
In a functional encryption scheme, secret keys are associated with functions and ciphertexts are associated with messages. Given a secret key for a function f, and a ciphertext for a message x, a decryptor learns f(x) and nothing else about x. Inner product encryption is a special case of functional encryption where both secret keys and ciphertext are associated with vectors. The combination of a secret key for a vector x and a ciphertext for a vector y reveal <x, y> and nothing more about y. An inner product encryption scheme is function- hiding if the keys and ciphertexts reveal no additional information about both x and y beyond their inner product. In the last few years, there has been a flurry of works on the construction of function-hiding inner product encryption, starting with the work of Bishop, Jain, and Kowalczyk (Asiacrypt 2015) to the more recent work of Tomida, Abe, and Okamoto (ISC 2016). In this work, we focus on the practical applications of this primitive. First, we show that the parameter sizes and the run-time complexity of the state-of-the-art construction can be further reduced by another factor of 2, though we compromise by proving security in the generic group model. We then show that function privacy enables a number of applications in biometric authentication, nearest-neighbor search on encrypted data, and single-key two-input functional encryption for functions over small message spaces. Finally, we evaluate the practicality of our encryption scheme by implementing our function-hiding inner product encryption scheme. Using our construction, encryption and decryption operations for vectors of length 50 complete in a tenth of a second in a standard desktop environment.

### Exploring Potential 6LoWPAN Traffic Side Channels

IACR Eprint - Wed, 06/13/2018 - 08:18
The Internet of Things (IoT) has become a reality: small connected devices feature in everyday objects including childrens' toys, TVs, fridges, heating control units, etc. Supply chains feature sensors throughout, and significant investments go into researching next-generation healthcare, where sensors monitor wellbeing. A future in which sensors and other (small) devices interact to create sophisticated applications seems just around the corner. All of these applications have a fundamental need for security and privacy and thus cryptography is deployed as part of an attempt to secure them. In this paper we explore a particular type of flaw, namely side channel information, on the protocol level that can exist despite the use of cryptography. Our research investigates the potential for utilising packet length and timing information (both are easily obtained) to extract interesting information from a system. We find that using these side channels we can distinguish between devices, different programs running on the same device including which sensor is accessed. We also find it is possible to distinguish between different types of ICMP messages despite the use of encryption. Based on our findings, we provide a set of recommendations to efficiently mitigate these side channels in the IoT context.

### Cryptanalysis of SFN Block Cipher

IACR Eprint - Tue, 06/12/2018 - 15:11
SFN is a lightweight block cipher designed to be compact in hardware environment and also efficient in software platforms. Compared to the conventional block ciphers that are either Feistel or Substitution-Permutation (SP) network based, SFN has a different encryption method which uses both SP network structure and Feistel network structure to encrypt. SFN supports key lengths of 96 bits and its block length is 64 bits. In this paper, we propose an attack on full SFN by using the related key distinguisher. With this attack, we are able to recover the keys with a time complexity of $2^{60.58}$ encryptions. The data and memory complexity of the attacks are negligible. In addition, in the single key mode, we present a meet in the middle attack against the full rounds block cipher for which the time complexity is $2^{80}$ SFN calculations and the memory complexity is $2^{87}$ bytes. The date complexity of this attack is only a single known plaintext and its corresponding ciphertext.

### Ramanujan graphs in cryptography

IACR Eprint - Tue, 06/12/2018 - 14:50
In this paper we study the security of a proposal for Post-Quantum Cryptography from both a number theoretic and cryptographic perspective. Charles-Goren-Lauter in 2006 proposed two hash functions based on the hardness of finding paths in Ramanujan graphs. One is based on Lubotzky--Phillips--Sarnak (LPS) graphs and the other one is based on Supersingular Isogeny Graphs. A 2008 paper by Petit-Lauter-Quisquater breaks the hash function based on LPS graphs. On the Supersingular Isogeny Graphs proposal, recent work has continued to build cryptographic applications on the hardness of finding isogenies between supersingular elliptic curves. A 2011 paper by De Feo-Jao-Pl\^ut proposed a cryptographic system based on Supersingular Isogeny Diffie--Hellman as well as a set of five hard problems. In this paper we show that the security of the SIDH proposal relies on the hardness of the SIG path-finding problem introduced in [CGL06]. In addition, similarities between the number theoretic ingredients in the LPS and Pizer constructions suggest that the hardness of the path-finding problem in the two graphs may be linked. By viewing both graphs from a number theoretic perspective, we identify the similarities and differences between the Pizer and LPS graphs.

### XS-circuits in Block Ciphers

IACR Eprint - Tue, 06/12/2018 - 14:50
XS-circuits describe block ciphers that utilize 2 operations: X) bitwise modulo 2 addition of binary words and S) substitution of words using key-dependent S-boxes with possibly complicated internal structure. We propose a model of XS-circuits which, despite the simplicity, covers a rather wide range of block ciphers. In our model, several instances of a simple round circuit, which contains only one S~operation, are linked together and form a compound circuit called a cascade. S operations of a cascade are interpreted as independent round oracles. We deal with diffusion characteristics of cascades. These characteristics are related to the cryptographic strength of corresponding block ciphers. We obtain results on invertibility, transitivity and 2-transitivity of mappings induced by round circuits and their cascades. We provide estimates on the first and second activation times where the i-th activation time is the minimum number of rounds which guarantees that at least i round oracles get different queries while processing two different cascade's inputs. The activation times are related to differential cryptanalysis. We introduce the similarity and duality relations between round circuits. Cascades of related circuits have the same or dual diffusion characteristics. We find canonical representatives of classes of similar circuits and show that the duality between circuits is related to duality between differential and linear attacks against corresponding block ciphers. We discuss families of circuits with growing number of inputs. Such families can be used to build wide-block ciphers.

### 4-bit crypto S-boxes: Generation with irreducible polynomials over Galois field GF(24) and cryptanalysis.

IACR Eprint - Tue, 06/12/2018 - 14:49
4-bit crypto S-boxes play a significant role in encryption and decryption of many cipher algorithms from last 4 decades. Generation and cryptanalysis of generated 4-bit crypto S-boxes is one of the major concerns of modern cryptography till now. In this paper 48, 4-bit crypto S-boxes are generated with addition of all possible additive constants to the each element of crypto S-box of corresponding multiplicative inverses of all elemental polynomials (EPs) under the concerned irreducible polynomials (IPs) over Galois field GF(2^4). Cryptanalysis of 48 generated 4-bit crypto S-boxes is done with all relevant cryptanalysis algorithms of 4-bit crypto S-boxes. The result shows the better security of generated 4-bit crypto S-boxes.

### The Twin Conjugacy Search Problem and Applications

IACR Eprint - Tue, 06/12/2018 - 14:48
We propose a new computational problem over the noncommutative group, called the twin conjugacy search problem. This problem is related to the conjugacy search problem and can be used for almost all of the same cryptographic constructions that are based on the conjugacy search problem. However, our new problem is at least hard as the conjugacy search problem. Moreover, the twin conjugacy search problem have many applications. One of the most important applications, we propose a trapdoor test which can replace the function of the decision oracle. We also show other applications of the problem, including: a non-interactive key exchange protocol and a key exchange protocol, a new encryption scheme which is secure against chosen ciphertext attack, with a very simple and tight security proof and short ciphertexts, under a weak assumption, in the random oracle model.

### Implementation and Performance Evaluation of RNS Variants of the BFV Homomorphic Encryption Scheme

IACR Eprint - Tue, 06/12/2018 - 14:47
Homomorphic encryption provides the ability to compute on encrypted data without ever decrypting them. Potential applications include aggregating sensitive encrypted data on a cloud environment and computing on the data in the cloud without compromising data privacy. There have been several recent advances resulting in new homomorphic encryption schemes and optimized variants of existing schemes. Two efficient Residue-Number-System variants of the Brakerski-Fan-Vercauteren homomorphic encryption scheme were recently proposed: the Bajard-Eynard-Hasan-Zucca (BEHZ) variant based on integer arithmetic with auxiliary moduli, and the Halevi-Polyakov-Shoup (HPS) variant based on a combination of integer and floating-point arithmetic techniques. We implement and evaluate the performance of both variants in CPU (both single- and multi-threaded settings) and GPU. The most interesting (and also unexpected) result of our performance evaluation is that the HPS variant in practice scales significantly better (typically by 15%-30%) with increase in multiplicative depth of the computation circuit than BEHZ. This implies that the runtime performance and supported circuit depth for HPS will always be better for most practical applications. The comparison of the homomorphic multiplication runtimes for CPU and GPU demonstrates that our best GPU performance results are 3x-33x faster than our best multi-threaded results for a modern server CPU environment. For the multiplicative depth of 98, our fastest GPU implementation performs decryption in 0.5 ms and homomorphic multiplication in 51 ms for 128-bit security settings, which is already practical for cloud environments supporting GPU computations. Our best runtime results are at least two orders of magnitude faster than all previously reported results for any variant of the Brakerski-Fan-Vercauteren scheme.

### BISEN: Efficient Boolean Searchable Symmetric Encryption with Verifiability and Minimal Leakage

IACR Eprint - Tue, 06/12/2018 - 14:46
The prevalence and availability of cloud infrastructures has made them the de facto solution for storing and archiving data, both for organizations and individual users. Nonetheless, the cloud's wide spread adoption is still hindered by data privacy and security concerns, particularly in applications with large data collections where efficient search and retrieval services are also major requirements. This leads to increased tension between security, efficiency, and search expressiveness, which current state of art solutions try to balance through complex cryptographic protocols that sacrifice efficiency and expressiveness for near optimal security. In this paper we tackle this tension by proposing BISEN, a new provably-secure boolean searchable symmetric encryption scheme that improves these three complementary dimensions by exploring the design space of isolation guarantees offered by novel commodity hardware such as Intel SGX, abstracted as Isolated Execution Environments (IEEs). BISEN is the first scheme to enable highly expressive and arbitrarily complex boolean queries, with minimal leakage of information regarding performed queries and accessed data. Furthermore, by exploiting trusted hardware and the IEE abstraction, BISEN reduces communication costs between the client and the cloud, boosting query execution performance. Experimental validation and comparison with the state of art shows that BISEN provides better performance with enriched search semantics and security

### Constructing Witness PRF and Offline Witness Encryption Without Multilinear Maps

IACR Eprint - Tue, 06/12/2018 - 14:46
Witness pseudorandom functions (witness PRFs), introduced by Zhandry [Zha16], was defined for an NP language L and generate a pseudorandom value for any instance x. The same pseudorandom value can be obtained efficiently using a valid witness w for x belongs to L. Zhandry built a subset-sum encoding scheme from multilinear maps and then converted a relation circuit corresponding to an NP language L to a subset-sum instance to achieve a witness PRF for L. The main goal in developing witness PRF in [Zha16] is to avoid obfuscation from various constructions of cryptographic primitives. Reliance on cryptographic tools built from multilinear maps may be perilous as existing multilinear maps are still heavy tools to use and suffering from many non-trivial attacks. In this work, we give constructions of the following cryptographic primitives without using multilinear maps and instantiating obfuscation from randomized encoding: – We construct witness PRFs using a puncturable pseudorandom function and sub-exponentially secure randomized encoding scheme in common reference string (CRS) model. A sub-exponentially secure randomized encoding scheme in CRS model can be achieved from a sub-exponentially secure public key functional encryption scheme and learning with error assumptions with sub-exponential hardness. – We turn our witness PRF into a multi-relation witness PRF where one can use the scheme with a class of relations related to an NP language. – Furthermore, we construct an offline witness encryption scheme using our proposed witness PRF. The offline witness encryption scheme of Abusalah et al. [AFP16] was built from a plain public-key encryption, a statistical simulation-sound non-interactive zero knowledge (SSS-NIZK) proof system and obfuscation. In their scheme, a(n) SSS-NIZK proof is needed for the encryption whose efficiency depends on the underlying public key encryption. We replace SSS-NIZK by our witness PRF and construct an offline witness encryption scheme. More precisely, our scheme is based on a public-key encryption, a witness PRF and employs a sub-exponentially secure randomized encoding scheme in CRS model instantiating obfuscation. Our offline witness encryption can be turned into an offline functional witness encryption scheme where decryption releases a function of a message and witness as output.

### Lower Bounds on Lattice Enumeration with Extreme Pruning

IACR Eprint - Tue, 06/12/2018 - 14:45
At Eurocrypt '10, Gama, Nguyen and Regev introduced lattice enumeration with extreme pruning: this algorithm is implemented in state-of-the-art lattice reduction software and used in challenge records. They showed that extreme pruning provided an exponential speed-up over full enumeration. However, no limit on its efficiency was known, which was problematic for long-term security estimates of lattice-based cryptosystems. We prove the first lower bounds on lattice enumeration with extreme pruning: if the success probability is lower bounded, we can lower bound the global running time taken by extreme pruning. Our results are based on geometric properties of cylinder intersections and some form of isoperimetry. We discuss their impact on lattice security estimates.

### Polynomial Functional Encryption Scheme with Linear Ciphertext Size

IACR Eprint - Tue, 06/12/2018 - 14:45
In this paper, we suggest a new selective secure functional encryption scheme for degree $d$ polynomial. The number of ciphertexts for a message with length $\ell$ in our scheme is $O(\ell)$ regardless of $d$, while it is at least $\ell^{d/2}$ in the previous works. Our main idea is to generically combine two abstract encryption schemes that satisfies some special properties. We also gives an instantiation of our scheme by combining ElGamal scheme and Ring-LWE based homomorphic encryption scheme, whose ciphertext length is exactly $2\ell+1,$ for any degree $d.$

### Bounded Fully Homomorphic Encryption from Monoid Algebras

IACR Eprint - Tue, 06/12/2018 - 14:44
We present a new method that produces bounded FHE schemes (see Definition 3), starting with encryption schemes that support one algebraic operation. We use this technique to construct examples of encryption schemes that, theoretically can handle any algebraic function on encrypted data.

### Ring Homomorphic Encryption Schemes

IACR Eprint - Tue, 06/12/2018 - 14:44
We analyze the structure of commutative ring homomorphic encryption schemes and show that they are not quantum IND-CCA secure.

### UWB with Pulse Reordering: Securing Ranging against Relay and Physical-Layer Attacks

IACR Eprint - Tue, 06/12/2018 - 11:32
Physical-layer attacks allow attackers to manipulate (spoof) ranging and positioning. These attacks had real-world impact and allowed car thefts, executions of unauthorized payments and manipulation of navigation. UWB impulse radio (UWB-IR) has emerged as a prominent technique for precise ranging that allows high operating distances despite power constraints by transmitting multi-pulse symbols. Unfortunately, longer symbols make UWB-IR vulnerable to physical-layer attacks. Currently, none of the existing systems is precise, performant and secure at the same time. We present UWB with pulse reordering (UWB-PR), the first modulation scheme that secures distance measurement between two mutually trusted devices against all physical-layer attacks without sacrificing performance and irrespective of the environment or attacker. We analyze the security of UWB-PR under the attacker that fully controls the communication channel and show that UWB-PR resists even such a strong attacker. We evaluate UWB-PR within a UWB system built on IEEE 802.15.4f and show that it achieves distances of up to 93m with 10cm precision (LoS).

### Asynchronous provably-secure hidden services

IACR Eprint - Tue, 06/12/2018 - 10:15
The client-server architecture is one of the most widely used in the Internet for its simplicity and flexibility. In practice the server is assigned a public address so that its services can be consumed. This makes theserver vulnerable to a number of attacks such as Distributed Denial of Service (DDoS), censorship from authoritarian governments or exploitationof software vulnerabilities. In this work we propose an asynchronous protocol for allowing a client to issue requests to a server without revealing any information about the location of the server. In addition, our solution reveals limited information about the network topology, leaking only the distance from the client to the corrupted participants. We also provide a simulation-based security definition capturing the requirement described above. Our protocol is secure in the semi-honest model against any number of colluding participants, and has linear communication complexity. Finally, we extend our solution to handle active adversaries. We show that malicious participants can only trigger a premature termination of the protocol, in which case they are identified. For this solution the communication complexity becomes quadratic. To the best of our knowledge our solution is the first asynchronous protocol that provides strong security guarantees.

### Loop-abort faults on supersingular isogeny cryptosystems

IACR Eprint - Mon, 06/11/2018 - 16:19
Cryptographic schemes based on supersingular isogenies have become an active area of research in the field of post-quantum cryptography. We investigate the resistance of these cryptosystems to fault injection attacks. It appears that the iterative structure of the secret isogeny computation renders these schemes vulnerable to loop-abort attacks. Loop-abort faults allow to perform a full key recovery, bypassing all the previously introduced validation methods. Therefore implementing additional countermeasures seems unavoidable for applications where physical attacks are relevant.

### Computing generator in cyclotomic integer rings, A subfield algorithm for the Principal Ideal Problem in L(1/2) and application to cryptanalysis of a FHE scheme

IACR Eprint - Mon, 06/11/2018 - 16:18
The Principal Ideal Problem (resp. Short Principal Ideal Problem), shorten as PIP (resp. SPIP), consists in finding a generator (resp. short generator) of a principal ideal in the ring of integers of a number field. Several lattice-based cryptosystems rely on the presumed hardness of these two problems. In practice, most of them do not use an arbitrary number field but a power-of-two cyclotomic field. The Smart and Vercauteren fully homomorphic encryption scheme and the multilinear map of Garg, Gentry, and Halevi epitomize this common restriction. Recently, Cramer, Ducas, Peikert, and Regev showed that solving the SPIP in such cyclotomic rings boiled down to solving the PIP. In this paper, we present a heuristic algorithm that solves the PIP in prime-power cyclotomic fields in subexponential time L(1/2) in the discriminant of the number field. This is achieved by descending to its totally real subfield. The implementation of our algorithm allows to recover in practice the secret key of the Smart and Vercauteren scheme, for the smallest proposed parameters (in dimension 256).