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

20
June
2017

ePrint Report
A Secure User Authentication and Key Agreement Scheme for HWSN Tailored for the Internet of Things Environment
Hamidreza Yazdanpanah, Mohammadreza Hasani Ahangar, Mahdi Azizi, Arash Ghafouri

Internet of things (IOT) is the term used to describe a world in which the things interact with other things through internet connection or communication means, share the information together and or people and deliver a new class of capabilities, application and services; the world in which all things and heterogeneous devices are addressable and controllable. Wireless Sensor Networks (WSN) play an important role in such an environment, since they include a wide application field. Researchers are already working on how to integrate WSN better into the IoT environment. One aspect of it is the security aspect of the integration. In 2014, Turkanovi´c proposed a lightweight user authentication and key agreement protocol for heterogeneous WSN(HWSN) based on the internet of things concept. In this scheme, remote user can access a single desired sensor node from the WSN without the necessity of firstly connecting with a gateway node (GWN). Moreover, this scheme is lightweight because it based on a simple symmetric cryptography and it uses simple hash and XOR computations. Turkanovi´c et al.'s scheme had some security shortages and it was susceptible to some security attacks. Recently Sabzinejad Farash et al. proposed an efficient user authentication and key agreement scheme for HWSN tailored for the Internet of Things environment based on Turkanovi´c et al.'s scheme. Although their scheme is efficient, we found out that this scheme is vulnerable to some cryptographic attacks. In this paper, we demonstrate some security weaknesses of the Sabzinejad Farash et al.’s scheme and then we propose an improved and secure mutual authentication and key agreement scheme.

14
June
2017

ePrint Report
Ouroboros Praos: An adaptively-secure, semi-synchronous proof-of-stake protocol
Bernardo David, Peter Ga{\v{z}}i, Aggelos Kiayias, Alexander Russell

We present “Ouroboros Praos”, a new proof-of-stake blockchain protocol that provides, for the first time, a robust distributed ledger that is provably secure in the semi-synchronous adversarial setting, i.e., assuming a delay \Delta in message delivery which is unknown to protocol participants, and fully adaptively secure, i.e., the adversary can choose to corrupt any participant of an ever evolving population of stakeholders at any moment as long the stakeholder distribution maintains an honest majority of stake at any given time. To achieve that, our protocol puts to use forward secure digital signatures and a new type of verifiable random functions that maintains unpredictability under malicious key generation, a property we introduce and instantiate in the random oracle model. Our security proof entails a combinatorial analysis of a class of forkable strings tailored to semi-synchronous blockchains that may be of independent interest in the context of security analysis of blockchain protocols.

ePrint Report
MXPUF: Secure PUF Design against State-of-the-art Modeling Attacks
Phuong Ha Nguyen, Durga Prasad Sahoo, Chenglu Jin, Kaleel Mahmood, Marten van Dijk

Silicon Physical Unclonable Functions (PUFs) have been proposed as an emerging hardware security primitive in various security applications such as device identification, authentication, and cryptographic key generation. Current so-called `strong' PUFs, which allow a large challenge response space, are compositions of Arbiter PUFs (APUFs), e.g. the $x$-XOR APUF. Wide-scale deployment of state-of-the-art compositions of APUFs, however, has stagnated due to various mathematical and physical attacks leading to software models that break the unclonability property of PUFs. The current state-of-the-art attack by Becker, CHES 2015, shows that the XOR APUF can be broken by modeling its APUF components separately thanks to CMA-ES, a machine learning algorithm, based on reliability information of measured XOR APUF responses. Thus, it is an important problem to design a strong PUF which can resist not only traditional modeling attacks but also Becker's attack. In this paper, we propose a new strong PUF design called $(x,y)$-MXPUF, which consists of two layers; the upper layer is an $n$-bit $x$-XOR APUF, and the lower layer is an $(n+1)$-bit $y$-XOR APUF. The response of $x$-XOR APUF for an $n$-bit challenge $\mathbf{c}$ in the upper layer is inserted at the middle of $\mathbf{c}$ to construct a new $(n+1)$-bit challenge for the $y$-XOR APUF in the lower layer giving the final response bit of the $(x,y)$-MXPUF. The reliability of $(x,y)$-MXPUF can be theoretically and experimentally shown to be twice the reliability of $(x+y)$-XOR PUF. In the context of traditional modeling attacks, when we keep the same hardware size, the security of $(x,y)$-MXPUF is only slightly weaker than that of $(x+y)$-XOR PUF. Our main contribution proves that the $(x,y)$-MXPUF is secure against Becker's attack.

There is a recent trend in cryptography to construct protocols based on the hardness of computing isogenies between supersingular elliptic curves. Two prominent examples are Jao-De Feo's key exchange protocol and the resulting encryption scheme by De Feo-Jao-Plût. One particularity of the isogeny problems underlying these protocols is that some additional information is given in input, namely the image of some torsion points with order coprime to the isogeny. This additional information was used in several active attacks against the protocols but the current best passive attacks on the protocols make no use of it at all.

In this paper, we provide new algorithms that exploit the additional information provided in isogeny protocols to speed up the resolution of the underlying problems. Our techniques lead to a heuristic polynomial-time key recovery on a non-standard variant of De Feo-Jao-Plût's protocols in a plausible attack model. This shows that at least some isogeny problems are easier to solve when additional information is leaked.

In this paper, we provide new algorithms that exploit the additional information provided in isogeny protocols to speed up the resolution of the underlying problems. Our techniques lead to a heuristic polynomial-time key recovery on a non-standard variant of De Feo-Jao-Plût's protocols in a plausible attack model. This shows that at least some isogeny problems are easier to solve when additional information is leaked.

ePrint Report
Assessing the No-Knowledge Property of SpiderOak ONE
Anders P. K. Dalskov, Claudio Orlandi

This paper presents the findings of an independent security review of SpiderOak ONE, a popular encrypted cloud storage application. In this application, the storage provider claims that, since all the users' data is password encrypted and the password never leaves the client, even the storage provider cannot learn any information about the users' data.

After providing a formal description of the key design choices in the reviewed application (e.g., how user's accounts are registered, how new devices are registered, how and what cryptographic keys are used, how file encryption is handled, etc.), we present a number of vulnerabilities that can be exploited by a malicious storage server to break, to different degrees, the confidentiality of the users' password and therefore the users' data.

Our findings have been communicated to SpiderOak in April 2017. The vendor promptly replied to our concerns by releasing an updated version of the application (v. 6.3.0, June 2017) which resolves most of the issues described in this paper.

After providing a formal description of the key design choices in the reviewed application (e.g., how user's accounts are registered, how new devices are registered, how and what cryptographic keys are used, how file encryption is handled, etc.), we present a number of vulnerabilities that can be exploited by a malicious storage server to break, to different degrees, the confidentiality of the users' password and therefore the users' data.

Our findings have been communicated to SpiderOak in April 2017. The vendor promptly replied to our concerns by releasing an updated version of the application (v. 6.3.0, June 2017) which resolves most of the issues described in this paper.

ePrint Report
Enforcing Input Correctness via Certification in Garbled Circuit Evaluation
Yihua Zhang, Marina Blanton, Fattaneh Bayatbabolghani

Secure multi-party computation allows a number of participants to securely evaluate a function on their private inputs and has a growing number of applications. Two standard adversarial models that treat the participants as semi-honest or malicious, respectively, are normally considered for showing security of constructions in this framework. In this work, we go beyond the standard security model in the presence of malicious participants and treat the problem of enforcing correct inputs to be entered into the computation. We achieve this by having a certification authority certify user’s information, which is consequently used in secure two-party computation based on garbled circuit evaluation. The focus of this work on enforcing correctness of garbler’s inputs via certification, as prior work already allows one to achieve this goal for circuit evaluator’s input. Thus, in this work, we put forward a novel approach for certifying user’s input and tying certification to garbler’s input used during secure function evaluation based on garbled circuits. Our construction achieves notable performance of adding only one (standard) signature verification and O(nρ) symmetric key/hash operations to the cost of garbled circuit evaluation in the malicious model via cut-and-choose, in which ρ circuits are garbled and n is the length of the garbler’s input in bits. Security of our construction is rigorously proved in the standard model.

ePrint Report
Towards Doubly Efficient Private Information Retrieval
Ran Canetti, Justin Holmgren, Silas Richelson

Private Information Retrieval (PIR) allows a client to obtain data from a public database without disclosing the locations accessed. Traditionally, the stress is on preserving sublinear work for the client, while the server's work is taken to inevitably be at least linear in the database size. Beimel, Ishai and Malkin (JoC 2004) show PIR schemes where, following a linear-work preprocessing stage, the server's work per query is sublinear in the database size. However, that work only addresses the case of multiple non-colluding servers; the existence of single-server PIR with sublinear server work remained unaddressed.

We consider single-server PIR schemes where, following a preprocessing stage in which the server obtains an encoded version of the database and the client obtains a short key, the per-query work of both server and client is polylogarithmic in the database size. We call such schemes {\em doubly efficient}. Concentrating on the case where the client's key is secret, we show:

- A scheme, based on one-way functions, that works for a bounded number of queries, and where the server storage is linear in the number of queries plus the database size.

- A scheme for an unbounded number of queries, whose security follows from a new hardness assumption that is related to the hardness of solving a system of noisy linear equations.

We also show the insufficiency of a natural approach for obtaining doubly efficient PIR in the setting where the preprocessing is public.

We consider single-server PIR schemes where, following a preprocessing stage in which the server obtains an encoded version of the database and the client obtains a short key, the per-query work of both server and client is polylogarithmic in the database size. We call such schemes {\em doubly efficient}. Concentrating on the case where the client's key is secret, we show:

- A scheme, based on one-way functions, that works for a bounded number of queries, and where the server storage is linear in the number of queries plus the database size.

- A scheme for an unbounded number of queries, whose security follows from a new hardness assumption that is related to the hardness of solving a system of noisy linear equations.

We also show the insufficiency of a natural approach for obtaining doubly efficient PIR in the setting where the preprocessing is public.

ePrint Report
Can We Access a Database Both Locally and Privately?
Elette Boyle, Yuval Ishai, Rafael Pass, Mary Wootters

We consider the following strong variant of private information retrieval (PIR). There is a large database x that we want to make publicly available. To this end, we post an encoding X of x together with a short public key pk in a publicly accessible repository. The goal is to allow any client who comes along to retrieve a chosen bit x_i by reading a small number of bits from X, whose positions may be randomly chosen based on i and pk, such that even an adversary who can fully observe the access to X does not learn information about i.

Towards solving the above problem, we study a weaker secret key variant where the data is encoded and accessed by the same party. This primitive, that we call an oblivious locally decodable code (OLDC), is independently motivated by applications such as searchable sym- metric encryption. We reduce the public-key variant of PIR to OLDC using an ideal form of obfuscation that can be instantiated heuristically with existing indistinguishability obfuscation candidates, or alternatively implemented with small and stateless tamper-proof hardware.

Finally, a central contribution of our work is the first proposal of an OLDC candidate. Our candidate is based on a secretly permuted Reed-Muller code. We analyze the security of this candidate against several natural attacks and leave its further study to future work.

Towards solving the above problem, we study a weaker secret key variant where the data is encoded and accessed by the same party. This primitive, that we call an oblivious locally decodable code (OLDC), is independently motivated by applications such as searchable sym- metric encryption. We reduce the public-key variant of PIR to OLDC using an ideal form of obfuscation that can be instantiated heuristically with existing indistinguishability obfuscation candidates, or alternatively implemented with small and stateless tamper-proof hardware.

Finally, a central contribution of our work is the first proposal of an OLDC candidate. Our candidate is based on a secretly permuted Reed-Muller code. We analyze the security of this candidate against several natural attacks and leave its further study to future work.

ePrint Report
Zero-Knowledge Contingent Payments Revisited: Attacks and Payments for Services
Matteo Campanelli, Rosario Gennaro, Steven Goldfeder, Luca Nizzardo

Zero Knowledge Contingent Payment (ZKCP) protocols allow fair exchange of sold goods and payments over the Bitcoin network. In this paper we point out two main shortcomings of current proposals for ZKCP.

First we show an attack that allows a buyer to learn partial information about the digital good being sold, without paying for it. This break in the zero-knowledge condition of ZKCP is due to the fact that in the protocols we attack, the buyer is allowed to choose common parameters that normally should be selected by a trusted third party.

We present ways to fix this attack that do not require a trusted third party.

Second, we show that ZKCP are not suited for the purchase of digital services rather than goods. Current constructions of ZKCP do not allow a seller to receive payments after proving that a certain service has been rendered, but only for the sale of a specific digital good. We define the notion of Zero-Knowledge Contingent Service Payment (ZKCSP) protocols and construct two new protocols, for either public or private verification.

We implemented and tested the attack on ZKCP, and our two new ZKCSP protocols, showing their feasibility for very realistic examples. We present code that learns, without paying, the value of a Sudoku cell in the "Pay-to-Sudoku" ZKCP implementation [17]. We also implement ZKCSP protocols for the case of Proof of Retrievability, where a client pays the server for providing a proof that the client's data is correctly stored by the server. A side product of our implementation effort is a new optimized circuit for SHA256 with less than a quarter than the number of AND gates of the best previously publicly available one. Our new SHA256 circuit may be of independent use for circuit-based MPC and FHE protocols that require SHA256 circuits.

First we show an attack that allows a buyer to learn partial information about the digital good being sold, without paying for it. This break in the zero-knowledge condition of ZKCP is due to the fact that in the protocols we attack, the buyer is allowed to choose common parameters that normally should be selected by a trusted third party.

We present ways to fix this attack that do not require a trusted third party.

Second, we show that ZKCP are not suited for the purchase of digital services rather than goods. Current constructions of ZKCP do not allow a seller to receive payments after proving that a certain service has been rendered, but only for the sale of a specific digital good. We define the notion of Zero-Knowledge Contingent Service Payment (ZKCSP) protocols and construct two new protocols, for either public or private verification.

We implemented and tested the attack on ZKCP, and our two new ZKCSP protocols, showing their feasibility for very realistic examples. We present code that learns, without paying, the value of a Sudoku cell in the "Pay-to-Sudoku" ZKCP implementation [17]. We also implement ZKCSP protocols for the case of Proof of Retrievability, where a client pays the server for providing a proof that the client's data is correctly stored by the server. A side product of our implementation effort is a new optimized circuit for SHA256 with less than a quarter than the number of AND gates of the best previously publicly available one. Our new SHA256 circuit may be of independent use for circuit-based MPC and FHE protocols that require SHA256 circuits.

ePrint Report
A Formal Foundation for Secure Remote Execution of Enclaves
Pramod Subramanyan, Rohit Sinha, Ilia Lebedev, Srinivas Devadas, Sanjit Seshia

Recent proposals for trusted hardware platforms, such as Intel SGX and the MIT Sanctum processor, offer compelling security features but lack formal guarantees. We introduce a verification methodology based on a trusted abstract platform (TAP) that formally models idealized enclaves and a parameterized adversary. We present machine-checked proofs showing that the TAP satisfies the three key security properties needed for secure remote execution: integrity, confidentiality and secure measurement. We then present machine-checked proofs showing that SGX and Sanctum are refinements of the TAP under certain parameterizations of the adversary, demonstrating that these systems implement secure enclaves for the stated adversary models.

ePrint Report
Performance Counters to Rescue: A Machine Learning based safeguard against Micro-architectural Side-Channel-Attacks
Manaar Alam, Sarani Bhattacharya, Debdeep Mukhopadhyay, Sourangshu Bhattacharya

Micro-architectural side-channel-attacks are presently daunting threats to most mathematically elegant encryption algorithms. Even though there exist various defense mechanisms, most of them come with the extra overhead of implementation. Recent studies have prevented some particular categories of these attacks but fail to address the detection of other classes. This paper presents a generic machine learning based multi-layer detection approach targeting these micro-architectural side-channel-attacks, without concentrating on a single category. The proposed approach work by proling low-level hardware events using Linux perf event API and then by analyzing these data with some appropriate machine learning techniques. This paper also presents a novel approach, using time-series data, to correlate the execution trace of the adversary with the secret key of encryption for dealing with false-positives and unknown attacks. The experimental results and performance of the proposed approach suggest its superiority with high detection accuracy and low performance overhead.

ePrint Report
Weak is Better: Tightly Secure Short Signatures from Weak PRFs
Jacob Alperin-Sheriff, Daniel Apon

The Boyen-Li signature scheme [Asiacrypt'16] is a major theoretical breakthrough. Via a clever homomorphic evaluation of a pseudorandom function over their verification key, they achieve a reduction loss in security linear in the underlying security parameter and entirely independent of the number of message queries made, while still maintaining short signatures (consisting of a single short lattice vector). All previous schemes with such an independent reduction loss in security required a linear number of such lattice vectors, and even in the classical world, the only schemes achieving short signatures relied on non-standard assumptions.

We improve on their result, providing a verification key smaller by a linear factor, a significantly tighter reduction with only a constant loss, and signing and verification algorithms that could plausibly run in about 1 second. Our main idea is to change the scheme in a manner that allows us to replace the pseudorandom function evaluation with an evaluation of a much more efficient weak pseudorandom function.

As a matter of independent interest, we give an improved method of randomized inversion of the G gadget matrix [MP12], which reduces the noise growth rate in homomorphic evaluations performed in a large number of lattice-based cryptographic schemes, without incurring the high cost of sampling discrete Gaussians.

We improve on their result, providing a verification key smaller by a linear factor, a significantly tighter reduction with only a constant loss, and signing and verification algorithms that could plausibly run in about 1 second. Our main idea is to change the scheme in a manner that allows us to replace the pseudorandom function evaluation with an evaluation of a much more efficient weak pseudorandom function.

As a matter of independent interest, we give an improved method of randomized inversion of the G gadget matrix [MP12], which reduces the noise growth rate in homomorphic evaluations performed in a large number of lattice-based cryptographic schemes, without incurring the high cost of sampling discrete Gaussians.

ePrint Report
Making Password Authenticated Key Exchange Suitable For Resource-Constrained Industrial Control Devices
Björn Haase, Benoît Labrique

Connectivity becomes increasingly important also for small embedded systems such as typically found in industrial control installations. More and more use-cases require secure remote user access increasingly incorporating handheld based human machine interfaces, using wireless links such as Bluetooth. Correspondingly secure operator authentication becomes of utmost importance. Unfortunately, often passwords with all their well-known pitfalls remain the only practical mechanism.
We present an assessment of the security requirements for the industrial setting, illustrating that offline attacks on passwords-based authentication protocols should be considered a significant threat. Correspondingly use of a Password Authenticated Key Exchange protocol becomes desirable. We review the signif-icant challenges faced for implementations on resource-constrained devices.
We explore the design space and shown how we succeeded in tailoring a partic-ular variant of the Password Authenticated Connection Establishment (PACE) protocol, such that acceptable user interface responsiveness was reached even for the constrained setting of an ARM Cortex-M0+ based Bluetooth low-energy transceiver running from a power budget of 1.5 mW without notable energy buffers for covering power peak transients.

ePrint Report
Privacy-Free Garbled Circuits for Formulas: Size Zero and Information-Theoretic
Yashvanth Kondi, Arpita Patra

Garbled circuits are of central importance in cryptography, finding widespread application in secure computation, zero-knowledge (ZK) protocols, and verifiable outsourcing of computation to name a few. We are interested in a particular kind of garbling scheme, termed privacy-free in the literature. We show that Boolean formulas can be garbled information-theoretically in the privacy-free setting, producing no ciphertexts at all. Existing garbling schemes either rely on cryptographic assumptions (and thus require cryptographic operations to construct and evaluate garbled circuits), produce garbled circuits of non-zero size, or are restricted to low depth formulaic circuits. Our result has both theoretical and practical implications for garbled circuits as a primitive. On the theory front, our result breaks the known theoretical lower bound of one ciphertext for garbling an AND gate in this setting. As an interesting implication of producing size zero garbled circuits, our scheme scores adaptive security for free. On the practical side, our garbling scheme involves only cheap XOR operations and produces size zero garbled circuits. As a side result, we propose several interesting extensions of our scheme. Namely, we show how to garble threshold and high fan-in gates.
An aspect of our garbling scheme that we believe is of theoretical interest is that it does not maintain the invariant that the garbled circuit evaluator must not at any point be in possession of both keys of any wire in the garbled circuit.

Our scheme directly finds application in ZK protocols where the verification function of the language is representable by a formulaic circuit. Such examples include Boolean formula satisfiability. The ZK protocols obtained by plugging in our scheme in the known paradigm of building ZK protocols from garbled circuits offer better proof size, while relying on standard assumptions. Furthermore, the adaptivity of our garbling scheme allows us to cast our ZK protocols in the offline-online setting and offload circuit dependent communication and computation to the offline phase. As a result, the online phase enjoys communication and computation (in terms of number of symmetric key operations) complexity that are linearly proportional to the witness size alone.

Our scheme directly finds application in ZK protocols where the verification function of the language is representable by a formulaic circuit. Such examples include Boolean formula satisfiability. The ZK protocols obtained by plugging in our scheme in the known paradigm of building ZK protocols from garbled circuits offer better proof size, while relying on standard assumptions. Furthermore, the adaptivity of our garbling scheme allows us to cast our ZK protocols in the offline-online setting and offload circuit dependent communication and computation to the offline phase. As a result, the online phase enjoys communication and computation (in terms of number of symmetric key operations) complexity that are linearly proportional to the witness size alone.

8
June
2017

ePrint Report
Notes on the design and analysis of SIMON and SPECK
Ray Beaulieu, Douglas Shors, Jason Smith, Stefan Treatman-Clark, Bryan Weeks, Louis Wingers

We discuss the design rationale and analysis of the SIMON and SPECK lightweight block ciphers.

ePrint Report
Human Computing for Handling Strong Corruptions in Authenticated Key Exchange
Alexandra Boldyreva, Shan Chen, Pierre-Alain Dupont, David Pointcheval

We propose the first user authentication and key exchange protocols that can tolerate strong corruptions on the client-side. If a user happens to log in to a server from a terminal that has been fully compromised, then the other past and future user's sessions initiated from honest terminals stay secure. We define the security model for Human Authenticated Key Exchange (HAKE) protocols and first propose two generic protocols based on human-compatible (HC) function family, password-authenticated key exchange (PAKE), commitment, and authenticated encryption. We prove our HAKE protocols secure under reasonable assumptions and discuss efficient instantiations.
We thereafter propose a variant where the human gets help from a small device such as RSA SecurID. This permits to implement an HC function family with stronger security and thus allows to weaken required assumptions on the PAKE. This leads to the very efficient HAKE which is still secure in case of strong corruptions. We believe that our work will promote further developments in the area of human-oriented cryptography.

ePrint Report
Detecting Large Integer Arithmetic for Defense Against Crypto Ransomware
Mehmet Sabir Kiraz, Ziya Alper Genç, Erdinç Öztürk

The evolution of crypto ransomware has increasingly influenced
real-life systems and lead to fatal threats to data security of
individuals and enterprises. A crypto ransomware basically encrypts files of victims using either standard or their own customized crypto functions and request ransom from users to retrieve them again. In this paper, we propose a new detection and analyzing approach, called ExpMonitor, which basically targets ransomware's public key cryptographic algorithms carried out on victim's computer. ExpMonitor is based on observing public key encryption running on the CPU. Monitoring integer multiplication instructions can detect large integer arithmetic operations, which constitute the backbone of public key encryption. While existing detection mechanisms can only targets particular cryptographic functions our technique complements the state-of-the-art.

ePrint Report
Watermarking Public-key Cryptographic Functionalities and Implementations
Foteini Baldimtsi, Aggelos Kiayias, Katerina Samari

A watermarking scheme for a public-key cryptographic functionality enables the embedding of a mark in the instance of the secret-key algorithm such that the functionality of the original scheme is maintained, while it is infeasible for an adversary to remove the mark (unremovability) or mark a fresh object without the marking key (unforgeability). Cohen et al. [STOC'16] has provided constructions for watermarking arbitrary cryptographic functionalities; the resulting schemes rely on indistinguishability obfuscation (iO) and leave two important open questions: (i) the realization of both unremovability and unforgeability, and (ii) schemes the security of which reduces to simpler hardness assumptions than iO.
In this paper we provide a new definitional framework that distinguishes between watermarking cryptographic functionalities and implementations (think of ElGamal encryption being an implementation of the encryption functionality), while at the same time provides a
meaningful relaxation of the watermarking model that enables both unremovability and unforgeability under minimal hardness assumptions.
In this way we can answer questions regarding the ability to watermark a given implementation of a cryptographic functionality which is more refined compared to the question of whether a watermarked implementation functionality exists. Taking advantage of our new formulation we present the first constructions for watermarking public key encryption that achieve both unremovability and unforgeability under minimal hardness assumptions. Our first construction enables the watermarking of any public-key encryption implementation assuming only the existence of one-way functions for private key detection. Our second construction is at the functionality level and uses a stronger assumption (existence of identity-based encryption (IBE)) but supports public detection of the watermark.

ePrint Report
Multiplication and Division over Extended Galois Field GF($p^q$): A new Approach to find Monic Irreducible Polynomials over any Galois Field GF($p^q$).
Sankhanil Dey, Ranjan Ghosh

Irreducible Polynomials (IPs) have been of utmost importance in generation of substitution boxes in modern cryptographic ciphers. In this paper an algorithm entitled Composite Algorithm using both multiplication and division over Galois fields have been demonstrated to generate all monic IPs over extended Galois Field GF($p^q$) for large value of both p and q. A little more efficient Algorithm entitled Multiplication Algorithm and more too Division Algorithm have been illustrated in this Paper with Algorithms to find all Monic IPs over extended Galois Field GF($p^q$) for large value of both p and q. Time Complexity Analysis of three algorithms with comparison to Rabin’s Algorithms has also been exonerated in this Research Article.

ePrint Report
Robust Non-Interactive Multiparty Computation Against Constant-Size Collusion
Fabrice Benhamouda, Hugo Krawczyk, Tal Rabin

Non-Interactive Multiparty Computations (Beimel et al., Crypto 2014) is a very powerful notion equivalent (under some corruption model) to garbled circuits, Private Simultaneous Messages protocols, and obfuscation. We present robust solutions to the problem of Non-Interactive Multiparty Computation in the computational and information-theoretic models. Our results include the first efficient and robust protocols to compute any function in $NC^1$ for constant-size collusions, in the information-theoretic setting and in the computational setting, to compute any function in $P$ for constant-size collusions, assuming the existence of one-way functions. Our constructions start from a Private Simultaneous Messages construction (Feige, Killian Naor, STOC 1994 and Ishai, Kushilevitz, ISTCS 1997) and transform it into a Non-Interactive Multiparty Computation for constant-size collusions.
We also present a new Non-Interactive Multiparty Computation protocol for symmetric functions with significantly better communication complexity compared to the only known one of Beimel et al.

In this paper we describe how to use a secret bug as a trapdoor to design trapped ellliptic curve E(Fp). This trapdoor can be used to mount an invalid curve attack on E(Fp). E(Fp) is designed to respect all ECC security criteria (prime order,high twist order, etc.) but for a secret exponent the point is projected on another unsecure curve. We show how to use this trap with a particular type of time/memory tradeoff to break the ECKCDSA verication process for any public key of the trapped curve. The process is highly undetectable : the chosen defender eort is quadratic in the saboter computational eort. This work provides a concrete hardly detectable and easily deniable example of cryptographic sabotage. While this proof of concept is very
narrow, it highlights the necessity of the Full Verifiable Randomness of ECC

We analyze the concrete security of a hash-based signature
scheme described in the most recent Internet Draft by McGrew, Fluhrer and
Curcio. We perform this analysis in the random-oracle model, where the
Merkle-Damg\r{a}rd hash compression function is models as the random oracle.
We show that, even with a large number of different keys the attacker can choose
from, and a huge computational budget, the attacker succeeds in creating a
forgery with negligible probability ($< 2^{-129}$).

ECDSA is a standard digital signature schemes that is widely used in TLS, Bitcoin and elsewhere. Unlike other schemes like RSA, Schnorr signatures and more, it is particularly hard to construct efficient threshold signature protocols for ECDSA (and DSA). As a result, the best-known protocols today for secure distributed ECDSA require running heavy zero-knowledge proofs and computing many large-modulus exponentiations for every signing operation. In this paper, we consider the specific case of two parties (and thus no honest majority) and construct a protocol that is approximately \textit{two orders of magnitude faster} than the previous best. Concretely, our protocol achieves good performance, with a single signing operation for curve P-256 taking approximately 37ms between two standard machine types in Azure (utilizing a single core only). Our protocol is proven secure under standard assumptions using a game-based definition. In addition, we prove security by simulation under a plausible yet non-standard assumption regarding Paillier.

ePrint Report
Noise-Tolerant Machine Learning Attacks against Physically Unclonable Functions
Fatemeh Ganji, Shahin Tajik, Jean-Pierre Seifert

Along with the evolution of Physically Unclonable Functions (PUFs) as a remedy for the shortcomings of conventional key storage and generation methods, numerous successful attacks against PUFs have been proposed in the literature. Among these are machine learning (ML) attacks, ranging from heuristic approaches to provable algorithms, that have attracted great attention. Nevertheless, the issue of dealing with noise has so far not been addressed in this context. Thus, it is not clear to what extent ML attacks can be launched on real-world, noisy PUFs. This paper aims to clarify this issue by focusing on provable ML algorithms, i.e., Probably Approximately Correct (PAC) learning algorithms. We prove that PAC learning algorithms for known PUF families are effective and applicable even in the presence of noise. Our proof relies heavily on the intrinsic properties of these PUF families, namely arbiter, Ring Oscillator (RO), and Bistable Ring (BR) PUF families. In addition to this proof, we introduce a new style of ML algorithms taking advantage of the Fourier analysis principle. We believe that this type of ML algorithms, and the notions related to it can broaden our understanding of PUFs by offering better measures of security.

ePrint Report
Committed MPC - Maliciously Secure Multiparty Computation from Homomorphic Commitments
Tore Frederiksen, Benny Pinkas, Avishay Yanay

We present a new approach to secure multiparty computation against a static and malicious dishonest majority. Unlike previous protocols that were based on working on MAC-ed secret shares, our approach is based on computations on homomorphic commitments to secret shares. Specifically we show how to realize MPC using any additively-homomorphic commitment scheme, even if such a scheme is an interactive two-party protocol.
Our new approach enables us to do arithmetic computation over arbitrary finite fields such as GF(p) for any prime. In addition, since our protocol computes over committed values, it can be readily composed within larger protocols, and can also be used for efficiently implementing committing OT or committed OT.
We do this in two steps, each of independent interest:
– First we show how to extend any (possibly interactive two-party) additively homomorphic commitment scheme to an additively homomorphic multiparty commitment scheme, only using coin-tossing and a “weak” equality evaluation functionality.
– We then show how to realize multiplication of commitments based on a lightweight preprocessing approach. Finally we show how to use the fully homomorphic commitments to compute any functionality securely in the presence of a malicious adversary corrupting any number of parties.

ePrint Report
ZeroTrace : Oblivious Memory Primitives from Intel SGX
Sajin Sasy, Sergey Gorbunov, Christopher Fletcher

We are witnessing a confluence between applied cryptography
and secure hardware systems in enabling secure cloud computing.
On one hand, work in applied cryptography has enabled efficient,
oblivious data-structure and memory primitives. On the other,
secure hardware and the emergence of Intel SGX has enabled a
low-overhead and mass market mechanism for isolated execution.
These works have disadvantages by themselves. Oblivious memory
primitives carry high performance overheads, especially when run
non-interactively. Intel SGX, while more efficient, suffers from
numerous software-based side-channel attacks.
We combine these two lines of work by designing a working
prototype library of oblivious memory primitives, which we call
ZeroTrace, on top of SGX. To the best of our knowledge, ZeroTrace
represents the first oblivious memory primitives running on a real
secure hardware platform. ZeroTrace simultaneously enables a
dramatic speedup over pure cryptography and protection from
software-based side-channel attacks. The core of our design is an
efficient and flexible block-level memory controller that provides
oblivious execution against any active software adversary, and
across asynchronous SGX enclave terminations. Performance-wise,
the memory controller can service requests for 4 Byte blocks in
1.2 ms and 1 KB blocks in 6 ms (given a 10 GB dataset). On top of
our memory controller, we evaluate Set/Dictionary/List interfaces
which can all perform basic operations (e.g., get/put/insert) in 1-
5 ms for a 4-8 Byte block size. Finally, we demonstrate how to re-
parameterize our system for the remote oblivious storage setting,
where we can service a 4 KB request in 267 ms, at less than an order
of magnitude WAN bandwidth overhead.

ePrint Report
Fully Homomorphic Encryption from the Finite Field Isomorphism Problem
Yark{\i}n Dor\"oz, Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman, Berk Sunar, William Whyte, Zhenfei Zhang

If $q$ is a prime and $n$ is a positive integer then any two finite
fields of order $q^n$ are isomorphic. Elements of these fields can be
thought of as polynomials with coefficients chosen modulo $q$, and a
notion of length can be associated to these polynomials. A
non-trivial isomorphism between the fields, in general, does not
preserve this length, and a short element in one field will usually
have an image in the other field with coefficients appearing to be
randomly and uniformly distributed modulo $q$. This key feature
allows us to create a new family of cryptographic constructions based
on the difficulty of recovering a secret isomorphism between two
finite fields. In this paper we describe a fully homomorphic encryption scheme based on this new hard problem.

ePrint Report
Security Analysis of an Ultra-lightweight RFID Authentication Protocol for M-commerce
Seyed Farhad Aghili, Hamid Mala

Over the last few years, more people perform their social activities on mobile devices, such as mobile payment or mobile wallet. Mobile commerce (m-commerce) refers to manipulating electronic commerce (e-commerce) by using mobile devices and wireless networks. Radio frequency identification(RFID) is a technology which can be employed to complete payment functions on m-commerce. As an RFID subsystem is applied in m-commerce and supply chains, the related security concerns is very important. Recently, Fan et al. have proposed an ultra-lightweight RFID authentication scheme for m-commerce(ULRAS) and claimed that their protocol is enough efficient, and provides a high level of security. In this paper, we show that their protocol is vulnerable to secret disclosure and reader impersonation attacks. Finally, we improve the Fan et al. protocol to present a new one, which is resistant to the mentioned attacks presented in this paper and the other known attacks in the context of RFID authentication. Our proposed improvement does not impose any additional workload on the RFID tag.

ePrint Report
X509CLOUD - FRAMEWORK FOR A UBIQUITOUS PKI
Hitesh Tewari, Arthur Hughes, Stefan Weber, Tomas Barry

The SSL protocol has been widely used for verifying digital identities and to secure Internet traffic since the early days of the web. Although X.509 certificates have been in existence for more than two decades, individual user uptake has been low due to the high cost of issuance and maintenance of such certs. This has led to a situation whereby users are able to verify the identity of an organization or e-commerce retailer via their digital certificate, but organizations have to rely on weak username and password combinations to verify the identity of customers registered with their service. We propose the X509Cloud framework which enables organizations to issue certificates to their users at zero cost, and allows them to securely store and disseminate client certificates using the Bitcoin inspired blockchain protocol. This in turn will enable organizations and individuals to authenticate and to securely communicate with other users on the Internet.

ePrint Report
Resource-efficient OT combiners with active security
Ignacio Cascudo, Ivan Damgård, Oriol Farràs, Samuel Ranellucci

An OT-combiner takes $n$ implementations of the oblivious transfer (OT) functionality, some of which may be faulty, and produces a secure instance of oblivious transfer as long as a large enough number of the candidates are secure. More specifically, an OT-combiner is a 2-party protocol between Alice and Bob which can make several black-box calls to each of the $n$ OT candidates. An adversary can corrupt one of the players and certain number of OT candidates, obtaining their inputs and (in the active case) full control of their outputs and we want the resulting protocol to be secure against such adversary.

In this work we consider perfectly (unconditionally, zero-error) secure OT-combiners and we focus on \emph{minimizing the number of calls} to the candidate OTs.

First, we extend a result from Ishai et. al (ISIT 2014), constructing a perfectly secure single-use (one call per OT candidate) OT-combiner which is secure against active adversaries corrupting one player and at most a tenth of the OT candidates. Ishai et. al obtained the same result for passive adversaries.

Second, we consider a general asymmetric corruption model where an adversary can corrupt different sets of OT candidates depending on whether it is Alice or Bob who is corrupted. We give sufficient and necessary conditions on the existence of an OT combiner with a given number of calls to each server in terms of the existence of secret sharing schemes with certain access structures and share-lengths. This allows us for example to reduce the number of calls needed by known OT combiners, and in fact to determine the optimal number of calls, in some concrete situations even in the symmetric case, e.g. when there are three OT candidates and one of them is corrupted.

In this work we consider perfectly (unconditionally, zero-error) secure OT-combiners and we focus on \emph{minimizing the number of calls} to the candidate OTs.

First, we extend a result from Ishai et. al (ISIT 2014), constructing a perfectly secure single-use (one call per OT candidate) OT-combiner which is secure against active adversaries corrupting one player and at most a tenth of the OT candidates. Ishai et. al obtained the same result for passive adversaries.

Second, we consider a general asymmetric corruption model where an adversary can corrupt different sets of OT candidates depending on whether it is Alice or Bob who is corrupted. We give sufficient and necessary conditions on the existence of an OT combiner with a given number of calls to each server in terms of the existence of secret sharing schemes with certain access structures and share-lengths. This allows us for example to reduce the number of calls needed by known OT combiners, and in fact to determine the optimal number of calls, in some concrete situations even in the symmetric case, e.g. when there are three OT candidates and one of them is corrupted.