Questions tagged [verifiability]

Verifiable encryption is an encryption scheme where one can prove some property of a message m, while the message is given in an encrypted form. When an encryption scheme is secure, the encryption E(m) should reveal no information regarding m.

Filter by
Sorted by
Tagged with
1
vote
1answer
61 views

What's the least computationally expensive way to verify a message is from who they say they are?

We're building an ingame GPS system where only 5 lines of code are executed a second. We're starting to face problems with people spoofing the satellites we use to triangulate. Is it feasible to ...
0
votes
0answers
19 views

Generate version 3 x509 certificate from version 1 CA

Please do forgive me for my naivety. I have inherited a legacy system wherein the CA which signs the certificate is of version 1. Is it possible to generate a x509 version 3 certificate which is ...
0
votes
1answer
14 views

Allowing third party to verify and/or replay a draw

I’m not an expert in crypto, and I would like to design draw system (like a lottery, but choosing one of the participants), the most open possible, allowing a third party to verify the data/draws, and ...
1
vote
1answer
64 views

How to compute certificates using Diffie-Hellman key exchange with certificates and Elgamal signature scheme

We consider the Diffie–Hellman key exchange scheme with certificates. We have a system with the three users Alice, Bob and Charley. The Diffie–Hellman algorithm uses p = 61 and α = 18. The three ...
3
votes
2answers
229 views

Certificate validation on an IoT device using few bytes

I'm trying to validate if an IoT device is authentic or it's a fraud. The problem is I only have 17 bytes to do that verification. What if I let the IoT device sign the message with the private key ...
1
vote
1answer
52 views

Scheme to verify AES key was correctly encrypted for public key recipient

In our file sharing scenario there are three participants: $A$, $B$ and $C$. Each participant has a public-private key pair (let's assume RSA for now). $A$ wants to share a symmetric AES key $k$ with ...
0
votes
1answer
60 views

Publicly verifiable secret sharing scheme

In https://www.win.tue.nl/~berry/papers/crypto99.pdf, Schoenmakers proposes a publicly verifiable secret sharing scheme, that uses a non-interactive DLEQ proof to allow any participant to verify the ...
0
votes
1answer
65 views

Secret sharing scheme verifiability

This secret sharing scheme takes place in the polynomial ring over a finite field $F_p[x]$, $p$ being a large prime, in the following simplified way: The dealer chooses a private polynomial $f(x)$. ...
2
votes
0answers
25 views

What are some examples of out of bound channels that work over the Internet in practice?

If I want to verify a public key (be it RSA, PGP, etc.) with another client over the Internet only, what are some viable out-of-bound channels for verification? Which channels have been used in ...
2
votes
1answer
83 views

Does anyone know an easily creatable asymmetric cryptosystem for usage in VDF?

I've read multiple papers about VDFs (1, 2, etc.). I look for a lighter alternative to El-Gamal regarding cryptosystem creation. It can be anything exotic too, but it would be nice to have at least ...
4
votes
2answers
258 views

Verifiable delay functions vs Proof of Sequential Work

I've read recent papers about verifiable delay functions (Boneh et al 2018) and proof of sequential works (Cohen et al. 2018). I understand that the core difference between the definitions is that a ...
3
votes
2answers
158 views

Verify partial message given hash of full message

I need to verify partial downloads (retrieved sequentially), given a (preferably short) hash of the complete download. Given a message $m_0 \mathbin\| m_1 \mathbin\| m_2 \mathbin\| \cdots$, hash ...
3
votes
1answer
150 views

Verifiable Encryption of a Pedersen Commitment

Can the Verifiable Encryption of a Discrete Logarithm scheme of the paper https://www.shoup.net/papers/verenc.pdf (page 19) be used to verify that a ciphertext encrypts the same value committed in a ...
0
votes
1answer
29 views

Can randomness protect a list of signatures against forgery attacks?

Suppose we have a list of signatures $S = [s_1, .., s_n]$ for a list of messages $M = [m_1, .., m_n]$, and we want to verify that $S$ is a valid signature of $M$, so each $s_i$ should be valid for ...
5
votes
1answer
169 views

Is this an error in the Pinocchio Protocol paper

I am going through the Pinocchio protocol paper and I need 2 clarifications in the section Protocol 1 (Verifiable Computation from strong QAP). The part that explains the Verify process, which ...
0
votes
0answers
47 views

Verifying valid public key and finding private key? [duplicate]

A naive user of RSA has announced the public key $n = 2903239, e = 5$. Eve has worked out that $n = 1237×2347$. Verify that the public key is valid and explain why the private key is $d = 2319725$. [...
1
vote
1answer
115 views

How can I generate large primes for Pedersen commitment?

I want to make a commitment on Shamir's Secret Sharing, based on the work of Pedersen, "Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing". To implement the commitment ...
2
votes
1answer
153 views

Does this description of verifiable random functions seem accurate?

I've been thinking about verifiable random functions recently due to my interest in sortition (random selection of political officials). I wrote up this little paragraph below, and I'm wondering: Does ...
1
vote
1answer
99 views

Verification in Threshold RSA or Threshold Paillier

In the key generation of the threshold version of RSA or the threshold version of the Paillier cryptosystem (e.g. "Shoup - 2000 - Practical threshold signatures" or "Fouque et al. - 2000 - Sharing ...
4
votes
1answer
78 views

Lightweight primality certificates for untrusted DH parameters

Are there any light-weight techniques to generate primality certificates for custom Diffie-Hellman parameters that could be sent to the client to allow it to verify primality without needing to run ...
1
vote
2answers
90 views

Constraint about encrypted values

Let V = $[x_1,\ldots ,x_n]$ be a binary vector of length $n$, and let $E(V)$ be the entrywise encryption of this vector. Suppose I want to give to another player, $E(V)$, but also let him have the ...
-1
votes
1answer
244 views

Random number generator in a 2p2 Network

for my thesis I am trying to develop a system where nodes from a peer to peer network agree in generate a random number every tot seconds. I am stocked in this problem since almost 1 week anyone can ...
2
votes
0answers
418 views

Can Verifiable Random Functions be used to pick a random node from a pool?

Let's say that I have a decentralized system and I have a list of nodes published on a public log like a blockchain. I want a node A to be able to connect to ...
2
votes
0answers
83 views

Are there any information-theoretically secure verifiable secret sharing protocols with t=n?

Disregarding matters such as efficiency and round complexity, can verifiable secret sharing be done in a way such that the secret cannot be decoded unless you have all n shares, and that this ...
3
votes
2answers
169 views

Why does the prover in an interactive proof run in exponential time with the space of the computation?

I'm currently trying to gain an understanding of verifiable computation and the strengths and weaknesses of past approaches. In particular, I've been watching the following YouTube video which talks ...
2
votes
4answers
197 views

Is it possible to verify and relay an encryption key with a trusted but transparent third party?

I'm wondering if it would be possible to implement this functionality with a trusted but transparent third party (maybe an Ethereum smart contract?): Bob has an encryption key. Alice has the ...
3
votes
1answer
264 views

zkSnarks - why isn't PCD more widely used?

I've been reading the paper Scalable Zero Knowledge from Cycles of Elliptic Curves, which elegantly solves (what seems to me) the main problem with zkSnarks; namely that performing non-trivial ...
2
votes
2answers
241 views

How can I prove the result of a long computation with a short string?

I have a simple program F (think of a cellular automaton) that, when executed in some input X, takes a while to complete and ...
5
votes
1answer
528 views

Proof of encrypted content

I would like to create a server that would verify a public/private key pair where the private key is encrypted with a key unknown to the server. The server should reject the keypair if the encrypted ...
2
votes
1answer
140 views

Verifiable computation on signed data

Consider the following setting. Alice receives a chunk of data from Victor, together with a cryptographic certificate of authenticity of some sort (eg hash signed with Victor’s private key). Bob ...
1
vote
1answer
96 views

how to efficiently prove the query result is empty?

Consider a simplified scenario. Suppose an untrusted server holds a set of data $A=\{ a_1,a_2,\cdots,a_n\}$. A client issues a query $b$ to the server and wants to decide if $b\in A$. The server ...
9
votes
1answer
1k views

What is the difference between signatures and VRF?

For example we have asymmetric signature scheme(RSA or ECC based) and VRF(also can be RSA/ECC based), both of them can be verified using public key of the signer/hasher and also are unique for each ...
5
votes
2answers
85 views

Swap information

Alice is trading information with Bob. Alice and Bob are in a Prisoner's Dilemma in that they'd prefer not sending their respective key while receiving each other's but would prefer an exchange taking ...
1
vote
1answer
200 views

Is there a way to verify an original author using encryption?

I feel like the title explains the problem fairly well. Is is possible to use encryption to verify a document's original author? In my case, I have a doc that I want to release online. Is there a way ...
0
votes
1answer
80 views

Verify membership of an item within a set while obscuring the number of elements in the set?

I'm wondering whether it is possible to achieve the following scenario: Say you have a set of names {Alice, Bob, Jake}. To verify that the name 'Bob' exists in the set, you can simply compare 'Bob' ...
4
votes
1answer
199 views

Only allow specific types of data to be transmitted via an end-to-end encryption service

I have a service that allows multiple parties to share domain-specific textual data. This data is also end-to-end encrypted. How can I be sure the sharing parties don't send non-domain-specific data, ...
2
votes
1answer
92 views

Public key verification schemes

I have a short question. Besides PKI, Web of Trust or secure out of band communication. Is there any other way to verify the public key of a communicating party? In other words, let's assume an ...
9
votes
3answers
384 views

Can a device prove the identity of its own code?

Say you have a computing system that has some functionality that is not in itself cryptographically secure, but you want to make sure is executed as specified, and, e.g. an adversary hasn't re-flashed ...
2
votes
1answer
243 views

Plausible Deniability in Schnorr

How does a dishonest verifier affect plausible deniability of the interactive Schnorr protocol?
1
vote
1answer
820 views

Quality test for an hardware source of randomness

Say that I developed an hardware source of randomness, which I would like to use to seed a cryptographically secure random number generator. How would I go about testing it? Are there standardized ...
9
votes
2answers
687 views

Universally verifiable random beacon

I am developing a network where potentially many many nodes (billions, in principle?) should be able to agree on a random number. I would really prefer to avoid $O(N^2)$ procedures where everyone ...
10
votes
1answer
804 views

Is there a formal language to define a cryptographic protocol?

I wanted to work on a personal project where I would attempt to identify the flaws in a cryptographic protocol. Now for that to work properly, the program should understand the syntax of protocol ...
4
votes
1answer
170 views

Why is cryptographic model not considered formal methods?

I have just started looking at different methods for analyzing the security of cryptographic protocols. According to my reading, there are two main approaches in this area. The first approach is so-...
25
votes
2answers
4k views

Formal verification in cryptography

I have seen in some places that people use formal verification and/or computer-aided verification for cryptography (tools like ProVerif, CryptoVerif, etc.). How do these approaches work?
5
votes
1answer
748 views

Simple application of verifiable random function?

I have been reading a little bit about verifiable random functions (e.g.). In the literature, these are described as "pseudo-random functions that provide a non-interactively verifiable proof for the ...
3
votes
1answer
164 views

How can I formally verify fuzzy commitment scheme based security protocol?

I am currently working on designing a security protocol which involves usage of fuzzy commitment schemes, for. eg Reed-Solomon codes which allows us to tolerate a certain level of error. I was ...
3
votes
1answer
513 views

How to calculate $v_k(s)$ in Quadratic Arithmetic Program?

In the paper Pinocchio: Nearly Practical Verifiable Computation, there are some polynomials $v_k(x)$, $w_k(x)$ and $y_k(x)$ representing the structure of there circuit. However, as in the "concrete ...
2
votes
1answer
252 views

Is succinct verification of an arbitrary data transformation theoretically possible? Is it feasible? How?

Given input string S, and transformation (i.e. computer program) T, is it possible to provide a succinct proof that another binary string S' is identical to the output T(S)? By "succinct", I ...
3
votes
1answer
460 views

Implementing forward secrecy in OpenPGP with public key authentication

I am trying to consider the feasibility of implementing an encrypted file sharing system, which both provides forward secrecy but also allows public key verification. I am stuck on the marriage ...
0
votes
0answers
242 views

arithmetic calculation problem to quadratic arithmetic program

I am reading the Pinocchio paper (verifiable computation): http://research.microsoft.com/pubs/180286/pinocchio.pdf The paper is rather hard for me. I am considering this calculation problem: $(c_1*...