Search

Forward privacy in existing searchable symmetric encryption approaches generally supports only keyword searches, rather than range searches. In addition, existing approaches that support range search over encrypted datasets have limitations associated with efficiency, accuracy, and security. Seeking to address these limitations, we formally propose the definition of the forward privacy for secure range searches. Also, we demonstrate how three widely-used cryptographic tools— order-preserving encryption (OPE), pseudorandom function, and one-time pad–can be leveraged to design an efficient, accurate, and forward secure (EAFS) searchable encryption scheme supporting range search in encrypted numerical databases. In the proposed EAFS scheme, a trapdoor only matches the last data record that satisfies the search range, and the other results are found iteratively using the previous result. The chain-like search and the embedded ciphertexts of OPE simultaneously guarantee its efficiency, forward privacy, and accuracy. We also use the simulation-based method to demonstrate that our scheme is secure. Then, we implement EAFS in Microsoft Azure and evaluate its performance. The evaluation findings demonstrate that our proposed scheme supports secure range search practically and efficiently.

Verifiable databases (VDB) enables the data owner to outsource a huge unencrypted database to the powerful but untrusted cloud such that any client could later retrieve the database and check whether the cloud returns valid records or not. To the best of our knowledge, there is no prior work considering privacy. Besides, they assume that the data owner and the client are fully trusted while they may be semi-honest in the real world. To address these problems, we propose a new primitive called privacy-preserving publicly verifiable database (PPVDB), which not only guarantees the integrity of the query result but also leaks no information. At the end of this protocol, the client can check whether the cloud returns a valid result and learns the query result but nothing else about the database. Besides, the cloud learns nothing about the database and the query, and the data owner does not know which item that the client has queried. Motivated by the comparison among some strawman solutions, we incorporate verifiable computation for the polynomial with oblivious pseudorandom function to construct a PPVDB scheme, which is the first VDB scheme providing stronger security against the malicious cloud and the semi-honest client and data owner.

To take advantages of location-based services (LBS) while protecting user privacy against untrusted LBS providers, privacy preserving LBS have attracted increasing attention. Considering that users in an LBS system are often equipped with resource-constrained mobile devices, most existing privacy preserving LBS methods are based on anonymization techniques. However, these existing schemes still have some privacy and efficiency limitations. In this paper, we propose a novel privacy preserving LBS scheme, which simultaneously achieves user privacy protection and high query efficiency. Specifically, we utilize the k-anonymity technique and the pseudo random function to protect the location privacy and the query message privacy of users. We design an enhanced one-round blind filter protocol (ORBFe) based on the Paillier cryptosystem to securely filter out redundant records generated by the k-anonymity technique. Compared with existing solutions, our ORBFe protocol not only ensures that users receive exactly satisfying results but also incurs a low computation and communication cost on the server side. Through the theoretical analysis and extensive experiments, we demonstrate the security and efficiency of our proposed scheme.

Pseudorandom functions ( PRFs ) are one of the foundational concepts in theoretical computer science, with numerous applications in complexity theory and cryptography. In this work, we study the security of PRFs when evaluated on quantum superpositions of inputs. The classical techniques for arguing the security of PRFs do not carry over to this setting, even if the underlying building blocks are quantum resistant. We therefore develop a new proof technique to show that many of the classical PRF constructions remain secure when evaluated on superpositions.

A nominative signature (NS) is a cryptographic primitive where two parties collude to produce a signature. It is a user certification system and has applications in a variety of sectors where nominee cannot trust heavily on the nominator to validate the nominee's certificate and only targeted entities are allowed to verify the signature on sensitive data. A new construction for NS from standard assumptions on lattice is provided. The authors’ construction relies on collision‐resistant preimage sampleable function and symmetric key primitives like collision‐resistant pseudorandom function and zero knowledge proof system ZKB++ for Boolean circuits. The authors provide detailed security analysis and show that their construction achieves security under unforgeability, invisibility, impersonation, and non‐repudiation in the existing model. Furthermore, our construction exhibits non‐transferability. The security under non‐repudiation is achieved in the quantum random oracle model using Unruh transform to ZKB++.

Traceable ring signature (TRS), a variant of ring signature, allows a signer to sign a message anonymously labeled with a tag on behalf of a group of users, but may reveal the signer’s identity if he creates two signatures with the same tag. TRS provides accountable anonymity for users, and serves as an important role in e-voting systems and e-coupon services. However, current TRS schemes are built on hard problems in number theory that cannot resist quantum attackers. To address this issue, first, we propose a general framework of TRS, by using a non-interactive zero-knowledge proof of knowledge, a hash family, and a pseudorandom function with some additional properties. Then, by instantiating our framework, we give two concrete efficient TRS schemes from lattices and symmetric-key primitives respectively, and both of them are proven to be secure in the quantum random oracle model. Moreover, both schemes have logarithmic signature size.

Predicate encryption (PE), formalized by Katz et al., is a new paradigm of public-key encryption that conceptually captures the public-key encryption that supports fine-grained access control policy. Because of the nature of PE, it is used for cloud storage so that users can retrieve encrypted data without revealing any information about the data to cloud servers and other users. Although lots of PE schemes have been studied, the predicate-hiding security is seldom considered; that is, the user’s secret key may leak sensitive information of the predicate. Additionally, the security of the current predicate-hiding PE schemes relies on the discrete logarithm assumption which cannot resist the quantum attacks in the future. In this paper, we propose a generic PE for inner product under symmetric-key setting, called private IPE, from specific key-homomorphic pseudorandom function (PRF). The rigorous proofs are provided to show that the construction is payload-hiding, attribute-hiding, and predicate-hiding secure. With the advantage of the generic construction, if the underlying PRF can resist quantum attacks, then, through our proposed generic construction, a quantum-resistant private IPE can be obtained.

Industrial Internet of Things (IIoT) brings together computers, devices, advanced analytics, and people in industries, such as transportation, oil plant, and power grid that leads to major efficiency and productivity gains for almost any industrial procedures. Due to the interconnection of devices in IIoT, communication security has become a critical issue to address in many emerging industry standards that require the authentication and key exchange procedure to be done to guarantee the authorized machine access (e.g., from users) and secure the data transmission between machines. To overcome the shortcoming (i.e., low entropy) of the memorable password in user authentication, it is rightfully recommended by industry standards (such as IEC-62443 family) to use multifactor authentication ( $\mathsf {MFA}$ ) for higher security levels. Notably, latency is one of the main sources of inefficiency when a device is communicating with other machines on IIoT. To mitigate latency, a smooth projective hash function ( $\mathsf {SPHF}$ ) built from well-studied standard assumptions is used to achieve a low-interactivity multifactor authenticated key exchange protocol ( $\mathsf {MFAKE}$ ) because $\mathsf {SPHF}$ allows each party to prove to the others that he knows the right authentication factor(s). In this article, we are, therefore, motivated to build a new $\mathsf {MFAKE}$ named “secure remote multifactor ( $\mathsf {SRMF}$ )” to achieve the human-involved “machine-to-machine” secure communication in IIoT. That is, $\mathsf {SRMF}$ leverages multiple user-centric authentication factors (such as password, biometric fingerprints, and PIN), and it can synergistically support multifactor registration ( $\mathsf {MFR}$ ), $\mathsf {MFA}$ , and multifactor key exchange ( $\mathsf {MFKE}$ ). Furthermore, to prevent authentication factors stored at the server exposing to attackers, the password-harden service (i.e., Pythia-PRF and USENIX’15) inspires us to develop a multifactor hardening service ( ${{\mathsf {MFHS}}}$ ) utilizing an oblivious pseudorandom function ( ${\mathsf {OPRF}}$ ). The balanced security of the proposed protocol is proved under the model of Bellare–Pointcheval–Rogaway (EUROCRYPTO’00) along with theoretical and experimental evaluations.

Owing to the development of wireless communication technology and the increasing number of automobiles, vehicular ad hoc networks (VANETs) have become essential tools to secure traffic safety and enhance driving convenience. It is necessary to design a conditional privacy-preserving authentication (CPPA) scheme for VANETs because of their vulnerability and security requirements. Traditional CPPA schemes have two deficiencies. One is that the communication or storage overhead is not sufficiently low, but the traffic emergency message requires an ultra-low transmission delay. The other is that traditional CPPA schemes do not consider updating the system secret key (SSK), which is stored in an unhackable Tamper Proof Device (TPD), whereas side-channel attack methods and the wide usage of the SSK increase the probability of breaking the SSK. To solve the first issue, we propose a CPPA signature scheme based on elliptic curve cryptography, which can achieve message recovery and be reduced to elliptic curve discrete logarithm assumption, so that traffic emergency messages are secured with ultra-low communication overhead. To solve the second issue, we design an SSK updating algorithm, which is constructed on Shamir’s secret sharing algorithm and secure pseudo random function, so that the TPDs of unrevoked vehicles can update SSK securely. Formal security proof and analysis show that our proposed scheme satisfies the security and privacy requirements of VANETs. Performance analysis demonstrates that our proposed scheme requires less storage size and has a lower transmission delay compared with related schemes.

Password-Based Key Derivation Function 2 (PBKDF2) is widely used cryptographic algorithm in order to generate secure keys to a password in various occasions. For example, it is used for file encryption and implementation of authentication systems, and so on. However, the generated derived key has a lower entropy than a general cryptography key, so its use is limited. To compensate for this the number of iteration counts of PBKDF2 should be increased. As the number of repetitive tasks increases, the entropy of the derived key increases, but it takes more time to generate the derived key. We present various optimization methods of PBKDF2. The main idea of our proposed method is reducing redundant block operations and optimizing the internal process of underlying Pseudo Random Function (PRF). In other words, we integrate several redundant operations and make full use of constant values used in PBKDF2. We use two HMAC algorithms: one using SHA-2 family and one using LSH family as the PRF of PBKDF2 (SHA-2 family is the most widely used hash functions, and LSH family is the latest hash function recently developed in South Korea). With our techniques, our implementations outperform Korea Internet & Security Agency (KISA) implementation by 121.26%, 325.91%, and 231.89% for using SHA256, LSH256, and LSH512 respectively; and also outperform OpenSSL implementation by 39.59% using SHA512. In addition, we show that the internal process of PBKDF2 can be computed independently. With our multi thread technique, our PBKDF2 implementations outperform KISA implementation by 2,152.66%, 1,986.85%, and 1,591.36% for using SHA256, LSH256, and LSH512 respectively; and our PBKDF2-HMAC-SHA512 implementation outperforms OpenSSL implementation by 523.57%. With our proposed implementation techniques, higher security can be achieved with more iteration operations. Furthermore, our optimization techniques can be easily expanded to optimize the performance of PBKDF2 on GPGPU and embedded devices.

FPGA system on chips (SoCs) are ideal computing platforms for edge devices in applications which require high performance through hardware acceleration and updatability due to long operation in the field. A secure update of hardware functionality can in general be achieved by using built-in cryptographic engines and provided secret key storage. However, reported examples have shown that such cryptographic engines may become insecure against side-channel attacks at any later point in time. This leaves already deployed systems vulnerable without any clear mitigation options. To solve this, we propose a comprehensive concept that uses an alternative and side-channel protected cryptographic engine within the FPGA logic instead of the built-in one for the crucial task of bitstream decryption. Remarkably this concept even allows to update the cryptographic engine itself. As proof of concept, we describe an application to the Xilinx Zynq-7020 FPGA SoC in detail. We provide two options for a leakage resilient decryption engine which are based on the same primitive, a leakage resilient pseudorandom function (LR-PRF). Depending on a side-channel evaluation of this primitive on the target platform, either a version with additional side-channel countermeasures or a more efficient variant is deployed. The lack of accessible secret key storage poses a significant challenge and requires the use of a physical unclonable function (PUF) to generate a device intrinsic secret within the FPGA logic. At the same time this means that manufacturer-provided secret key storage or cryptography is no longer required; only a public key for signature verification of the first stage bootloader and initial static bitstream. We provide empirical results proving the side-channel security of the protected cryptographic engine as well as an evaluation of the PUF quality. The full design and source code is made available to encourage further research in this direction.

Private set intersection (PSI) allows participants to securely compute the intersection of their inputs, which has a wide range of applications such as privacy-preserving contact tracing of COVID-19. Most existing PSI protocols were based on asymmetric/symmetric cryptosystem. Therefore, keys-related operations would burden these systems. In this paper, we transform the problem of the intersection of sets into the problem of finding roots of polynomials by using point-value polynomial representation, blind polynomials’ point-value pairs for secure transportation and computation with the pseudorandom function, and then propose an efficient PSI protocol without any cryptosystem. We optimize the protocol based on the permutation-based hash technique which divides a set into multisubsets to reduce the degree of the polynomial. The following advantages can be seen from the experimental result and theoretical analysis: (1) there is no cryptosystem for data hiding or encrypting and, thus, our design provides a lightweight system; (2) with set elements less than 212, our protocol is highly efficient compared to the related protocols; and (3) a detailed formal proof is given in the semihonest model.

PBKDF2 [1] is a well-known password-based key derivation function. In order to slow attackers down, PBKDF2 introduces CPU-intensive operations based on an iterated pseudorandom function (in our case HMAC-SHA-1). If we are able to speed up a SHA-1 or an HMAC implementation, we are able to speed up PBKDF2-HMAC-SHA-1. This means that a performance improvement might be exploited by regular users and attackers. Interestingly, FIPS 198-1 [2] suggests that it is possible to precompute first message block of a keyed hash function only once, store such a value and use it each time is needed [3] . Therefore the computation of first message block does not contribute to slowing attackers down, thus making the computation of second message block crucial. In this paper we focus on the latter, investigating the possibility to avoid part of the HMAC-SHA-1 operations. We show that some CPU-intensive operations may be replaced with a set of equivalent, but less onerous, instructions. We identify useless XOR operations exploiting and extending Intel optimizations [4] , and applying the Boyar-Peralta heuristic [5] . In addition, we provide an alternative method to compute the SHA-1 message scheduling function and explain why attackers might exploit these findings to speed up a brute force attack against PBKDF2.

A round function based on chaos is designed combining Feistel structure's pseudo-randomness, chaotic system's parameter sensitivity and image data characteristics. The round function composes of two parts—data transformation based on Feistel (abbreviated as FST) and sampling output based on chaos (abbreviated as SMP). FST bases on Feistel structure and several efficient operations including bitwise xor, permutation and circulating shift. SMP is a chaos based pseudo-random sampling algorithm. It is from theoretical analysis that the round function is a pseudo-random function. The upper bounds of the average maximum differential probability and average maximum linear probability are p2 and q2 respectively. Finally, the good pseudo-randomness of the round function is examined with the NIST random test. The design of this round function provides an important cryptographic component for the design of chaotic image encryption algorithm.

The Messaging Layer Security (MLS) project is an IETF effort aiming to establish an industry-wide standard for secure group messaging (SGM). Its development is supported by several major secure-messaging providers (with a combined user base in the billions) and a growing body of academic research. MLS has evolved over many iterations to become a complex, non-trivial, yet relatively ad-hoc cryptographic protocol. In an effort to tame its complexity and build confidence in its security, past analyses of MLS have restricted themselves to sub-protocols of MLS---most prominently a type of sub-protocol embodying so-called continuous group key agreement (CGKA). However, to date the task of proving or even defining the security of the full MLS protocol has been left open. In this work, we fill in this missing piece. First, we formally capture the security of SGM protocols by defining a corresponding security game, which is parametrized by a safety predicate that characterizes the exact level of security achieved by a construction. Then, we cast MLS as an SGM protocol, showing how to modularly build it from the following three main components (and some additional standard cryptographic primitives) in a black-box fashion: (a) CGKA, (b) forward-secure group AEAD (FS-GAEAD), which is a new primitive and roughly corresponds to an "epoch'' of group messaging, and (c) a so-called PRF-PRNG, which is a two-input hash function that is a pseudorandom function (resp.\ generator with input) in its first (resp.\ second) input. Crucially, the security predicate for the SGM security of MLS can be expressed purely as a function of the security predicates of the underlying primitives, which allows to swap out any of the components and immediately obtain a security statement for the resulting SGM construction. Furthermore, we provide instantiations of all component primitives, in particular of CGKA with MLS's TreeKEM sub-protocol (which we prove adaptively secure) and of FS-GAEAD with a novel construction (which has already been adopted by MLS). Along the way we introduce a collection of new techniques, primitives, and results with applications to other SGM protocols and beyond. For example, we extend the Generalized Selective Decryption proof technique (which is central in CGKA literature) and prove adaptive security for another (practical) more secure CGKA protocol called RTreeKEM (Alwen et al.,\ CRYPTO '20). The modularity of our approach immediately yields a corollary characterizing the security of an SGM construction using RTreeKEM.

We provide a systematic analysis of two related multiparty protocols, namely (Non-Interactive Fully) Distributed Verifiable Random Functions (DVRFs) and Decentralised Random Beacons (DRBs), including their syntax and definition of robustness and privacy properties. These two protocols are run by multiple network nodes where each node contributes with a partial evaluation and the collection of these partial values is used to evaluate a pseudorandom function. We refine current pseudorandomness definitions for distributed functions and show that the privacy provided by strong pseudorandomness, where an adversary is allowed to make partial function evaluation queries on the challenge value, is strictly better than that provided by standard pseudorandomness, where such adversarial queries are disallowed. We provide two new DVRF instantiations, named DDH-DVRF and GLOW-DVRF, that meet strong pseudorandomness under widely accepted cryptographic assumptions. We show the usefulness of our DRB formalism in two different ways. Firstly, we give a rigorous treatment of a folklore generic construction that builds a Decentralized Random Beacon from any DVRF instance and prove that it satisfies robustness and pseudorandomness provided that the original DVRF protocol is secure. Secondly, we capture several existing DRB protocols from academia and industry within our framework, which serves as an evidence of its wider applicability. Finally, we report on experimental evaluations of our newly introduced DVRFs with implementations under different cryptographic libraries, and we also report preliminary benchmark results on two of the DRBs obtained from the generic DVRF-to-DRB transformation. Our benchmarks can be independently verified as we provide an open source C++ reference implementation of the new DVRFs. Finally, we conclude that our new DRB instantiations are the most efficient instantiations currently available while enjoying strong and formally proven security properties.

A weak pseudorandom function (WPRF) is a keyed function \(f_k:\{0,1\}^n\rightarrow \{0,1\}\) such that, for a random key k, a collection of samples \((x, f_k(x))\), for uniformly random inputs x, cannot be efficiently distinguished from totally random input-output pairs (x, y). We study WPRFs in \(\mathtt {AC}0[\mathtt {MOD}2] \), the class of functions computable by \(\mathtt {AC}0 \) circuits with parity gates, making the following contributions.

At FSE 2017, Gaži et al. demonstrated a pseudorandom function (PRF) distinguisher (Gaži et al., ToSC 2016(2)) on PMAC with Ω(lq2/2n) advantage, where q, l, and n, denote the number of queries, maximum permissible query length (in terms of n-bit blocks), and block size of the underlying block cipher. This, in combination with the upper bounds of Ο(lq2/2n) (Minematsu and Matsushima, FSE 2007) and Ο(qσ/2n) (Nandi and Mandal, J. Mathematical Cryptology 2008(2)), resolved the long-standing problem of exact security of PMAC. Gaži et al. also showed that the dependency on l can be dropped (i.e. O(q2/2n) bound up to l ≤ 2n/2) for a simplified version of PMAC, called sPMAC, by replacing the Gray code-based masking in PMAC with any 4-wise independent universal hash-based masking. Recently, Naito proposed another variant of PMAC with two powering-up maskings (Naito, ToSC 2019(2)) that achieves l-free bound of O(q2/2n), provided l ≤ 2n/2. In this work, we first identify a flaw in the analysis of Naito’s PMAC variant that invalidates the security proof. Apparently, the flaw is not easy to fix under the existing proof setup. We then formulate an equivalent problem which must be solved in order to achieve l-free security bounds for this variant. Second, we show that sPMAC achieves O(q2/2n) bound for a weaker notion of universality as compared to the earlier condition of 4-wise independence. Third, we analyze the security of PMAC1 (a popular variant of PMAC) with a simple modification in the linear combination of block cipher outputs. We show that this simple modification of PMAC1 has tight security O(q2/2n) provided l ≤ 2n/4. Even if l < 2n/4, we still achieve same tight bound as long as total number of blocks in all queries is less than 22n/3.

Multi-factor authentication (MFA) has been widely used to safeguard high-value assets. Unlike single-factor authentication (e.g., password-only login), $t$ -factor authentication ( $t$ FA) requires a user always to carry and present $t$ specified factors so as to strengthen the security of login. Nevertheless, this may restrict user experience in limiting the flexibility of factor usage, e.g., the user may prefer to choose any factors at hand for login authentication. To bring back usability and flexibility without loss of security, we introduce a new notion of authentication, called $(t,n)$ threshold MFA , that allows a user to actively choose $t$ factors out of $n$ based on preference. We further define the “most-rigorous” multi-factor security model for the new notion, allowing attackers to control public channels, launch active/passive attacks, and compromise/corrupt any subset of parties as well as factors. We state that the model can capture the most practical security needs in the literature. We design a threshold MFA key exchange (T-MFAKE) protocol built on the top of a threshold oblivious pseudorandom function and an authenticated key exchange protocol. Our protocol achieves the “highest-attainable” security against all attacking attempts in the context of parties/factors being compromised/corrupted. As for efficiency, our design only requires $4+t$ exponentiations, 2 multi-exponentiations and $\mathbf {2}$ communication rounds. Compared with existing $t$ FA schemes, even the degenerated $(t,t)$ version of our protocol achieves the strongest security (stronger than most schemes) and higher efficiency on computational and communication. We instantiate our design on real-world platform to highlight its practicability and efficiency.

Providing methods to anonymously validate user identity is essential in many applications of electronic identity (eID) systems. A feasible approach to realize such a privacy-preserving eID is the usage of group signature protocols or pseudonym-based signatures. However, providing a revocation mechanism that preserves privacy is often the bottleneck for the scalability of such a system. In order to bridge this gap between practicability and privacy, we propose a new pseudonym-based mobile eID signature scheme suitable for smart cards and secure elements that also enables efficient and scalable revocation checks. By using a pseudorandom function, we derive one-time verification tokens used for identity verification as well as revocation checks and generate proofs of validity using a new method referred to as disposable dynamic accumulators. Our scheme preserves unlinkability and anonymity of the eID holder even beyond revocation and does not require online connectivity to a trusted party for verification and revocation checks.

Constrained pseudorandom functions (CPRF) are an enriched variant of traditional pseudorandom functions (PRF)—a fundamental tool of modern cryptography. A CPRF enables a master PRF key holder to issue constrained keys corresponding to specific constraint predicates over the input domain. A constrained key can be used to evaluate the PRF on inputs accepted by the associated constraint predicate, while the PRF outputs on the rest of the inputs still remain computationally indistinguishable from uniformly random values. A constrained verifiable pseudorandom function (CVPRF) enhances a CPRF by adding a non-interactive public verification mechanism for checking the correctness of PRF evaluations. On the other hand, a delegatable constrained pseudorandom function (DCPRF) augments a CPRF with the ability to empower constrained key holders to delegate further constrained keys that allow PRF evaluations on inputs accepted by more restricted constraint predicates compared to ones embedded in their own constrained keys. Until recently, all the proposed constructions of CPRFs and their extensions (i) either could handle constraint predicates representable as circuits or (ii) were based on risky knowledge-type assumptions. In EUROCRYPT 2016, Deshpande et al. presented a CPRF supporting constraint predicates realizable by Turing machines (TM) based on indistinguishability obfuscation and injective pseudorandom generators. Their construction was claimed to be selectively secure. The first contribution of this paper is demonstrating that their claim is not valid. In fact, their CPRF construction can actually be proven secure not in the selective model, rather in a significantly weaker one where the adversary is completely static. We then modify their construction with innovative techniques so as to make the resulting CPRF selectively secure. Towards our goal, we suitably redesign the security proof as well. Most significantly, our modification does not involve any additional heavy duty cryptographic tool. Next, employing only standard public key encryption, we extend our improved CPRF construction to present the first ever CVPRF and DCPRF constructions that can handle constraints expressible as TMs.

To ensure security and obtain fine-grained data access control policies in many management domains, multi-authority attribute-based encryption (MA-ABE) schemes were presented and have been applied in cloud storage system. There exist certain scenes where the application domains managed by different attribute authorities ($$ AAs $$) often change, and hence domain managements require more autonomous and independent. However, most of existing schemes do not support flexible managements. In order to support dynamic managements, we propose a new decentralized ciphertext-policy MA-ABE scheme with mediated obfuscation (MA-DCP-ABE-WMO) where each of $$ AAs $$ works independently without any interaction with other $$ AAs $$. When issuing a secret key to a user, each of $$ AAs $$ uses his secret to compute a share of the system master secret. Data are encrypted under the public keys of attribute management domains. To resist collusion attack, a common pseudorandom function $$ PRF( \cdot ) $$ is shared among $$ AAs $$ and is used to randomize each user’s global identifier $$ Gid $$. The randomized $$ Gid $$ is adopted to unify all target messages which need to be reconstructed from different management domains. We first introduce the mediated obfuscation (MO) model into MA-ABE scheme to provide online service and the interaction works among data owner, data user and the mediator. In the MO model, we define a special functional encryption scheme where the function program can be coded into an element of the multiplicative cyclic group. We obfuscate the function by randomly selecting a blinding factor to conduct exponent arithmetic with the base of the function. A special input of the function is constructed to cancel the blinding factor when calling the obfuscated function. It makes other participants know nothing about the inner function program but can evaluate the function program. Furthermore, the MA-DCP-ABE-WMO scheme is proved to be secure. Compared with related schemes, our scheme is suitable to dynamic domain managements. When the management domains are added or removed, the workload to update original ciphertexts and private keys is dramatically reduced.

Wireless sensor networks (WSNs) deployed in hostile environments for applications such as battle-field surveillance are vulnerable to various attacks, including node capture attack wherein an adversary physically captures, reprograms, and redeploys a node in the network. In this paper, we present a novel approach of program integrity verification (PIV) protocol to detect whether a node is captured. The cluster head equipped with trusted platform module (TPM) verifies by comparing the program memory content of the sensor node before and after capture. The proposed TPM-enabled PIV (TPIV) protocol uses dynamically computed hash-based key and pseudorandom function for detection of a captured node in the network. The security analysis of the TPIV protocol reveals that the probability of a node capture attack victim eluding the PIV and leaking the secret of any noncaptured node is negligible. The proposed TPIV protocol can detect the captured node even in the presence of a strong adversary capable of putting additional memory to elude the PIV. With the results of analytical and experimental comparisons, we show the performance improvement of TPIV protocol in terms of low communication, computation, and storage overhead as compared to the related protocols for PIV in WSN.

The golden collision problem asks us to find a single, special collision among the outputs of a pseudorandom function. This generalizes meet-in-the-middle problems, and is thus applicable in many contexts, such as cryptanalysis of the NIST post-quantum candidate SIKE.

Oblivious Pseudorandom Function (OPRF) is a protocol between a client holding input x and a server holding key k for a PRF F. At the end, the client learns \(F_k(x)\) and nothing else while the server learns nothing. OPRF’s have found diverse applications as components of larger protocols, and the currently most efficient instantiation, with security proven in the UC model, is \(F_k(x)=H_2(x,(H_1(x))^k)\) computed using so-called exponential blinding, i.e. the client sends \(a=(H_1(x))^r\) for random r, the server responds \(b=a^k\), which the client unblinds as \(v=b^{1/r}\) to compute \(F_k(x)=H_2(x,v)\).

In this work we present a new construction for a batched Oblivious Pseudorandom Function (OPRF) based on Vector-OLE and the PaXoS data structure. We then use it in the standard transformation for achieving Private Set Intersection (PSI) from an OPRF. Our overall construction is highly efficient with O(n) communication and computation. We demonstrate that our protocol can achieve malicious security at only a very small overhead compared to the semi-honest variant. For input sizes \(n = 2^{20}\), our malicious protocol needs 6.2 s and less than 59 MB communication. This corresponds to under 450 bits per element, which is the lowest number for any published PSI protocol (semi-honest or malicious) to date. Moreover, in theory our semi-honest (resp. malicious) protocol can achieve as low as 219 (resp. 260) bits per element for \(n=2^{20}\) at the added cost of interpolating a polynomial over n elements.

Catalano and Fiore propose a scheme to transform a linearly-homomorphic encryption into a homomorphic encryption scheme capable of evaluating quadratic computations on ciphertexts. Their scheme is based on the linearly-homomorphic encryption (such as Goldwasser-Micali, Paillier and ElGamal) and need to perform large integer operation on servers. Then, their scheme have numerous computations on the servers. At the same time, their scheme cannot verify the computations and cannot evaluate more than degree-4 computations. To solve these problems, we no longer use linearly-homomorphic encryption which based on number theory assumptions. We use label and pseudorandom function to encrypt message, which significantly reduce the computations on the servers and enable us to use homomorphic MACs technology to realize verifiable computations naturally. We also extend the method to construct $d$-server schemes, which allow the client to delegate degree-$d$ computations on outsourced data., Comment: IEEE Transactions on Cloud Computing

Verifiable Oblivious Pseudorandom Functions (VOPRFs) are protocols that allow a client to learn verifiable pseudorandom function (PRF) evaluations on inputs of their choice. The PRF evaluations are computed by a server using their own secret key. The security of the protocol prevents both the server from learning anything about the client’s input, and likewise the client from learning anything about the server’s key. VOPRFs have many applications including password-based authentication, secret-sharing, anonymous authentication and efficient private set intersection. In this work, we construct the first round-optimal (online) VOPRF protocol that retains security from well-known subexponential lattice hardness assumptions. Our protocol requires constructions of non-interactive zero-knowledge arguments of knowledge (NIZKAoK). Using recent developments in the area of post-quantum zero-knowledge arguments of knowledge, we show that our VOPRF may be securely instantiated in the quantum random oracle model. We construct such arguments as extensions of prior work in the area of lattice-based zero-knowledge proof systems.

Farfalle, a permutation-based construction for building a pseudorandom function (PRF), is really versatile. It can be used for message authentication code, stream cipher, key derivation function, authenticated encryption and so on. Farfalle construction relies on a set of permutations and on so-called rolling functions: it can be split into a compression layer followed by a two-step expansion layer.

We study the problem of batch verification for verifiable delay functions (VDFs), focusing on proofs of correct exponentiation (PoCE), which underlie recent VDF constructions. We show how to compile any PoCE into a batch PoCE, offering significant savings in both communication and verification time. Concretely, given any PoCE with communication complexity c, verification time t and soundness error \(\delta \), and any pseudorandom function with key length \(\mathsf{k}_\mathsf{prf}\) and evaluation time \( t_\mathsf{prf}\), we construct: A batch PoCE for verifying n instances with communication complexity \(m\cdot c +\mathsf{k}_\mathsf{prf}\), verification time \(m\cdot t + n\cdot m\cdot O(t_\mathsf{op} + t_\mathsf{prf})\) and soundness error \(\delta + 2^{-m}\), where \(\lambda \) is the security parameter, m is an adjustable parameter that can take any integer value, and \(t_\mathsf{op}\) is the time required to evaluate the group operation in the underlying group. This should be contrasted with the naive approach, in which the communication complexity and verification time are \(n \cdot c\) and \(n \cdot t\), respectively. The soundness of this compiler relies only on the soundness of the underlying PoCE and the existence of one-way functions. An improved batch PoCE based on the low order assumption. For verifying n instances, the batch PoCE requires communication complexity \(c +\mathsf{k}_\mathsf{prf}\) and verification time \(t + n\cdot (t_\mathsf{prf} + \log (s)\cdot O(t_\mathsf{op}))\), and has soundness error \(\delta + 1/s\). The parameter s can take any integer value, as long as it is hard to find group elements of order less than s in the underlying group. We discuss instantiations in which s can be exponentially large in the security parameter \(\lambda \).

A weak pseudorandom function (weak PRF) is one of the most important cryptographic primitives for its efficiency although it has lower security than a standard PRF.

We consider a generalized construction of stream ciphers with forward security. The design framework is modular: it is built from a so-called layer function that updates the key and (optionally) the nonce and generates a new pseudorandom output stream. We analyze the generalized construction for four different instantiations: two possible layer functions that are in turn instantiated with either a block cipher or a pseudorandom function. We prove that each of these instantiations gives a stream cipher that is pseudorandom and forward secure in the multi-user setting with a very tight bound. A comprehensive analysis shows that the two block cipher based instantiations achieve very similar bounds. For the pseudorandom function based instantiations there is no clear winner: either layer can be beneficial over the other one, depending on the choice of parameters. By instantiating the pseudorandom function with a generic construction such as the sum of permutations, we obtain a highly efficient and competitive stream cipher based on an n-bit block cipher that is secure beyond the $2^{\text {n}/2}$ birthday bound.

The construction of Power LTE Private Network privacy protection authentication protocol based on a symmetric cryptosystem is a hot issue in academic and industrial research. The integrity privacy protection protocol is not efficient enough, because it is necessary to exhaustively search all terminals in the system, which is difficult to apply to the environment of mass terminals in the Internet of Things. This paper presents a method for constructing an efficient privacy protection authentication protocol for power LTE private network terminals. This protocol uses a single-bit output pseudo-random function. In this paper, the authentication process of the protocol is broken down into multiple steps. Compared with traditional protocols, the proposed protocol significantly improves search efficiency. The protocol has privacy and small computational overhead, so it can be applied to the network environment of a large number of terminals.

MuSig is a multi-signature scheme for Schnorr signatures, which supports key aggregation and is secure in the plain public key model. Standard derandomization techniques for discrete logarithm-based signatures such as RFC~6979, which make the signing procedure immune to catastrophic failures in the randomness generation, are not applicable to multi-signatures as an attacker could trick an honest user into producing two different partial signatures with the same randomness, which would reveal the user's secret key. In this paper, we propose a variant of MuSig in which signers generate their nonce deterministically as a pseudorandom function of the message and all signers' public keys and prove that they did so by providing a non-interactive zero-knowledge proof to their cosigners. The resulting scheme, which we call MuSig-DN, is the first Schnorr multi-signature scheme with deterministic signing. Therefore its signing protocol is robust against failures in the randomness generation as well as attacks trying to exploit the statefulness of the signing procedure, e.g., virtual machine rewinding attacks. As an additional benefit, a signing session in MuSig-DN requires only two rounds instead of three as required by all previous Schnorr multi-signatures including MuSig. To instantiate our construction, we identify a suitable algebraic pseudorandom function and provide an efficient implementation of this function as an arithmetic circuit. This makes it possible to realize MuSig-DN efficiently using zero-knowledge proof frameworks for arithmetic circuits which support inputs given in Pedersen commitments, e.g., Bulletproofs. We demonstrate the practicality of our technique by implementing it for the secp256k1 elliptic curve used in Bitcoin.

Private set intersection (PSI) is a hot topic in cryptography and has a wide range of applications such as privacy preserving personal properties matching and data mining. Many PSI protocols have been presented, which discussed the efficiency and formal security. However, there are few PSI protocols for the cloud computing environments, where the cloud server offers effective computations and storage capabilities to clients and performs the PSI computations for clients. In this paper, we propose an efficient PSI protocol for the cloud computing environments, which is based on homomorphic encryption, pseudorandom function, set polynomial representation, and point-value form of polynomials. Our PSI protocol enjoys the following advantages: (a) our protocol gives a natural secure data storage; (b) normal channels are suitable to our protocol; (c) the communication and computation complexity are linear to the dataset size; (d) our protocol provides a formal detailed simulated-based security proof; (e) our protocol is a scalable protocol that could be extended to multiple clients conveniently, and a formal simulated-based security proof is provided in details.

Large-scale quantum computing poses a major threat to classical public-key cryptography. Recently, strong &ldquo, quantum access&rdquo, security models have shown that numerous symmetric-key cryptosystems are also vulnerable. In this paper, we consider classical encryption in a model that grants the adversary quantum oracle access to encryption and decryption, but where we restrict the latter to non-adaptive (i.e., pre-challenge) queries only. We formalize this model using appropriate notions of ciphertext indistinguishability and semantic security (which are equivalent by standard arguments) and call it QCCA 1 in analogy to the classical CCA 1 security model. We show that the standard pseudorandom function ( PRF )-based encryption schemes are QCCA 1 -secure when instantiated with quantum-secure primitives. Our security proofs use a strong bound on quantum random-access codes with shared randomness. Revisiting plain IND - CPA -secure Learning with Errors ( LWE ) encryption, we show that leaking only a single quantum decryption query (and no other leakage or queries of any kind) allows the adversary to recover the full secret key with constant success probability. Information-theoretically, full recovery of the key in the classical setting requires at least a linear number of decryption queries. Our results thus challenge the notion that LWE is unconditionally &ldquo, just as secure&rdquo, quantumly as it is classically. The algorithm at the core of our attack is a new variant of the well-known Bernstein&ndash, Vazirani algorithm. Finally, we emphasize that our results should not be interpreted as a weakness of these cryptosystems in their stated security setting (i.e., post-quantum chosen-plaintext secrecy). Rather, our results mean that, if these cryptosystems are exposed to chosen-ciphertext attacks (e.g., as a result of deployment in an inappropriate real-world setting) then quantum attacks are even more devastating than classical ones.

Traceable ring signature (TRS), a variant of ring signature, allows a signer to sign a message anonymously labeled with a tag on behalf of a group of users, but may reveal the signer’s identity if he creates two signatures with the same tag. TRS provides accountable anonymity for users, and serves as an important role in e-voting systems and e-coupon services. However, current TRS schemes are built on hard problems in number theory that cannot resist quantum attackers. To address this issue, first, we propose a general framework of TRS, by using a non-interactive zero-knowledge proof of knowledge, a collision-resistant hash function, and a pseudorandom function with some additional properties. Then, we construct an efficient TRS scheme in the quantum random oracle model, by instantiating the framework with appropriate lattice-based building blocks. Moreover, the signature size of the lattice-based TRS is logarithmic in the ring size.

In this work, we introduce the notion of puncturable witness pseudorandom function (pWPRF) which is a stronger variant of WPRF proposed by Zhandry, TCC 2016. The punctured technique is similar to what we have seen for puncturable PRFs and is capable of extending the applications of WPRF. Specifically, we construct a semi-adaptively secure offline witness encryption (OWE) scheme using a pWPRF, an indistinguishability obfuscation (\(i\mathcal {O}\)) and a symmetric-key encryption (SKE), which enables us to encrypt messages along with NP statements. We show that replacing \(i\mathcal {O}\) with extractability obfuscation, the OWE turns out to be an extractable offline witness encryption scheme. To gain finer control over data, we further demonstrate how to convert our OWEs into offline functional witness encryption (OFWE) and extractable OFWE. All of our OWEs and OFWEs produce an optimal size ciphertext, in particular, encryption of a message is as small as the size of the message plus the security parameter multiplied with a constant, which is optimal for any public-key encryption scheme. On the other hand, in any previous OWE, the size of a ciphertext increases polynomially with the size of messages. Finally, we show that the WPRF of Pal et al. (ACISP 2019) can be extended to a pWPRF and an extractable pWPRF.

An oblivious PRF, or OPRF, is a protocol between a client and a server, where the server has a key k for a secure pseudorandom function F, and the client has an input x for the function. At the end of the protocol the client learns F(k, x), and nothing else, and the server learns nothing. An OPRF is verifiable if the client is convinced that the server has evaluated the PRF correctly with respect to a prior commitment to k. OPRFs and verifiable OPRFs have numerous applications, such as private-set-intersection protocols, password-based key-exchange protocols, and defense against denial-of-service attacks. Existing OPRF constructions use RSA-, Diffie-Hellman-, and lattice-type assumptions. The first two are not post-quantum secure.

Authenticated encryption refers to symmetric cryptography providing both privacy and authenticity. It is most common to construct it as a block-cipher mode of operation. Another promising approach is to construct it based on cryptographic hashing. This paper proposes a nonce-based authenticated encryption scheme based on the Lesamnta-LW hashing mode. Lesamnta-LW is a block-cipher-based iterated hash function, which is specified in the ISO/IEC 29192-5 lightweight hash-function standard. This paper also shows that the proposed scheme is secure if the underlying block cipher is a pseudorandom permutation. Both of the other ISO/IEC 29192-5 mechanisms, PHOTON and SPONGENT, are hardware-oriented sponge-based hash functions, and nonce-based authenticated encryption schemes can also be constructed based on them. On the other hand, Lesamnta-LW is a software-oriented Merkle-Damgard hash function. Thus, the proposed scheme is a new option for authenticated encryption based on lightweight cryptographic hashing.

A software watermarking scheme can embed a message into a program without significantly changing its functionality. Moreover, any attempt to remove the embedded message in a marked program will substantially change the functionality of the program. Prior constructions of watermarking schemes focus on watermarking cryptographic functions, such as pseudorandom function (PRF), public key encryption, etc.

We build symmetric encryption schemes from a pseudorandom function/permutation with domain size N which have very high security – in terms of the amount of messages q they can securely encrypt – assuming the adversary has \(S < N\) bits of memory. We aim to minimize the number of calls k we make to the underlying primitive to achieve a certain q, or equivalently, to maximize the achievable q for a given k. We target in particular \(q \gg N\), in contrast to recent works (Jaeger and Tessaro, EUROCRYPT ’19; Dinur, EUROCRYPT ’20) which aim to beat the birthday barrier with one call when \(S < \sqrt{N}\).

In a threshold symmetric-key encryption (\(\text {TSE}\)) scheme, encryption/decryption is performed by interacting with any threshold number of parties who hold parts of the secret-keys. Security holds as long as the number of corrupt (possibly colluding) parties stay below the threshold. Recently, Agrawal et al. [CCS 2018] (alternatively called DiSE) initiated the study of \(\text {TSE}\). They proposed a generic \(\text {TSE}\) construction based on any distributed pseudorandom function (DPRF). Instantiating with DPRF constructions by Naor, Pinkas and Reingold [Eurocrypt 1999] (also called NPR) they obtained several efficient TSE schemes with various merits. However, their security models and corresponding analyses consider only static (and malicious) corruption, in that the adversary fixes the set of corrupt parties in the beginning of the execution before acquiring any information (except the public parameters) and is not allowed to change that later.

Particular instantiations of the Offset Merkle Damgard authenticated encryption scheme (OMD) represent highly secure alternatives for AES-GCM. It is already a fact that OMD can be efficiently implemented in software. Given this, in our paper we focus on speeding-up OMD in hardware, more precisely on FPGA platforms. Thus, we propose a new OMD instantiation based on the compression function of BLAKE2b. Moreover, to the best of our knowledge, we present the first FPGA implementation results for the SHA-512 instantiation of OMD as well as the first architecture of an online authenticated encryption system based on OMD.

Password-Based Key-Derivation Function 2 (PBKDF2) is commonly employed to derive secure keys from a password in real life such as file encryption and implementation of authentication systems. Nevertheless, owing to the limited entropy of the password, the security of the generated keys is lower than that of the normally generated keys. To address this, issue increase the number of iterative operations during the PBKDF2 may increase. However, the higher the number of iterative operations, the more time it takes to generate the key. This paper presents various techniques for optimizing the performance of PBKDF2. The main idea of our proposed methods is to reduce redundant block operations and to optimize Pseudo Random Function (PRF) itself by combining operations and making full use of fixed values within PBKDF2. As the underlying hash function in PRF, we utilize two algorithms: Hash-based Message Authentication Code-Secure Hash Algorithm 256 (HMAC-SHA256) and HMAC-Lightweight Secure Hash 256 (HMAC-LSH256) (SHA256 is the most widely used hash function and LSH256 was recently developed hash function in South Korea). With the proposed techniques, the proposed implementation of PBKDF2-HMAC-SHA256 provides a performance enhancement of about 135.27% over the reference implementation provided by Korea Internet & Security Agency (KISA) and about 80.21% over OpenSSL. Concerning PBKDF2-HMAC-LSH256, the proposed implementation provides a huge performance enhancement of about 330.48% over the reference implementation provided by KISA. With the proposed implementation, more iteration operations can be possible for higher security. Furthermore, we can use the proposed techniques to optimize PBKDF2 performance on embedded MCUs.

Correlated secret randomness is a useful resource for many cryptographic applications. We initiate the study of pseudorandom correlation functions (PCFs) that offer the ability to securely generate virtually unbounded sources of correlated randomness using only local computation. Concretely, a PCF is a keyed function $F_{k}$ such that for a suitable joint key distribution ( $k_{0}, k_{1}$ ), the outputs $(f_{k_{0}}(x), f_{k_{1}}(x))$ are indistinguishable from instances of a given target correlation. An essential security requirement is that indistinguishability hold not only for outsiders, who observe the pairs of outputs, but also for insiders who know one of the two keys. We present efficient constructions of PCFs for a broad class of useful correlations, including oblivious transfer and multiplication triple correlations, from a variable-density variant of the Learning Parity with Noise assumption (VDLPN). We also present several cryptographic applications that motivate our efficient PCF constructions. The VDLPN assumption is independently motivated by two additional applications. First, different flavors of this assumption give rise to weak pseudorandom function candidates in depth-2 $\text{AC}^{0}[\oplus]$ that can be conjectured to have subexponential security, matching the best known learning algorithms for this class. This is contrasted with the quasipolynomial security of previous (higher-depth) $\text{AC}^{0}[\oplus]$ candidates. We support our conjectures by proving resilience to several classes of attacks. Second, VDLPN implies simple constructions of pseudorandom generators and weak pseudorandom functions with security against XOR related-key attacks.