Practical witness encryption for algebraic languages or how to encrypt under Groth-Sahai proofs
type: Item
instance of: scholarly article
title: Practical witness encryption for algebraic languages or how to encrypt under Groth-Sahai proofs
zbMATH Open document ID: 1408.68057
author: David Derler
author: Daniel Slamanig
published in: Designs, Codes and Cryptography
publication date: 2018-10-10T00:00:00Z
review text: A language \(L\subset (0+1)^*\) in NP has a witnessing relation \(R\subset [(0+1)^*]^2\) associated such that \[ \forall x\in (0+1)^* \left[x\in L\;\Longleftrightarrow\;\exists w\in (0+1)^*: (x,w)\in R\right]. \] For any word \(x\in L\), the corresponding witness \(w\) is hard to be found in terms of \(x\) itself. A witness encryption (WE) scheme, in rather general terms, consists of two probabilistic polynomial-time maps: an encryption map \(\operatorname{Enc}:(\text{par},x,\mu)\mapsto c\), here \(\mu\) is a plain text, \(c\) is the cipher text and par is a list of parameters, and a decryption map \(\operatorname{Dec}:(w,c)\mapsto \mu\) such that \(\left((x,w)\in R\;\Longrightarrow\operatorname{Pr}\left[\operatorname{Dec}(w,\operatorname{Enc}(\operatorname{par},x,\mu) = \mu)\right] = 1\right).\) The words in the language \(L\) act as a kind of public keys, while the corresponding witnesses are the private keys. On the other hand, suppose that for a keyed hash function \(h:(k,x) \mapsto v\), where \(k\) is a key, \(x\) is a plain text and \(v\) is the produced hash value, there is constructed, for a language \(L\), a corresponding keyed projective hashing map \(h_L:(k_L,x,w) \mapsto v\), where \(k_L\) is a secondary key depending on the key \(k\), such that \(\left((x,w)\in R\;\Longrightarrow\;h_L(k_L,x,w) = h(k,x)\right).\) The hash map is smooth if it is statistically indistinguishable from a uniformly distributed random variable. In this paper a WE scheme is proposed based the above smooth projective hash functions. Bob (the sender) is ciphering his messages to Alice (the receiver), who should be the unique person able to decipher the received messages. They fix a language \(L\). Alice publishes a set \(A\subset L\) such that for any \(x\in A\) Alice is able to find a corresponding witness \(w\). Initially a procedure is given to cipher just a bit \(b\in\{0,1\}\). {\begin{itemize}\item[Encryption.] If \(b=0\), then the cipher text is chosen randomly, else Bob sel…
reviewed by: Guillermo Morales Luna
Mathematics Subject Classification ID: 68P25
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 94A60
zbMATH DE Number: 6951309
zbMATH Keywords: witness encryption
zbMATH Keywords: smooth projective hash functions
zbMATH Keywords: algebraic languages
zbMATH Keywords: Groth-Sahai proofs
zbMATH Keywords: encryption
zbMATH Keywords: privacy
MaRDI profile type: Publication
full work available at URL: s10623-018-0460-y
OpenAlex ID: W2787848470
Wikidata QID: Q113903988
cites work: Smooth Projective Hashing for Conditionally Extractable Commitments
cites work: Disjunctions for Hash Proof Systems: New Constructions and Applications
cites work: Offline Witness Encryption
cites work: Adaptive Witness Encryption and Asymmetric Password-Based Cryptography
cites work: Policy-Based Signatures
cites work: Efficient UC-Secure Authenticated Key-Exchange for Algebraic Languages
cites work: New Techniques for SPHFs and Efficient One-Round PAKE Protocols
cites work: Structure-Preserving Smooth Projective Hashing
cites work: Q4783728
cites work: Advances in Cryptology – CRYPTO 2004
cites work: Publicly Evaluable Pseudorandom Functions and Their Applications
cites work: Optimal Randomness Extraction from a Diffie-Hellman Element
cites work: Q4249317
cites work: Q4737235
cites work: Conditional Oblivious Transfer and Timed-Release Encryption
cites work: An Algebraic Framework for Diffie-Hellman Assumptions
cites work: Predictable Arguments of Knowledge
cites work: Candidate indistinguishability obfuscation and functional encryption for all circuits
cites work: Witness encryption and its applications
cites work: On the Implausibility of Differing-Inputs Obfuscation and Extractable Witness Encryption with Auxiliary Input
cites work: Witness Encryption from Instance Independent Assumptions
cites work: Probabilistic encryption
cites work: How to Run Turing Machines on Encrypted Data
cites work: Efficient Non-interactive Proof Systems for Bilinear Groups
cites work: A Pseudorandom Generator from any One-way Function
cites work: Practical Covert Authentication
cites work: Private Mutual Authentication and Conditional Oblivious Transfer
cites work: Round-Optimal Password-Based Authenticated Key Exchange
cites work: Group Encryption
cites work: A New Randomness Extraction Paradigm for Hybrid Encryption
cites work: Fuzzy Identity-Based Encryption
cites work: Efficient Chosen-Ciphertext Security via Extractable Hash Proofs
cites work: How to Avoid Obfuscation Using Witness PRFs
DOI: 10.1007/S10623-018-0460-Y
description: scientific article; zbMATH DE number 6951309