We explain how to extend the Bitcoin backbone model of Garay et al. (Eurocrypt, 2015) to accommodate for redactable blockchains. Our extension captures fluid blockchain-based databases (with mutability requirements) and compliance with existing legislation, such as the GDPR right to be forgotten, or the need to erase offending data from nodes’ databases that would otherwise provoke legal shutdowns. Our redactable backbone protocol retains the essential properties of blockchains. Leveraging zero-knowledge proofs, old data can be erased without requiring trusted third parties or heuristics about past chain validation. Our solution can be implemented on Bitcoin immediately without hard-forks, and it is scalable. It allows the redaction of data from UTXOs or unconfirmed transactions that have not yet flooded the network, while guaranteeing invariance of the Bitcoin state. Thus, offending data does not need to persist in the system, not even temporarily.

Private function evaluation aims to securely compute a function$f(x_1, \ldots, x_n)$without leaking any information other than what is revealed by the output, where$f$is a private input of one of the parties (say$\mathsf {Party}_1$) and$x_i$is a private input of the$i$th party$\mathsf {Party}_i$. In this article, we propose a novel and securetwo-party private function evaluation(2PFE) scheme based on the DDH assumption. Our scheme introduces a reusability feature that significantly improves the state-of-the-art. Accordingly, our scheme has two variants, one is utilized in the initial execution of the function$f$, and the other is utilized in its subsequent evaluations. To the best of our knowledge, this is the first and most efficient 2PFE scheme that enjoys a reusablity feature. Our protocols achieve linear communication and computation complexities and a constant number of rounds which is at most three.

Abstract During the past decade, several misbehaving certificate authorities (CAs) have issued fraudulent TLS certificates allowing man-in-the-middle (MITM) kinds of attacks that result in serious security incidents. In order to avoid such incidents, Yakubov et al. ((2018) A blockchain-based PKI management framework. NOMS 2018 - 2018 IEEE/IFIP Network Operations and Management Symposium, Taipei, Taiwan, April, pp. 16. IEEE) recently proposed a new public key infrastructure (PKI) architecture where CAs issue, revoke and validate X.509 certificates on a public blockchain. However, in their proposal TLS clients are subject to MITM kinds of attacks, and certificate transparency is not fully provided. In this paper, we eliminate the issues of the Yakubov et al.’s scheme and propose a new PKI architecture based on permissioned blockchain with PBFT consensus mechanism where the consensus nodes utilize a dynamic threshold signature scheme to generate signed blocks. In this way, the trust to the intermediary entities can be completely eliminated during certificate validation. Our scheme enjoys the dynamic property of the threshold signature because TLS clients do not have to change the verification key even if the validator set is dynamic. We implement our proposal on private Ethereum network to demonstrate the experimental results. The results show that our proposal has negligible overhead during TLS handshake. The certificate validation duration is less than the duration in the conventional PKI and Yakubov et al.’s scheme.

Private function evaluation (PFE) is a special case of secure multi-party computation (MPC), where the function to be computed is known by only one party. PFE is useful in several real-life applications where an algorithm or a function itself needs to remain secret for reasons such as protecting intellectual property or security classification level. In this paper, we focus on improving 2-party PFE based on symmetric cryptographic primitives. In this respect, we look back at the seminal PFE framework presented by Mohassel and Sadeghian at Eurocrypt’13. We show how to adapt and utilize the well-known half gates garbling technique (Zahur et al., Eurocrypt’15) to their constant-round 2-party PFE scheme. Compared to their scheme, our resulting optimization significantly improves the efficiency of both the underlying Oblivious Evaluation of Extended Permutation (OEP) and secure 2-party computation (2PC) protocols, and yields a more than 40% reduction in overall communication cost (the computation time is also slightly decreased and the number of rounds remains unchanged).

Abstract Norway experienced internet voting in 2011 and 2013 for municipal and parliamentary elections, respectively. Its security depends on the assumptions that the involving organizations are completely independent, reliable, and the receipt codes are securely sent to the voters. In this paper, we point out the following aspects: The vote privacy of the Norwegian scheme is violated if Ballot Box and Receipt Generator cooperate because the private key of Decryption Service can be obtained by the two former players. We propose a solution to avoid this issue without adding new players. To assure the correctness, the receipt codes are sent to the voters over a pre‐channel (postal service) and a post‐channel (Short Message Service [SMS]). However, by holding both SMS and the postal receipt code, a voter can reveal his vote even after the elections. Albeit revoting is a fairly well solution for coercion or concealment, intentional vote revealing is still a problem. We suggest SMS only for notification of vote submission. In case the codes are falsely generated or the pre‐channel is not secure, a vote can be counted for a different candidate without detection. We propose a solution in which voters verify the integrity of the postal receipt codes. Copyright © 2016 John Wiley & Sons, Ltd.

One of the most important benefits of public cloud storage is outsourcing of management and maintenance with easy accessibility and retrievability over the internet. However, outsourcing data on the cloud brings new challenges such as integrity verification and privacy of data. More concretely, once the users outsource their data on the cloud they have no longer physical control over the data and this leads to the integrity protection issue. Hence, it is crucial to guarantee proof of data storage and integrity of the outsourced data. Several pairing-based auditing solutions have been proposed utilizing the Boneh-Lynn-Shacham (BLS) short signatures. They basically provide a desirable and efficient property of non-repudiation protocols. In this work, we propose the first ID-based privacy-preserving public auditing scheme with message recoverable signatures. Because of message recoverable auditing scheme, the message itself is implicitly included during the verification step that was not possible in previously proposed auditing schemes. Furthermore, we point out that the algorithm suites of existing schemes is either insecure or very inefficient due to the choice of the underlying bilinear map and its baseline parameter selections. We show that our scheme is more efficient than the recently proposed auditing schemes based on BLS like short signatures.

Abstract Bringer et al. proposed two cryptographic protocols for the computation of Hamming distance. Their first scheme uses oblivious transfer and provides security in the semi‐honest model. The other scheme uses committed oblivious transfer and is claimed to provide full security in the malicious case. The proposed protocols have direct implications to biometric authentication schemes between a prover and a verifier where the verifier has biometric data of the users in plain form. In this paper, we show that their protocol is not actually fully secure against malicious adversaries. More precisely, our attack breaks the soundness property of their protocol where a malicious user can compute a Hamming distance, which is different from the actual value. For biometric authentication systems, this attack allows a malicious adversary to pass the authentication without knowledge of the honest user's input with at most O(n) complexity instead of O(2n), where n is the input length. We propose an enhanced version of their protocol where this attack is eliminated. The security of our modified protocol is proven using the simulation‐based paradigm. Furthermore, as for efficiency concerns, the modified protocol utilizes verifiable oblivious transfer, which does not require the commitments to outputs, which improves its efficiency significantly. Copyright © 2015 John Wiley & Sons, Ltd.

Abstract This paper examines Vaudenay's privacy model, which is one of the first and most complete privacy models that featured the notion of different privacy classes. We enhance this model by introducing two new generic adversary classes,k‐strong andk‐forward adversaries where the adversary is allowed to corrupt a tag at mostktimes. Moreover, we introduce an extended privacy definition that also covers all privacy classes of Vaudenay's model. In order to achieve highest privacy level, we study low cost primitives such as physically unclonable functions (PUFs). The common assumption of PUFs is that their physical structure is destroyed once tampered. This is an ideal assumption because the tamper resistance depends on the ability of the attacker and the quality of the PUF circuits. In this paper, we have weakened this assumption by introducing a new definitionk‐resistant PUFs.k‐PUFs are tamper resistant against at mostkattacks; that is, their physical structure remains still functional and correct until at mostkthphysical attack. Furthermore, we prove that strong privacy can be achieved without public‐key cryptography usingkPUF‐based authentication. We finally prove that our extended proposal achieves both reader authentication andk‐strong privacy. Copyright © 2014 John Wiley & Sons, Ltd.