International Association for Cryptologic Research

# IACR News Central

You can also access the full news archive.

Further sources to find out about changes are CryptoDB, ePrint RSS, ePrint Web, Event calender (iCal).

2015-05-19
21:17 [Pub][ePrint]

Time-lock encryption is a method to encrypt a message such that it can only be decrypted after a certain deadline has passed. A computationally powerful adversary should not be able to learn the message before the deadline. However, 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 show how to realize this strong notion of secure encryption by making the additional, very realistic assumption that intermediate results of an iterative, public, large-scale computation --- like the computations performed by users of the popular cryptocurrency Bitcoin --- are publicly available. We use these computations as a \"computational reference clock\", which mimics a physical clock in a computational setting, and show how the computations performed by the reference clock can be \"reused\" to build secure time-lock encryption. A nice feature of this approach is that it can be based on a public computation which is performed \"anyway\" and independent of the time-lock encryption scheme.

We provide the first formal definitions of computational reference clocks and time-lock encryption, and give a proof-of-concept construction which combines a computational reference clock with witness encryption (Garg et al., STOC 2013). We also explain how to construct a computational reference clock based on Bitcoins.

09:17 [Pub][ePrint]

We describe a new methodology that enables the di-

rect execution of multi-threaded applications inside of

Shadow, an existing parallel discrete-event network sim-

ulation framework. Our methodology utilizes function

interposition and an application-layer thread library to

emulate the ordinary thread interface to the application.

Using this methodology, we implement a new Shadow

plug-in that directly executes the Bitcoin reference client

software. We describe optimizations that enable scalable

execution of thousands of Bitcoin nodes on a single ma-

chine, and discuss how to model the Bitcoin network for

experimental purposes. Finally, we present novel denial-

of-service attacks against the Bitcoin software, which

exploit low-level implementation artifacts in the Bitcoin

reference client. We demonstrate these attacks using our

methodology, tools, and models.

09:17 [Pub][ePrint]

In CRYPTO 2014 Bitansky et al. introduced a natural strengthening of indistinguishability obfuscation (iO) called strong iO (siO) and showed candidate constructions of such primitive from reasonable assumptions. In this paper, assuming quasi-siO, a natural weakening of siO, for a class of circuits C we construct a public-key functional encryption (FE) scheme with function privacy (FPFE) for the same class C. In the public-key setting known constructions of FPFE were limited to very restricted classes of functionalities like inner-product [Agrawal et al. - PKC 2015] whereas ours can be instantiated for general functionalities.

Then, inspired by the Naor\'s transformation from IBE to signature schemes, we construct from FPFE a natural generalization of a signature scheme endowed with functional properties, that we call functional anonymous signature (FAS) scheme. In a FAS (that we show to be equivalent to quasi-siO and FPFE), Alice can sign a circuit C chosen from some distribution D to get a signature $\\sigma$ and can publish a verification key that allows anybody holding a message m to verify that (1) $\\sigma$ is a valid signature of Alice for some (possibly unknown to him) circuit C and (2) C(m) = 1. Beyond unforgeability the security of FAS guarantees that the signature hide as much information as possible about C except what can be inferred from knowledge of D.

As other application of FPFE, we show that it can be used to construct in a black-box way (without using obfuscation directly) FE for randomized functionalities (RFE). Previous constructions of (public-key) RFE relied on iO [Goyal et al. - TCC 2015]. Combining properties of RFE and FAS, we obtain what we call signed probabilistic programs, in which Bob can verify that a (possibly hidden to him) probabilistic program P was signed by Alice and run P on any input but can not maliciously choose its random coins. Furthermore, our constructions of FPFE and RFE naturally generalize to the multi-inputs setting. Finally, we present a general picture of the relations among all these related primitives. One of the key points that such implications draw is that Attribute-based Encryption with function privacy implies FE, a notable fact that sheds light on the importance and power of function privacy for FE.

09:17 [Pub][ePrint]

Physical Unclonable Functions (PUFs), as novel lightweight

hardware security primitives, provide a higher level security with lower power and area overhead in comparison with traditional cryptographic solutions. However, it has been demonstrated that PUFs are vulnerable to model building attacks, especially those using linear additive functions such as Arbiter PUF (APUF) and k-sum PUF as building units. Nevertheless, both APUFs and k-sum PUFs are highly desirable security primitives, especially for authentication, because they are capable of producing a huge number of challenge response pairs (CRPs) and can be easily integrated into silicon. In this paper, we actually rely on the

demonstrated vulnerability of PUFs to model building attacks as well as the relative ease with which this can be achieved to develop a new parameter-based authentication protocol based on obfuscating challenges sent to PUFs and their subsequent recovery. We show, using statistical analysis and model building attacks using published approaches, that constructing a model using machine learning techniques are infeasible when our proposed method is employed. Finally, we also demonstrate that our challenge obfuscation and recovery method can be successfully

used for secure key exchange between two parties.

09:17 [Pub][ePrint]

We present a unified view of the two-party and multi-party computation protocols based on oblivious transfer first outlined in Nielsen et al and Larraia et al. We present a number of modifications and improvements to these earlier presentations, as well as full proofs of the entire protocol. Improvements include a unified pre-processing and online MAC methodology, mechanisms to pass between different MAC methodologies, fixing a minor bug in the protocol of Larraia et al in relation to a selective failure attack.

2015-05-18
23:14 [Conf][Crypto]

The list of papers accepted to CRYPTO 2015 is now up:

https://www.iacr.org/conferences/crypto2015/acceptedpapers.html

09:17 [Pub][ePrint]

We present the oblivious machine, a concrete notion for multiparty

random access machine (RAM) computation and a toolchain to allow the

efficient execution of general programs written in a subset of C that

allows RAM-model computation over integers. The machine only leaks the

list of possible instructions and the running time. Our work is based

on the oblivious array for secret-sharing-based multiparty computation

by Keller and Scholl (Asiacrypt 14). This means that we only incur a

polylogarithmic overhead over the execution on a normal CPU.

We implemented our construction using the clang compiler from the LLVM

project and the SPDZ protocol by Damgård et al. (Crypto 12). The

latter provides active security against a dishonest majority and works

in the preprocessing model. The online phase clock rate of the

resulting machine is 41 Hz for a memory size of 1024 64-bit integers

and 2.2 Hz for a memory of 2^20 integers. Both timings have been taken

for two parties in a local network.

To further showcase our toolchain, we implemented and benchmarked

private regular expression matching. Matching a string of length 1024

against a regular expression with 69270 transitions as a finite state

machine takes seven hours online time, of which more than six hours

09:17 [Pub][ePrint]

We present a new fully homomorphic encryption (FHE) scheme that is efficient for practical applications. The main feature of our scheme is that noise reduction considered essential in current FHE schemes, such as boot strapping and modulus switching, is not needed in our scheme, because it allows arbitrarily large noises in its ciphertexts.

A ciphertext in our scheme is a vector with its dimension specified as a security parameter of the encryption key. The dimension of ciphertexts does not change with homomorphic operations and all ciphertext elements are in a finite domain, so our scheme is compact. In addition, our scheme can directly encrypt big integers, rather than only bit messages.

We proved the hardness of recovering encryption keys from any number of ciphertexts with chosen plaintexts and then the semantic security of our scheme. The hardness of recovering keys from ciphertexts is based on the approximate greatest common divisors problem.

We implemented a prototype of our scheme and evaluated its concrete performance extensively from the aspects of encryption, decryption, homomorphic operations,

and bitwise operators over ciphertexts.

The efficiency of our scheme is confirmed by the evaluation result.

2015-05-17
09:17 [Pub][ePrint]

Besides attracting a billion dollar economy, Bitcoin revolutionized the field of digital currencies and influenced many adjacent areas. This also induced significant scientific interest. In this survey, we unroll and structure the manyfold results and research directions. We start by introducing the Bitcoin protocol and its building blocks. From there we continue to explore the design space by discussing existing contributions and results. In the process, we deduce the fundamental structures and insights at the core of the Bitcoin protocol and its applications. As we show and discuss, many key ideas are likewise applicable in various other fields, so that their impact reaches far beyond Bitcoin itself.

09:17 [Pub][ePrint]

Advanced modern processors support Single Instruction Multiple Data (SIMD) instructions (e.g. Intel-AVX, ARM-NEON) and a massive body of

research on vector-parallel implementations of modular arithmetic, which are crucial components for modern public-key cryptography ranging from RSA, ElGamal, DSA and ECC, have been conducted.

In this paper, we introduce a novel Double Operand Scanning (DOS) method to speed-up multi-precision squaring with non-redundant representations on SIMD architecture.

The DOS technique partly doubles the operands and computes the squaring operation without Read-After-Write (RAW) dependencies between source and destination variables.

Furthermore, we presented Karatsuba Cascade Operand Scanning (KCOS) multiplication and Karatsuba Double Operand Scanning (KDOS) squaring by adopting additive and subtractive Karatsuba\'s methods, respectively.

The proposed multiplication and squaring methods are compatible with separated Montgomery algorithms and these are highly efficient for RSA crypto system.

Finally, our proposed multiplication/squaring, separated Montgomery multiplication/squaring and RSA encryption outperform the best-known results by 22/41\\%, 25/33\\% and 30\\% on the Cortex-A15 platform.

09:17 [Pub][ePrint]

Fully homomorphic encryption (FHE) has important applications in cloud computing. However, almost all fully homomorphic encryption schemes share two common flaws that they all use large-scale secret keys and some operations inefficient. In this paper, the \"special b\" variant of the Learning With Errors problem (bLWE) is presented, and helps us construct the first circularly secure key switching process which can replace the key switching process and similar re-linearization process used by the existing FHE schemes. Then, we present an efficient FHE. Compared with Brakerski\'s scheme, our scheme reduces L secret keys to one and is more efficient. Finally, we prove the chosen-plaintext attack (CPA) security of the fully homomorphic scheme and the circular security of key switching process in standard model under the learning with errors problem (LWE) assumption.